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