Two players A and B flip a coin sequentially. The game finishes when the sequence TTH is formed and player A wins or the sequence HTT is formed and player B wins. What is the probability that the game will finish at the $n$-th flip?
What I did:
- A wins iff the sequence is $n-1$ T's followed by a single H : $\frac{1}{2^n}$
- B wins iff the sequence ends with HTT and we have no two consecutive T's in the first $n-3$ flips: this happens (I think) with probability $\frac{F_{n-2}}{2^n}$ where $F_{n}$ is the $n$-th Fibonacci number. I proved this by induction.
- Thus, the total probability is $\frac{F_{n-2}+1}{2^n}$
Can someone verify that this is correct and/or share how you would solve this problem?
If the answer is correct, then by summing over all $n$ we can obtain an interesting identity involving the Fibonacci numbers!
In the first three tosses, one of the players will win is $\frac{2}{8}$ i.e HTT and THH are the winning flips out of $2^3$. Thus the proability the game will end in 3 tosses is $\frac{1}{4}$. In an addtional toss, one of the players will win is $\frac{4}{16}$, i.e THTT, HHTT, TTHH, HTHH are the winning flips out of $2^4$. Thus the probability that the game will end in 4 tosses is equal to game not ending in the first three tosses and ends in the fourth toss and thus equal to $\frac{3}{4}.\frac{4}{16}$ $=(\frac{3}{4})^{4-3}.\frac{1}{4}$ Extending the logic, you will have the probability that the game will end ( in other words one of the players will win) in n flips is $=(\frac{3}{4})^{n-3}.\frac{1}{4}$. The book is correct in its solution.