Markov Chain: flip 8 coins and get 3 consecutive heads 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?)
 A: 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$
A: 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.
A: I have an alternative way of explaining the Markov chain solution, from the perspective of conditional expectations. Suppose that we set $p_n=P(\text{number of toss until HHH}=n)$. Then we have the following recursion relations:
$$
p_1 = p_2 = 0,\,p_3 = \frac{1}{8}
$$
and
$$
p_n = P(\text{first toss is T})\cdot p_{n-1}+P(\text{first two tosses is HT})\cdot p_{n-2}+P(\text{first three tosses is HHT})\cdot p_{n-3}
$$
which is
$$
\frac{1}{2}\cdot p_{n-1}+\frac{1}{4}\cdot p_{n-2}+\frac{1}{8}\cdot p_{n-3}
$$
Now we have
$$
p_4 = \frac{1}{16}
$$
$$
p_5=\frac{2}{32}
$$
$$
p_6 = \frac{4}{64}
$$
$$
p_7 = \frac{7}{128}
$$
$$
p_8 = \frac{13}{256}
$$
I was thinking about writing a general formula for $p_n$ but gave an improper trail. Thanks for clarifying from the comment below!
