So my friend gave me this question this other day, and I've tried to start it (I'll show my logic below), but I couldn't find any efficient way to do the problem.
You start out with 1 coin. At the end of each minute, all coins are flipped simultaneously. For each heads that is flipped, you get another coin. But for every tails that is flipped, a coin is lost. (Note any new coins are not flipped until the next moment). Once there are no more coins remaining, the process stops. What is the probability that exactly after 5 minutes (that's 5 sets of flips), that the process will have stopped (so no earlier or no later)?
I've taken a few approaches to this problem. What I've tried to do is to find the total amount of possibilities for each amount of coins by the 5th moment, and then multiply that by the probability that all coins will be vanished on the 5th moment. But I'm just not able to calculate how many possible ways exist to get to each amount of total coins by the end. Does anyone have any other ideas, or perhaps a formula to solve this problem?
Best Answer
Let $q(k)$ be the probability that the process initiated by a single coin will stop on or before $k$ minutes. We write $q(k+1)$ in terms of $q(k)$: \begin{align} q(1) &= 1/2\\ q(2) &= (1/2) + (1/2)q(1)^2 = 5/8\\ q(3) &= (1/2) + (1/2)q(2)^2 = 89/128\\ q(4) &= (1/2) + (1/2)q(3)^2 = 24305/32768\\ q(5) &= (1/2) + (1/2)q(4)^2 = 16644\hspace{0pt}74849/2147483648 \end{align}
and the probability we stop at 5 minutes exactly is: $$q(5)-q(4) = \frac{71622369}{2^{31}} \approx 0.0333517645...$$