| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
46 |
|
Paper 2, Section II, H |
2011 |
(i) Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain on the finite state space $S$ with transition matrix $P$. Fix a subset $A \subseteq S$, and let
$$H=\inf \left{n \geqslant 0: X_{n} \in A\right} .$$
Fix a function $g$ on $S$ such that $0<g(i) \leqslant 1$ for all $i \in S$, and let
$$V_{i}=\mathbb{E}\left[\prod_{n=0}^{H-1} g\left(X_{n}\right) \mid X_{0}=i\right]$$
where $\prod_{n=0}^{-1} a_{n}=1$ by convention. Show that
$$V_{i}= \begin{cases}1 & \text { if } i \in A \ g(i) \sum_{j \in S} P_{i j} V_{j} & \text { otherwise. }\end{cases}$$
(ii) A flea lives on a polyhedron with $N$ vertices, labelled $1, \ldots, N$. It hops from vertex to vertex in the following manner: if one day it is on vertex $i>1$, the next day it hops to one of the vertices labelled $1, \ldots, i-1$ with equal probability, and it dies upon reaching vertex 1. Let $X_{n}$ be the position of the flea on day $n$. What are the transition probabilities for the Markov chain $\left(X_{n}\right)_{n \geqslant 0}$ ?
(iii) Let $H$ be the number of days the flea is alive, and let
$$V_{i}=\mathbb{E}\left(s^{H} \mid X_{0}=i\right)$$
where $s$ is a real number such that $0<s \leqslant 1$. Show that $V_{1}=1$ and
$$\frac{i}{s} V_{i+1}=V_{i}+\frac{i-1}{s} V_{i}$$
for $i \geqslant 1$. Conclude that
$$\mathbb{E}\left(s^{H} \mid X_{0}=N\right)=\prod_{i=1}^{N-1}\left(1+\frac{s-1}{i}\right)$$
[Hint. Use part (i) with $A={1}$ and a well-chosen function $g$. ]
(iv) Show that
$$\mathbb{E}\left(H \mid X_{0}=N\right)=\sum_{i=1}^{N-1} \frac{1}{i}$$