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? 
 A: 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.
A: 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.
