Balls into bins : minimum bins for that the chance of having an empty bin at the end is larger than 50%?

Question

We throw X times N balls into K bins. Each time, we remove bins that are not empty. What is the minimum amount of bins such that the chance of having an empty bin at the end is larger than 50% ?

Thank you in advance !

Answer 1

You can model this as a Markov chain. For a given number of balls, each state will consist of the number of throws left and the number of bins left. You can calculate the transition probabilities. It is easiest to start with the last throw. As an example, we take the case of $4$ balls. If on the last throw there is only one bin, the chance of having none at the end is $1$. If on the last throw there are two bins, the chance of having none at the end is $\frac 78$ because to have on left the last three balls thrown have to match the first one. If on the last throw there are three bins, the chance of having none at the end is $\frac {3\cdot {4 \choose 2}\cdot 2}{3^4}=\frac {36}{81}$ because we have to distribute the balls $2-1-1$ and we choose the bin to get two, which two balls it gets, and the empty bin the first other ball goes in. If on the last throw there are four bins, the chance of having none at the end is $\frac {4!}{4^4}=\frac {24}{256}$

If we have two throws at four bins, we can compute the chance of having none after the first throw is $\frac {24}{256}$. The chance of having one is $\frac{ 4\cdot 36}{4^4}=\frac {144}{256}$ because we can choose three bins in four ways, then use the previous computation. The chance of having three is $\frac 4{256}$ because all the balls have to go in the same bin. The chance of having two is then $\frac {104}{256}$