Recursive random draw

Question

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?

Answer 1

Let $E(n)$ denote the expected number. Then $$E(1) = 1$$ $$E(n) = 1 + \frac{1}{n}\sum_{k=1}^{n-1}E(k),\:\: n > 1$$ since we always require at least 1, and with probability $1/n$ we land on one of the other $n-1$ numbers $k = 1$ to $n-1$, at which point we will require an additional $E(k)$. Inspection of how $E(n+1)$ is produced form $E(n)$ reveals $$E(n) = E(n-1) + \frac{1}{n}, \:\:n > 1$$ so $$E(n) = \sum_{k=1}^{n}\frac{1}{k}=H_n, \:\: n > 0$$ or the $n^{th}$ harmonic number. So $$E(10^{100}) = H_{10^{100}}$$ This will be approximately $\ln(10^{100})+\gamma$ where $\gamma$ is the Euler-Mascheroni constant, or $100/\log_{10}{e} + \gamma \approx 230.8.$

Answer 2

@PT272 great you added this part, but I think there is a little typo. Unfortunately I do not have the permissions to comment or even edit so I put it as a new answer.

After "and simplify" I it should be

$E(n+1) = 1+E(n)-\frac{\color{red}{n}}{n+1}$