Expected number of flips vs probability in a Markov Chain 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!
 A: 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$
A: 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).
