Expected Absorption Time in a Particular Markov Chain

Question

This question comes from a quant finance interview practice test:

If $X_0 = x$ and $X_i \sim \mathcal{U}\{0, X_i-1\}$ (discrete uniform on $\{0,\dots, X_i-1\}$), what is the expected absorption time when the process reaches $0$.

Answer 1

Let $T$ be the absorption time and $g(x) = E[T|X_0 = x], x \in \mathbb{N_0}$. The boundary condition is $g(0) = 0$ and we have the recurrence relationship

$$ g(x) = 1 + \frac {1} {x}\sum_{y=0}^{x-1} g(y), x \in \mathbb{N}$$

by first step analysis. Calculate the first few terms and we have

$$ g(1) = 1, g(2) = 1 + \frac {1} {2}, g(3) = 1 + \frac {1} {2} + \frac {1} {3}$$

So we can guess a proposition $p(x)$:

$$ g(x) = \sum_{k=1}^x \frac {1} {k}, x \in \mathbb{N}$$

and try to proof this proposition by induction. Assume $p(n)$ is true for all $n \in \{1, 2, \ldots, m\}$. Consider $p(m+1)$:

$$ \begin{align} g(m+1) &= 1 + \frac {1} {m+1}\sum_{y=0}^{m} g(y) \\ &= 1 + \frac {1} {m+1}\sum_{y=1}^{m} \sum_{k=1}^{y} \frac {1} {k} \\ &= 1 + \frac {1} {m+1}\sum_{k=1}^{m} \sum_{y=k}^{m} \frac {1} {k} \\ &= 1 + \frac {1} {m+1}\sum_{k=1}^{m} \frac {m-k+1} {k} \\ &= 1 + \frac {1} {m+1}\sum_{k=1}^{m} \left(\frac {m+1} {k} - 1\right)\\ &= 1 + \sum_{k=1}^{m} \frac {1} {k} - \frac {m} {m+1}\\ &= \sum_{k=1}^{m} \frac {1} {k} + \frac {1} {m+1}\\ &= \sum_{k=1}^{m+1} \frac {1} {k}\\ \end{align}$$

So $p(m+1)$ is also true if $p(1), p(2), \ldots, p(m)$ are ture. Therefore we have proved the proposition by induction. In other words the expected stopping time is the $x$-th harmonic number.