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
 A: 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.
A: 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.$$
A: 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$.
A: 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: (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$
