Valor esperado del algoritmo recursivo

Question

Sara y Macey quieren jugar al juego de Verdad o Reto. Utilizan el siguiente algoritmo recursivo para decidir quién va primero:

$\textbf{Algorithm} \hspace{2mm} GoesFirst(k):$
$// \hspace{2mm}k ≥ 1$ el dado es justo, y todas las tiradas son independientes
Shelly tira el dado, deja $s$ sea el resultado;
Macey tira el dado, deja $m$ sea el resultado;
$ \textbf{if } s > m \\ \textbf{then} \text{ Sara goes first} \\ \quad \quad return \hspace{2mm} k \\ \textbf{end if } \\ \textbf{if } s < n \\ \textbf{then} \text{ Macey goes first} \\ \quad \quad return \hspace{2mm} k \\ \textbf{end if } \\ \textbf{if } s = m \\ \textbf{then} \text{ GoesFirst(k + 1)} \\ \textbf{end if } \\ $

El algoritmo de las señoras corre $GoesFirst(1)$ es decir, con $k = 1$ . Definir la variable aleatoria $X$ para ser el valor de la salida de este algoritmo. ¿Cuál es el valor esperado $\mathbb{E}(X)$ de la variable aleatoria $X$ ?

(a) $3/2$
(b) $5/4$
(c) $5/6$
(d) $6/5 \hspace{2mm} \text{ This is the answer} $

¿Por qué es esta la respuesta? Sé que la fórmula del valor esperado es $\mathbb{E}(X) = \sum_{}^{} k \cdot Pr(X = k)$ .

En clase aprendí que el valor esperado de una distribución geométrica es $1/p$ donde $p$ es la probabilidad de éxito.

Es $5/6$ ¿es la probabilidad de éxito? (es decir. $5/6$ veces obtendremos una respuesta sobre quién irá primero).

Si es así, entonces repetimos este algoritmo hasta llegar a un éxito, que supongo que sigue la Distribución Geométrica:

$\frac{1}{5/6} = 6/5$ que es la respuesta.

Intenté hacer la suma pero me di cuenta de que no tenía sentido.

$\mathbb{E}(X) = 1 \cdot 5/6 + 2 \cdot 1/6$ ...

Creo que mi primera solución es correcta. Si alguien puede formalizar mi pensamiento sería genial.

Gracias.

Answer 1

El algoritmo devuelve el número de la primera tirada del dado en la que se obtiene un número diferente. Como dices, la probabilidad de éxito (la probabilidad de que saquen números diferentes) es $5/6.$ El número esperado de ensayos hasta el primer éxito es $1/p$ como usted sabe. La respuesta es $6/5$ .

No es "inútil" calcular la suma. Así es como el valor esperado de $1/p$ se llega en primer lugar. Sin embargo, el segundo término debe ser $$2 \cdot 1/6\cdot 5/6$$ Es $2$ veces la probabilidad de que obtengan el mismo número en la primera tirada, veces la probabilidad de que obtengan números diferentes en la segunda.

Answer 2

Hay $36$ posibles resultados de $(s,m)$ dibujos, de los cuales $6$ hacer un empate, con probabilidad $\dfrac16$ .

Entonces tenemos la recurrencia

$$p_{k+1}=\frac{p_k}6$$

porque $k$ se incrementa sólo en caso de empate, y efectivamente tenemos una ley geométrica con parámetro $1-p=\dfrac56$ . Se sabe que la expectativa es la inversa del parámetro.

---

Por cálculo de dirección, la expectativa es

$$E=\frac{1p+2p^2+3p^3+\cdots}{p+p^2+p^3+\cdots}=1+\frac{1p^2+2p^3+\cdots}{p+p^2+p^3+\cdots}=1+p\frac{1p+2p^2+\cdots}{p+p^2+p^3+\cdots}=1+pE$$ y dibujamos

$$E=\frac65.$$

Answer 3

Su salida X sigue un Distribución binomial negativa . X es el número de pruebas antes del primer éxito.

Aquí el éxito S es cuando los 2 dados sacan un número diferente. Supongamos que hemos tirado el primer dado, ¿cuál es la probabilidad de que el segundo dado dé un número diferente? La probabilidad de éxito es $p=P(B=1)=\frac 56$

Entonces repetimos este experimento hasta el éxito y X=k significa $B_1=0$ y $B_2=0$ y $\dots$ $B_k=1$ .

La expectativa de la binomial negativa es $E(X)=\frac 1p$ . Una buena explicación está disponible en Wikipedia . Una prueba formal es la siguiente:

$E(X)=E(X|B_1=0)P(B_1=0) + E(X|B_1=1)P(B_1=1) = (E(X)+1)(1-p) + p$ $E(X)=\frac 1p $