La probabilidad de ganar un juego de dados peculiar.

Question

Soy un profesor de secundaria, y los estudiantes en mi probabilidad de clase creado las siguientes divertido acertijo. Hemos sido atrapados en un par de semanas:

• Considere la posibilidad de este juego de dados que se juega con una feria de $n$caras de los dados.
• En la primera vuelta, un rollo de $n$ gana, mientras que un rollo de $1$ pierde. En cualquier otro resultado, el jugador tira de nuevo.
• En la 2ª rollo, rollo de $n$ gana, mientras que un rollo de $1$ o $2$ pierde. En cualquier otro rollo, el juego continúa.
• En rollo $k$, el jugador gana con un rollo de $n$ y pierde con un rollo de $k$ o por debajo.
• ¿Cuál es la probabilidad de ganar como $n \to \infty$ ?.

El juego debe ser ganado en no más de $n - 1$ vueltas, y para cualquier $n$, $$ \mathrm{P}\left(win\right) = {1 \over n} + \sum_{i = 2}^{n - 1}\frac{\left(n - 2\right)!}{\left(n - i - 1\right)!\, n^{i}} $$

Aquí es donde estoy atascado. No: $$ \lim_{n \to \infty}\mathrm{P}\left(win\right) = 0? $$ o $\mathrm{P}\left(win\right)$ convergen en algún otro distinto de cero la probabilidad como $n \to \infty$?. Cómo puede uno demostrar esto ?.

Answer 1

No puedo probar que $P(win) \approx {1 \over \sqrt{n}}$, pero aquí es una prueba de que:

Reclamo: $P(win) \le {2 \over \sqrt{n}}$

lo que por supuesto implica la $P(win) \to 0$, respondiendo al OP pregunta.

Prueba: Por comodidad, vamos a $G =$ el OP del juego original. Considere algunos de los grandes, fijos $n$. Definir:

• evento de $A =$ ganar $G$ o antes de $\sqrt{n}$ vueltas

• evento de $B =$ ganar $G$ después $\sqrt{n}$ vueltas

Vamos por separado vinculado $P(A), P(B)$ ambos $\le {1 \over \sqrt{n}}$. El principal reclamo que sigue a continuación, debido a que $P(win) = P(A)+P(B)$.

Lema: $P(A) \le {1\over \sqrt{n}}$: Imagina un juego modificado $G'$ donde el morir es siempre laminado para todos los $n$ rondas, y el resultado del juego es el primero de ganar o perder rollo. Este juego modificado $G'$ es claramente equivalente a la OP versión truncada $G$.

Vamos variable aleatoria $X=$ no. de rollos de ganancia entre el inicial $\sqrt{n}$ rondas de $G'$. Para ganar en o antes de $\sqrt{n}$ rondas, es necesario (aunque no suficiente) $X\ge 1$, es decir, $P(A) \le P(X\ge 1)$. Mientras tanto, para cualquier entero no negativo r.v.s, tenemos:

$$P(X\ge 1) = \sum_{k=1}^\infty P(X=k) \le \sum_{k=1}^\infty kP(X=k) = E[X]$$

En este caso, por la linealidad, $E[X] = {1\over n} \sqrt{n} = {1 \over \sqrt{n}}.$ Combinar, tenemos:

$$P(A) \le P(X\ge 1) \le E[X] = {1 \over \sqrt{n}} \;\;\; \square$$

Lema: $P(B) \le {1 \over \sqrt{n}}$: en Primer lugar, definir:

• evento de $E= $ juego $G$ no es concluyente (ni ganado ni perdido) después de $\sqrt{n}$ rondas

Tenga en cuenta que evento $B$ requiere evento $E$, es decir, $P(B) = P(B \cap E) = P(E) P(B \mid E)$.

Ahora imaginemos a dos diferentes juegos modificados. En $G_1$, el juego comienza con $1$ a $\sqrt{n}$ como la pérdida de los números y agrega uno más a perder el número de cada ronda. Por construcción, $P(\text{win }G_1) = P(B \mid E)$.

En $G_2$, el juego comienza con $1$ a $\sqrt{n}$ como la pérdida de los números y el conjunto de perder los números no cambia para el resto del juego. Claramente, $G_2$ es más fácil ganar que $G_1$ (por ejemplo, a través de un muestreo punto de muestreo punto de dominancia argumento).

El juego modificado $G_2$ no se limita a $n$ rondas, pero no terminar con una probabilidad de $1$. Por lo tanto, la relación:

$${P(\text{win }G_2) \over P(\text{lose }G_2)} = {P(\text{win }G_2 \mid G_2 \text{ terminates}) \over P(\text{lose }G_2 \mid G_2 \text{ terminates})} = {\text{no. of winning rolls} \over \text{no. of losing rolls}} = {1 \over \sqrt{n}}$$

La más sencilla prueba de lo anterior es considerar $G_2$ como $3$-estado de la cadena de Markov con $2$ de absorción de los estados, para ganar y perder. Alternativamente se puede considerar que exista $1+\sqrt{n}$ estados de finalización, por simetría, todos igualmente probables, y luego de color exactamente $1$ de ellos como "ganar" y otros como "perder".

La combinación de todo, tenemos:

$$P(B) = P(E) P(B \mid E) \le P(B \mid E) = P(\text{win }G_1) \le P(\text{win }G_2) = {1 \over 1 + \sqrt{n}} < {1 \over \sqrt{n}} \;\;\; \square$$

Answer 2

Esto no es una respuesta completa, pero se sugiere @Henry es aproximadamente correcto con la $P(win) \approx \frac{1}{\sqrt{n}}$.

Si $p(n, k)$ es la probabilidad de ganar al $k$ es el más grande "perder" valor

$$p(n,k) = \frac{1}{n} + \left(1 - \frac{k+1}{n}\right)p(n, k+1)$$

El uso de este fácil de recurrencia es sencillo para calcular muchos de los valores. He trazado los primeros 1000 valores de $p(n,1)$ a lo largo de con $\frac{1}{\sqrt{n}}$. Siguen muy de cerca (aunque no idéntica):

Usando python, me golpeó max profundidad de la recursión en torno a $n=2750$. En ese momento $p(2750,1)=0.02342415256724741$ e $\frac{1}{\sqrt{2750}}\approx 0.019069251784911846$.