(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}$$