The problem is the following:
(a) We keep flipping coins until we see the sequence HTHH. Find the expected number
of flips.
(b) Alice and Bob play the following game. They keep flipping coins until either the
sequence HHTH or HTHH occurs. Alice wins if the sequence HHTH occurs first, and
Bob wins if the sequence HTHH occurs first. Find the probability that Alice wins.
For part (a) I set a transition matrix with states {0, 1, 2, 3, 4} corresponding to the "progress" made in achieving the sequence HTHH. Going from 0 to 0 means getting a Tails, going from 0 to 1 means getting Heads, from 1 to 1 means getting Heads again, from 1 to 2 means getting Tails (after getting Heads), going from 2 to 0 is getting Tails (after getting Tails) and so on.
$\begin{bmatrix} 0.5 & 0.5 & 0 & 0 & 0 \\ 0 & 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$
The expected number of tosses would be first entry of the solution to $\overrightarrow{v}=R\overrightarrow{v}+\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}$ if I'm not mistaken, which is 18.
Now for part (b) I don't know how to set up the matrices for Alice and Bob (if even that is the correct approach). I would greatly appreciate any advice on how to proceed, thank you!
Best Answer
You can also solve part (b) using a Markov chain, having the $8$ states described in the table below. The first column of the table is an index for each state, the second and third are the number of steps which Alice and Bob will have taken towards their targets in the give state, and the third and fourth are the indices of next states when heads or tails is tossed in the given state. The final column lists all the preceding sequences of tosses of lengths $0$ to $4$ that would lead up to the given state, with $\ \lambda\ $ denoting the empty sequence.
\begin{array}{ccccl} \text{State}&\text{Alice}&\text{Bob}&\text{Next}_H&\text{Next}_T&\text{Preceding sequences}\\ 1&2&1&1&2&HH,THH,HHH,TTHH,THHH,HHHH\\ 2&3&2&3&8&HHT,HHHT,THHT\\ 3&4&2&3&3&HHTH\\ 4&2&4&4&4&HTHH\\ 5&1&2&7&8&HT,THT,TTHT,HTHT\\ 6&1&1&1&5&H,TH,TTH,TTTH,HTTH\\ 7&1&3&4&5&HTH,THTH\\ 8&0&0&6&8&\lambda,T,TT,HTT,TTT,HHTT,TTTT,HTTT,THTT \end{array} States $3$ and $4$ are absorbing states in which Alice or Bob, respectively, have won the game. The transition matrix is $$ P=\pmatrix{0.5&0.5&0&0&0&0&0&0\\ 0&0&0.5&0&0&0&0&0.5\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&0.5&0.5\\ 0.5&0&0&0&0.5&0&0&0\\ 0&0&0&0.5&0.5&0&0&0\\ 0&0&0&0&0&0.5&0&0.5} $$ The probability that Alice wins is the probability that the chain ends up in state $3$. If you let $\ a_k\ $ be the probability that Alice wins, given that the current state is $\ k\ $, then obviously $\ a_3=1\ $, $\ a_4=0\ $, and $$ a_k=\sum_{j=1}^8p_{kj}a_j\ , $$ where $\ p_{kj}\ $ is the entry in the $\ k^\text{th}\ $ row and $\ j^\text{th}\ $ column of $\ P\ $. The third and fourth of these equations are the tautologies $\ 1=1\ $ and $\ 0=0\ $, respectively, and the rest may be written as $$ \pmatrix{a_1\\a_2\\a_5\\a_6\\a_7\\a_8}=\pmatrix{0.5&0.5&0&0&0&0\\ 0&0&0&0&0&0.5\\ 0&0&0&0&0.5&0.5\\ 0.5&0&0.5&0&0&0\\ 0&0&0.5&0&0&0\\ 0&0&0&0.5&0&0.5}\pmatrix{a_1\\a_2\\a_5\\a_6\\a_7\\a_8}+\pmatrix{0\\0.5\\0\\0\\0\\0} $$ The solution of these equation is $$ \pmatrix{a_1\\a_2\\a_5\\a_6\\a_7\\a_8}=\pmatrix{\frac{4}{5}\\\frac{4}{5}\\\frac{2}{5}\\\frac{4}{5}\\\frac{3}{5}\\\frac{1}{5}\\\frac{3}{5}}\ . $$ The probability you want is the probability, $a_8=\frac{3}{5}\ $, that Alice wins given that the Markov chain is in state $8$, because that is the state it will be in when the game starts, which thus confirms the results of true blue anil's simulation.