Filling three bins from a coin flip

HardProbability Combinatorics~10m

Flip a fair coin until the first head. If the first head lands on flip $k$ , you receive $k$ balls, which you then drop independently and uniformly at random into $3$ labelled bins. What is the probability that none of the three bins is empty? The probability equals $\tfrac{1}{M}$ for an integer $M$ ; find $M$ .

Show hints (2)+

Given $k$ balls, the chance all $3$ bins are occupied is a surjection probability: $(3^k - 3\cdot2^k + 3)/3^k$ (and $0$ for $k<3$ ).
Weight by $\mathbb{P}(k)=(1/2)^k$ and sum. The cross terms become geometric series in $1/3$ and $1/6$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Hedge Fund Quant

Filling three bins from a coin flip

Answer

Related questions