Coin Flipping Game - Probability and Expected Value

Question

This isn't Home-Work - I am exercising for a test.

Alice and Bob are playing a coin flipping game where they flip coins until one of them wins. Alice wins when we get a sequence of "h,h,h" and Bob wins if we get a sequence of "t, h, t".

At first I needed to find the probability of winning for each of them and I think I've done it correctly.

Now I need to find $E[X]$ when $X$ is the number of flips they flipped until one of them wins. Now, the answer is between 5 and 6 but I can't understand why. I think it might have something to do with the Geometric distribution.

Thanks in advance,

Yaron.

Answer 1

This is a Markov chain problem. There are four states that can recur, which I will label $HH, HT, TH, TT$ for the last two throws. I will use the same name for the expected number of throws from each state to the end. If you are in HH, half the time you flip heads and stop, the other half you throw tails and go to HT, so $HH=\frac 12(1+(1+HT))$ You can write three more equations like that and solve the system. Starting from scratch, you flip twice to get into one of these states, so $E[X]=2+\frac 14(HH+HT+TH+TT)$

Answer 2

:Prefacing with mentioning that this method works exactly like Ross's above, however may appear a bit more tangible to use:

Assuming the coin is fair and $Pr(H)=Pr(T)=\frac{1}{2}$

This can be described with a Markov Chain with seven states (including a start and a placeholder state which can only be entered after a single flip). Denoting the states by the most recent coin flips (except $*H$ which denotes the first coin flip was a heads with no prior flips), we have the transition diagram:

Matrix with order $HHH, THT, *H, .T, .TH, .HH, Start$

$\begin{bmatrix}1 & 0 & 0 & 0 & 0 & h & 0\\ 0 & 1 & 0 & 0 & t & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & h\\ 0 & 0 & t & t & 0 & t & t\\ 0 & 0 & 0 & h & 0 & 0 & 0\\ 0 & 0 & h & 0 & h & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$

This is a matrix in the form $A=\begin{bmatrix} I & S \\ 0 & R\end{bmatrix}$, which gives the limiting matrix $\lim\limits_{n\to\infty} A^n = \begin{bmatrix} I & S(I-R)^{-1}\\0 & 0\end{bmatrix}$.

Calculating the fundamental matrix, $(I-R)^{-1}$ will tell us what the expected game length will be.

Replacing $h$ and $t$ with $\frac{1}{2}$ we get:

$(I-R)^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 & .5\\ 2 & 8/3 & 2/3 & 4/3 & 7/3\\ 1 & 4/3 & 4/3 & 2/3 & 7/6\\ 1 & 2/3 & 2/3 & 4/3 & 5/6\\ 0 & 0 & 0 & 0 & 1\end{bmatrix}$

As our initial state configuration was entirely in the $Start$, by multiplying by $[0,0,0,0,1]^{T}$ on the right, we get $5+\frac{5}{6}$ as the number of turns on average the game is played for. In general, the fundamental matrix will tell you how many time increments on average until it reaches a stable state given some initial distribution (and as Ross points out, we could have done away with the $*H$ and the $Start$ locations, and noted that after two flips, half of the time we will be in the $.T$ state, a quarter of the time we will be in the $.TH$ state, and a quarter of the time we will be in the $.HH$ state.

To satisfy our curiosity, we may finish calculating the limiting matrix:

$\begin{bmatrix} 1 & 0 & .5 & 1/3 & 1/3 & 2/3 & 5/12\\ 0 & 1 & .5 & 2/3 & 2/3 & 1/3 & 7/12\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$

Which by multiplying by our initial state vector, shows us that Alice has a $\frac{5}{12}$ chance of winning, and Bob has a $\frac{7}{12}$ chance of winning.