<s>[INST] How to find $E(f(f(f(\ldots f(x)))$ I have a random function $f(x)$ which returns one of the integers in the range $[0, x-1]$ with equal probability and $f(0) = 0$.
What is the expected value $E(f(f(f(\ldots f(x)))$ ($n$-times $f(x)$)? The answer should be a function of $x$ and $n$.
 [/INST] I fail to find a general pattern, but here are some results.
Write $E_n(x) = E(f^n(x))$.
It is easily seen that $E_n(x) = 0$ if $x \leq n$ and $E_n(n+1) = \frac{1}{(n+1)!}$.
Furthermore, if $x \geq 1$, we have
$$
E_1(x) = \frac{x-1}{x} + \dots + \frac{1}{x} = \frac{x-1}{2}
$$
$$
E_2(x) = \frac{1}{x}\sum_{y=1}^{x-1}\frac{y-1}{2} = \frac{1}{4}\frac{(x-1)(x-2)}{x} = \frac{1}{4}\left(x-3+\frac{2}{x}\right)
$$
$$
E_3(x) = \frac{1}{4x} \sum_{y=1}^{x-1}(y-3) + \frac{1}{2x}\sum_{y=1}^{x-1}\frac{1}{y} = \frac{(x-1)(x-4)}{8x} + \frac{H_{x-1}}{2x}
$$
The appearance of the harmonic sum $H_x$ makes me think that no simplification will be possible in general.
</s>