Probabilidad de perder un juego de "Paseo aleatorio" sesgado

Question

Considera un juego en el que empiezas con 1 punto.

Entonces se lanza una moneda justa infinitas veces.

Por cada cara, ganas 2 puntos. Por cada cara, pierdes 1 punto.

¿Cuál es la probabilidad de que su puntuación nunca sea inferior a 1?

edit: Estoy buscando específicamente la respuesta con voltear infinitas veces, no la probabilidad después de $N$ se voltea como $N$ se acerca al infinito.

Answer 1

Una forma de solucionarlo es dejar que $p_n$ sea la probabilidad de que, si se empieza con $n$ puntos, eventualmente cero puntos. Observe que $p_1$ es también la probabilidad de que si se empieza con $n$ puntos, alguna vez has $n-1$ puntos.

De este modo, se puede ver que $p_n=p_1p_{n-1}$ ya que la probabilidad de llegar de $n$ a cero es igual a la probabilidad de llegar finalmente a $n-1$ entonces la probabilidad de llegar de ahí a $0$ . En particular, obtenemos que $p_n=p_1^n$ utilizando este argumento.

Entonces, observe que $p_n=\frac{p_{n+2}+p_{n-1}}{2}$ observando lo que ocurre después del primer paso. Sustituyendo en $n=1$ da $p_1=\frac{p_1^3+1}2$ da que $p_1$ tiene que ser $1$ o $\frac{-1\pm\sqrt{5}}{2}$ . Claramente $p_1$ no puede ser $\frac{-1-\sqrt{5}}2$ porque eso es negativo. Así, $p_1$ es $1$ o $\frac{-1+\sqrt{5}}2$ .

Para ver que $p_1$ es el valor menor, podemos definir $p_{n,t}$ para ser la probabilidad de llegar a cero en un máximo de $t$ pasos. Tenga en cuenta que $p_{n,t+1}=\frac{p_{n-1,t}+p_{n+2,t}}2$ y $p_{n,0}=0$ para $n>0$ . Inducción en $t$ utilizando esta fórmula muestra rápidamente que $p_{n,t}\leq \left(\frac{-1+\sqrt{5}}2\right)^n$ para todos $n$ y $t$ . Entonces, $p_n=\lim_{t\rightarrow\infty}p_{n,t}\leq \left(\frac{-1+\sqrt{5}}2\right)^n$ lo que implica $p_1=\frac{-1+\sqrt{5}}2$

Finalmente, la probabilidad que te interesa es $1-p_1$ que es igual a $\frac{3-\sqrt{5}}2$ .

Answer 2

Consideremos el problema truncado, en el que se gana una vez que se llega al menos a $M$ puntos. Esto satisface la recursión:

$$p_n=\frac{p_{n-1}+p_{n+2}}{2}$$

con las condiciones de contorno $p_0=0,p_M=p_{M+1}=1$ . La solución general de esta recursión es $c_1 r_1^n + c_2 r_2^n + c_3 r_3^n$ donde $r_1,r_2,r_3$ son las raíces de $x^3-2x+1=0$ . Se puede comprobar que uno de ellos es $1$ Después de encontrar esa, es fácil calcular las otras como $\frac{-1 \pm \sqrt{5}}{2}$ . Las condiciones de contorno implican

$$c_1+c_2+c_3=0 \\ c_1 + c_2 r_2^M + c_3 r_3^M = 1 \\ c_1 + c_2 r_2^{M+1} + c_3 r_3^{M+1} = 1.$$

Este sistema puede ser resuelto para un sistema finito $M$ y luego puede enviar $M \to \infty$ al final. Esto es un poco laborioso. Si quieres un atajo, podemos usar algunas heurísticas menores para conseguirlo. Establezca $c_3=0$ (ya que la única alternativa es tener $c_1$ y/o $c_2$ crecer sin límites). Supongamos también que $c_2$ crece más lentamente que $r_2^{-M}$ para que el $c_2$ los términos de la segunda y la tercera ecuación desaparecen.

Entonces el $M \to \infty$ ecuaciones leídas $c_3=0,c_1+c_2=0,c_1=1$ Así que $c_2=-1$ . Así, con esta heurística, la solución general a su problema es $p_n=1-\left ( \frac{\sqrt{5}-1}{2} \right )^n$ y el resultado deseado en particular es $p_1=\frac{3-\sqrt{5}}{2}$ .

Estrictamente hablando, se trata de calcular la probabilidad de que su puntuación nunca sea $0$ y va hasta el infinito. No es totalmente obvio que la puntuación tenga que llegar al infinito para poder jugar eternamente sin perder. De hecho, hay secuencias de volteos, como $HTTHTTHTT\dots$ que nunca llegan a cero y no van al infinito.

La razón por la que esto funciona es que en cualquier truncamiento finito de este tipo, el proceso termina en tiempo finito con probabilidad $1$ . (En otras palabras, estas secuencias "oscilatorias" tienen colectivamente probabilidad cero). Esto puede verse como un caso especial de un resultado general sobre las cadenas de Markov irreducibles en un espacio de estados finito con un estado absorbente: el tiempo de absorción es a.s. finito. Alternativamente, un atajo para este problema en particular es observar que, independientemente de dónde se empiece, una ejecución de al menos $M/2$ Las cabezas sucesivas te harán ganar la partida. Por lo tanto, en un juego arbitrariamente largo (truncado) en el que nunca pierdes, tienes que acabar ganando. Como quiera que se vea, la única manera de jugar para siempre sin perder es superar todos los umbrales finitos sin perder, que es lo que se ha calculado anteriormente.

Answer 3

En lugar de lanzar las monedas una a una, podemos considerar el lanzamiento de monedas en rondas. Al comienzo de la ronda 1 se tiene $1$ punto. En cada ronda, lanzas tantas monedas como puntos tenías al comienzo de esa ronda. Tenga en cuenta que esto significa que nunca podrá alcanzar $0$ puntos a mitad de una ronda, porque la duración de la ronda es lo más rápido que se puede llegar a cero. Así que el problema original es equivalente a determinar si tienes $0$ puntos al final de cualquier ronda.

Ahora bien, si tienes $k$ puntos al comienzo de una ronda, su total de puntos al final de la ronda será $k+\sum_{i=1}^kX_i$ donde el $X_i$ son independientes y toman valores $+2,-1$ con probabilidad $1/2$ cada uno. Equivalentemente, esto es $\sum_{i=1}^kY_i$ , donde $Y_i=X_i+1$ son independientes tomando valores $3,0$ con probabilidad $1/2$ cada uno. Así que esto es un Proceso de Galton-Watson con una distribución de la descendencia dada por la $Y_i$ . Un resultado estándar es que la probabilidad de extinción de dicho proceso es la raíz positiva más pequeña de $f(t)=t$ , donde $f(t)$ es la función generadora de probabilidad de la distribución de la descendencia.

Aquí $f(t)=(1+t^3)/2$ por lo que la probabilidad de extinción es la raíz positiva más pequeña de $t^3-2t+1=0$ que es $\frac{\sqrt{5}-1}{2}$ . Por lo tanto, la probabilidad de que su puntuación nunca llegue a $0$ es $1-\frac{\sqrt{5}-1}{2}=\frac{3-\sqrt{5}}{2}$ .

Answer 4

Este es un enfoque diferente. He calculado la probabilidad de perder si se lanza exactamente $h$ cabezas, para $h=0,1,2,\dots$

A001764 enumera (entre otras cosas) el "Número de trayectorias de celosía de $n$ Escalones del este y $2n$ Pasos al norte de $(0,0)$ a $(n,2n)$ y que se encuentra débilmente por debajo de la línea $y=2x.$ " Si consideramos un paso del Este como cara y un paso del Norte como cruz, esto es sólo el número de secuencias perdedoras $a_n$ con exactamente $n$ cabezas, teniendo en cuenta que lanzaremos una cola más al final.

Según A001764, $$a_n={{3n\choose n}\over 2n+1}$$ y la probabilidad de perder es $$ \sum_{n=0}^{\infty}a_n2^{-3n-1} $$

Un comentario del 17 de julio de 2108 sobre A001764 de Michael Somos dice que $$A(1/8) = -1+\sqrt5$$ donde $A(z)$ es la función generadora del $a_n$ . Es fácil ver que $A(1/8)$ es la probabilidad de perder, por lo que la probabilidad de ganar es $${3-\sqrt5\over2}$$

Alternativamente, Wolfram Alpha da este valor si se sustituye la fórmula explícita de $a_n$ en la suma.

He estado tratando de encontrar una derivación simple para la fórmula de $a_n$ basado en la elegante solución de Milo Brandt. Si la probabilidad de salir cara es $p,$ entonces el mismo argumento que dio Milo muestra que la probabilidad de perder es $$-\frac12+\frac{\sqrt{4p-3p^2}}{2p}\tag{1}$$ La serie es $$(1-p)\sum_{n=0}^{\infty}a_ny^n, \text{ where } y = p(1-p)^2$$

Hasta ahora, no he podido manipular $(1)$ en una expresión en $y$ que me permitirá calcular el $a_n.$

NOTA

He eliminado la explicación de por qué no estaba satisfecho con mi solución original, que deja algunos de los comentarios sin contexto. Mi solución original era muy parecida a la de Ian, pero mi argumento no era completo. Este punto se discute en los comentarios a la solución de Ian, tanto por Ian como por Aaron Montgomery.