Suppose I have $n$ boxes, and an infinity of balls. All balls are regarded the same.

I randomly throw balls into the boxes, each time the ball may be thrown into one of the box, with equal probability, i.e., $\frac{1}{n}$.

Now I throw $k$ times, each time one ball thrown into one box. Let $E_{k, m, n}$ denote the situation where the k balls go into at most (including) m boxes (with $m\leq n\leq k$). What is the probability for $E_{k,m,n}$ to happen?

  • $\begingroup$ Are the boxes indistinguishable? $\endgroup$ – user208649 Jun 26 '15 at 2:48
  • $\begingroup$ Yes. The boxes are the same. $\endgroup$ – zell Jun 26 '15 at 2:48

I think the answer could be as follows:

Using stars and bars, the number of ways k balls could get into m boxes is $(k-1)\choose(m-1)$ ways. the number of ways m boxes could be chosen amongst n boxes is $n\choose m$. The probability that each of the k balls could hit any of the boxes is $\frac{1}{n}$.If it is thrown k times, it is $(\frac{1}{n})^k$. Thus

$E(n,m,k) = {(k-1)\choose(m-1)}.{n\choose m}.(\frac{1}{n})^k$

  • $\begingroup$ Shouldn't $E(n,n,k)=1$ ? I don't see how ${k-1\choose n-1}\cdot \frac{1}{n^k}=1$. $\endgroup$ – Alexey Burdin Jun 26 '15 at 3:51
  • $\begingroup$ the k could get into n boxes however they want. In one box you may gave 1 and in other box you may have two given the fact that k>n $\endgroup$ – Satish Ramanathan Jun 26 '15 at 3:53
  • $\begingroup$ So how can I achieve a sum probabilities of $1$ to test the formula? Don't I misunderstand something? $\endgroup$ – Alexey Burdin Jun 26 '15 at 3:58
  • $\begingroup$ I think you can test the formula by running all values of m and n upto k. Then the sum would be 1. I have not tested but I am hoping that it will be right. I am talking about running values of m=1 to n and n = 1 to k. $\endgroup$ – Satish Ramanathan Jun 26 '15 at 4:17
  • $\begingroup$ The simplest case would be have m = 1, n = 1 then the probability is 1 always $\endgroup$ – Satish Ramanathan Jun 26 '15 at 4:27

We have to take .care of the fact that

(a) more than one ball can go into a box

(b) arrangements through stars and bars are not equi-probable.

(c) probabilities (including box n) must sum to 1.

I believe we shall have to apply PIE, as illustrated below for n = 6, k = 10

Let $m_k$ denote the # of ways k boxes can be filled. Applying PIE, we get

$m_1 = {6\choose 1}\cdot 1^{10} = 6$

$m_2 = {6\choose 2}\cdot [2^{10} - {2\choose 1}\cdot1^{10}] = 15,330$

$m_3 ={6\choose 3}\cdot [3^{10} - {3\choose 2}\cdot2^{10} + {3\choose 1}\cdot 1^{10}] = 1119600$

Proceeding similarly,

$m_4 = 12277800$

$m_5 = 30618000$

$m_6$ = 16435440

Divide by 6^10 for the probabilities, which will sum to 1, as they must.

You can now generalise for $P[E_{k,m,n}]$


Oh, comment gives boxes as indistinguishable ! Shall have to rethink !

Edit 2:

In effect, there are n targets at which you are throwing k missiles which always hit some target or other. This makes the targets distinct, which is what I took in my answer


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.