Two players A and B play a game in which they alternately flips a coin. Player A starts the game. If a player gets T and another player got H before, he/she is the winner. What is the expected no. of flips for A to win ?
Ex:-
Game-1: HT --> B wins
Game-2: HHT --> A wins
On
Given that $A$ wins, we have an odd number of flips.
Last flip is $T$ and others consist of a possible run of tails, followed by a definite run of heads.
Let $N$ be the number of flips total.
$$P(N=n)=\frac{1}{2}\sum_{k=1}^{n-1}\left(\frac{1}{2}\right)^{n-1}=\frac{n-1}{2^n}$$ $$P(A)=P(N\equiv 1\mod 2)=\sum_{k=1}^\infty P(N=2k+1)=\sum_{k=0}^\infty\frac{k}{4^k}=\frac{4}{9}$$.
$$E(N|A)=\frac{9}{4}\sum_{k=1}^\infty\frac{k(2k+1)}{4^k}=\frac{13}{3}$$
The $E(N)=4$ result above is wrong since it is the total expectation $E(N)$ of coin flips until endgame. The total expectation $E(N)$ is, however, an interesting quantity as well, since it is equivalent to a special case of the following theorem involving a typing monkey:
Let a monkey type letters on a typewriter that has some alphabet $\Sigma$ and let $w\in\Sigma^*$. Also let $\{w_1,\cdots,w_n\}$ be the set of those strings that are both a prefix and suffix of $w$.
If the monkey types until the last letters typed form $w$ and then stops typing, let $X$ be the total number of letters typed. Then $$E(X)=\sum_{k=1}^n|\Sigma|^{|w_k|}$$
The theorem is provable with Martingale Theory.
Example:
Typewriter alphabet: $\{A,B,\cdots,Z\}$ (Standard English).
Monkey's Goal: $ABRACADABRA$.
Prefix-Suffix Strings: $\{A,ABRA,ABRACADABRA\}$ of sizes $1,4,11$.
So the monkey will on average type $26+26^4+26^{11}=3670344487444778$ letters.
We expect four coin flips. That's because we first expect two flips to get the first heads, and then we expect two flips to get the first tails.
More detailed: as a player is about to throw, the game is in one of two states: either there hasn't been any heads yet, or there has been at least one head (and since the game isn't over, the last throw must've been a head). Let's call the expected number of throws left until the game is over if we're in the first state $E_1$, and the expected number of throws left if we're in the second state $E_2$.
First we calculate $E_2$. If a player is about to throw, and the last throw was a heads, then there's a probability of $0.5$ of the game ending in one more throw, and a probability of $0.5$ of the game continuing to the next player still in the same state, which means that after that we expect another $E_2$ throws. This implies $$ E_2=0.5\cdot1+0.5(1+E_2)\\ E_2=2 $$ Now we get to $E_1$. If a player is about to throw, and there hasn't been any heads yet, then there is a probability of $0.5$ that the player throws heads, and the game continues in state two, which means that we expect another $E_2=2$ throws, and there is a probability of $0.5$ of the player throwing tails, which means that the game continues in the first state, and we expect another $E_1$ throws. This gives $$ E_1=0.5(1+E_2)+0.5(1+E_1)\\ E_1=4 $$ which is our answer.