Función decreciente uniforme del valor esperado

Question

Se nos da una función $f(n,k)$ como

for(i=0;i < k;i++)
  n = rand(n);
return n;

rand se define como un generador de números aleatorios que genera uniformemente valores en el rango $[0,n)$ . Devuelve un valor estrictamente inferior a $n$ También $\operatorname{rand}(0)=0$ .

¿Cuál es el valor esperado de nuestra función $f(n,k)$ dado $n$ y $k$ ?

Answer 1

Voy a hacer una suposición de que rand(n) devuelve reales uniformes en el intervalo [0,n) . Desde rand(n) da la misma distribución que n*rand(1) . Así, para un determinado $n$ y $k$ la variable aleatoria producida por el algoritmo es $$ X = n \prod_{m=1}^k U_m $$ donde $U_m$ son variables aleatorias continuas uniformes independientes e idénticamente distribuidas en el intervalo unitario. Así, $$ \mathbb{E}\left(X\right) = n \prod_{m=1}^k \underbrace{\mathbb{E}(U_m)}_{=\frac{1}{2}} = n 2^{-k} $$

---

Respondiendo a la petición de la OP de considerar el caso cuando rand(n) devuelve enteros aleatorios unifrom $[0,n]$ . Dejemos que $Y_m \sim \mathcal{DU}\left([0,Y_{m-1}\right)$ sea un número entero aleatorio uniforme extraído en $m$ -ésima iteración. Supongamos que $Y_0 = n$ . Entonces buscamos encontrar $$ \mathbb{E}\left(Y_k\right) = \mathbb{E}\left( \mathbb{E}\left(Y_k \mid Y_{k-1}\right)\right) = \mathbb{E}\left(\frac{1}{2}Y_{k-1}\right) = \ldots =\frac{1}{2^k} Y_0 = \frac{n}{2^k} $$ Por tanto, la expectativa es la misma que en el caso de los uniformes continuos.

---

Ahora, asumiendo rand(n) genera enteros uniformes en $[0,n)$ , en lugar de $[0,n]$ . En ese caso $Y_k|Y_{k-1} \sim \mathcal{DU}\left( \left[0, \max(Y_{k-1}-1,0)\right]\right)$ . La obtención de una forma cerrada no es factible para un $k$ pero con la ayuda de Mathematica Pude obtener expectativas para valores bajos de $k$ : $$ \mathbb{E}\left(Y_1\right) = \begin{cases} \frac{n-1}{2} & n > 1 \\[5pt] 0 & \text{otherwise} \end{cases} $$ $$ \mathbb{E}\left(Y_2\right) = \begin{cases} \frac{(n-1)(n-2)}{4 n} & n>2 \\[5pt] 0 & \text{otherwise} \end{cases} $$ $$ \mathbb{E}\left(Y_3\right) = \begin{cases} \frac{1}{8 n} \left(4 H_{n-1}+(n-1)(n-6)\right) & n>3 \\[5pt] 0 & \text{otherwise} \end{cases} $$ $$ \mathbb{E}\left(Y_4\right) = \begin{cases} \frac{1}{16 n} \left( 4 \left(H_{n-1}\right){}^2+12 H_{n-1}-4 H_{n-1}^{(2)}+(n-1)(n-14) \right) & n>4 \\[5pt] 0 & \text{otherwise} \end{cases} $$

Este es el código de reproducción:

Block[{z, yc, ypr}, 
  Rest@NestList[(Piecewise[{{Expectation[(#1 /. z -> yc), 
            Distributed[yc, 
             DiscreteUniformDistribution[{0, Max[ypr - 1, 0]}]], 
            Assumptions -> Element[ypr, Integers] && ypr >= 1], 
           ypr >= 1}}, # /. z -> 0] /. ypr -> z) &, z, 4] /. z -> n] //
  Simplify[#, Element[n, Integers] && n >= 0] &

La parte racional en la expectativa parece ser $\frac{(n-1)(n+2-2^k)}{2^k n}$ Así, en el gran $n$ límite, la expectativa estaría de acuerdo con el caso continuo. La expresión que involucra a los números armónicos es de orden $\mathcal{O}\left(\log(n)^{k-2}\right)$ y, por lo tanto, pequeño en comparación con $n$ .

Con el trabajo de adivinación, también pude encontrar $\mathbb{E}(Y_5)$ : $$ \mathbb{E}(Y_5) = [n > 5 ] \left( \frac{(n-1)(n-30)}{32 n} + \frac{1}{32n} \ell_n \right) $$ donde $$ \ell_n = -8 H_{n-1} H_{n-1}^{(2)}+\frac{8}{3} \left(H_{n-1}\right){}^3+12 \left(H_{n-1}\right){}^2+28 H_{n-1}-12 H_{n-1}^{(2)}+\frac{16 }{3} H_{n-1}^{(3)} $$ Aquí está la confirmación con simulaciones:

In[153]:= 
With[{n = 17},
    (28 HarmonicNumber[n-1] + 12 HarmonicNumber[n-1]^2 + 
     8/3 HarmonicNumber[n-1]^3 - 12 HarmonicNumber[n-1,2] - 
     8 HarmonicNumber[n-1] HarmonicNumber[n-1,2] + 
     16/3 HarmonicNumber[n-1,3] + (n-1)(n-30))/(32 n)] // N

Out[153]= 0.131232

In[157]:= 
Table[Nest[RandomInteger[{0,Max[#1-1,0]}]&, 17, 5], {10^7}] // N // Mean

Out[157]= 0.13157

Answer 2

@joriki: ¿cómo se explica la existencia de valores no integrales de la expectativa para la siguiente iteración (bajo el supuesto de que la función es integral)? Ej, $f(3,2)$ la única cadena no nula es $3 \rightarrow 2 \rightarrow 1$ y esto ocurre con probabilidad $\frac{1}{3}*\frac{1}{2}=\frac{1}{6}$ por lo que el valor esperado es $\frac{1}{6}$ . Mientras que su análisis da el valor 0.

PD: ¿es posible mover esto en la sección de comentarios la respuesta de joriki? No creo que tenga suficiente reputación para hacerlo yo mismo.

EDITAR
He encontrado la misma pregunta aquí (la misma pregunta, con tan poco tiempo de diferencia O.o)
La respuesta de @coffeemath da la expectativa correcta; se basa en la simple relación de recurrencia $f(x,y)=\frac{1}{x}\sum\limits_{i=0}^{x-1} f(i,y-1)$ . Ambos análisis dados anteriormente por Sasha y joriki, funcionan correctamente en los reales; pero cuando se trata de definir rand(n) $\mathbb{N} \rightarrow \mathbb{N}$ ambos parecen descuidar el hecho de que la salida es sólo de números enteros (pruebe $f(3,2)$ en sus respuestas, el valor esperado debería ser $\frac{1}{6}$ )

Answer 3

Si los números aleatorios no se limitan a los enteros, sino que se generan uniformemente en todo el intervalo $[0,n)$ el valor esperado se reduce a la mitad en cada iteración, por lo que, por linealidad de la expectativa, el valor esperado de $f(n,k)$ es $2^{-k}n$ .

Si $n$ y los números aleatorios se restringen a enteros, el valor esperado disminuye de $a_i$ a $(a_i-1)/2$ en cada iteración, por lo que tenemos que desplazarnos por $1$ para obtener la recurrencia $a_{i+1}+1=(a_i+1)/2$ por lo que en este caso el valor esperado de $f(n,k)$ es $2^{-k}(n+1)-1$ .