Expected Value of a Randomly decreasing function

Question

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

Answer 1

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.