¿Explicación del experimento numérico que se aproxima a e?

Question

Recientemente he encontrado este post en Reddit. Se describe el algoritmo siguiente para buscar el correo:

Aquí es un ejemplo de e inflexión de forma inesperada. Seleccione un número aleatorio entre 0 y 1. Ahora seleccione otro y agregar a la primera. Seguir haciendo esto, acumulando números aleatorios. ¿ muchos números aleatorios, en promedio, hacer usted necesita para hacer el total de una mayor de 1? La respuesta es la e.

Esto significa que usted necesita en promedio ~2.7 aleatoria de los números reales para realizar la suma mayor que 1.

Sin embargo, un número aleatorio entre 0 y 1, en promedio, es igual a 0,5. Así que intuitivamente me gustaría pensar que, en promedio, sólo 2 números aleatorios sería necesario para tener una cantidad > 1.

Así que, ¿dónde puedo ir mal en mi forma de pensar?

Actualización

Simplemente me imaginé a mí mismo: necesita al menos dos números para tener una cantidad > 1, pero a menudo necesitará tres, a veces usted necesitará cuatro, a veces cinco, etc... Así que es natural que el promedio requerido números está por encima de 2.

Gracias por las respuestas!

Answer 1

Las otras respuestas deben tener resuelto por lo que el número es >2, pero por la razón exacta de por qué es el correo:

Para tener N aleatoria de números cuya suma es <1, la probabilidad es exactamente el mismo que el volumen de una unidad estándar de N-simplex, es decir, 1/N!.

Por lo tanto, la probabilidad de que se tarda exactamente N números aleatorios para una suma de ≥1, la probabilidad es

$$ \frac1{(N-1)!} - \frac1{N!} = \frac1{N(N-2)!} $$

Por lo tanto, el número esperado es

$$ \sum_{N=1}^\infty \frac N{N(N-2)!} = e $$

Answer 2

"Cuántos..., en promedio,..." significa que el número esperado de números al azar. Es decir, la suma de cada número posible de números aleatorios multiplicados por su probabilidad. Como dice la respuesta de Qiaochu Yuan, es imposible ser mayor que 1 en el primer intento, por lo que el número esperado es $$2\cdot P(\mathrm{it\ takes\ exactly\ 2\ numbers})+3\cdot P(\mathrm{it\ takes\ exactly\ 3\ numbers})$$ $% $ $+\;4\cdot P(\mathrm{it\ takes\ exactly\ 4\ numbers})+\cdots$ya que cada una de esas probabilidades es distinto de cero, pero la suma de las probabilidades es 1, el número esperado debe ser estrictamente mayor que 2.

Answer 3

Creo que la respuesta se relaciona con esto:

$e = \sum_{n = 0}^\infty \frac{1}{n!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots$

En que, eligiendo números al azar, estamos aproximando una muestra de eso serie.

Para su diversión, aquí está un pequeño programa en Python que hace un cálculo de la fuerza bruta:

#!/usr/bin/env python
import random
iterations = 100000000
count = 0.0
for i in range(iterations):
    sum = 0
    while sum < 1:
            sum += random.random()
            count += 1
print count / iterations

Answer 4

Nunca es posible obtener mayor que 1 en el primer intento, por lo que la media debe ser estrictamente mayor que 2.

Answer 5

Lo siento, no puedo explicar bien. Es obvio que se necesitan al menos dos números al azar para ir mayor que 1. Y si los números aleatorios son, en promedio, .5 necesitará (editar) en promedio (/editar) un máximo de tres números. Así que terminamos en el intervalo [2..3], pero eso es lo más cerca que puedo llegar a el correo.

Mientras que el método seguro de que se ve curioso, debe ser sobre la forma menos eficaz que nunca para calcular e dígitos. Una rápida y sucia programa de prueba escribí sólo dio 4 correcto de cifras significativas después de un mil millones de iteraciones. O tal vez Delphi PRNG no es perfecto.