Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.