valor de retorno esperado de una función recursiva probabilístico

Question

En esta pregunta se pide en Stackoverflow, el autor de la pregunta da un Java función similar a este:

public int f(){
    if(Math.random() >= 0.5){
        return 1;
    }
    else{
        return 1 + Math.max(f(), f());
    }
}

En matemáticas-habla, que se habrían de escribir algo como esto:

$$f = \left\{ \begin{array}{ll} 50\%\ chance : & 1 \\ 50\%\ chance : & 1 + max(f, f) \end{array} \right.$$

So basically, $f()$ is a probabilistic function that calls itself twice with 50% probability, and returns the maximum depth of its calls.

---

If you draw the call-tree and label the first case "tails" and the second case "heads," you can see that the question "What is the probability that this function eventually returns" is the same as the question "What is the probability of eventually getting more heads than tails.". Thus, this function terminates with probability 1. This also allows you to calculate the expected number of total times that $f()$ is called.

---

However, the one question I haven't been able to answer is, what is the expected return value of $f()$?

My first thought was that the expected value $E_f$ debe ser $$E_f = 0.5 * 1 + 0.5 * (1 + max(E_f, E_f))$$ Sin embargo, es claramente errónea; lo que significa que, no importa cuántas llamadas de $f()$ hace a sí mismo en el segundo caso, $E_f = 2$ !

Así que, ¿alguien sabe cómo calcular el retorno esperado valor de $f()$?

Answer 1

El resultado del procedimiento es aleatorio entero positivo $X$ tal que $$ X=1+B\cdot\max(X_1,X_2), $$ donde $X_1$ $X_2$ dos copias independientes de $X$ $B$ es una variable aleatoria de Bernoulli con $P[B=1]=P[B=0]=\frac12$.

Para describir la distribución de $X$, vamos a $R_n=P[X\geqslant n]$ para cada entero positivo $n$. El estocástico identidad anterior se traduce en $$ P[X\geqslant n+1]=P[B=1]\cdot P[X_1,\geqslant n\ \text{o}\ X_2\geqslant n], $$ es decir, $$ R_{n+1}=R_n-\tfrac12R_n^2. $$ Desde $R_1=1$, esta repetición que caracteriza la distribución de $X$.

Por desgracia, la iteración de funciones cuadráticas es muy difícil. Afortunadamente, la estimación de $R_n$ es bastante sencillo, llevando a $R_n\sim\frac2n$. Por lo tanto, el "retorno esperado valor" $E[X]=\sum\limits_{n\geqslant1}R_n$ es infinito, mientras que el valor de retorno $X$ es casi sin duda finitos.