1
$\begingroup$

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?)

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ @ByronSchmuland Yes. Thanks for the clarifying! I have fixed it up. $\endgroup$ – Xuxu Oct 5 '16 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.