Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
Presumably each integer is equally likely to be an output? –  Daniel Littlewood Mar 4 '13 at 21:49
What is random in the question? What is its probability distribution? What do you know about $f$? If nothing more than you have written here, then there probably isn't any description of the expected value that is nicer than "the expected value of such-and-such". –  Henning Makholm Mar 4 '13 at 21:49
Each integer is equally like to be an output and x is a possitive integer. For example f(5) returns numbers 0 .. 4 with probability of 1/5. So E(f(5)) = 1/5*(0 + 1 + 2 + 3 + 4) = 10 / 5 = 2 –  user65009 Mar 4 '13 at 21:55
It looks like the range should be $[0,x-1]$, that is, that $x-1$ is included. –  Ross Millikan Mar 4 '13 at 22:00
The meaning of the question is not very clear (see the comments), perhaps due to some confusion between random variables and deterministic quantities. A way I can make sense of it is to consider a Markov chain $(X_n)_{n\geqslant0}$ such that $X_0=x$, for some $x\geqslant0$, and such that, conditionally on $X_{n-1}=y$, $X_n$ is uniformly distributed on $\{0,1,\ldots,y-1\}$ if $y\geqslant1$ and $X_n=0$ if $y=0$. The question would be to compute $\mathbb E(X_n)$ for every $n\geqslant0$. Could you confirm this is the model you have in mind? –  Did Mar 4 '13 at 22:48
show 1 more comment

3 Answers

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.

share|improve this answer
add comment

Presumably you mean the interval $[0,x-1]$.
Let $Z_{1}$, $Z_{2}, \ldots Z_{n}$ be random variables with probability mass functions $f(z)$, $f^{2}(z),\ldots f^{n}(z)$ respectively. Then $P(Z_{n}=z)=P(Z_{n-1}=z|0\le z< x-n)$.
Therefore, $$f^{n}(z)=\frac{f^{n-1}(z)}{f^{n-1}(x-n)}$$
When $0\le z<x-n$, and $0$ otherwise.

share|improve this answer
No, the second iteration of $f$ has a range that depends on the result of the first, so $0$ is more probable than $x-n$ –  Ross Millikan Mar 4 '13 at 22:01
The problem is several iterations of the function don't return integers in range[0,x - n] with equal likelihood. Take for instance f(f(5)). The probability that f(f(5)) returns 3 is 5 -> 4 -> 3 is 1/5 * 1/4 = 1/20, while for example the probability that f(f(5)) returns 0 is 5 -> 4 -> 0 (which is just 1/5 * 1/4 = 1/20) plus 5 -> 3 -> 0 and so on. Long story short it's what Ross Millikan said. –  user65009 Mar 4 '13 at 22:09
My mistake; I completely misunderstood the question. I have written what is now hopefully a more helpful answer. –  Daniel Littlewood Mar 4 '13 at 22:17
add comment

According to an answer by the OP in the comments, the question is to consider a Markov chain $(X_n)_{n\geqslant0}$ such that $X_0=x$, for some $x\geqslant1$, and, for each $n\geqslant1$, conditionally on $X_{n-1}=y$, $X_n$ is uniformly distributed on $\{0,1,\ldots,y-1\}$ if $y\geqslant1$ and $X_n=0$ if $y=0$. The question is to compute $\mathbb E(X_n)$ for every $n\geqslant0$.

A standard approach is to note that $\mathbb E(X_n\mid X_{n-1}=0)=0$ and, for every $y\geqslant1$, $$ \mathbb E(X_n\mid X_{n-1}=y)=\frac1y\sum_{k=0}^{y-1}k=\tfrac12(y-1). $$ To sum up, $$ 2\mathbb E(X_n)=\mathbb E(X_{n-1}-1;X_{n-1}\geqslant1)=\mathbb E(X_{n-1})-1+\mathbb P(X_{n-1}=0). $$ On the other hand, $\mathbb P(X_n=0\mid X_{n-1}=0)=1$ and, for every $y\geqslant1$, $$ \mathbb P(X_n=0\mid X_{n-1}=y)=\frac1y, $$ hence $$ \mathbb P(X_n=0)=\mathbb P(X_{n-1}=0)+\mathbb E(1/X_{n-1};X_{n-1}\geqslant1). $$ At this point it seems necessary to compute recursively $\mathbb E(1/X_{n};X_{n}\geqslant1)$ but I am suddenly not so sure that this would make the end of the road any nearer...

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.