I have seen similar arguments at other places but couldn't convince myself so far about it. I am reading some literature related to graph theory but let me post the analogous problem which avoids the graph theory terminology:

There are $M$ boxes and $m$ balls which we want to randomly uniformly distribute among those boxes.

Now author essentially says that the expected number of balls in each box $i$ is $p_{i} = \frac{m}{M}$. However, then he says that if $m << M$, this can also be considered as the probability of filling that box with one of the $m$ balls.

I don't understand this. I tried deriving expression for the expected value but that itself involves the probability that a ball goes into the box. Can somebody please clarify this? Thanks


The expected value of a random variable $X$ whose values are natural numbers is $$ 0\cdot P(X=0) + 1\cdot P(X=1) + 2\cdot P(X=2) + 3\cdot P(X=3) + \cdots $$

In your case, if $m\ll M$, then the probability that there's more than one ball in the box will be vanishingly small, so the terms with $P(X=2)$ and so forth can be ignored. So what is left is $$ 0\cdot P(X=0) + 1\cdot P(X=1)$$ which is of course just $P(X=1)$.

  • $\begingroup$ Thanks. Can you please add some trend by which the probabilities of higher X values decrease so that it would be evident that they are negligible? Also, why the expected value is exactly m/M when m is not small compared to M? $\endgroup$ – Peaceful Jun 15 '16 at 9:27
  • $\begingroup$ @SnehalShekatkar: The expected value of the sum of the number of balls in any box is of course $m$ (because that is always the value). Because expectation is additive, this is also the sum of the expectations of the number of balls in each of the $M$ boxes, and since those must be equal (by symmetry), the expectations for each box can only be $m/M$, or they wouldn't sum to $m$. $\endgroup$ – Henning Makholm Jun 15 '16 at 9:45
  • 1
    $\begingroup$ The probability of having exactly $1$ ball in box $i$ must be $m\frac1M(1-\frac1M)^{m-1}$, so the $m/M$ estimate is good as long as $(1-\frac1M)^{m-1}$ is close to $1$. For large $m$ we have $(1-\frac1M)^{m-1} \approx e^{-m/M}$, so when $m/M$ is small it is also a good approximation. $\endgroup$ – Henning Makholm Jun 15 '16 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.