¿Cuál es la probabilidad de que una secuencia de tiradas de la moneda nunca tiene el doble de cabezas de las colas?

Question

Me dio mi amigo este problema como un rompecabezas; mientras que su intento de solución no funciona, plantea una pregunta interesante.

Me lanza una moneda repetidamente y registrar los resultados. Me detendrá tan pronto como el número de caras es igual a dos veces el número de colas (por ejemplo, voy a parar después de ver HHT o THTHHH o TTTHHHHHH). ¿Cuál es la probabilidad de que yo nunca deje?

He intentado calcular la respuesta directamente, pero los términos puso feo con bastante rapidez. Yo estoy esperando una pista hacia una mancha de la solución, pero voy a seguir intentando a la fuerza bruta de una respuesta en el ínterin.

Answer 1

Aquí hay otra solución, siguiendo a Ross de Millikan sugerencia:

Vamos a $n=H−2T$ (H=cabezas, T=colas). En cada paso, $n := n+1 $ o de la $n := n-2$ con una probabilidad de 1/2. El juego comienza con $n=0$ y se detiene cuando $n=0$.

Para cualquier iteración (después de la primera), deja que $P(n)$ ser la probabilidad de que el juego finalmente se detiene, dado el valor actual de $n$ (y dado que el evento no ha ocurrido todavía). Es claro que $P(n)$ no depende del tiempo. A continuación, la siguiente recurrencia se tiene:

$$P(n)= \frac{P(n+1)+P(n-2)}{2} \;, \;\; n\ne 0 $$

con $P(0)=1$. También sabemos (¿tenemos?) que $P(-\infty)=0$ (pero aún no sabemos de $P(+\infty)$)

La solución a esta diferencia la ecuación (me ahorraré los detalles, sólo el habitual lineal de la diferencia de la ecuación de procedimiento, en las dos regiones, con las anteriores condiciones de contorno) está dada por:

$$ P(n)= \left\{ \begin{array}{ll} \phi^{-n} & \mbox{si } n \le 0 \\ 1 + B \, [(-\phi)^n -1] & \mbox{si } n \ge 0 \end{array} \right. $$

con $ B= \phi^2 (1-\phi)$, $\phi = (\sqrt{5}-1)/2$

Ahora, después de que el primer paso que hemos de $n=1$ o $n=-2$, con igual probabilidad, entonces la probabilidad de que el juego finalmente se detiene es

$$\frac{P(1)+P(-2)}{2}=\frac{2 \phi^2 -\phi +1}{2} = 0.572949$$

El formulario de $P(n)$ es interesante:

Este, por ejemplo, muestra que la probabilidad de parada es fuertemente dependiente de la primera sacudida de moneda (menos de 40% si la cola, más de un 75% si la cabeza).

Este procedimiento también parece directamente generalizables, ya sea asimétrico monedas u otros cocientes de enteros.

Añadido: Aquí va los detalles para la solución de la recursividad:

Postulamos una solución de la forma $P(n)= r^n$ y reemplazando en la recursividad de $2 P(n) - P(n+1) - P(n-2) = 0 $ obtenemos $$2 \; r^2 - r^3 - 1 = 0 $$ La raíz $r_1=1$ viene inmediatamente, y entonces los otros: $r_2 = - \phi$, $r_3 = 1/\phi$. Entonces la solución general está dada por de $a + B (-\phi)^n + C \phi^{-n}$, $a,B,C$, en cada zona.

En la zona de $n \le 0$: tenemos $P(0)=1$ y $P(-\infty)=0$. Como $\phi \aprox 0.618 < 1$, esto implica $A=0$, $B=0$,$C=1$ por lo tanto

$$P(n) = \phi^{-n} \hspace{10px} n \le 0$$

En la zona de $n \ge 0$: tenemos $P(0)=1$, pero no sabemos de $P(\infty)$. Sabemos que está acotada, por lo que $C=0$ y $A=1-B$, por lo que

$$P(n) = 1 + B \, [(-\phi)^n -1] \hspace{10px} n \ge 0$$

Para deshacerse de los restantes grados de libertad, podemos escribir la recursividad para $n=1$, y reemplazar el valor de $P(-1)$ para la solución anterior:

$$ 2 \, P(1) = P(2) + P(-1)$$ $$ 2 \, (1 + B \, [-\phi -1]) = 1 + B \, [(-\phi)^2 -1] + \phi$$

A partir de este, se obtiene $B= \phi^2 (1-\phi)$.

Answer 2

El juego se detiene con una probabilidad de $u=\frac34(3-\sqrt5)=0.572949017$.

Ver el final del post, para la generalización de este resultado, en primer lugar para cada asimétrica cabezas o colas de juegos (Edición 1) y, a continuación, para cada relación entero (Edición 2).

---

Para probar esto, considere la posibilidad de la caminata al azar que va dos pasos a la derecha cada vez que la cola se produce y un paso a la izquierda cada vez que un jefe se produce. A continuación, el número de colas es el doble del número de cabezas cada vez que el pie está de vuelta en su punto de partida (y sólo entonces). En otras palabras, la probabilidad de que el juego nunca se detiene es de $1 por u$ donde $u=P_0(\text{hits}\ 0)$ para el paseo aleatorio con equiprobables pasos $+2$ y $-1$.

La clásica de un paso de análisis de golpear a veces para las cadenas de Markov rendimientos de $2u=v_1+w_2$ donde, por cada positivo de $k$, $v_k=P_{-k}(\text{hits}\ 0)$ y $w_k=P_{k}(\text{hits}\ 0)$. Debemos evaluar primero $w_2$ entonces $v_1$.

El $(w_k)$ parte es fácil: la única pasos a la izquierda son de $-1$ pasos de ahí llegará a $0$ desde $k\ge1$, el pie debe primero golpear $k-1$ a partir de $k$, a continuación, pulse $k-2$ desde $k-1$, y así sucesivamente. Estos $k$ eventos son equiprobables por lo tanto $w_k=(w_1)^k$. Otro paso de análisis, esta vez para la caminata a partir de $1$, los rendimientos $$ 2w_1=1+w_3=1+(w_1)^3 $$ por lo tanto $w_k=w^k$ donde $w$ resuelve $w^3-2w+1=0$. Desde $w\ne1$, $w^2+w=1$ y desde $w<1$, $w=\frac12(\sqrt5-1)$.

Consideremos el $(v_k)$ parte. La caminata aleatoria tiene una deriva a la derecha, de ahí su posición converge a $+\infty$, casi con toda seguridad. Deje que $k+R$ denotar la primera posición visitó a la derecha del punto de partida de $k$. Entonces $I\in\{1,2\}$, casi con toda seguridad, la distribución de los $R$ no dependen de $k$ porque la dinámica es invariante por traslaciones y $$ v_1=r+(1-r)w_1\quad\text{donde}\ r=P_{-1}(R=1). $$ Ahora, a partir de $0$, $R=1$ implica que el primer paso es de $-1$ por lo tanto $2r=P_{-1}(A)$ con $A=[\text{hits}\ 1 \text{antes}\ 2]$. Considerar $R'$ para la caminata aleatoria a partir de $-1$. Si $R'=2$, $A$ se produce. Si $R'=1$, el pie está de vuelta en la posición $0$ por lo tanto $$ ocurre con probabilidad $r$. En otras palabras, $2r=(1-r)+r^2$, es decir, $r^2-3r+1=0$. Desde $r<1$, $i=\frac12(3-\sqrt5)$ (por lo tanto, $r=1-w$).

Conectar estos valores de $w$ y $r$ en $v_1$ y $w_2$ se obtiene el valor de $u$.

---

Edición de 1 de Cada asimétrica de paseo aleatorio que realiza pasos elementales $+2$ con una probabilidad de p $$ y $-1$ con una probabilidad de $1-p$ es transitoria $+\infty$ mientras $p>\frac13$ (y, por supuesto, por cada $p\le\frac13$ el pie golpea $0$ con total probabilidad). En este régimen, se puede calcular la probabilidad $u(p)$ llegará a $0$. El resultado es el siguiente.

Por cada $p$ en $(0,\frac13)$, $u(p)=\frac32\left(2-p-\sqrt{p(4-3p)}\right).$

Tenga en cuenta que $u(p)\1$ cuando $p\a\frac13$ y $u(p)\to0$ cuando $p\a 1$, como era de esperar.

---

Edit 2 Volviendo a simétrica cabezas o colas de juegos, tenga en cuenta que, para cualquier fijo entero $N\ge2$, las mismas técnicas que se aplican para calcular la probabilidad de $u_N$ alcanzar $N$ veces más colas de las cabezas.

Obtiene $2u_N=E(w^{R_N-1})+w^N$ donde $w$ es la única solución en $(0,1)$ de la ecuación polinómica $2w=1+w^{1+N}$, y la variable aleatoria $R_N$ es casi seguramente en $\{1,2,\ldots,N\}$. La distribución de $R_N$ se caracteriza por su generación de función, que resuelve $$ (1-(2-r_N)s)E(s^{R_N})=r_Ns-s^{N+1}\quad\text{con}\quad r_N=P(R_N=1). $$ Esto es equivalente a un sistema de $$ N ecuaciones con incógnitas las probabilidades de $P(R_N=k)$ para $k$ en $\{1,2,\ldots,N\}$. Uno puede deducir de este sistema que $r_N$ es la única raíz $r<1$ del polinomio $(2-r)^Nr=1$. Uno puede, a continuación, tenga en cuenta que $r_N=w^N$ y que $E(w^{R_N})=\dfrac{Nr_N}{2-r_N}$ por lo tanto algunas simplificaciones rendimiento por último el siguiente resultado general.

Por cada $N\ge2$, $u_N=\frac12(N+1)r_N$ donde $r_N<1$ resuelve la ecuación $(2-r)^Nr=1$.

Answer 3

Yo sugeriría $1-\phi=1-\frac{\sqrt{5}-1}{2}$. Si definir el $P(n)$ como la probabilidad de que si tenemos un exceso de colas de $n$ eventualmente tienen el doble de los jefes como de las colas, la recurrencia es de $$P(n)=\frac{P(n+1)+P(n-2)}{2}$$ con las condiciones de contorno $$P(n)=\begin {casos}1 &n\gt 0 \\ 0 &n=-\infty \end {casos}$ De$ la recurrencia tiene solución $P(n)=\phi ^n$

Answer 4

(Actualización: La respuesta a la pregunta original es que la probabilidad de parar es $\frac{3}{4} \left(3 - \sqrt{5}\right)$. Ver al final del post para una serie infinita de expresión en el caso general.)

---

Vamos $S(n)$ denotar el número de maneras de parar después de ver $n$ colas. Ver $n$ colas significa ver $2n$ cabezas, por lo que este sería detenerse después de $3n$ volteretas. Ya hay $2^{3n}$ secuencias posibles en $3n$ volteretas, la probabilidad de parar es $\sum_{n=1}^{\infty} S(n)/8^n$.

Para determinar $S(n)$, vemos que hay $\binom{3n}{n}$ de las formas para elegir cuales $n$ de $3n$ voltea será colas. Sin embargo, este overcounts para $n > 1$, como podríamos haber visto dos veces como muchos cabezas de las colas para algunos $k < n$. De estos $\binom{3n}{n}$ secuencias, hay $S(k) \binom{3n-3k}{n-k}$ secuencias de $3n$ volteretas en el que hay $k$ colas de la primera vez que iba a ver dos veces la cantidad de cabezas de las colas, como cualquiera de los de$, S(k)$ secuencias de $3k$ voltea podría ser completado por la elección de $n-k$ de los restantes $3n-3k$ voltea a ser colas. Por lo tanto $S(n)$ satisface la recurrencia $S(n) = \binom{3n}{n} - \sum_{k=1}^{n-1} \binom{3n-3k}{n-k}S(k)$, con $S(1) = 3$.

La solución a esta recurrencia es de $S(n) = \frac{2}{3n-1} \binom{3n}{n}.$ Esto se puede verificar fácilmente, como sustituyendo esta expresión en la recurrencia de los rendimientos de una ligera variación en la Identidad 5.62 en Concreto de las Matemáticas (p. 202, 2ª ed.)., es decir, $$\sum_k \binom{tk+r}{k} \binom{tn-tk+s}{n-k} \frac{r}{tk+r} = \binom{tn+r+s}{n},$$ con $t = 3$, $r = -1$, $s=0$.

Por lo que la probabilidad de parar es $$\sum_{n=1}^{\infty} \binom{3n}{n} \frac{2}{3n-1} \frac{1}{8^n}.$$

Mathematica le da la forma cerrada para esta probabilidad de detener a ser de $$2 \left(1 - \cos\left(\frac{2}{3} \arcsin \frac{3 \sqrt{3/2}}{4}\right) \right) \aprox 0.572949.$$

Añadido: La suma es hipergeométrica y tiene una simplificación de la representación. Ver a Sasha comentarios para ¿por qué la suma de los rendimientos de esta forma cerrada de la solución y también por qué la respuesta es $$\frac{3}{4} \left(3 - \sqrt{5}\right) \aprox 0.572949.$$

---

Añadido 2

: Esta respuesta es generalizable a otras relaciones, $r$ a la serie infinita de expresión. Para el general $r \geq 2$ caso, el argumento anterior es fácilmente adaptado para producir la recurrencia $S(n) = \binom{(r+1)n}{n} - \sum_{k=1}^{n-1} \binom{(r+1)n-(r+1)k}{n-k}S(k)$, con $S(1) = r+1$. La solución a la recurrencia es de $S(n) = \frac{r}{(r+1) n - 1} \binom{(r+1) n}{n}$ y se puede comprobar fácilmente mediante el binomio de convolución de la fórmula dada anteriormente. Por lo tanto, para la relación $r$, la probabilidad de detener la tiene la serie infinita de expresión $$\sum_{n=1}^{\infty} \binom{(r+1)n}{n} \frac{r}{(r+1)n-1} \frac{1}{2^{(r+1)n}}.$$ Esto puede ser expresado como una función hipergeométrica, pero no estoy seguro de cómo simplificar más general $r$ (y tampoco Mathematica). También se puede expresar mediante la generalización de la binomial serie discutido en Concreto de las Matemáticas (p. 200, 2ª ed.)., pero no veo cómo simplificar aún más en esa dirección.

---

Añadido 3

: En caso de que a alguien le interesa, he encontrado una combinatoria prueba de la fórmula para $S(n)$. Funciona en la general, $r$ caso, también.