Consider the following problem, from Tijms's Understanding Probability:
Calculate the probability of a run of five heads or five tails occurring in 20 tosses of a fair coin. What is the probability of a run of five heads occurring in 20 tosses of a fair coin? Do you think the following game is fair? A fair coin is tossed until heads appears three times in a row. You pay \$1 for each toss of the coin, but you get \$12.50 as soon as heads has appeared three times in a row.
This problem should be solvable by an absorbing Markov chain.
Let 1 be the state where in the last two tosses we had HT or TH, 2 be the state where in the last three tosses we got HTT or THH, 3 be the state HTTT or THHH in the last four tosses, 4 be the state HTTTT or THHHH in the last five tosses, 5 be the state with 5 heads or 5 tails.
The problem is equivalent to asking what is the probability of reaching state 5 in 20 steps starting from state 1.
The transition probabilities are the following:
$$ P= \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 1 \\ \end{bmatrix}, $$ because, for example, if we currently have HT (state 1), we can get to HTH (state 1) with probability $1/2$, and to HTT (state 2) with probability $1/2$ (this explains the numbers in the first column of $P$).
The entry in row 5, column 1 of $P^{20}$ is 0.47802, but the book says this probability is wrong (it should be 0.4584).
As for the second problem (if the game is a fair game), I suppose that we should compute the expected number of tosses before having three heads in a row, but I am not sure on how to do this.
Edit: following the hint by lulu, for the second part of the problem I think we should proceed as follows.
Let the state 1 correspond to only one T, or to a string that ends in T, the state 2 correspond to a single H or something that ends in TH, state 3 correspond to HH or something that ends in THH, state 4 correspond to HHH or something that ends in THHH. State 4 is absorbing.
The transition matrix is: $$ P = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$ (note that I use the opposite convention with respect to the first part of the problem, namely $P$ now would be $P^T$ in the first part).
Now, let $e_i$ be the expected number of tosses for reaching state 4 starting from state $i$. Clearly $e_4=0$ because if we are at state 4 we don't need to toss to arrive at state 4.
We have the following system of equations for the expected number of tosses: $$ \begin{aligned} e_1 &= (1+e_1)\frac12 + (1+e_2)\frac12 \\ e_2 &= (1+e_1)\frac12 + (1+e_3)\frac12 \\ e_3 &= (1+e_1)\frac12 + (1+e_4)\frac12. \end{aligned} $$ Replacing $e_4=0$ and solving for $e_1$, we get $e_1=14$. So the game would be fair if the reward were of 14\$ or more, otherwise it is a losing game.
Does it sound right?
You are starting with HT or TH, which consists of two flips, the full outcome of which is (HT,TH) = state 1 and (TT,HH) = state 2.
So you start with $(1/2,1/2,0,0,0)$ and multiply by $P^{18}$ , which in fact gives $$p(5)= \frac{240335}{524288} \approx 0.45840 \ldots$$