There are $K$ boxes, and there are $N$ apples. Every box is large enough to accommodate any number of apples. Each apple is placed into random box (probability for an apple to be put into a box is $p=1/K$).

What is the probability that some box contains at least $M$ apples? Or, as a dual problem, what is the probability that every box contains at most $M-1$ apples?

This is obviously "independent trials" problem, and I know formula for polynomial distribution

$P_n$($m_1$,$m_2$,...,$m_k$) = $\frac{n!}{m_1!m_2!...m_k!}p^n$

where $m_i$ is a number of apples put into the i-th box, but I have no idea how to apply it to the problem.

BTW, if it can be solved using Moivre-Laplase integral theorem for polynomial distrubution (which for me looks even more puzzling), it would be welcome too.

  • $\begingroup$ Have you tried the problem for small numbers? Let's say $N=10, K=3$ and $M=1,2,3,...,10$? Using the Pigeonhole Principle, there is a 100% chance for $M=1,2,3,4$ for some box to contain at least $M$ apples. For $M$ equal to 5 or higher, you actually need to do some calculations. Figure out the number of ways for no box to have at least 5, and that will be your answer. You can have 3,3,4 or 3,4,3, or 4,3,3. So, the probability that some box has at least 5 would be: $$1 - \dbinom{3}{1}\dfrac{10!}{3!3!4!}\left(\dfrac{1}{3}\right)^{10}$$. $\endgroup$ – InterstellarProbe Feb 6 at 21:58
  • $\begingroup$ Also, what form are you looking for? Are you looking for a closed form solution? Because you could use the following: Let $$A = \left\{(m_1,\ldots, m_K) \in [N]^K \mid \sum_{i=1}^K m_i = N\right\}$$ where $$[N] = \{0,1,\ldots, N\}$$ Then you can write the probability you are looking for as $$\dfrac{1}{K^N} \sum_{\begin{matrix}(m_1, \ldots, m_K) \in A \\ \forall i, m_i < M\end{matrix}} \dfrac{N!}{\prod_{i=1}^K m_i}$$ But this is obviously not even close to a closed form. $\endgroup$ – InterstellarProbe Feb 6 at 22:09
  • $\begingroup$ Oops, in my first example, I forgot the cases 2,4,4, 4,2,4, and 4,4,2. So, it would actually be: $$1-\left(\dbinom{3}{1}\dfrac{10!}{3!3!4!} + \dbinom{3}{1}\dfrac{10!}{2!4!4!}\right)\dfrac{1}{3^{10}}$$ $\endgroup$ – InterstellarProbe Feb 6 at 22:17

Here is one solution. Let $E_{m-1}(x)=\sum_{i=0}^{m-1}\frac{x^i}{i!}$ be the partial exponential series. Then the probability is $$ P(\text{every box has less than $m$ apples})=\frac{n![x^n]E_{m-1}(x)^k}{k^n} $$ where $[x^n]f(x)$ denotes the coefficient of $x^n$ in the polynomial (or Taylor series) $f(x)$.

For example, when $m=2$, you get $$k^{-n}n![x^n] (1+x)^k=k^{-n}n!\binom{k}n=\frac{k}k\cdot \frac{k-1}k\cdot \frac{k-2}k\cdots\frac{k-n+1}k,$$ which is indeed the probability that no box has two or more apples, or that all apples are in different boxes.


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.