Consider the following inductively defined generative model: \begin{align} x_0 &= N \\
x_{n+1} \vert x_n &\sim \mathrm{Uniform}(0, x_{n - 1}). \end{align} We suppose that the sequence of random variables terminates when the sequence reaches zero for the first time. That is, we define the random variable $S = \inf \set{n : x_n = 0}$. As a function of $N$, what is the expected value of $S$?

Suppose $x_0=1$, then it follows immediately that $x_1 = 0$ and hence $\mathbb{E}\left[S \vert N=1\right] = 1$. Suppose that $N=2$. Then, \begin{align} \mathbb{E}\left[S \vert x_0=2\right] &= \sum_{k=0}^1 \mathrm{Pr}\set{x_1 = k} \left[1 + \mathbb{E}\left[S \vert N=k\right]\right] \\
&= \frac{1}{2} + \frac{2}{2} \\
&= \frac{1}{1} + \frac{1}{2}. \end{align} Similarly, \begin{align} \mathbb{E}\left[S \vert x_0=3\right] &= \sum_{k=0}^2 \mathrm{Pr}\set{x_1 = k} \left[1 + \mathbb{E}\left[S \vert N=k\right]\right] \\
&= \frac{1}{3} + \frac{2}{3} + \frac{5/2}{3} \\
&= \frac{1}{3} + \frac{2}{3} + \frac{5}{6} \\
&= \frac{11}{6} \\
&= \frac{1}{1} + \frac{1}{2} + \frac{1}{3}. \end{align} One can additionally check that \begin{align} \mathbb{E}\left[S \vert N=3\right] = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}. \end{align}

These patterns lead us to speculate that the general solution of this problem is of the form \begin{align} \mathbb{E}\left[S \vert x_0=N\right] = H_N, \end{align} where $H_n$ is the $n$-th harmonic number. This fact can be established via induction. Before proceeding, however, we introduce a useful lemma pertaining to harmonic numbers.

\begin{align} \sum_{k=1}^N H_k = (N+1)H_N - N. \end{align}

By direct calculation, we have, \begin{align} \sum_{k=1}^N H_k &= \sum_{k=1}^N \sum_{n=1}^k \frac{1}{n} \\ &= \frac{N}{1} + \frac{N-2}{2} + \cdots + \frac{1}{N} \\ &= \frac{N}{1} + \frac{N-2}{2} + \cdots + \frac{1}{N} + \paren{\frac{1}{1} + \frac{2}{2} + \cdots + \frac{N}{N}} - N \\ &= \frac{N+1}{1} + \frac{N+1}{2} +\cdots + \frac{N+1}{N} - N \\ &= (N+1) H_N - N. \end{align}

With this lemma we may now establish the principle result:

\begin{align} \mathbb{E}\left[S\vert x_0 = N\right] = H_N. \end{align}

\begin{align} \mathbb{E}\left[S\vert x_0 = N\right] &= \sum_{k=0}^{N-1} \mathrm{Pr}\set{x_1 = k} \left[1 + \mathbb{E}\left[S\vert x_0 = k\right]\right] \\ &= 1 + \sum_{k=0}^{N-1} \frac{1}{N} \mathbb{E}\left[S\vert x_0 = k\right] \\ &= 1 + \sum_{k=1}^{N-1} \frac{1}{N} \mathbb{E}\left[S\vert x_0 = k\right] \\ &= 1 + \frac{1}{N} \sum_{k=1}^{N-1} H_k \\ &= 1 + \frac{1}{N} \paren{N H_{N-1} - (N - 1)} \\ &= \frac{N}{N} + H_{N-1} - \frac{N-1}{N} \\ &= H_{N-1} + \frac{1}{N} \\ &= H_N. \end{align}