| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
22 |
|
Paper 1, Section II, H |
2020 |
Let $\left(X_{n}\right){n \geqslant 0}$ be a Markov chain with transition matrix $P$. What is a stopping time of $\left(X{n}\right)_{n \geqslant 0}$ ? What is the strong Markov property?
A porter is trying to apprehend a student who is walking along a long narrow path at night. Being unaware of the porter, the student's location $Y_{n}$ at time $n \geqslant 0$ evolves as a simple symmetric random walk on $\mathbb{Z}$. The porter's initial location $Z_{0}$ is $2 m$ units to the right of the student, so $Z_{0}-Y_{0}=2 m$ where $m \geqslant 1$. The future locations $Z_{n+1}$ of the porter evolve as follows: The porter moves to the left (so $Z_{n+1}=Z_{n}-1$ ) with probability $q \in\left(\frac{1}{2}, 1\right)$, and to the right with probability $1-q$ whenever $Z_{n}-Y_{n}>2$. When $Z_{n}-Y_{n}=2$, the porter's probability of moving left changes to $r \in(0,1)$, and the probability of moving right is $1-r$.
(a) By setting up an appropriate Markov chain, show that for $m \geqslant 2$, the expected time for the porter to be a distance $2(m-1)$ away from the student is $2 /(2 q-1)$.
(b) Show that the expected time for the porter to catch the student, i.e. for their locations to coincide, is
$$\frac{2}{r}+\left(m+\frac{1}{r}-2\right) \frac{2}{2 q-1} .$$
[You may use without proof the fact that the time for the porter to catch the student is finite with probability 1 for any $m \geqslant 1$.]