Consider the following game: $n$ participants have a fair coin each, on a given round, the not already discarded participants flip their coins, those who flip a tail are discarded from the game, the remaining ones continue to play until there are at most $k$ of them left.
The question is: what's the distribution of the number of rounds in this game?
Bonus question: idem, but the $n$ coins are all unfair, with probabilities $p_1$, $p_2$, $\ldots$, $p_n$.
Disclaimer: this is not a homework question, it came up when considering distributed routing protocols with a colleague.
Best Answer
Each coin follows a Geometric Distribution $P(X_i=k)=p_i(1-p_i)^{k-1}$ because it has probability $1-p_i$ of showing a head on each of the $k-1$ tries, and then, it has probability $p_i$ of showing tail on the $k$th try.
Then, we are trying to find the distribution of $\max_iX_i$. We have that: $$P(\max_iX_i \leq k)=P(X_i\leq k \forall i)=\prod_iP(X_i \leq k)=\prod_i \sum_{j=1}^k p_i(1-p_i)^{j-1}=\prod_i p_i\frac{1-(1-p_i)^k}{1-(1-p_i)}=\prod_i (1-(1-p_i)^k)$$
Then, I have no good idea on how to continue that, if someone has one...
EDIT: My bad, I just saw that the game stops when less than $k$ players are left. So this is just for the case $k=1$...