Valor esperado de una función decreciente al Azar

Question

Se nos pide encontrar el valor esperado de la siguiente función

RDF(N, K)

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

Random(N) devuelve un número entero en el rango de $[0, N)$, con igual probabilidad y Random(0) = 0.

Vamos a tener un caso-

N = 4 y K = 3

Nuestra función de los valores de retorno

4 → 0 → 0 con probabilidad 1/4.

4 → 1 → 0 con probabilidad 1/4.

4 → 2 → 0 con probabilidad de 1/8.

4 → 2 → 1 con probabilidad de 1/8.

4 → 3 → 0 con una probabilidad de 1/12.

4 → 3 → 1 con una probabilidad de 1/12.

4 → 3 → 2 con una probabilidad de 1/12.

Por lo tanto el valor esperado es

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

Si el resultado de azar($N$) eran de $[0,N]$ en lugar de $[0,N)$, las cosas serían más fáciles y la respuesta sería la $\frac n{2^k}$ : Si $k=0$, $n$ es devuelto de inmediato. De lo contrario, el resultado esperado es $$\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}$$ por inducción.