Flip $n$ coins, discard tails, and continue until $k$ heads remain 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.
 A: 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$...
A: Partial approach. This is not a complete solution.  I'm still thinking about it, but perhaps what I write down may suggest a completion for someone else.
We will be satisfied with arriving at a set of $z$-transforms
$$
P_n(z) = \sum_{m=0}^\infty
         P(\text{$m$ tosses required to get down to $k$ or less} \mid n) z^m
$$
With this definition, we observe that for $n \leq k, P_n(z) = 1$, while for $n > k$,
\begin{align}
P_n(z) & = \sum_{j=0}^n \binom{n}{j} \left(\frac{1}{2}\right)^n zP_j(z) \\
       & = \frac{z}{2^n} \sum_{j=0}^n \binom{n}{j} P_j(z) \\
       & = \frac{z}{2^n} \sum_{j=0}^{n-1} \binom{n}{j} P_j(z)
         + \frac{z}{2^n} P_n(z)
\end{align}
Multiplying both sides by $2^n$, then subtracting $zP_n(z)$, we obtain
$$
\left(2^n-z\right)P_n(z) = z\sum_{j=0}^{n-1} \binom{n}{j} P_j(z)
$$
or
$$
P_n(z) = \frac{z}{2^n-z} \sum_{j=0}^{n-1} \binom{n}{j} P_j(z)
$$
Using our boundary condition, we can "simplify" this to
$$
P_n(z) = \frac{z}{2^n-z} \left[ \sum_{j=0}^k \binom{n}{j}
                              + \sum_{j=k+1}^{n-1} \binom{n}{j} P_j(z) \right]
$$
but I'm not sure this is the proper way to proceed.
A: Let these participants have an unfair coin each with probability of heads equal to $p$.
Suppose that after $m$ rounds there are exactly  k participants left.
Let's introduce the sum
$$S_k=X_1+X_2+...+X_k$$
where $P(X_i=1)=p$ and $P(X_i=0)=q=1-p$
For a fixed $k$ the generating function of $S_k$ is
$$(q+ps)^k$$
Now, actually $k$ changes from round to round, that means $k$ is a random variable (independent of the $X_i$).
Let $p(m,k)$ be the probability that after $m$ rounds there are exactly  k participants left.
Let $Z_m(s)$ be the generating function of $p(m,k)$. Then we have a simple recurrence relation
$$Z_{m+1}(s)=Z_m(q+ps)$$
with $Z_1(s)=(q+ps)^n$
Now, in principle we can calculate the generating functions sequentially. But much more interesting is to compute the expected number of participants  after $m$ rounds, $E_m=Z'_m(1)$.
Differentiate the recurrence relation with respect to $s$ and set $s=1$ to get
$$E_{m+1}=pE_m$$
Since $E_0=n$ we obtain
$$E_m=np^m$$
How many rounds are needed to have $E_m=1$?
$$m=-\frac{\ln n}{\ln p}$$
For example if $n=1000$ and $p=\frac{1}{2}$ (fair coin) then $m≈10$
In fact, I thought that number was higher. Maybe someone can run a simulation model to check this result?
