# Expected value uniform decreasing function

We are given a function $f(n,k)$ as

for(i=0;i < k;i++)
n = rand(n);
return n;


rand is defined as a random number generator that uniformly generates values in the range $[0,n)$. It returns a value strictly less than $n$; also $\operatorname{rand}(0)=0$.

What is the expected value of our function $f(n,k)$ given $n$ and $k$?

I will make a guess that rand(n) returns uniform reals on the interval [0,n). Since rand(n) gives the same distribution as n*rand(1). Thus for given $n$ and $k$ the random variable produced by the algorithm is $$X = n \prod_{m=1}^k U_m$$ where $U_m$ are independent identically distributed continuous uniform random variables on the unit interval. Thus $$\mathbb{E}\left(X\right) = n \prod_{m=1}^k \underbrace{\mathbb{E}(U_m)}_{=\frac{1}{2}} = n 2^{-k}$$

Responding to OP's request to consider the case when rand(n) returns unifrom random integers $[0,n]$. Let $Y_m \sim \mathcal{DU}\left([0,Y_{m-1}\right)$ be such a uniform random integer drawn on $m$-th iteration. Assume $Y_0 = n$. Then we seek to find $$\mathbb{E}\left(Y_k\right) = \mathbb{E}\left( \mathbb{E}\left(Y_k \mid Y_{k-1}\right)\right) = \mathbb{E}\left(\frac{1}{2}Y_{k-1}\right) = \ldots =\frac{1}{2^k} Y_0 = \frac{n}{2^k}$$ Thus the expectation is the same as in the case of continuous uniforms.

Now, assuming rand(n) generates uniform integers on $[0,n)$, instead of $[0,n]$. In that case $Y_k|Y_{k-1} \sim \mathcal{DU}\left( \left[0, \max(Y_{k-1}-1,0)\right]\right)$. Obtaining closed form is not feasible for arbitrary $k$, but with the help of Mathematica I was able to get expectations for low values of $k$: $$\mathbb{E}\left(Y_1\right) = \begin{cases} \frac{n-1}{2} & n > 1 \\[5pt] 0 & \text{otherwise} \end{cases}$$ $$\mathbb{E}\left(Y_2\right) = \begin{cases} \frac{(n-1)(n-2)}{4 n} & n>2 \\[5pt] 0 & \text{otherwise} \end{cases}$$ $$\mathbb{E}\left(Y_3\right) = \begin{cases} \frac{1}{8 n} \left(4 H_{n-1}+(n-1)(n-6)\right) & n>3 \\[5pt] 0 & \text{otherwise} \end{cases}$$ $$\mathbb{E}\left(Y_4\right) = \begin{cases} \frac{1}{16 n} \left( 4 \left(H_{n-1}\right){}^2+12 H_{n-1}-4 H_{n-1}^{(2)}+(n-1)(n-14) \right) & n>4 \\[5pt] 0 & \text{otherwise} \end{cases}$$

This is the reproducing code:

Block[{z, yc, ypr},
Rest@NestList[(Piecewise[{{Expectation[(#1 /. z -> yc),
Distributed[yc,
DiscreteUniformDistribution[{0, Max[ypr - 1, 0]}]],
Assumptions -> Element[ypr, Integers] && ypr >= 1],
ypr >= 1}}, # /. z -> 0] /. ypr -> z) &, z, 4] /. z -> n] //
Simplify[#, Element[n, Integers] && n >= 0] &


The rational part in the expectation appears to be $\frac{(n-1)(n+2-2^k)}{2^k n}$, thus in the large $n$ limit, expectation would agree with the continuous case. The expression involving harmonic numbers is of order $\mathcal{O}\left(\log(n)^{k-2}\right)$, and thus small compared to $n$.

With the guess-work, I was also able to find $\mathbb{E}(Y_5)$: $$\mathbb{E}(Y_5) = [n > 5 ] \left( \frac{(n-1)(n-30)}{32 n} + \frac{1}{32n} \ell_n \right)$$ where $$\ell_n = -8 H_{n-1} H_{n-1}^{(2)}+\frac{8}{3} \left(H_{n-1}\right){}^3+12 \left(H_{n-1}\right){}^2+28 H_{n-1}-12 H_{n-1}^{(2)}+\frac{16 }{3} H_{n-1}^{(3)}$$ Here is confirmation with simulations:

In[153]:=
With[{n = 17},
(28 HarmonicNumber[n-1] + 12 HarmonicNumber[n-1]^2 +
8/3 HarmonicNumber[n-1]^3 - 12 HarmonicNumber[n-1,2] -
8 HarmonicNumber[n-1] HarmonicNumber[n-1,2] +
16/3 HarmonicNumber[n-1,3] + (n-1)(n-30))/(32 n)] // N

Out[153]= 0.131232

In[157]:=
Table[Nest[RandomInteger[{0,Max[#1-1,0]}]&, 17, 5], {10^7}] // N // Mean

Out[157]= 0.13157

• great.. what if rand function returned only integers. – Fluvid Mar 5 '13 at 12:50
• Sasha: Unfortunately the range is $\{0,1,\ldots,n-1\}$ if $n\geqslant0$ and $\{0\}$ if $n=0$, which complicates things since the mean is not $\frac12(n-1)$ for every $n$ but $\frac12(n-1)^+$. – Did Mar 6 '13 at 8:19

@joriki: how would you account for non integral values of expectation for next iteration (under assumption of function being integral)? Eg, $f(3,2)$, the only non-zero chain is $3 \rightarrow 2 \rightarrow 1$, and this happens with probability $\frac{1}{3}*\frac{1}{2}=\frac{1}{6}$, hence expected value is $\frac{1}{6}$. Whereas your analysis gives value 0.

PS: is it possible to move this under comments section joriki's answer? I don't think I've enough reputation to do that myself.

EDIT
I found the same question here (same question, such small time gap O.o)
The answer by @coffeemath gives out the correct expectation; it is based on the simple recurrence relation $f(x,y)=\frac{1}{x}\sum\limits_{i=0}^{x-1} f(i,y-1)$. Both the analysis given above by Sasha and joriki, work correctly on reals; but when it comes to rand(n) being defined $\mathbb{N} \rightarrow \mathbb{N}$ both seem to neglect the fact that output is integer only (try $f(3,2)$ on their answers, expected value should be $\frac{1}{6}$)

If the random numbers are not restricted to integers but are uniformly generated on the entire interval $[0,n)$, the expected value is halved in each iteration, and thus by linearity of expectation the expected value of $f(n,k)$ is $2^{-k}n$.

If $n$ and the random numbers are restricted to integers, the expected value decreases from $a_i$ to $(a_i-1)/2$ in each iteration, so we need to shift by $1$ to obtain the recurrence $a_{i+1}+1=(a_i+1)/2$, so in this case the expected value of $f(n,k)$ is $2^{-k}(n+1)-1$.

• great. What if the values returned are all integers? – Fluvid Mar 5 '13 at 12:49
• @Fluvid: I don't understand -- that's what the second paragraph is about. – joriki Mar 5 '13 at 13:06
• @joriki : as I've pointed in my answers (that gained me right to comment anywhere :) ) that your analysis seem to "lose" the fact that output is integral only. Consider the case $f(3,2)$, your analysis will give expected value of 0, whereas it is $\frac{1}{6}$. Take another example, $f(6,3)$, where you'll give negative expectation! – Five Mar 5 '13 at 14:01