Sumas de una distribución aleatoria uniforme

Recientemente, encontré algunas páginas sobre un problema que simulé en Python hace años, pero que nunca resolví analíticamente, aunque un lector dejó una pista en los Comentarios.

Aquí empezamos echando un vistazo a lo que este autor llama “Blackjack de números aleatorioso el problema de la suma de números aleatorios uniformemente distribuidos.

Para el resto de la publicación, todos los números aleatorios de los que hablaremos están dados por un generador de números aleatorios que se basa en números reales distribuidos uniformemente en el rango [0,1), i.e. greater than or equal to zero, and less than one.  

We also consider the sum of one or more independent values from such a distribution, which forms a different distribution.

the game

On each turn of this unusual game, you draw a random number.  You receive $100 for each turn you play, including the last.  Suppose you drew 0.45, 0.35, 0.25, on the third turn you would go bust, since the sum of the numbers drawn would be 1.05 > 1.0.  The payout would be $300.

And the question is, what is your expected winnings if you play the game many times?  Is it worth it to play (accepting some risk of bad luck) if the initial buy-in requires $250?

initial thoughts

First of all, since the generator always gives a number less than 1.0, you always play at least two turns.  The expected value (mean) of the first number is 0.5.  For a continuous distribution, the mean has a technical definition, but it is always on the axis of symmetry of the distribution, which is obviously 0.5 here.

The expected value of the sum of several random numbers is the sum of their expectations.

So, for example, E[3] = 1,5. La mayoría de las veces saldremos después de dos o tres turnos, pero ocasionalmente habrá una serie extendida de números más pequeños y un aumento correspondiente en el número de turnos.

[spoiler alert, you may want to look at random number blackjack to try to work out the answer]

¿Qué número famoso sabemos que se encuentra entre dos y tres? Esto es tan trivial de simular en Python que ni siquiera publicaré un ejemplo.

En una carrera obtuve 2.718531.

Entonces parece que el resultado es igual a e. (Internet dice que agregar más rondas no ayuda a la precisión debido a las limitaciones en el generador de números aleatorios).

Encontré este problema en una forma ligeramente diferente en el excelente libro de introducción al cálculo, Cálculo hecho fácil, que fue escrito originalmente por Sylvanus P. Thompson (y disponible como descarga del Proyecto Gutenberg).

Fue añadido por Martin Gardner cuando editó la obra clásica (edición de 1998, p. 153) y es simplemente una nota sobre cómo e aparece en todas partes.

Pero el problema es al menos tan antiguo como el texto clásico de Feller Probabilidad (que no tengo, por desgracia).

problema relacionado

Tim Black resuelve un problema relacionado (aquí).

Recuerde que para un dado o dados estándar (justo), el valor esperado de un lanzamiento es la suma de cada valor por la probabilidad de que ocurra. Para un solo dado, el promedio es (1 + … 6).1/6 = 21/6 o 3.5.

Para dos dados, tenemos

1(2) + 2(3) + … + 6(7) + … + 2(11) + 1(12)

La distribución ya no es uniforme, pero sigue siendo simétrica alrededor del valor de 7, que es la media. Se observa que los valores esperados de sumar dos sorteos aleatorios de una distribución uniforme se suman, pero la distribución resultante ya no es uniforme.

Supongamos que conocemos una distribución de probabilidad para la suma de n números aleatorios, para algún valor de n, y luego calculamos la probabilidad de que la suma sea mayor o igual a 1. Entonces podemos obtener el valor esperado después de varios intentos como valor n veces la probabilidad que calculamos.

La distribución de probabilidad de la suma de dos números aleatorios del generador tiene una media de 1,0, por lo que la probabilidad de exceder 1,0 es 0,5. Ese evento tiene un peso de 2, por lo que la contribución al valor total esperado para un número de intentos es 2(0.5) = 1. Entonces, de la misma manera que hicimos con los dados, tenemos que P(2) = 0.5.

También tenemos que P(1) = 1. Ese es otro 1 para agregar al valor esperado general.

Ahora bien, ¿cuál es la distribución de probabilidad de la suma de tres números aleatorios? Eso se vuelve un poco más complicado. La dificultad es que la distribución de probabilidad cambia cuando cambia n. Eventualmente, se vuelve normal, pero ¿qué tan diferente es para n pequeños como 3, 4 o 5?

Aquí es donde nuestro analista tiene una gran idea.

Imagina que cambiamos un poco el juego. Todavía tenemos $100 como pago en cada etapa.

A partir de una secuencia de números aleatorios, a medida que se extraen los números, escribimos en otra secuencia la suma en cada etapa. Así que en el ejemplo anterior obtendríamos 0, 0,45, 0,80, y luego en el tercer sorteo la suma es 1.05. En lugar de escribir el último valor, resta 1 primero, luego escríbalo y continúe.

Observe que en este tramo tenemos un juego válido, una secuencia de valores crecientes seguidos de uno que debe ser menor que el anterior.

Los valores son

0 0,45 0,80 0,05

Los valores están en orden ascendente hasta el último, que puede ser inferior a 0,80. Esto debe ser cierto para una sola ronda del juego de acuerdo con las reglas que hemos establecido.

Ya que hay n! formas de ordenar n valores, y solo uno de esos arreglos tiene los números en orden estrictamente ascendente, la probabilidad del evento (para una distribución aleatoria uniforme) es 1/n!. En otras palabras, comenzando al principio de una secuencia de números aleatorios

la probabilidad de obtener un resultado de 1 es 1.

la probabilidad de obtener un resultado de 2 es 1/2!.

la probabilidad de obtener un resultado de 3 es 1/3!.

Multiplicando el valor de cada resultado por su probabilidad obtenemos 1 + 1 + 1/2!. El valor esperado de una serie de juegos es la suma de todas las posibilidades.

E = suma 1/n!

Esta es solo la serie infinita para e.

simulaciones

Escribí dos simulaciones para mostrar resultados relevantes para este problema. Él el primero muestra la distribución de sumas de n = 1, 2, 3 o 4 números aleatorios. Como se puede ver en la figura

incluso 3 a la vez, las sumas se parecen bastante a una distribución normal. El teorema del límite central dice que tenderán a la normalidad, y hay un montón de teorías que no entiendo que dicen que si los sorteos son de una distribución uniforme, entonces la convergencia es muy rápida.

Sentí curiosidad acerca de este juego alternativo, así que escribí una simulación que muestra que la suma de números aleatorios, cuando se calcula como se indicó anteriormente, al descartar los números enteros del resultado, parece ser uniforme al azar. (esencia aquí). Los datos originales y la serie sumada se representan en el mismo hisograma con transparencia 0,5. Los nuevos datos son aleatorios uniformes o cercanos a ellos.

No sé cuál es la explicación teórica de esto. Sin embargo, si es cierto, en lugar de hacer las sumas, podemos sacar de la distribución uniforme aleatoria y contar las series en las que todos los valores aumentan, hasta la última. Si llevamos la contabilidad correctamente, obtenemos e como el resultado.

Eso significa que el problema original tiene lo mismo que el alternativo.

análisis serio

He reelaborado lo que está en Mathworld. página como sigue:

Ahí es donde estoy hasta ahora. Hay mucho más para investigar.

La suma de dos números aleatorios de una distribución uniforme tiene una distribución que viene dada por la convolución de las distribuciones individuales. Pero entonces cada distribución para n > 2 está formada por otra convolución. En última instancia, las distribuciones tienden a la normalidad.

¡No veo cómo llegas a algo tan simple como 1 – 1/n! de eso, aunque Tim Black nos dio un camino diferente arriba, por eso escribí esta publicación.

[Update:  I’ve been dense.  The “different path” is in fact the means by which the integral is evaluated.  It is not done by writing some complex expression and then seeking the antiderivative and evaluating it.  Instead, we know that the value for the cumulative distribution function at the upper bound must be 1, and at the lower bound it must be 1/n!. ]

Hay una sugerencia de que este tipo de cosas se hace más fácilmente con funciones generadoras o características.

Probablemente lo primero y simple sería ejecutar la simulación usando números aleatorios y no molestarse con la suma, como también vimos aquí. [Update:  the result is as I suspected.  See gist.  If we simply find the length of runs in a stream of random numbers from a uniform distribution, where they are in increasing order, and then find the mean of those lengths, the result is e.]