If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls?

Question

If I randomly throw 10,000 balls to 4,000 buckets, what is the probability that at least one bucket contains more than 10 balls?

I don't know how to even approach this.

A rough number is also accepted - it doesn't have to be precise.

Answer 1

You have a Poisson distribution with mean $2.5$ (the average number of balls per bucket). Find the chance that one bucket has at most $10$ balls, raise to the $4000$ power to have them all have ten or less, and subtract from $1$. This is not exact-if one bucket is low that increases marginally the chance that another is high, but it will be very close.

Answer 2

Let $X=(x_1, x_2 \cdots x_N)$ ($N=4000$) be the number of balls in each bucket; then $p_X(X)$ follows a multinomial distribution, with $\sum x_i = M$ ($M=10000$). Now, let $Y$ be $N$ iid Poisson variables with mean $\lambda$ -still not specified. Then the distribution of $Y$ conditioned on $\sum y_i = M$ is the same as our multinomial. Let $E$ be the event that all buckets have less than $K=10$ balls. Then

$$P(E) = P(y_i < K \mid \sum y_i = M)= \frac{P( \sum y_i = M \mid y_i < K )}{P(\sum y_i = M)} P(y_i<K)$$ where $y_i < K $ implies $\forall i$.

Each factor can be computed or approximated :

$$P(y_i<K)= \left[ g(K,\lambda) \right]^N$$

where $$g(K,\lambda) = e^{-\lambda} \sum_{x=0}^{K-1} \frac{\lambda^x}{x!}=\frac{\Gamma(K,\lambda)}{\Gamma(K)}$$ Now, because the sum of iid Poisson variables is Poisson: $$P(\sum y_i =M) = e^{-N\lambda} \frac{(N \lambda)^M}{M!}$$

The remaining factor can be approximated using CLT as

$$P( \sum y_i = M \mid y_i < K ) \approx \frac{1}{\sqrt{2 \pi N \sigma^2}}\exp{\left(-\frac{M-N\mu}{2N \sigma^2}\right)}$$ where $\mu$,$\sigma^2$ are the mean and variance of a Poisson with parameter $\lambda$ truncated to $0,K-1$.

A good selection of $\lambda$ would be that that gives $\mu N=M$, because that would probably produce a good approximation.