Probability Matrix
You will need to know how to multiply matrices to tackle the later stages of this problem.
The diagram below shows three nodes, numbered $1,2,$ and $3$. If I am at node $1$, I am equally likely to visit node $2$ or $3$ next. If I am at node $3$ I am equally likely to visit node $1$ or $2$ next. If I am at node $2$ I will remain there. These probabilities are shown on the diagram by the arrows linking the nodes.
I can also represent this diagram using a matrix:
$$A= \left( \begin{array}{ccc} 0 &0.5 &0.5 \\ 0 &1 &0 \\ 0.5 &0.5 &0 \end{array}\right)$$
Each entry in this matrix $a_{ij}$ gives the probability of travelling from vertex $i$ to vertex $j$. So for example the entry in row $1$ column $2$ gives the probability of travelling from vertex $1$ to vertex $2$.
What can you say about the total of the entries in each row of a matrix such as this one?
The probability of being at vertex $2$ after two moves if I started from vertex $1$ is $0.75$. Work out the other entries for the matrix representing the probability of moving from vertex to vertex in two moves.
How is this matrix related to the original matrix?
$$A^2=\left(\begin{array}{ccc} 0.25 &0.75 &0 \\ 0 &1 &0 \\ 0 &0.75 &0.25 \end{array} \right)$$
$$A^3=\left(\begin{array}{ccc} 0 &0.875 &0.125 \\ 0 &1 &0 \\ 0.125 &0.875 &0 \end{array} \right)$$
Can you explain the zero entries in these two matrices?
Make a suggestion of the form the matrix takes showing the probabilities after $n$ moves. You may wish to consider $n$ odd and even separately. Can you prove that the form you have suggested is correct?
What happens as $n$ gets very large? How can this be explained by the diagram?
