¿Cómo determinar el valor esperado del$f(x,y)$?

Question

Cómo determinar el valor esperado del$f(x,y)$ definido como:

f (x, y):
$\quad$ para i = 1 a y
$\quad$$\quad$ do x = R (x)
$\quad$$\quad$ return x

donde$R(N)$ devuelve cualquier número entero en el rango$[0,N)$ con igual probabilidad y$R(0) = 0$

No tengo ni idea de cómo abordar esta, ¿alguna idea?

Answer 1

Para $y=1$ es el promedio de $0,1,...,x-1$ dar $(x-1)/2$. Esto es obvio, pero es el primer caso, el cual puede ser escrito como $$(1/x)\sum_{x_2=0}^{x-1}x_2.$$ Para $y=2$ es

$$(1/x)\sum_{x_2=1}^{x-1}(1/x_2)\sum_{x_3=1}^{x_2-1}x_3,$$ lo que viene a $(x-1)(x-2)/(4x).$

Incluso tan pequeños como $y=3$ el parecido de suma iterada no evaluar a nada bueno cuando se pone en arce; el resultado implicó la $\Psi$ función y la constante $\gamma.$ Pero la suma (no la forma cerrada de la versión para $y=3$ es obtenido por encadenar a lo largo de una variable más: $$(1/x)\sum (1/x_2) \sum (1/x_3) \sum x_4,$ $ , donde cada suma va de 1 a menos que la siguiente variable externa.

Dada la complejidad de maple forma cerrada para la $y=3$ caso, me gustaría ser sorprendido por la forma cerrada para el caso general de $y$.