# Andrei flips a coin over and over again until he gets a tail followed by a head, then he quits. What is the expected number of coin flips?

(a) Andrei flips a coin over and over again until he gets a tail followed by a head, then he quits. What is the expected number of coin flips?

(b) Bela flips a fair coin over and over again until she gets two tails in a row, then she quits. What is the expected number of coin flips?

Hello, I have been having some trouble with this problem. I have tried to use state diagrams, but bonked my head on the table, because obviously, that wouldn't work. I have not yet been able to find any method in doing this. Any help is appreciated

• It may help to work out what some of the admissible sequences are in each case. The first one has a fairly simple characterization, and I imagine the second one as well. – Semiclassical Sep 8 '14 at 1:28
• Conway's algorithm gives $2^2$ for TH, as it does for HT, while it gives $2^1+2^2$ for TT and HH. The curiosity is that if they combine their tosses to see which comes first (i.e. Penney's game), TH and TT are equally likely to come before the other, but if they were looking for TH and HH then TH would be three times as likely to come before HH as the other way round. – Henry Sep 8 '14 at 7:14

In the first case (a) the sequence of the outcomes is something like $H^j T^k H$ with $j\geq 0$ and $k\geq 1$. Such a sequence has length $j+k+1$, hence the expected number of coin flips is given by: $$\sum_{j\geq 0}\sum_{k\geq 1}\frac{j+k+1}{2^{j+k+1}}=\sum_{h,k\geq 1}\frac{h+k}{2^{h+k}}=4.$$ In the second case (b), the sequence of outcomes is a string over $\{H,TH\}$ plus a $TT$ suffix. The number of strings of length $N$ over $\Sigma=\{H,TH\}$ is given by the $(N+1)$-th Fibonacci number $F_{N+1}$, hence the expected number of coin flips is given by: $$2+\sum_{N=0}^{+\infty}\frac{N\cdot F_{N+1}}{2^{N+2}}=6.$$

Hint for the case of TH (tails-heads).

First let $y$ be the expected number of flips until a T is obtained. You can prove that $y = (1/2)\cdot 1 + (1/2)\cdot( 1 + y)$ by considering what happens in the first flip: you have a 50% chance of needing one flip, and a 50% chance of having to start over.

Now, can you explain why the required expected value is $2y$? (Hint: Define two random variables $X_1$ and $X_2$, where $X_1$ is the number of flips you need to obtain your first T, and $X_2$ the number to obtain the first $H$ after that. There's a formula for $E(X_1 + X_2)$.)

Hint for $TT$.

You have a 25% chance of getting TT immediately. You have a 50% chance of starting with H, in which case you start over, etc.

Now do a similar calculation to the first case.

• In case b), how do you deal with the case in which we start with TH ? – Jack D'Aurizio Sep 8 '14 at 2:17
• You start over. So if $x$ is the expectation you're looking for, that counts for $2 + x$. – Dave Sep 8 '14 at 2:25

There are two states:

A: Just flipped a Head; and
B: Just flipped a Tail.

They both might as well start in State A because they need to start with a Tail.

Let $M$ be the average number of flips needed to go from State A to State B, and $N$ be the average number of flips needed to go from State B to finish.

Going from state A to B might take 1 flip, with a tail, or might stay in state A with a head, and take M+1 flips. They are equally likely, so $M=\frac12 1+\frac12(M+1)$. Solve for $M$.

Do the same thing for $N$.

Andrei's allowable sequences are $H^i T^j TH$, where $i \ge 0, j\ge 0$.

The expected length is $\sum_{i=0}^\infty \sum_{j=0}^\infty (i+j+2) {1 \over 2^i} {1 \over 2^j} {1 \over 2^2}$.

Bela's allowable sequences are $S^i TT$, where $S \in \{ H, TH\}$, where $i \ge 0$.

The expected length is $\sum_{i=0}^\infty (i+2) \sum_{k=0}^i \binom{i}{k}({1 \over 2^k} {1 \over 4^{i-k}} ){1 \over 2^2} = \sum_{i=0}^\infty (i+2) ({1 \over 2}+{1 \over 4})^i{1 \over 2^2}$.

(a) $E[X=T] = p(X=T) + 0.5 \cdot (E[X=T] + 1) = 0.5 + 0.5 \cdot E[X=T] + 0.5 <=> E[X=T] = 2$ $E[X=TH] = E[X=T] + p(X=H) + 0.5 \cdot (E[X=T] + 1) = 2 + 0.5 + 0.5 \cdot (2 + 1) = 4$

(b) from above $E[X=T] = 2$ $E[X=TT] = E[X=T] + p(X=T) + 0.5 \cdot (E[X=TT] + 1) = 2 + 0.5 + 0.5 \cdot E[X=TT] + 0.5 <=> 0.5 \cdot E[X=TT] = 3 <=> E[X=TT] = 6$