A coin is tossed repeatedly until two successive heads appear. I have to find the mean number of tosses required using a Markov Chain and its transition matrix.


Let $X$ be the random variable that represents the number of tosses required. So we need to find $\mathbb{E}[X]$, where $\mathbb{E}$ denotes the mean.

Otherwise, let $X_n$ be the cumulative number of successive heads. The state space is $\{0,1,2\}$ and the transition probability matrix is $$ \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{pmatrix} $$

And then the answer continues (I have the problem solved), but I don't know how the transition matrix (above) is constructed.

Can somebody explain me?

  • $\begingroup$ yeah of course, it must be 1 @JohnDoe $\endgroup$ May 15 '17 at 4:04

The transition matrix reads: $P(X_n=0\to X_{n+1}=0)=\frac12$, and $P(X_n=0\to X_{n+1}=1)=\frac12$, and $P(X_n=0\to X_{n+1}=2)=0$. This is me reading off the first row.

In the context, this means the probability of going from $0$ successive heads to $0$ successive heads is $\frac12$ which makes sense, since this is the probability of rolling a tails. The probability of going from $0$ successive heads to $1$ successive head is also $\frac12$ since this is probability of hitting heads. Finally, probability of going from $0$ successive heads to $2$ successive heads is obviously not possible in one toss, so this probability is $0$.

Similarly, you can read off the other two rows.

Judging by the last row, this game ends when you get $2$ successive heads, since from here it can never go back down to $0$. I suppose this must have been in the question.


In an attempt to explain this better, I will also go through the second row.

Firstly, we must recognise what the columns and rows mean. The row represents the state in which we start - so the first row represents starting in the state of having $0$ successive heads, etc. The column represents the state in which we finish after $1$ toss of a coin. So the second column represents finishing with $1$ successive head, which means you used to have none, and you have just rolled a heads.

Now, the second row is $$\left(\begin{matrix}\frac12 & 0 & \frac12 \end{matrix}\right)$$ The first element in this represents the probability of going from the state of $1$ successive heads to $0$ successive heads (row $2$ corresponds to starting with $1$ successive heads, column $1$ corresponds to ending with $0$ successive heads). Clearly, to go from having $1$ successive heads to having none means we rolled a tails, which has probability $\frac12$.

The second element in this represents the probability of going from the state of $1$ successive heads to staying in this state. But we must toss the coin, and as I wrote in the comments, no matter what we get from the toss, we must change - rolling heads means we now have $2$ successive heads, rolling tails means we now have none (as described above). So we see it is impossible to stay in this state, hence why this entry is $0$.

Finally the third element represents the probability of going from $1$ successive heads to $2$. This of course happens when we roll a heads, which has probability half.

I hope this helped to simplify it.

  • $\begingroup$ following your argument i think my transition probability matrix is wrong then, because from 1 successive heads to 1 successive head is 1/2 and not $0$ as the matrix says. Am I correct? $\endgroup$ May 15 '17 at 4:23
  • $\begingroup$ @AaronMartinez No, the matrix is correct in this aspect. It says going from $1$ successive heads to $1$ successive heads is $0$. Why is this true? Because you can only get a heads or a tails - suppose you have already got $1$ heads, so are in that state. Then if you get a tails, then you are now on $0$ successive heads, if you get a heads you are on $2$ successive heads. So it is not possible to stay on $1$ successive head. $\endgroup$
    – John Doe
    May 15 '17 at 4:32
  • $\begingroup$ I don't know why I don't get it $\endgroup$ May 15 '17 at 4:41
  • 1
    $\begingroup$ @AaronMartinez No worries. Good luck for your exams :) $\endgroup$
    – John Doe
    May 15 '17 at 5:31
  • 1
    $\begingroup$ FYI, the correct notation for what you write $$P(X_n=x\to X_{n+1}=y)$$ is $$P(X_{n+1}=y\mid X_n=x)$$ $\endgroup$
    – Did
    May 15 '17 at 11:43

To understand the matrix, you need to understand what the states mean.

In this case,

State 0: The previous flip was not a head.

State 1: The previous flip was a head.

State 2: You have seen two heads in a row.

Assume you are in state 0. You flip a coin. With heads you go to state 1, and with tails you stay in state 0. So we stay in state 0 with probability $1/2$ and go to state 1 with probability $1/2$. This gives the first row in the transition matrix. $$ \begin{pmatrix} 1/2 & 1/2 & 0 \end{pmatrix} $$

Similarly, you can construct the other rows.


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.