Si se lanza una moneda 150 veces, ¿cuál es la probabilidad de que volvería a la tierra colas de 7 veces en una fila? Cómo alrededor de 6 veces en una fila? Hay algunos forumula que puede calcular esta probabilidad?
Respuestas
¿Demasiados anuncios?
Matt Dawdy
Puntos
5479
Aquí están algunos detalles; yo sólo funcionarán el caso en el que desea $7$ colas en una fila, y el caso general es similar. Interpreto tu pregunta a decir "¿cuál es la probabilidad de que, al menos una vez, voltear al menos 7 colas en una fila?"
Deje de $a_n$ denotar el número de maneras para voltear $n$ monedas de que en ningún punto de hacer voltear a más de $6$ consecutivos colas. A continuación, el número que desea calcular es de $1 - \frac{a_{150}}{2^{150}}$. Los últimos moneda gira en una secuencia de $n$ coin flips debe ser uno de $H, HT, HTT, HTTT, HTTTT, HTTTTT$, o $HTTTTTT$. Después de la eliminación de este último, lo que queda es otra secuencia de tiradas de la moneda, con no más de $6$ consecutivos colas. Por lo que se deduce que
$$a_{n+7} = a_{n+6} + a_{n+5} + a_{n+4} + a_{n+3} + a_{n+2} + a_{n+1} + a_n$$
con las condiciones iniciales de $a_k = 2^k, 0 \le k \le 6$. El uso de un equipo que no ha de ser muy duro para calcular $a_{150}$ a partir de aquí, especialmente si usted utiliza el método de la matriz que David Speyer sugiere.
En cualquier caso, vamos a ver lo que podemos decir aproximadamente. El crecimiento asintótico de $a_n$ es controlado por el mayor positivo de la raíz del polinomio característico $x^7 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$, que es un poco menos de $2 dólares. Reorganización de esta identidad le da $2 - x = \frac{1}{x^7}$, por lo que en una primera aproximación el más grande de la raíz es de $r \aprox 2 - \frac{1}{128}$. Esto significa que $a_n$ es de aproximadamente $\lambda \left( 2 - \frac{1}{128} \right)^n$ constantes $\lambda$, lo que significa que $\frac{a_{150}}{2^{150}}$ es aproximadamente
$$\lambda \left( 1 - \frac{1}{256} \right)^{150} \approx \lambda e^{ - \frac{150}{256} } \approx 0.56 \lambda$$
aunque $\lambda$ todavía necesita ser determinado.
Edit: Así que vamos aproximado de $\lambda$. Yo afirmación de que la generación de la función de $a_n$ es
$$A(x) = 1 + \sum_{n \ge 1} a_{n-1} x^n = \frac{1}{1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7}.$$
Esto es porque, al recorrer el argumento en el segundo párrafo, podemos descomponer cualquier secuencia válida de tiradas de la moneda en una secuencia de uno de los siete bloques de $H, HT, ...$ excepcionalmente, excepto que el segmento inicial no necesariamente comienza con $H$. Para simplificar la expresión anterior, escribir $A(x) = \frac{1 - x}{1 - 2x + x^8}$. Ahora, la fracción parcial de la descomposición de $A(x)$ tiene la forma
$$A(x) = \frac{\lambda}{r(1 - rx)} + \text{otros}$$
donde $\lambda, r$ son como anteriormente, y es el primer término que determina el comportamiento asintótico de $a_n$ como el anterior. Para calcular $\lambda$ podemos utilizar la regla de l'Hospital; nos encontramos con que $\lambda$ es igual a
$$\lim_{x \to \frac{1}{r}} \frac{r(1 - rx)(1 - x)}{1 - 2x + x^8} = \lim_{x \to \frac{1}{r}} \frac{-r(r+1) + 2r^2x}{-2 + 8x^7} = \frac{r^2-r}{2 - \frac{8}{r^7}} \approx 1.$$
Así que mi oficial estimar el valor real de la respuesta es de $1 - 0.56 = 0.44$. Cualquiera cuidado para validar?
Secuencias como $a_n$ contar el número de palabras en objetos llamados regulares de idiomas, cuya enumerativa de comportamiento es descrito por lineal recurrencias y que también pueden ser analizados utilizando máquinas de estado finito. Esas son todas las buenas palabras clave para buscar si usted está interesado en la generalización de este método. Me discutir algunas de estas cuestiones en mis notas en la generación de funciones, pero usted puede encontrar una introducción más completa en la sección correspondiente de Stanley Combinatoria Enumerativa.
Chris Benard
Puntos
1430
Voy a esbozar una solución; los detalles están a la izquierda.
Como se le da la vuelta a la moneda, pensar acerca de lo que los datos que desea guardar la pista de a ver si $7$ jefes han llegado todavía. Te gustaría saber: Si usted ya ha ganado y lo que el número de caras en la final de la secuencia actual era. En otras palabras, hay $8 dólares de los estados:
$$: No Hemos volteado $7$ cabezas en una fila sin embargo, y el último cambio fue de $T$.
$B$: no Hemos volteado $7$ cabezas en una fila sin embargo, y los dos últimos lanzamientos fue de $TH$.
$C$: no Hemos volteado $7$ cabezas en una fila sin embargo, y los tres últimos lanzamientos fueron de $THH$.
$\ldots$
$G$: no Hemos volteado $7$ cabezas en una fila sin embargo, y en los últimos siete lanzamientos fueron de $THHHHHH$.
$H$: Hemos volteado $7$ cabezas en una fila!
Si estamos en estado de $A$, entonces, con probabilidad de $1/2$ pasamos al estado $B$ y con una probabilidad de $1/2$, nos quedamos en estado de $A$. Si estamos en el estado $B$, con una probabilidad de $1/2$ pasamos al estado $C$ y con una probabilidad de $1/2$ nos desplazamos de nuevo a estado $A$. $\ldots$ Si estamos en estado de $G$, con una probabilidad de $1/2$ avanzamos a estado $H$ y con una probabilidad de $1/2$ nos desplazamos de nuevo a estado $A$. Una vez que estamos en estado de $H$ nos quedamos allí.
En resumen, definir $M$ a ser la matriz de $$\begin{pmatrix} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 1 \end{pmatrix}$$
A continuación, las entradas de $M^n$ dar la probabilidad de transición de un estado a otro en $n$ coin flips. (Por favor, por favor, por favor, no se vaya hasta que usted entiende por qué esto funciona! Este es uno de los estándar de la mayoría de los usos de la multiplicación de la matriz.) Usted está interesado en la parte inferior izquierda de la entrada de $M^{150}$.
Por supuesto, un sistema de álgebra computacional puede calcular este número para que usted muy rápidamente. En lugar de hacer esto, voy a hablar de algunos cálculos interesantes que sale de esto.
(1) El Perron-Frobenius teorema nos dice que $1$ es un autovalor de $M$ (con el correspondiente autovector $(0,0,0,0,0,0,0,1)^T$, en este caso) y todos los demás valores propios son menos de $1$. Deje que $\lambda$ ser el mayor autovalor de menos de $1$, entonces la probabilidad de obtener $7$ cabezas en una fila, cuando nos flip $$ n veces, es de aproximadamente $1-c \lambda^n$ constantes $c$.
(2) Usted podría preguntarse qué tipo de configuraciones de tiradas de la moneda puede ser contestada por este método. Por ejemplo, podríamos entender el caso en el que el flip $3$ cabezas en una fila antes de voltear $2$ colas en una fila? (Respuesta: Sí.) Podríamos entender la cuestión de si la primera de $2k$ volteretas son un palíndromo $k$? (Respuesta: No, no por este método). En general, la cuestión es que las propiedades puede ser reconocido por el autómata de estado finito, también llamado el regular idiomas. Hay un montón de estudio de este tema.
(3) Véase el capítulo de $8.4$ de Concreto de las Matemáticas, por Graham, Knuth y Patashnik, para que muchos más la moneda flipping problemas.
palehorse
Puntos
8268
Con respecto a la respuesta exacta, la recursividad es la relativa a la de Fibonacci de n-Números de Paso (mira la frase debajo de la tabla).
Con respecto a un aproximado de/asympotic solución: también puede ser obtenido por el razonamiento probabilístico.
En lugar de tirar N (150), monedas, vamos a considerar el (pensamiento) experimento de tirar M alternativos se ejecuta (un 'run' es una secuencia de consecutivos colas/cabezas). Que es, en lugar de tirar N iid variables aleatorias de Bernoulli (dos valores con prob=1/2), tiramos M iid geométricas variables aleatorias ( p(1)=1/2 p(2)=1/4 p(3)=1/8 ...) que podemos interpretar como la longitud de cada una de las alternativas de ejecución de consecutivos colas/cabeza en las monedas de la secuencia.
El valor esperado de las pistas (en ambos experimentos) es de 2. Si elegimos M=N/2, el esperado número total de monedas (en la segunda experimento) será N, y por lo que podemos esperar (de manera informal) que los dos experimentos son asympotically equivalente (en el experimento original el número de monedas es fijo, el número de carreras es una variable aleatoria; en el segundo, a la inversa; esto podría estar relacionado con el uso de diferentes conjuntos de la física estadística).
Ahora, en la versión modificada de experimento es fácil calcular la probabilidad de que la ejecución no supera una longitud L: es sólo $(1-1/2^{L})^{N/2}$ Si consideramos sólo las colas, el número de "pruebas" sería N/4 en su lugar. Esto, en nuestro caso, (L=150, N=6) da P=0.44160
Ved
Puntos
238
La probabilidad de que NO se ejecute en $n$ volteretas es el coeficiente de $x^n$ de la polynom serie de $$G := (p,r,x) \a \frac{1-p^r^r} {1-x+(1-p)*(p^r)*x^{i+1}}$$ Por $p=0.5$, $r=7$, el coeficiente de $x^{150}$ es $0.558041257197$.
La probabilidad de que Una carrera o más es de $0.441958742803$ (44.19%).
Yuriy Nemtsov
Puntos
111
He aquí una manera de obtener una aproximación de la respuesta a través de una simulación. Es un poco divertido para ajustar los números y ver la probabilidad de cambio.
Ejecutar esto en Tools -> Javascript Console en Chrome o Tools -> Web Developer -> Web Console en FireFox:
function experiment(streak, tosses) {
var i, ctr = 0;
for (i = 0; i < tosses; i++) {
if (Math.random() < 0.5) ctr = 0;
else if (++ctr === streak) return 1;
}
return 0;
}
function run(streak, tosses, runs) {
var i, total = 0;
for (i = 0; i < runs; i++) {
total += experiment(streak, tosses);
}
return total / runs;
}
console.log('\nP(A) = %s\n',
run(7, 150, 1e6));
Me da el siguiente resultado:
P(A) = 0.441693
Que está cerca de las otras respuestas aquí.
