

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

How to determine the expected value of the $f(x,y)$ defined as:

$\quad$ for i = 1 to y
$\quad$ $\quad$ do x = R(x)
$\quad$ $\quad$ return x

where $R(N)$ returns any integer in the range $[0,N)$ with equal probability and $R(0) = 0$

I have absolutely no clue on how to approach this one, any ideas?

share|cite|improve this question
Wecome to MSE. I assume R(N) = random(x)? More importantly, I don't understand your question: as you don't sum over the y trials, you will simply, at each step, return a number uniformly distributed over $[0, i)$, for $i = 1, \dots, y$ (whose (step) expectation would be $\frac{i+1}{2}$). Could you look at your source and see what is really meant? I don't believe it is exactly as you write it. Did you mean to sum the $y \in \mathbb{N}$ trials? Or ...? – gnometorule Mar 2 '13 at 18:23
@gnometorule: After the edits, I am very confident about the problem statement :) – NotSoSmart Mar 2 '13 at 18:31
Thanks for making some edits, which makes some calculations in my older comment incorrect. So in plain English you do the following: (1) start with some $x \in \mathbb{N}$; (2) draw a value $z$ from a uniformly $[0, x)$ distributed random variable, and in the next iteration draw from $[0, z)$; (3) do this $y \in \mathbb{N}$ times? If yes, then note that your algorithm does this: you return a vector $(z_1, \dots, z_y)$. Do you want to the expectation of that vector? Only the final value? Something else? – gnometorule Mar 2 '13 at 18:40
Possible duplicate: – Willie Wong Mar 8 '13 at 10:00

For $y=1$ it is the average of $0,1,...,x-1$ giving $(x-1)/2$. This is obvious but is the first case, which can be written as $$(1/x)\sum_{x_2=0}^{x-1}x_2.$$ For $y=2$ it is

$$(1/x)\sum_{x_2=1}^{x-1}(1/x_2)\sum_{x_3=1}^{x_2-1}x_3,$$ which comes to $(x-1)(x-2)/(4x).$

For even as small as $y=3$ the similar iterated sum didn't evaluate to anything nice when put into maple; the result involved the $\Psi$ function and the constant $\gamma.$ But the summation (not closed form) version for $y=3$ is obtained by stringing along one more variable: $$(1/x)\sum (1/x_2) \sum (1/x_3) \sum x_4,$$ where each sum goes from 1 to one less than the next outer variable.

Given the intricacy of maple's closed form for the $y=3$ case, I would be surprised by a closed form for the case of general $y$.

share|cite|improve this answer

Your Answer


