Expected value: Random sequence Let $R$ be a random number generator such that R(n) returns an integer in the range  $0,1,...,n−1$ with uniform probability. Note that this is not a true function in the mathematical sense, as in- putting the same number a second time will not necessarily yield the same result. The random number generator only works for $n>1$.
Starting from a googol, ie $x_0 = 10^{100}$, consider the sequence $x_i = R(x_i−1)$. Eventually the sequence terminates when $x_s = 0$ for some $s$ and no further generation is possible. What is E[s]
 A: One can frame the problem as a tower of states, where one can transition to lower states until reaching zero. Note that this is a Markov process, since the probability of reaching a given integer only depends on the previous state (the previous maximum integer $x$). Let $p_n(x|y)$ denote the transition probability of going from $y$ to $x$ in $n$ steps. From an integer $y$ we can only go downwards, e.g., to $x<y$. The mean of $n$ steps required to go from $x_0$ to 0 is thus
\begin{equation}
E(n,x_0)=\sum_{i=1}^{x_0} \, i \, p_i(0|x_0) 
\end{equation}
Note that $p_1(y|x)=1/x$, $\forall y<x$, since we have the same probability to go to any of the integers between 0 and $x$. Also, descending from an integer $x$ in $x$ steps implies perform $x$ decays to the immediately inferior state, i.e., $p_x(0|x)=\prod_y^x p_1(y-1|y)$.
We can proceed in an inductive approach, starting from small initial integers.

*

*Firstly, for $x_0=1$, $p_1(0|1)=1$, and hence $E(n,1)=p_1(0|1)=1$.


*For $x_0=2$, we have to consider $p_1(0|2)=1/2$ and $p_2(0|2)=p_1(0|1)p_1(1|2)=1 \times 1/2$. Thus, $E(n,2)=p_1(0|2) + 2 p_2(0|2)=1/2 + 2\times 1/2=1 + 1/2$.


*For $x_0=3$, $E(n,3)=p_1(0|3) + 2 p_2(0|3) + 3 p_3(0|3)$. We have $p_3(0|3)=p_1(2|3)p_1(1|2)p_1(0|1)=(1/3)\times(1/2)\times 1$. On the other hand, to reach 0 in 2 steps, we have two possibilities, and hence we sum over both possible paths: $p_2(0|3)=p_1(2|3)p_1(0|2) + p_1(1|3)p_1(0|1)=1/3 \times (1 + 1/2)$. Therefore, $E(n,3)=1 + 1/2 + 1/3$.
We can already see the trend
\begin{equation}
E(n,x)=\sum_{k=1}^x \frac{1}{k} = H_x,
\end{equation}
where $H_x$ is the $x^{th}$ harmonic number. Since asymptotically, $H_x \sim \ln(x) + \gamma$, where $\gamma$ is the Euler-Mascheroni constant, for a googol $x=10^{100}$ we get $E(n,10^{100})=H_{10^{100}} \sim 230$.
