4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ for $i=1$, what is the value of $N$ or did you mean random$(i)$ on the second line? $\endgroup$ – jay-sun Mar 9 '13 at 22:29
  • $\begingroup$ @jay-sun $N$ is an input parameter of the function. Especially, $K=0$ leads to immediate output of $N$ itself. $\endgroup$ – Hagen von Eitzen Mar 9 '13 at 22:30
  • $\begingroup$ 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 $\endgroup$ – Ankur Mar 9 '13 at 22:34
  • $\begingroup$ 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. $\endgroup$ – cardinal Mar 9 '13 at 22:53
  • $\begingroup$ @cardinal please could you elaborate your comment as an answer. $\endgroup$ – Ankur Mar 9 '13 at 23:04
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yes thats the main problem, random(N) gives x belonging to [0,N) instead of [0,N].. $\endgroup$ – Ankur Mar 9 '13 at 23:20

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.