13

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

Bravo
  • 4,413
user65009
  • 131
  • 2
    Presumably each integer is equally likely to be an output? – preferred_anon Mar 04 '13 at 21:49
  • 2
    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". – hmakholm left over Monica Mar 04 '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 04 '13 at 21:55
  • 1
    It looks like the range should be $[0,x-1]$, that is, that $x-1$ is included. – Ross Millikan Mar 04 '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 04 '13 at 22:48
  • Yes, precisely. – user65009 Mar 04 '13 at 22:53

3 Answers3

2

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.

Siméon
  • 10,664
  • 1
  • 21
  • 54
0

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.

preferred_anon
  • 17,121
  • 3
    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 04 '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 04 '13 at 22:09
  • My mistake; I completely misunderstood the question. I have written what is now hopefully a more helpful answer. – preferred_anon Mar 04 '13 at 22:17
0

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

Did
  • 279,727