Question
This question will connect Markov chains and directed graphs.
Abi is playing a game that involves a fair coin with heads on one side and tails on the other, together with two tokens, one with a fish’s head on it and one with a fish’s tail on it. She starts off with no tokens and wishes to win them both. On each turn she tosses the coin, if she gets a head she can claim the fish’s head token, provided that she does not have it already and if she gets a tail she can claim the fish’s tail token, provided she does not have it already. There are 4 states to describe the tokens in her possession; A: no tokens, B: only a fish’s head token, C: only a fish’s tail token, D: both tokens. So for example if she is in state B and tosses a tail she moves to state D, whereas if she tosses a head she remains in state B.
After $n$ throws the probability vector, for the 4 states, is given by $\mathbf{v}_n=\left(\begin{array}{l}a_n \\ b_n \\ c_n \\ d_n\end{array}\right)$ where the numbers represent the probability of being in that particular
state, e.g. $b_n$ is the probability of being in state B after $n$ throws. Initially $\mathbf{v}_0=\left(\begin{array}{l}1 \\ 0 \\ 0 \\ 0\end{array}\right)$.
a.i. Draw a transition state diagram for this Markov chain problem.
a.ii.Explain why for any transition state diagram the sum of the out degrees of the directed edges from a vertex (state) must add up to +1 .
b. Write down the transition matrix M, for this Markov chain problem.
c.i. Find the steady state probability vector for this Markov chain problem.
c.ii.Explain which part of the transition state diagram confirms this.
d. Explain why having a steady state probability vector means that the matrix $\mathbf{M}$ must have an eigenvalue of $\lambda=1$.
e. Find $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{v}_4$.
f. Hence, deduce the form of $\mathbf{v}_n$.
g. Explain how your answer to part (f) fits with your answer to part (c).
h. Find the minimum number of tosses of the coin that Abi will have to make to be at least $95 \%$ certain of having finished the game by reaching
$[4]$
state C.
▶️Answer/Explanation
a.
a.ii.You must leave the state along one of the edges directed out of the vertex. $\boldsymbol{R 1}$
[1 mark]
b.
$$
\left(\begin{array}{llll}
0 & 0 & 0 & 0 \\
\frac{1}{2} & \frac{1}{2} & 0 & 0 \\
\frac{1}{2} & 0 & \frac{1}{2} & 0 \\
0 & \frac{1}{2} & \frac{1}{2} & 1 \\
& &
\end{array}\right) \quad \text { M1A2 }
$$
[3 marks]
c.i.
$$
\left(\begin{array}{cccc}
0 & 0 & 0 & 0 \\
\frac{1}{2} & \frac{1}{2} & 0 & 0 \\
\frac{1}{2} & 0 & \frac{1}{2} & 0 \\
0 & \frac{1}{2} & \frac{1}{2} & 1
\end{array}\right)\left(\begin{array}{l}
w \\
x \\
y \\
z
\end{array}\right)=\left(\begin{array}{c}
w \\
x \\
y \\
z
\end{array}\right) \Rightarrow 0=w, \frac{w}{2}+\frac{x}{2}=x, \frac{w}{2}+\frac{y}{2}=y, \frac{x}{2}+\frac{y}{2}+z=z \quad \boldsymbol{M 1}
$$
$\Rightarrow w=0, x=0, y=0, z=1$ since $w+x+y+z=1$ so steady state vector is $\left(\begin{array}{l}0 \\ 0 \\ 0 \\ 1\end{array}\right)$.
A1R1A1
[4 marks]
c.ii.There is a loop with probability of 1 from state $D$ to itself.
A1
[1 mark]
d. Let the steady state probability vector be $\mathbf{s}$ then $\mathbf{M s}=1 \mathbf{s}$ showing that (Nambda $=1 \mathrm{~V})$ is an eigenvalue with associated eigenvector of $\mathbf{s}$.
[2 marks]
e.
$$
\mathbf{v}_1=\left(\begin{array}{c}
0 \\
\frac{1}{2} \\
\frac{1}{2} \\
0
\end{array}\right), \mathbf{v}_2=\left(\begin{array}{c}
0 \\
\frac{1}{4} \\
\frac{1}{4} \\
\frac{2}{4}
\end{array}\right), \mathbf{v}_3=\left(\begin{array}{c}
0 \\
\frac{1}{8} \\
\frac{1}{8} \\
\frac{6}{8}
\end{array}\right), \mathbf{v}_4=\left(\begin{array}{c}
0 \\
\frac{1}{16} \\
\frac{1}{16} \\
\frac{14}{16}
\end{array}\right)
$$
A1A1A1A1
[4 marks]
f.
$\mathbf{v}_n=\left(\begin{array}{c}0 \\ \frac{1}{2^n} \\ \frac{1}{2^n} \\ \frac{2^n-2}{2^n}\end{array}\right) \quad$ A2
[2 marks]
g.
$\lim _{n \rightarrow \infty} \mathbf{v}_n=\left(\begin{array}{l}0 \\ 0 \\ 0 \\ 1\end{array}\right)$ the steady state probability vector
M1R1
[2 marks]
h. Require $\frac{2^n-2}{2^n} \geqslant 0.95 \Rightarrow \frac{2}{2^n} \leqslant 0.05 \Rightarrow n=6$ (e.g. by use of table)
R1M1A2
[4 marks]
Question
A geneticist uses a Markov chain model to investigate changes in a specific gene in a cell as it divides. Every time the cell divides, the gene may mutate between its normal state and other states.
The model is of the form
$$
\left(\begin{array}{c}
X_{n+1} \\
Z_{n+1}
\end{array}\right)=M\left(\begin{array}{c}
X_n \\
Z_n
\end{array}\right)
$$
where $X_n$ is the probability of the gene being in its normal state after dividing for the $n$th time, and $Z_n$ is the probability of it being in another state after dividing for the $n$th time, where $n \in \mathbb{N}$.
Matrix $M$ is found to be $\left(\begin{array}{cc}0.94 & b \\ 0.06 & 0.98\end{array}\right)$.
The gene is in its normal state when $n=0$. Calculate the probability of it being in its normal state
a.i. Write down the value of $b$.
a.ii.What does $b$ represent in this context?
b. Find the eigenvalues of $\boldsymbol{M}$.
c. Find the eigenvectors of $\boldsymbol{M}$.
d.i. when $n=5$.
d.iijn the long term.
▶️Answer/Explanation
a.i. 0.02
A1
[1 mark]
a.ii.the probability of mutating from ‘not normal state’ to ‘normal state’
A1
Note: The $\boldsymbol{A 1}$ can only be awarded if it is clear that transformation is from the mutated state.
[1 mark]
b. $\operatorname{det}\left(\begin{array}{cc}0.94-\lambda & 0.02 \\ 0.06 & 0.98-\lambda\end{array}\right)=0 \quad$ (M1)
Note: Award $\boldsymbol{M 1}$ for an attempt to find eigenvalues. Any indication that $\operatorname{det}(\boldsymbol{M}-\lambda \boldsymbol{I})=0$ has been used is sufficient for the (M1).
$(0.94-\lambda)(0.98-\lambda)-0.0012=0$ OR $\lambda^2-1.92 \lambda+0.92=0$
(A1)
$\lambda=1,0.92\left(\frac{23}{25}\right)$
A1
[3 marks]
C. $\left(\begin{array}{ll}0.94 & 0.02 \\ 0.06 & 0.98\end{array}\right)\left(\begin{array}{l}x \\ y\end{array}\right)=\left(\begin{array}{l}x \\ y\end{array}\right)$ OR $\left(\begin{array}{ll}0.94 & 0.02 \\ 0.06 & 0.98\end{array}\right)\left(\begin{array}{l}x \\ y\end{array}\right)=0.92\left(\begin{array}{l}x \\ y\end{array}\right) \quad$ (M1)
Note: Award $\boldsymbol{M 1}$ can be awarded for attempting to find either eigenvector.
$0.02 y-0.06 x=0$ OR $0.02 y+0.02 x=0$
$\left(\begin{array}{l}1 \\ 3\end{array}\right)$ and $\left(\begin{array}{c}1 \\ -1\end{array}\right) \quad$ A1A1
Note: Accept any multiple of the given eigenvectors.
[3 marks]
d.i. $\left(\begin{array}{ll}0.94 & 0.02 \\ 0.06 & 0.98\end{array}\right)^5\left(\begin{array}{l}1 \\ 0\end{array}\right)$ OR $\left(\begin{array}{ll}0.744 & 0.0852 \\ 0.256 & 0.915\end{array}\right)\left(\begin{array}{l}1 \\ 0\end{array}\right) \quad$ (M1)
Note: Condone omission of the initial state vector for the $\boldsymbol{M 1}$.
0.744 ( $0.744311 \ldots)$
A1
[2 marks]
d.ii. $\left(\begin{array}{l}0.25 \\ 0.75\end{array}\right)$
(A1)
Note: Award A1 for $\left(\begin{array}{l}0.25 \\ 0.75\end{array}\right)$ OR $\left(\begin{array}{ll}0.25 & 0.25 \\ 0.75 & 0.75\end{array}\right)$ seen.
0.25
A1
[2 marks]
Question
Question
Question