# Calculating the expected winner of a Penney's Game using a Markov Chain.

I am trying to calculate the probability that one sequence of coin tosses is more likely to win than the other in a game of Penney's. The sequences are: HTHT and THTT.

So far I've come up with the following:
$q_0=P_H*q_1+P_T*q_5$
$q_1=P_H*q_1+P_T*q_2$
$q_2=P_H*q_3+P_T*q_5$
$q_3=P_H*q_1+P_T*q_4$
$q_4=1$
$q_5=P_H*q_6+P_T*q_5$
$q_6=P_H*q_1+P_T*q_7$
$q_7=P_H*q_3+P_T*q_8$
$q_8=1$

After some cleaning up we can see that:

$q_0=0.5(q_1+q_5)$
$q_1=\frac{P_{T}*q_{2}}{1-P_{H}}=q_2$
$q_2=0.5(q_3+q_5)$
$q_3=0.5(q_1+q_4)$
$q_4=1$
$q_5=\frac{P_{H}*q_{6}}{1-P_{T}}=q_6$
$q_6=0.5(q1+q7)$
$q_7=0.5(q_3+q_8)$
$q_8=1$

$q_2$ and $q_6$ were left out at first, my mistake. Thanks @SteveKass for pointing that out.

But this is where I get stuck. Trying to solve as a system of linear equations gets me no where since I have too many unknown variables.

I want to figure out the possibilities being absorbed in either state $q_4$ or $q_8$ given the current state. Should it really be this difficult?

• To have nine unknowns for nine equations seems perfect, why do you say there are too many unknown variables? // To compute the probability to hit HTHT before THTT, I guess your $q_4$ is $1$ but your $q_8$ should be $0$. // To allow you to check your computations, let me mention that, when PH=PT=1/2, (I believe that) one hits HTHT before THTT with probability 9/34. – Did Oct 1 '14 at 19:55
• And it seems 9/34 should actually read 9/14. Well... – Did Oct 1 '14 at 20:19
• Please do not destroy content in that way. This question has an answer —an accepted one, in fact; while you may no longer be interested in this question, someone invested time and effort to respond, and it is rather unpolite to try to brush it off in that way. – Mariano Suárez-Álvarez Oct 8 '14 at 18:36

First off, you need to choose one and only one absorbing state $a$ for your equations. Let's pick state #4, so in the first set of equations, $q_4=1$, but $q_8=0$.
More importantly for where you're stuck, you seem to have just thrown away two of your equations when you "cleaned up": $q_2=\frac{1}{2}(q_3+q_5)$ and $q_6=\frac{1}{2}(q_1+q_7)$. If you put those back, you'll have nine equations in nine unknowns, and the system will have a solution (for the particular absorbing state I chose, #4). Here's a snapshot of Mathematica's solution. • Please replace $2q_4=1$ by $q_4=1$. – Did Oct 1 '14 at 20:14