Expected number of flips vs probability in a Markov Chain

Question

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!

Answer 1

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.

Answer 2

For part (a), checking by a different method, I get the same result for the expected number of flips.
Renaming the states $\;0,1,2,3\;$ as $\;a,b,c,d$
the equations for $HTHH$ would be

$\displaylines{a = 1 +0.5b+0.5a\\b=1+0.5c+0.5b\\c=1+0.5d+0.5a\\d=1+0.5c}$

which yields $ a=18$

For part (b), I don't see how there is symmetry.
I don't know exactly how to compute the probability,
so I ran it on an online simulator which gives $HTHH$ a win probability of around $0.6$

Answer 3

In (a) the last equation in your system is wrong. You should have $\mathbf{v}_4=0$ (zero indexing as you did). But instead you defined it as $\mathbf{v}_4=\mathbf{v}_4+1$ which actually has no solution at all. Edit: this was me misreading OP by assuming $R$ was the same as $P$ when actually $R$ is the top left $4 \times 4$ block of $P$. OP's part a is actually correct.

There is a solution to (b) using a similar renewal theory setup to what you did. But I don't immediately see a way to avoid working with the entire state, i.e. a $16 \times 16$ transition matrix. So I will describe how to do it with a big matrix like this.

Suppose you have already flipped at least four coins (the first four flips will be handled separately at the end). Treat the most recent four flips as the state of the process. If you think in a binary encoding with the older flips to the left, the update is done as follows: discard the leftmost bit, then insert a random bit on the right. So the first 8 rows of the transition probability matrix describe these transitions:

$$0000 \to 0000,0001 \\ 0001 \to 0010,0011 \\ 0010 \to 0100,0101 \\ 0011 \to 0110,0111 \\ 0100 \to 1000,1001 \\ 0101 \to 1010,1011 \\ 0110 \to 1100,1101 \\ 0111 \to 1110,1111$$

The remaining 8 rows are the same behave the same because the leftmost bit wasn't actually being used (so for programming you can just vertically concatenate two copies of this $8 \times 16$ matrix).

This gives you a transition matrix $P$ (row-stochastic). Define $L=P-I$. For ease of notation, say heads are 1s and convert to decimal (zero indexing again). Then you want to find the solution to $(L\mathbf{v})_j=0,j \neq 11,13,\mathbf{v}_{11}=1,\mathbf{v}_{13}=0$. The answer to your question is then $\mathbf{u} \mathbf{v}$ where $\mathbf{u}=(1/16,\dots,1/16)$ (a row vector).