Voltear cabezas de 10 veces en una fila

Question

Si me lanza una moneda 10 veces en una fila, obviamente la probabilidad de hacer rodar cabezas y diez veces en una fila es $\left(\frac{1}{2}\right)^{10}$. Sin embargo, no estoy seguro de cómo calcular las probabilidades exactas que voy a tener en algún punto de rodar cabezas 10 veces en una fila durante una serie de n lanzamientos. He escrito un programa para calcular las probabilidades, pero se ejecuta en tiempo exponencial en n por lo que es relativamente inutilizable. Aquí están los primeros resultados:

in 10 rolls, 0.0009765625.
in 11 rolls, 0.00146484375.
in 12 rolls, 0.001953125.
in 13 rolls, 0.00244140625.
in 14 rolls, 0.0029296875.
in 15 rolls, 0.00341796875.
in 16 rolls, 0.00390625.
in 17 rolls, 0.00439453125.
in 18 rolls, 0.0048828125.
in 19 rolls, 0.00537109375.
in 20 rolls, 0.005859375.
in 21 rolls, 0.006347179412841797.
in 22 rolls, 0.006834745407104492.
in 23 rolls, 0.007322072982788086.
in 24 rolls, 0.007809162139892578.
in 25 rolls, 0.008296012878417969.
in 26 rolls, 0.008782625198364258.
in 27 rolls, 0.009268999099731445.
in 28 rolls, 0.009755134582519531.
in 29 rolls, 0.010241031646728516.
in 30 rolls, 0.010726690292358398.

El código fuente está aquí

Answer 1

Aquí está mi intento: Para denotar por $P_i$ la probabilidad de tener $10$ cabezas en una fila en $i$ lanzamientos. Por lo $P_{10}=1/2^{10}$.

Para $i=10,...,20$, se puede calcular la probabilidad recta hacia adelante diciendo: Probabilidad de que yo consiga $10$ jefes de fila y de mis jefes empezar a $1$ más probabilidad de que yo consiga $10$ cabezas en una fila y yo comienzo a las $2$ más, y así sucesivamente. Por ejemplo, para $i=16$ tenemos $1/2^{10}+6/2^{11}=0.390625$ precisamente lo que tenemos.

Al $i>20$, entonces la cuenta se vuelve un poco más complicado, pero creo que es factible el uso de la recursividad. Tenga en cuenta que $P_{i+1}=P_i+$de Probabilidad de que mi $10$ cabezas en una fila de inicio en $i-9$ (déjame denotar esta probabilidad $Q_i$). Así que ya sabes que $P_i$ es para el primer par de casos, tenga en cuenta que el $Q_i$ $i\leq 20$ es sólo $1/2^{11}$ porque necesitamos una $T$ ir en el $i-10$ posición y seguido por $10$ cabezas, sin embargo, que no trabaja para decir $i=21$ porque queremos más, queremos que la $11$th posición para ser un $T$, el siguiente 10 $H$s, y la previouse que no sea una cadena de $10$ cabezas, porque estamos contando las cadenas cuyo punto de partida es en $12$. Por lo tanto, $Q_{21}=(1/2^{11})(1-P_{10})$. Por lo tanto, $P_{21}=P_{20}+Q_{21}$ a exactamente lo que usted tiene.

Para $P_{22}=P_{21}+Q_{22}$ donde $Q_{22}=(1/2^{11})(1-P_{11})$, lo acabo de comprobar y, de hecho, puedo obtener el mismo resultado.

En general, usted puede construir de forma recursiva, y el uso de $Q_i=(1/2^{11})(1-P_{i-11})$.

Un poco más claro (anteriormente estaba yo pensando que como he escrito, por lo que resultó un poco sucio): Se puede denotar $P_0,..,P_9$ todos los ser $0$, $P_{10}=1/2^{10}$, y $P_n=P_{n-1}+(1/2^{11})(1-P_{n-11})$.

Answer 2

Aquí está el próximo 20 números de la lista (sugerencia sugerencia...no-algoritmo de tiempo exponencial):

in 31 rolls, 0.0112121105194
in 32 rolls, 0.0116972925607
in 33 rolls, 0.0121822365327
in 34 rolls, 0.0126669425517
in 35 rolls, 0.0131514107343
in 36 rolls, 0.0136356411967
in 37 rolls, 0.0141196340555
in 38 rolls, 0.0146033894271
in 39 rolls, 0.0150869074278
in 40 rolls, 0.015570188174
in 41 rolls, 0.0160532317823
in 42 rolls, 0.0165360383689
in 43 rolls, 0.0170186080503
in 44 rolls, 0.0175009409426
in 45 rolls, 0.0179830371621
in 46 rolls, 0.0184648968248
in 47 rolls, 0.0189465200469
in 48 rolls, 0.0194279069443
in 49 rolls, 0.0199090576331
in 50 rolls, 0.0203899722291

Aquí está el código de Python (el de arriba es el resultado de una llamada a makelist(10,31,50)):

import numpy

def transitionmatrix(n):
    N = 2**n
    A = numpy.matrix([[0.0]*N]*N)
    A[0,0] = 1
    for i in range(1,N):
        A[(2*i)% N,i] = 0.5
        A[(2*i+1)%N,i] = 0.5
    return A

def makelist(n,a,b):
    A = transitionmatrix(n)
    N = 2**n
    v = numpy.matrix([1./N]*N).T
    B = A**(a-n)
    for i in range(a,b+1):
        p = (B*v)[0,0]
        print('in '+str(i)+' rolls, '+str(p))
        B = A*B

Answer 3

Lo que usted está pidiendo es la probabilidad de una ejecución. Esto parece ser un problema de volver a De Moirve. Wolfram tiene una exposición detallada aquí que incluye la generación de las funciones y relaciones de recurrencia. Por desgracia, la forma cerrada cálculos parecen ser difíciles de conseguir.

Answer 4

Hay constantes $c,\alpha$ tal que, para $n \ge 11$, $$P_n = 1-c\alpha^n$$ with the error less than $2^{-n}$ : $$\alpha\approx 0.999509316355050569331704619564576430927155038 \hskip{0.5in}c\approx 1.0039472560945626.$$

---

Es más fácil mirar primero en la probabilidad de $Q_k=1-P_k$ de no tener ninguna carrera de $10$ consecutivos cabezas en $k$ volteretas de un (feria) de la moneda. Así $Q_0=Q_1=\cdots Q_9=1$ , $Q_{10}=1-1/2^{10}$ y, a continuación, para $n \ge 11$ tenemos $$Q_{n}=Q_{n-1}-\frac{Q_{n-11}}{2^{11}}$$

Un enfoque estándar para este homogénea de la recurrencia de la relación es buscar en las raíces de $$X^{11}-X^{10}+\frac{1}{2^{11}}=(X-\frac12)(X^{10}-\frac{X^9}{2}-\frac{X^8}{4}-\cdots-\frac{X}{2^9}-\frac{1}{2^{10}})$$

Estos vienen a ser los tres raíces reales $-0.49515547\cdots,0.5,\alpha=0.999509316355\cdots$ junto con ocho complejos raíces con el módulo entre las $0.451$ $0.484$

A partir de este uno sabe que $$\frac{Q_{k+1}}{Q_k}\approx \alpha.$$ This is true to high accuracy (starting at $k=10$ con la exactitud mejorando rápidamente). Y de esto sabemos que no es una fórmula asintótica como en el inicio.

---

La recurrencia he utilizado es la de poner a $P_k=1-Q_k$ en la dada por Daniel. Una alternativa de recurrencia (básicamente factorizando los $(X-\frac12)$ ) es:

$Q_0=Q_1=\cdots Q_9=1$ $Q_{10}=1-1/2^{10}$ y, a continuación, para $N \ge 10$:

$$Q_{N}=\sum_{j=1}^{10}\frac{Q_{N-j}}{2^{j}}$$ Because $\frac{Q_{N-j}}{2^{j}}$ is the probability of first $j-1$ flips being heads, then flip $j$ being a tail, then $N-j$ lanzamientos más sin una carrera de 10 cabezas. El análisis es el mismo.

Answer 5

Hay un reciente (2002) el libro de Balakrishnan y Koutras, título bein "Corre y exámenes, etc ...", que estudia en detalle la distribución de probabilidad del número de pistas después de $n$ volteretas o incluso la distribución de probabilidad del número de lanzamientos necesarios para observar $n$ tal funciona.

ISBN 0-471-24892-4

Allí, usted encontrará la forma cerrada de expresión y asymptotics, así como algunos bibliografía.