2

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$.

Idonknow
  • 15,643

1 Answers1

1

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.

kludg
  • 2,599
  • 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. – antkam Jan 01 '20 at 20:54
  • @antkam see https://math.stackexchange.com/q/3494598/42926 for convergence. – kludg Jan 02 '20 at 01: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? – antkam Jan 02 '20 at 02:33
  • @antkam I updated the solution to make it more clear. When in doubt, drawing correspondent Markov chain helps. – kludg Jan 02 '20 at 02: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. – antkam Jan 02 '20 at 04:08