6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ great.. what if rand function returned only integers. $\endgroup$ – Fluvid Mar 5 '13 at 12:50
  • $\begingroup$ 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)^+$. $\endgroup$ – Did Mar 6 '13 at 8:19
2
$\begingroup$

@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}$)

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ great. What if the values returned are all integers? $\endgroup$ – Fluvid Mar 5 '13 at 12:49
  • $\begingroup$ @Fluvid: I don't understand -- that's what the second paragraph is about. $\endgroup$ – joriki Mar 5 '13 at 13:06
  • 2
    $\begingroup$ @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! $\endgroup$ – Five Mar 5 '13 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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