0
$\begingroup$

The question is the distribution of the number of empty cells.

Imagine to have $N$ cells, and I have $k$ balls to distribute randomly (uniform) among $N$ cells so that no more than 1 ball can occupy the cell. where $k\leq N$.

Then we repeat the same procedure $n$-times.

Now the other balls of different "types" can go in the cells where other-type of balls are.

After the complete process:

  • What is the probability that a randomly chosen cell is empty?
  • The expected number of empty cell?
  • What changes if I remove the condition of only one ball per "type"?

___________ Sketch of solution _________

the probability that each of n specified cells will be occupied is ${{N}\choose{k}}^{-1}$, and there are ${{N}\choose{k}}^n$ random allocations of $kn$ balls among the $N$ cells.

$\endgroup$
  • $\begingroup$ Is this homework? $\endgroup$ – Neil G Mar 31 '17 at 8:18
  • $\begingroup$ no, it is my research interest. I see there are "almost" no problem for me if there is no restriction on the passage of only one ball per cell per trial. But with this restriction I need some help about things that I guess it is missing to my knowledge. $\endgroup$ – FabIO Mar 31 '17 at 8:20
  • $\begingroup$ 1. The probability that a randomly chosen cell is empty equals the probability that the first cell is empty, by symmetry. The probability that the first cell is empty after the first set of balls is $\frac{N-k}{N}$. After $n$ passes, that falls to $\left(\frac{N-k}{N}\right)^n$ by independence. 2. The probability that the first $m$ cells stay empty after one pass is $\frac{N-k}{N} \cdots \frac{N-k-m+1}{N-m+1} = \frac{(N-k)!m!}{N!(N-k-m)!}$. The chance that exactly $m$ cells stay empty is that times $N\choose m$, which is $\frac{(N-k)!}{(N-k-m)!(N-m)!}$… $\endgroup$ – Neil G Mar 31 '17 at 8:55
  • $\begingroup$ so, the probability to find $m=0$ empty cells is $1/N!$ ? $\endgroup$ – FabIO Apr 3 '17 at 17:10

Your Answer

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

Browse other questions tagged or ask your own question.