# Expected no. of coin flips to win

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

• You must share your thoughts on the problem. – StubbornAtom Aug 26 '17 at 16:34
• What I can think is to find probability for A to win in n flips and then use the formula of expectation to find the expected no. of flips. But this method is quite lengthy. Is there any better solution? – Sumit Kumar Aug 26 '17 at 16:38
• So the person who wins is the first person to get tails after someone has gotten heads, is that right? – Arthur Aug 26 '17 at 16:41
• If B wins, presumably A never wins – Henry Aug 26 '17 at 16:43
• @Arthur A player who get tails wins if and only if another player has gotten heads in the previous flip i.e. a sequence HT occurs – Sumit Kumar Aug 26 '17 at 16:43

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.

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.

• I have done exactly the same except that i have not multiplied 9/4 as you did in the last equation. Can you please explain why have you done that? – Sumit Kumar Aug 27 '17 at 6:11
• We are only concerned with expected value $E(N|A)$ of coin flips given that $A$ wins. $A$ wins if $N$ is odd, and loses if $N$ is even. We know how to easily get the total expectation $E(N)$ and the probability of $A$ winning. It is known that if $N$ is a random variable and $A$ is any event, then $E(N|A)$ is given as the weighted arithmetic mean of $E(N|X=x)$ with weights being probabilities of those outcomes $X=x$ that make $A$ happen. Recall that in the discrete case, the weighted mean is $\frac{w_1x_1+\cdots+w_nx_n}{w_1+\cdots+w_n}$ – Roman Chokler Aug 27 '17 at 13:40