¿Lo que ' s la probabilidad de obtener 1000 cabezas en una fila?

Question

Estoy leyendo El Maestro Algoritmo de Pedro Domingos y estoy teniendo un tiempo difícil la comprensión de algo que él escribió en la página 74:

"Si usted hace un millón de pistas de mil coin flips, es prácticamente seguro que al menos una carrera de venir todos los jefes."

Mi intuición me dice que esto es falso. Mi comprensión de la probabilidad indicaría que la probabilidad de encontrar $1000$ cabezas en una fila después de intentar $1000000$ veces es:

$$\frac{1}{2^{1000}} *1000000$$

que es minúsculo y casi "prácticamente seguro". Es mi entendimiento correcto, o me estoy perdiendo algo?

Answer 1

Sí, el autor es incorrecta. La probabilidad de que al menos uno es todas las cabezas %#% $ de #% sin embargo, $$ 1-(1-2^{-1000})^{10^6} $ es muy grande. De hecho, tenemos desde $2^{1000}$ $2^{10}=1024>1000=10^3$, que % de desigualdad de Bernoulli $2^{1000}>10^{300}$$ y así $$ (1-2^{-1000})^{10^6}\geq 1-\frac{10^6}{2^{1000}}>1-\frac{10^{6}}{10^{300}}$ $

Answer 2

Para otra perspectiva en por qué estimación heurística de OP es tan acertada:

El número de éxitos en los ensayos de #% de #% % donde la probabilidad de un éxito es $n = 10^6$ está bien aproximado por una distribución de Poisson con parámetro $p = \frac{1}{2^{1000}}$ $

En una distribución de Poisson la probabilidad de que no hay ocurrencia de al menos 1 es $$\lambda = np = \frac{10^6}{2^{1000}}.$. Pero $1 - e^{-\lambda}$$$1 - e^{-\lambda} \approx \lambda$\lambda \approx 0$ for $\lambda = \frac{10^6}{2^{1000}}$.

Answer 3

Las posibilidades que mover de un tirón 1000 monedas le da a todos los jefes está dado por $\frac{1}{2^{1000}}$ como se predijo. Sin embargo, las probabilidades de que esto suceda, dado que lo intente $1000000$ veces es: $$1 - \left(1 - \frac{1}{2^{1000}}\right)^{1000000}$$ La certeza de que, no estoy muy seguro acerca de. Mi calculadora parece que no puede manejar.

EDIT: Parece que la probabilidad es todavía insignificante. El autor se equivoca en esta cuenta. Sin embargo, el punto es que la adición de más ensayos provoca un crecimiento exponencial de probabilidad, haciendo imposible que las cosas sucedan si estás dispuesto a correr pruebas suficientes.

Answer 4

Esto es absolutamente falso. Como otros señalan, la probabilidad de que esto ocurra es $1-(1-2^{-1000})^{10^6}$ que es pequeño. El autor es el equivocado, o el OP incomprendido.
Para algunos el sentido de la escala, les presento la siguiente matemáticas:

$$ \begin{align} (1-2^{-1000})^{10^6} &= (1-n)^a \\&=\exp[a\log (1-n)] \\&\approx\exp\left[a\left(-n-\frac{n^2}{2}+O(n^3)\right)\right] \\&= \exp\left[-an-\frac{an^2}{2}+O(n^3)\right] \\&\approx 1-an-\frac{an^2}{2}+O(n^3)+\frac{1}{2}\left(-an-\frac{an^2}{2}+O(n^3)\right)^2+O(n^3) \\&= 1-an\left[1+\frac{n}{2}(1+a)\right]+O(n^3) \end{align}$$ En consecuencia, tenemos que $$\begin{align} 1-(1-2^{-1000})^{10^6} &\approx 10^62^{-1000}\left[1+2^{-1001}(1+10^6)\right] \\&= 10^62^{-1000}\left[1+2^{-1001}10^6+2^{-1001}\right] \\&= 10^6 2^{-1000}+ 2^{-2001}(10^{12}+10^6) \end{align}$$ Claramente este segundo término es mucho más pequeño que el primer término (curiosamente, si nos la quita, recuperamos el OP estimación!) El error es $O(n^3)$, por lo que esta aproximación debe ser muy buena!

Answer 5

El número calculado es el número esperado de éxitos: $$ 10 ^ 6\cdot2 ^ {-1000} \lt10^ {-295} $$ la probabilidad de éxito al menos una es $$ 1 \left(1-2^{-1000}\right) ^ {10 ^ 6} $ que, por el teorema del binomio, es un poco menos: $$ 10^6\cdot2^{-1000}-\binom{10^6}2\cdot2^{-2000}+\binom{10^6}3\cdot2^{-3000}-\cdots $$ donde $\binom{10^6}2\cdot2^{-200}\lt10^{-590}$ y $\binom{10^6}3\cdot2^{-300}\lt10^{-885}$. Así, el número esperado y la probabilidad son menos de $10^{-295}$.