Probability of empty bin, where the number of balls is based on another game...

Question

Came across this interesting question:

We are given $j$ balls. We put them into bins labelled $1$, $2$, and $3$ at random. We want to calculate P(all bins have at least a ball).

The approach I'm using is as follows:

Given $k$ balls, the probability that all bins are empty is: $\frac{^{K-1}C_2}{3^k}$.

In expectation, I'll get heads on the 2nd flip $(\frac{1}{\frac{1}{2}}) = 2$. Therefore, for the final answer, I can just plug in $k=2$.

Answer 1

We certainly get at least one ball and put it into one of the bins, leaving two empty bins.

Now there are three possible outcomes on each flip. With probability $\frac12$ we obtain heads and fail. With probability $\frac12\cdot\frac13=\frac16$ we get another ball and put it in the same bin, leaving the situation unchanged. With probability $\frac12\cdot\frac23=\frac13$ we get another ball and put it in one of the empty bins, leaving one empty bin. The probability that the third outcome occurs before the first outcome occurs is

$$ \frac{\frac13}{\frac13+\frac12}=\frac25\;. $$

So with probability $\frac25$ we reach the stage where only one bin is empty. The analysis for this stage is the same as for the stage with two empty bins, except now the probability for leaving the situation unchanged is $\frac12\cdot\frac23=\frac13$ and the probability for filling the empty bin is $\frac12\cdot\frac13=\frac16$. Thus, the probability (given we’ve reached this stage) of filling the empty bin before obtaining heads is

$$ \frac{\frac16}{\frac16+\frac12}=\frac14\;. $$

So the overall probability of completing both stages before we obtain heads is

$$ \frac25\cdot\frac14=\frac1{10}\;. $$

Answer 2

Alternative approach

For $~n \in \Bbb{Z_{\geq 3}},~$ let:

• $f(n)~$ denote the probability that the 1st head is on coin flip $~n.~$
  Then $~f(n) = 2^{-n}.$

• $g(n)~$ denote the probability that none of the bins are empty, given that the 1st head occurred on coin flip $~n.$
  Then, by Inclusion Exclusion, which is also discussed here, you have that
  $\displaystyle g(n) = 1 - 3\left[ ~\frac{2^n}{3^n} ~\right] + 3\left[ ~\frac{1^n}{3^n} ~\right] = 1 - 3\left( ~\frac{2}{3} ~\right)^n + 3\left( ~\frac{1}{3} ~\right)^n.$

So, the overall computation is

$$\sum_{n=3}^\infty [ ~f(n) \times g(n) ~] $$

$$= \sum_{n=3}^\infty \left\{ ~2^{-n} \times \left[ ~1 - 3\left( ~\frac{2}{3} ~\right)^n + 3\left( ~\frac{1}{3} ~\right)^n ~\right] ~\right\} $$

$$= \sum_{n=3}^\infty \left[ \left( ~\frac{1}{2} ~\right)^n - 3\left( ~\frac{1}{3} ~\right)^n + 3\left( ~\frac{1}{6} ~\right)^n ~\right]. \tag1 $$

Note that for $~|x| < 1,~$ you have that

$$\sum_{n=3}^\infty x^n = x^3 \sum_{n=0}^\infty x^n = x^3 \times \left[ ~\frac{1}{1 - x} ~\right]. \tag2 $$

So, (1) above can be evaluated by using the formula in (2) above. Therefore, the probability is

$$\left[ ~\frac{1}{8} \times 2 ~\right] - 3 \left[ ~\frac{1}{27} \times \frac{3}{2} ~\right] + 3 \left[ ~\frac{1}{216} \times \frac{6}{5} ~\right]$$

$$= \left[ ~\frac{1}{4} ~\right] - \left[ ~\frac{1}{6} ~\right] + \left[ ~\frac{1}{60} ~\right]$$

$$= \frac{15 - 10 + 1}{60} = \frac{6}{60} = \frac{1}{10}.$$