# About the transition matrix of Markov Chains

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.

Solution:

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?

• yeah of course, it must be 1 @JohnDoe 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.

EDIT:

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.

• 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? May 15 '17 at 4:23
• @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. May 15 '17 at 4:32
• I don't know why I don't get it May 15 '17 at 4:41
• @AaronMartinez No worries. Good luck for your exams :) May 15 '17 at 5:31
• 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)$$
– 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.