Denote by $R(n)$ a random draw of integers between 0 and $n-1$ (inclusive). We repeatedly apply $R(n)$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
This looks like a optional stopping however the process is not really a martingale. Is there a result for Markov processes that would make the computations easier in this case?
Let $E(n)$ be the expected number of repeated applications until zero is obtained, starting from $n$.
Then, $E(0) = 0$ and $\displaystyle E(n) = 1 + \frac1n\sum_{k=0}^{n-1}E(k)$.
$$\begin{array}{rcl} nE(n) &=& \displaystyle n + \sum_{k=0}^{n-1} E(k) \\ (n-1)E(n-1) &=& \displaystyle (n-1) + \sum_{k=0}^{n-2} E(k) \\ nE(n) - (n-1)E(n-1) &=& 1 + E(n-1) \\ nE(n) - nE(n-1) &=& 1 \\ E(n) &=& \displaystyle \frac1n + E(n-1) \end{array}$$
which means that $E(n) = \displaystyle \sum\limits_{k=1}^n \frac1k = H_n$.
It is well known that $H_n \sim \ln(n)$, so $E(10^{100}) \approx 100 \ln 10 \approx 230.3$.