n tasks assigned to n computers, what is the EX value of a computer getting 5 or more tasks? Say a central server assigns each of n tasks uniformly and independently at random to n computers connected to it on a network. Say a computer is ‘overloaded’ if it receives 5 or more tasks.
Q: Calculate the expected number of overloaded computers.
I thought of doing [1 - Pr(a computer is not overloaded)] but that leads me to a complicated expression of:
$$1 - PR(NotOver) = 1 - \sum_{i=0}^4  \left( \frac{1}{n} \right)^{i} { \left( \frac{n-1}{n} \right)}^{n-i}$$
multiplying this by n would(hopefully) give the Expected value. But the answer seems not very elegant atall, is there something I'm missing or an easier way to tackle this?
Thanks!
 A: I believe your formula for the P(overloaded) is wrong. It looks like you are trying to calculate 
1 - (P(0 tasks) + P(1 task) + ... + P(4 tasks))
However the probability of k tasks is ${n \choose k}\left(\frac{1}{n}\right)^k\left(\frac{n-1}{n}\right)^{(n-k)}$, not simply $\left(\frac{1}{n}\right)^k\left(\frac{n-1}{n}\right)^{(n-k)}$. You are missing the binomial coefficient.
So the exact formula for E[overloaded] is:
$n\left(1-\sum_{i=0}^4 {n \choose i}\left(\frac{1}{n}\right)^i\left(\frac{n-1}{n}\right)^{(n-i)}\right)$
To answer your question, I don't believe there are any tricks to simplify this any further.
Consider using the Multiplicative Chernoff Bound to estimate an upper bound on the probability of one computer being overloaded and then multiplying by $n$ to get an upper bound on the expected number of overloaded computers.
Let $X_i$ be a random variable describing the number of tasks assigned to computer $i$. We have $E(X_i) = 1$, and the Chernoff bound of the probability of $X_i$ being overloaded is given by:
$$P(X_i > 4) = P \Big( X_i > (1+3) \cdot 1 \Big) < \frac {\textrm e^3} {(1+3)^{1+3}}$$
and so the expected number of overloaded computers can by bounded by:
$$E \left( \sum X_i \right) = \sum E(X_i) < n \frac {\textrm e^3} {(1+3)^{1+3}} \sim 0.078 n .$$
This seems to be a loose bound, however. For example simulating in Python for n=1000000 gives 0.0037*n:
>>> n = 1000000; t = [randint(1,n) for i in range(n)]; c = Counter(t); sum(1 for v in c.values() if v > 4)/n    
0.003653

