# Expected Value of a Randomly decreasing function

We are asked to find the expected value of the following function

RDF(N, K)

for i = 1 to K
do N = random(N)
return N


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

Let's have a case-

N = 4 and K = 3

Our function will return values

4 → 0 → 0 with probability 1/4.

4 → 1 → 0 with probability 1/4.

4 → 2 → 0 with probability 1/8.

4 → 2 → 1 with probability 1/8.

4 → 3 → 0 with probability 1/12.

4 → 3 → 1 with probability 1/12.

4 → 3 → 2 with probability 1/12.

Hence the expected value is

0 * 1/4 + 0 * 1/4 + 0 * 1/8 + 1 * 1/8 + 0 * 1/12 + 1 * 1/12 + 2 * 1/12 = 1/8 + 1/12 + 1/6 = 3/8 = 0.375

• for $i=1$, what is the value of $N$ or did you mean random$(i)$ on the second line? – jay-sun Mar 9 '13 at 22:29
• @jay-sun $N$ is an input parameter of the function. Especially, $K=0$ leads to immediate output of $N$ itself. – Hagen von Eitzen Mar 9 '13 at 22:30
• let us take a case.. suppose N=4 and k=1.. than the returned/random values that function can produce are 0,1,2,3 i.e 4->0, 4->1, 4->2, 4->3 each with probability of 1/4 so the expected value is (0+1+2+3)/4 = 1.5 – Ankur Mar 9 '13 at 22:34
• Note that this can be viewed as a Markov chain with a diagonal state-transition matrix, an absorbing state at zero and an initial distribution of $\delta_N$. You are then interested in the $K$th iterate $\mathbf P^K$ of the probability transition matrix. – cardinal Mar 9 '13 at 22:53
• @cardinal please could you elaborate your comment as an answer. – Ankur Mar 9 '13 at 23:04

If the result of random($N$) were from $[0,N]$ instead of $[0,N)$, things would be easier and the answer would be $\frac n{2^k}$ : If $k=0$, then $n$ is returned immediately. Otherwise, the expected result is $$\mathbb E(R(n,k))=\frac1{n+1}\sum_{j=0}^n\mathbb E(R(j,k-1))=\frac1{n+1}\sum_{j=0}^n\frac{j}{2^{k-1}}=\frac1{n+1}\frac{n(n+1)}{2\cdot2^{k-1}} =\frac n{2^k}$$ by induction.