Markov Chain: flip 8 coins and get 3 consecutive heads

Question

I was reading the material and I am confused at the following example.

Q: In a sequence of independent flips of a fair coin, let N denote the number of flips until there is a run of three consecutive heads. Find $P(N = 8)$.

ANS: Another way to determine P(N = 8) is to consider a Markov chain with states 0, 1, 2, 3, 4 where, as before, for i < 3 state i means that we currently are on a run of i consecutive heads, state 3 means that the first run of size 3 has just occurred, and state 4 that a run of size 3 occurred in the past. That is, this Markov chain has transition probability matrix

$Q=\begin{matrix} 1/2&1/2&0&0&0\\1/2&0&1/2&0&0\\1/2&0&0&1/2&0\\0&0&0&0&1\\0&0&0&0&1 \end{matrix}$

P(N=8)=$Q^8_{0,3}$

*Confusion: I am wondering what is the state 4? Can I say state 4 is the probability of getting three consecutive heads when we flip the coin 8 times? (State 3 is the until we flip the coin 8 times?)

Answer 1

Here, state 4 is needed to sort out the difference between "the third heads just happened" and "the third head happened before now". The probability that it takes 8 flips to get 3 heads in a row is the probability the process is in state 3 just after the 8th flip (that is, the third heads happened on the 8th flip). Notice, if the state is 4 just after the 8th flip, the 3rd heads happened sometime before the 8th flip. We don't want to count this in the probability it takes exactly 8 flips.

Notice that the process enters state 4 after it is in state 3 no matter what the outcome of the flip is. State 4 is what's known as an "absorbing state". Once the process reaches state 4, it stays there forever.

I was curious about the answer. I get $\frac{13}{256}\approx 0.05$

Answer 2

I see you already got an answer. I thought I could add some details if you are curious.

The state 4 is required for Q to be tied to a probability measure. Without it any previous 3-in-a-row would "leak out" and the total probability would no longer sum up to 1. Matrices like Q must always have an eigenvalue equal to $1$ for this to be true. If we calculate the eigenvalues we get:

$$\rm{eig}(Q) = \left[\begin{array}{ccccc} 0.91964-0i,&-0.20982-0.30314i,&-0.20982+0.30314i,&0,&1 \end{array}\right]$$

$$\rm{eig}(Q-lastrow) = \left[\begin{array}{ccccc} 0.91964-0i,&-0.20982-0.30314i,&-0.20982+0.30314i,&0,&0 \end{array}\right]$$

So we see what happens when removing the last row ( setting it to 0 ), the eigenvalue 1 in the list above disappears. The eigenvector associated with this eigenvalue is the vector full of ones. This corresponds to the requirement of a probability measure that the sum of all outcomes must be 1 (all probability adds up to 100%). And for our Markov chain - that the sum of probability of all states must be 1.