Copyright © University of Cambridge. All rights reserved.
Congratulations to Angus from Bexhill College; Richard from
Bournemouth School and Andrei from Tudor Vianu National College,
Bucharest, Romania for their clearly explained and excellent
solutions to this problem.
The numbers on the edges of this graph give the probabilities of a
particle travelling along those edges in the direction given by the
arrow. The same information is given by the entry $a_{ij}$ in the
following matrix which gives the probability of travelling from
vertex $i$ to vertex $j$. $$A=\left (\begin{array}{cccc} 0 &1
&0 &0\\ 0 &0 &0.5 &0.5\\ 1 &0 &0
&0\\ 0 &0 &0 &1 \end{array} \right)$$ This is
Angus's solution. Firstly, we see that when we multiply matrices :
$$ \left ( \begin{array}{ccc} A &B &C \\ D &E &F \\
G &H &I \end{array} \right) \left ( \begin{array}{ccc} a
&b &c \\ d &e &f \\ g &h &i \end{array}
\right) = \left ( \begin{array}{ccc} Aa+Bd+Cg & Ab+Be+Ch
&Ac+Bf+Ci\\ Da+Ed+Fg &Db+Ee+Fh &Dc+Ef+Fi \\ Ga+Hd+Ig
&Gb+He+Ih &Gc+Hf+Ii \end{array} \right) $$ and similarly
for larger matrices. Hence when the matrix gives probabilities:
$$A= \left( \begin{array}{cccc} P(1\to 1) &P(1\to 2)
&P(1\to 3) &P(1\to 4)\\ P(2\to 1) &P(2\to 2)
&P(2\to 3) &P(2\to 4)\\ P(3\to 1) &P(3\to 2)
&P(3\to 3) &P(3\to 4)\\ P(4\to 1) &P(4\to 2)
&P(4\to 3) &P(4\to 4) \end{array} \right)$$ where $P(1\to
2)$ is the probability of travelling to $2$ when at $1$. Then the
first column of $A^2$ is: $$\left ( \begin{array}{c} P(1\to 1)P
(1\to 1) + P (1\to 2) P(2\to 1) + P(1\to 3)P(3\to 1) + P(1\to 4)
P(4\to 1)\\ P(2\to 1)P (1\to 1) + P (2\to 2) P(2\to 1) + P(2\to
3)P(3\to 1) + P(2\to 4) P(4\to 1)\\ P(3\to 1)P (1\to 1) + P (3\to
2) P(2\to 1) + P(3\to 3)P(3\to 1) + P(3\to 4) P(4\to 1) \\ P(4\to
1)P (1\to 1) + P(4\to 2) P(2\to 1) + P(4\to 3)P(3\to 1) + P(4\to 4)
P(4\to 1) \end{array} \right ) $$ and so on for the four
columns.
Now, the probability of getting from $1$ to $2$ in $x$ steps equals
the sum of the probabilities of all the ways of getting from 1 to 2
in x steps : $P(1\to 2 \text{ (2 steps)}) = P(1\to 1)P(1\to 2)+
P(1\to 2)P (2\to 2)+ P(1\to 3)P(3\to 2)+\ldots$. Thus we have in
$A^2$ the probability of getting from one point to another in two
steps, as each entry in the matrix is the sum of probabilities of
getting between the two points in two steps. Similarly, we find
that if we cube the matrix, we are adding the probabilities of
three-stage routes between two points, and so on for higher
powers.
Now, we look at what happens for higher powers of $A$. $$A^{20}=
\left( \begin{array}{cccc} 0 &0 &0.008 &0.992 \\ 0.008
&0 &0 &0.992 \\ 0 &0016 &0 &0.984 \\ 0
&0 &0 &1 \end{array} \right) $$ $$A^{21}= \left(
\begin{array}{cccc} 0.008 &0 &0 &0.992 \\ 0 &0.008
&0 &0.992 \\ 0 &0 &0.008 &0.992 \\ 0 &0
&0 &1 \end{array} \right) $$ $$A^{22}= \left(
\begin{array}{cccc} 0 &0.008 &0 &0.992 \\ 0 &0
&0.004 &0.996 \\ 0.008 &0 &0 &0.992 \\ 0 &0
&0 &1 \end{array} \right) $$ First (and easiest) we explain
the fourth row. In the network, an object at vertex (4) has a
probability of 1 of returning to (4) at the next journey. It
therefore always returns to (4) and never reaches any other vertex.
The fourth row will remain at $0$ $0$ $0$ $1$ as an object at (4)
will remain at (4).
Next we come to the cycling of the three values in the loop at the
left. At vertices (3) and (1), an object may only travel to one
other vertex ((1) and (2) respectively), and at vertex (2) it
travels to (3) (with a probability of $0.5$ which we ignore to
explain the cycling). Therefore, an object at vertex (1) can travel
to (2), then (3) then (1) again and so on. However, it moves on one
vertex at a time so, if it cycles through the vertices, after n
journeys the object will be at vertex $n (\text{mod } 3)$.
Similarly, if it starts at (2), it will be at vertex $(n +
1)(\text{mod } 3)$ and, from (3), at $(n + 2)(\text{mod }
3)$.
Lastly, we explain the numerical values of the probabilities. Every
time an object is at vertex (2), it travels to (4) with a
probability p where p = 0.5 . Therefore, it will only avoid going
to (4) with a probability of $(1 - p)^m$ , where $m$ is the number
of times the object is at vertex (2) and $m$ is roughly $n/3$.
Therefore, the probability of an object starting at vertices (1),
(2) or (3) arriving at (4) is $1 - (1 - p)^m$ . As once the object
is at (4) it cannot travel to any other vertex, the probability of
being at (4) after n journeys can only increase.
With this information, we can predict the behaviour of $A^n$ as we
let $n$ increase. All values in the fourth column will tend to one
as $n$ tends to infinity, as they are given (roughly) by $1 -
0.5^{n/3}$ and $0.5^{n/3}$ tends to 0. The other nine values will
cycle as shown above, in the manner : $$ \left( \begin{array}{ccc}
0 &a &0 \\ 0 &0 &b \\ c &0 &0 \end{array}
\right) \to \left( \begin{array}{ccc} 0 &0 &b \\ c/2 &0
&0 \\ 0 &a &0 \end{array} \right) \to \left(
\begin{array}{ccc} c/2 &0 &0 \\ 0 &a/2 &0 \\ 0
&0 &b \end{array} \right) \to \left( \begin{array}{ccc} 0
&a/2 &0 \\ 0 &0 &b/2 \\ c/2 &0 &0
\end{array} \right) $$ and so on for $n=3x+1,\ 3x+2,\ 3x+3,\
3(x+1)+1$ respectively where $x$ is an integer.
The values of $a,\ b$ and $c$ will tend to zero as they are given
by $0.5^m$ for $n$ stages where $m$ is of the order of $n/3$. Hence
$$A^{100}= \left ( \begin{array}{cccc} 1 &1\times 10^{-10}
&0 &0.9999999999 \\ 0 &0 &5\times 10^{-11}
&0.99999999995\\ 1\times 10^{-10} &0 &0
&0.9999999999 \\ 0 &0 &0 &1 \end{array}
\right)$$