First to flip N heads wins?

Question

Everyone knows the classic problem of A and B playing a game, with the first to flip heads winning the game. I understand that we can easily solve for the probability of A winning if she flips first, which is $2/3$, since $p_A=p_A/2 + (1-p_A)/2$.

Now what if I generalise the problem to $N$ heads, such that the first to flip a total of $N$ heads wins? I’m unsure of how to construct the recursion relation here. My gut tells me the probabilities of either player winning if $N\rightarrow\infty$ is $1/2$. Could someone guide me on this? Thank you!

Answer 1

We can solve this question through states. Suppose $p_{i,j}$ denotes the probability that $A$ wins if he starts first, with $i$ heads, and $B$ starts with $j$ heads. Note that $p_{N,j}=1$ and $p_{i,N}$ for $i<N$ is $0$. (Here, I will let $p_{N,N}=1$ for convenience.) Now, consider the first turn when at least one person flips a head. Clearly, the probability that it is only $A$, only $B$, or both is equal, so we have the recurrence $p_{i,j}=\frac{1}{3}\left(p_{i+1,j}+p_{i,j+1}+p_{i+1,j+1}\right)$. This is very similar to Pascal's triangle, and the closed form for this can be computed explicitly through finite differences.

Answer 2

Use the Negative Binomial Distribution. The probably of $X$ number of trials to obtain $N$ successes is

$f(x;N,p_A)=\binom{x-1}{N-1}p_A^N(1-p_A)^{x-N}$, for $x=N,N+1,...$

Since this is likely a fair coin, $f(x;N,0.5)=\binom{x-1}{N-1}\times 0.5^x$