Tengo una función random $f(x)$ que devuelve uno de los enteros en el rango de $[0, x-1]$, con igual probabilidad y $f(0) = 0$.
¿Cuál es el valor esperado $E(f(f(f(\ldots f(x)))$ ($n$-veces $f(x)$)? La respuesta debe ser una función de $x$$n$.
Respuestas
¿Demasiados anuncios?
Siméon
Puntos
8691
No he podido encontrar un patrón general, pero aquí están algunos de los resultados.
Escribir $E_n(x) = E(f^n(x))$.
Es fácil ver que $E_n(x) = 0$ si $x \leq n$$E_n(n+1) = \frac{1}{(n+1)!}$.
Además, si $x \geq 1$, tenemos
$$ E_1(x) = \frac{x-1}{x} + \dots + \frac{1}{x} = \frac{x-1}{2} $$
$$ E_2(x) = \frac{1}{x}\sum_{y=1}^{x-1}\frac{y-1}{2} = \frac{1}{4}\frac{(x-1)(x-2)}{x} = \frac{1}{4}\left(x-3+\frac{2}{x}\right) $$
$$ E_3(x) = \frac{1}{4x} \sum_{y=1}^{x-1}(y-3) + \frac{1}{2x}\sum_{y=1}^{x-1}\frac{1}{y} = \frac{(x-1)(x-4)}{8x} + \frac{H_{x-1}}{2x} $$
La aparición de la armónica suma $H_x$ me hace pensar que no la simplificación será posible en general.
Ty221
Puntos
143
Es de suponer que usted significa el intervalo de $[0,x-1]$.
Vamos $Z_{1}$, $Z_{2}, \ldots Z_{n}$ ser variables al azar, con una probabilidad de masa funciones $f(z)$, $f^{2}(z),\ldots f^{n}(z)$ respectivamente. A continuación,$P(Z_{n}=z)=P(Z_{n-1}=z|0\le z< x-n)$.
Por lo tanto, $$f^{n}(z)=\frac{f^{n-1}(z)}{f^{n-1}(x-n)}$$
Al $0\le z<x-n$, e $0$ lo contrario.
Did
Puntos
1
De acuerdo a una respuesta por parte de la OP en los comentarios, la pregunta es a que considere una cadena de Markov $(X_n)_{n\geqslant0}$ tal que $X_0=x$, para algunas de las $x\geqslant1$, y, para cada una de las $n\geqslant1$, condicionalmente en $X_{n-1}=y$, $X_n$ se distribuye uniformemente en $\{0,1,\ldots,y-1\}$ si $y\geqslant1$ $X_n=0$ si $y=0$. La cuestión es calcular los $\mathbb E(X_n)$ por cada $n\geqslant0$.
Un método estándar es para que tenga en cuenta que $\mathbb E(X_n\mid X_{n-1}=0)=0$ y, para cada $y\geqslant1$, $$ \mathbb E(X_n\mid X_{n-1}=y)=\frac1y\sum_{k=0}^{y-1}k=\tfrac12(y-1). $$ Para resumir, $$ 2\mathbb E(X_n)=\mathbb E(X_{n-1}-1;X_{n-1}\geqslant1)=\mathbb E(X_{n-1})-1+\mathbb P(X_{n-1}=0). $$ Por otro lado, $\mathbb P(X_n=0\mid X_{n-1}=0)=1$ y, para cada $y\geqslant1$, $$ \mathbb P(X_n=0\mid X_{n-1}=y)=\frac1y, $$ por lo tanto $$ \mathbb P(X_n=0)=\mathbb P(X_{n-1}=0)+\mathbb E(1/X_{n-1};X_{n-1}\geqslant1). $$ En este punto parece necesario calcular recursivamente $\mathbb E(1/X_{n};X_{n}\geqslant1)$ pero estoy de repente no es tan seguro que este sería el final de la carretera cualquiera, más cerca de la...
