IB Questionbank

User interface language: English | Español

Date	May Example question	Marks available	4	Reference code	EXM.3.AHL.TZ0.4
Level	Additional Higher Level	Paper	Paper 3	Time zone	Time zone 0
Command term	Find	Question number	4	Adapted from	N/A

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$ $n$ throws the probability vector, for the 4 states, is given by $v_{n} = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} a_{n} b_{n} c_{n} d_{n} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ ${{\mathbf{v}}_n} = \left( {\begin{array}{*{20}{c}} {{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}$ ${b_n}$ is the probability of being in state B after $n$ $n$ throws. Initially $v_{0} = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 1000 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ ${{\mathbf{v}}_0} = \left( {\begin{array}{*{20}{c}} 1 \\ 0 \\ 0 \\ 0 \end{array}} \right)$ .

Draw a transition state diagram for this Markov chain problem.

[3]

a.i.

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.

[1]

a.ii.

Write down the transition matrix M, for this Markov chain problem.

[3]

Find the steady state probability vector for this Markov chain problem.

[4]

c.i.

Explain which part of the transition state diagram confirms this.

[1]

c.ii.

Explain why having a steady state probability vector means that the matrix M must have an eigenvalue of $λ = 1$ $\lambda = 1$ .

[2]

Find $v_{1}, v_{2}, v_{3}, v_{4}$ ${{\mathbf{v}}_1}{\text{,}}\,\,{{\mathbf{v}}_2}{\text{,}}\,\,{{\mathbf{v}}_3}{\text{,}}\,\,{{\mathbf{v}}_4}\,$ .

[4]

Hence, deduce the form of $v_{n}$ ${{\mathbf{v}}_n}$ .

[2]

Explain how your answer to part (f) fits with your answer to part (c).

[2]

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 state C.

[4]

Markscheme

M1A2

[3 marks]

a.i.

You must leave the state along one of the edges directed out of the vertex. R1

[1 mark]

a.ii.

$⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 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{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ $\left( {\begin{array}{*{20}{c}} 0&0&0&0 \\ {\tfrac{1}{2}}&{\tfrac{1}{2}}&0&0 \\ {\tfrac{1}{2}}&0&{\tfrac{1}{2}}&0 \\ 0&{\tfrac{1}{2}}&{\tfrac{1}{2}}&1 \end{array}} \right)$ M1A2

[3 marks]

$⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 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{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} w x y z \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} w x y z \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠ \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$ $\left( {\begin{array}{*{20}{c}} 0&0&0&0 \\ {\tfrac{1}{2}}&{\tfrac{1}{2}}&0&0 \\ {\tfrac{1}{2}}&0&{\tfrac{1}{2}}&0 \\ 0&{\tfrac{1}{2}}&{\tfrac{1}{2}}&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} w \\ x \\ y \\ z \end{array}} \right) = \left( {\begin{array}{*{20}{c}} w \\ x \\ y \\ z \end{array}} \right) \Rightarrow 0 = w{\text{,}}\,\,\frac{w}{2} + \frac{x}{2} = x{\text{,}}\,\,\frac{w}{2} + \frac{y}{2} = y{\text{,}}\,\,\frac{x}{2} + \frac{y}{2} + z = z$ M1

$\Rightarrow w = 0, x = 0,, y = 0, z = 1$ $\Rightarrow w = 0{\text{,}}\,\,x = 0,{\text{,}}\,\,y = 0{\text{,}}\,\,z = 1\,$ since $w + x + y + z = 1$ $w + x + y + z = 1$ so steady state vector is $⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0001 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ $\left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \\ 1 \end{array}} \right)$ . A1R1A1

[4 marks]

c.i.

There is a loop with probability of 1 from state D to itself. A1

[1 mark]

c.ii.

Let the steady state probability vector be s then Ms = 1s showing that (\lambda = 1\) is an eigenvalue with associated eigenvector of s. A1R1

[2 marks]

$v_{1} = ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 \frac{1}{2} \frac{1}{2} 0 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎠, v_{2} = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 \frac{1}{4} \frac{1}{4} \frac{2}{4} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠, v_{3} = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 \frac{1}{8} \frac{1}{8} \frac{6}{8} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠, v_{4} = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 \frac{1}{16} \frac{1}{16} \frac{14}{16} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ ${{\mathbf{v}}_1} = \left( {\begin{array}{*{20}{c}} 0 \\ {\tfrac{1}{2}} \\ {\tfrac{1}{2}} \\ 0 \end{array}} \right){\text{,}}\,\,{{\mathbf{v}}_2} = \left( {\begin{array}{*{20}{c}} 0 \\ {\tfrac{1}{4}} \\ {\tfrac{1}{4}} \\ {\tfrac{2}{4}} \end{array}} \right){\text{,}}\,\,{{\mathbf{v}}_3} = \left( {\begin{array}{*{20}{c}} 0 \\ {\tfrac{1}{8}} \\ {\tfrac{1}{8}} \\ {\tfrac{6}{8}} \end{array}} \right){\text{,}}\,\,\,{{\mathbf{v}}_4} = \left( {\begin{array}{*{20}{c}} 0 \\ {\tfrac{1}{{16}}} \\ {\tfrac{1}{{16}}} \\ {\tfrac{{14}}{{16}}} \end{array}} \right)\,$ A1A1A1A1

[4 marks]

$v_{n} = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0 \frac{1}{2^{n}} \frac{1}{2^{n}} \frac{2^{n} - 2}{2^{n}} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠$ ${{\mathbf{v}}_n} = \left( {\begin{array}{*{20}{c}} 0 \\ {\tfrac{1}{{{2^n}}}} \\ {\tfrac{1}{{{2^n}}}} \\ {\tfrac{{{2^n} - 2}}{{{2^n}}}} \end{array}} \right)$ A2

[2 marks]

$lim n \to \infty v_{n} = ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} 0001 \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠$ $\mathop {{\text{lim}}}\limits_{n \to \infty } {{\mathbf{v}}_n} = \left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \\ 1 \end{array}} \right)$ the steady state probability vector M1R1