# Generalization of alternative coin flipping problem

Two players $$A$$ and $$B$$ are flipping a fair coin alternatively, with $$A$$ starting first. The first player to obtain head wins the game. Then the probability that $$A$$ wins this game is $$\frac{2}{3}.$$

The answer above can be obtained easily by using recursion: Let $$p$$ be the probability that $$A$$ wins. Then $$p = \frac{1}{2} +\frac{1}{2}(1-p).$$ Solving the equation above leads to $$p = \frac{2}{3}.$$

Another extended question:

The same setting as above. The game ends if there is a head followed by a tail and the player who obtains tail wins the game. Then the probability that $$A$$ wins the game is $$\frac{4}{9}.$$

The answer above can be obtained in this post.

I notice that the answer to the second question is just a square of the first question. I wonder whether there is a generalization. More precisely,

Fixed a natural number $$n.$$ Two players $$A$$ and $$B$$ flip a fair coin alternatively, with $$A$$ starting first. The game ends if there exists a subsequence $$HTHT...HT$$ with length $$n$$ and the player who obtains the last toss in the subsequence wins the game. What is the probability that $$A$$ wins?

Note that if $$n$$ is odd, then the last toss is $$H$$ and $$n$$ is even, the last toss is $$T$$.

Let $$p_n$$ be the probability we are looking for.

If $$n$$ is odd, player $$A$$ wins if he looses in $$n-1$$ game and the next toss is Heads; if the next toss is Tails the game restarts with $$A$$ being the second player; so

$$p_n=P_{Heads}(1-p_{n-1})+P_{Tails}(1-p_n)=\frac12(1-p_{n-1})+\frac12(1-p_n)$$

and $$p_n=\frac{2-p_{n-1}}{3}$$

or (thanks @J.W.Tanner) $$p_n=\dfrac12-\dfrac12\left(-\dfrac13\right)^n$$

The solution for "$$n$$ is even" case is the same up to Heads $$\leftrightarrow$$ Tails swap; since $$P_{Heads}=P_{Tails}=1/2$$ it does not matter.

• I don't think the main equation covers all the cases. What if $A$ wins the $n-1$ game? Also, I would intuitively guess (not sure) that $p_\infty = 1/2$, but that doesn't satisfy the recurrence. Jan 1, 2020 at 20:54
• @antkam see math.stackexchange.com/q/3494598/42926 for convergence. Jan 2, 2020 at 1:20
• you're right about the convergence. i made a silly arithmetic mistake. :) but i still don't understand the first equation. sorry for being slow... also, wouldnt the logic be slightly different if $n$ is even? Jan 2, 2020 at 2:33
• @antkam I updated the solution to make it more clear. When in doubt, drawing correspondent Markov chain helps. Jan 2, 2020 at 2:57
• But when $n$ is even, the winning string ends in T. So if the next toss is H, then it is not equivalent to the game re-starting with A being 2nd player. Jan 2, 2020 at 4:08