algorithm - sobre - Probar que un número generado aleatoriamente sea uniforme

test de futbol 2017 (8)

Me hicieron esta pregunta en una entrevista.

Dado que un generador de números aleatorios genera un número entre [0, N), la forma de probar este número es una distribución uniforme.

No estoy seguro de cómo abordar este problema, ¿alguna sugerencia?

¿Solo un número del generador, o tantos como quieras? Si solo uno, no puedes decir nada acerca de la uniformidad. Mientras 0 ≤ número <N, está bien.

Suponiendo que el entrevistador significó "[la uniformidad de] una gran cantidad de resultados", debe observar tanto la distribución resultante como los patrones en los resultados. Lo primero sería ordenar y agrupar los resultados y observar el histograma resultante. Debe ser razonablemente "plano" (por ejemplo, no una curva de Gauss) para un gran número de valores.

La segunda prueba es un poco más difícil, ya que podría obtener patrones de 2, 3 o incluso 4 o más números de longitud. Una prueba que vi, para los trillizos, es trazar los resultados en grupos de tres, en coordenadas esféricas (primero es el acimut, segundo es la altitud y el tercero es el radio). No recuerdo los detalles, pero IIRC deberías estar viendo una esfera uniformemente llena, o algo así. Probablemente haya un término formal para esta prueba, pero la conclusión es que hay una serie de pruebas para ver qué está haciendo un RNG, por lo que es difícil predecir el próximo número a partir del último número (no hay un patrón aparente) .

Comenzaría preguntando qué tan pronto querrían una respuesta, y qué tan buena sería una respuesta que obtendrían una vez que tuvieran el generador.

Sí, ejecutar un conjunto completo de pruebas estadísticas es bueno si desea ser exhaustivo. Pero eso puede llevar días o semanas. En algunas situaciones, la pregunta se puede hacer en una reunión con un grupo de personas que desean una respuesta de inmediato, y la mejor respuesta puede ser usar Google allí mismo en la reunión para ver si el generador es "lo suficientemente bueno" según otros usuarios Existe un amplio espectro de respuestas entre ''google rápido'' y ''pruebas exhaustivas''.

Puntos de bonificación por mencionar que en REALISTICAMENTE no puede probar que el generador es 100% uniforme en todas las situaciones. Los casos son:

1) No puedes mirar el código fuente. Por lo tanto, incluso si genera N números aleatorios que parezcan uniformes, no hay forma de saber que todos los números desde N + 1 en adelante son 10 (por ejemplo) sin generar más números. No importa dónde se detenga, no puede hacer ninguna reclamación sobre los números que aún no ha generado.

2) Puedes mirar el código fuente. Probablemente sea demasiado feo para entenderlo, a menos que sea un generador lineal congruente muy simple. Si es demasiado feo, diría que, además de admirar el código, probablemente no puedas sacar conclusiones sólidas.

Aunque es arriesgado, puede valer la pena mencionar que si la aplicación tiene un número predecible de llamadas al generador de números aleatorios, puede probar ese generador para tantas llamadas. Sin embargo, he visto algunos entrevistadores que malinterpretarían esto y asumirían que no saben cómo hacer algoritmos que sean sólidos y que se amplíen bien.

Dado que esta es una entrevista, el problema real no es probar una distribución uniforme, el problema real es ser seleccionado para el trabajo. Le sugeriría un enfoque en el que usted decida rápidamente si el entrevistador está buscando una discusión interesante sobre matemáticas avanzadas o si está evaluando su pensamiento práctico. Mi conjetura sería que hay una buena probabilidad de que el entrevistador esté buscando lo último. Una buena respuesta de la entrevista podría ser así: "Todo depende de para qué se necesita el generador de números aleatorios. Si cumple una función de reproducción aleatoria en un reproductor de música, le permitiría generar 100 números, verificar si el promedio es aproximadamente igual a N / 2 A continuación, revise brevemente los números y podría estar satisfecho en ese punto. Si el propósito estuviera relacionado con el cifrado, sería una historia diferente, comenzaría a investigar, pero probablemente terminaría no probándolo, pero confiaría En la prueba existente, independiente ".

Esta es una pregunta un tanto cruel para una entrevista (a menos que se trate de una posición de investigación), pero divertida para un foro. Hace 20 años, después de terminar mi licenciatura en matemáticas, hubiera presentado alegremente un generador aleatorio escrito por mí mismo con la prueba matemática de que era aleatorio. Mirando ese código ahora, me cuesta creer que lo escribí. En estos días, hago lo que cualquier programador práctico haría, y uso un algoritmo implementado por NAG, numpy, matlab o algún otro paquete bien respetado (confío en NAG), y tal vez haga un análisis estadístico simple para verificar, si la distribución fue crítica por alguna razón u otra

Sin embargo, lo importante en una entrevista es ser honesto. Si no lo sabe, entonces dígales que tiene que buscarlo. Si no lo sabe y no le interesa que lo busque, está bien decirles eso también. Hacer un trabajo desafiante que requiera investigación constante tiene que ser algo que el empleador atienda proporcionando un buen ambiente de trabajo. El desafío es bueno, pero la confrontación y la competencia son contraproducentes (demasiadas ''C'').

Hay una discusión accesible de esto en el Princeton Companion to Mathematics

¿Cómo, sin embargo, se usa una computadora determinista para seleccionar diez mil números aleatorios entre 10 30 y 10 31? La respuesta es que, de hecho, no es necesario hacerlo: casi siempre es lo suficientemente bueno como para hacer una selección pseudoaleatoria. ...
¿Cuándo deberíamos considerar tal secuencia como "aleatoria"? Una vez más, se han sugerido muchas respuestas diferentes. Una idea es considerar pruebas estadísticas simples: esperaríamos que a la larga la frecuencia de ceros sea aproximadamente la misma que la de unos y, más generalmente, que una pequeña subsecuencia como 00110 aparezca con la frecuencia "correcta" ( que para esta secuencia sería 1/32 ya que tiene longitud 5).
Sin embargo, es perfectamente posible que una secuencia pase estas pruebas simples pero que se genere mediante un procedimiento determinista. Si uno está tratando de decidir si una secuencia de ceros y unos es en realidad aleatoria, es decir, producida por algunos medios, como lanzar una moneda, seremos muy sospechosos de una secuencia si podemos identificar un algoritmo que produzca la misma secuencia. . Por ejemplo, rechazaríamos una secuencia que se derivó de manera simple de los dígitos de π, incluso si pasara las pruebas estadísticas. Sin embargo, el simple hecho de pedir que una secuencia no pueda producirse mediante un procedimiento recursivo no da una buena prueba de aleatoriedad: por ejemplo, si uno toma una secuencia de este tipo y alterna los términos de esa secuencia con ceros, uno obtiene una nueva secuencia que está lejos de ser aleatorio, pero todavía no se puede producir de forma recursiva.
Por esta razón, von Mises sugirió en 1919 que una secuencia de ceros y unos debería llamarse aleatoria si no es solo el caso de que el límite de la frecuencia de unos sea 1/2, sino que lo mismo es cierto para cualquier subsecuencia. eso se puede extraer "por medio de un procedimiento razonable". En 1940, la Iglesia hizo esto más preciso al traducir "por medio de un procedimiento razonable" a "por medio de una función recursiva". Sin embargo, incluso esta condición es demasiado débil: Son aquellas secuencias que no satisfacen la "ley del logaritmo iterado" (algo que una secuencia aleatoria podría satisfacer). Actualmente, la llamada tesis de Martin-Löf, formulada en 1966, es una de las definiciones de aleatoriedad más utilizadas: una secuencia aleatoria es una secuencia que satisface todas las "pruebas estadísticas secuenciales efectivas", una noción que no podemos formule precisamente aquí, pero que utiliza de manera esencial la noción de función recursiva. En contraste con la tesis de Church, con la que casi todos los matemáticos están de acuerdo, la tesis de Martin-Löf todavía está muy en discusión.

No hay manera de probarlo, ya que el generador podría generar primero una distribución uniforme y luego desviarse hacia una distribución no uniforme.

Para probarlo , necesita conocer el algoritmo que se está utilizando y mostrar en términos gráficos que el conjunto de todos los estados constituye un ciclo, que no hay subciclos y que la cardinalidad del espacio de estados módulo N es cero para que no haya Conjunto de estados que ocurren con mayor o menor frecuencia que otros. Así es como sabemos que Mersenne Twister, por ejemplo, se distribuye de manera uniforme a pesar de que la versión de 64 bits tiene una longitud de ciclo de 2 ¹⁹⁹³⁷ -1 y nunca se podría enumerar durante la vida útil del universo.

De lo contrario, se usan pruebas estadísticas para probar la hipótesis de uniformidad. Las estadísticas no pueden probar un resultado, no refuta la hipótesis. Cuanto mayor sea el tamaño de la muestra, más convincente será el fracaso para refutar una hipótesis, pero nunca es una prueba. (Esta perspectiva causa más problemas de comunicación con los no estadísticos / no científicos que con cualquier otra cosa que conozca). Hay muchas pruebas de uniformidad, incluidas las pruebas de chi-cuadrado, Anderson-Darling y Kolmogorov-Smirnov, por nombrar solo algunas.

Todas las pruebas de uniformidad pasarán secuencias de valores como 0,1,2, ..., N-1,0,1, ... por lo que la uniformidad no es suficiente para decir que tiene un buen generador. También debe probar la correlación en serie con las pruebas tales como pruebas de espaciamiento, corridas / bajadas, ejecuciones por encima / debajo de la media, pruebas de "cumpleaños", etc.

George Marsaglia creó un conjunto de pruebas bastante completo para la uniformidad y la correlación en serie a lo largo de su carrera, y se publicó en 1995 como lo que él llamaba en broma las " pruebas de Diehard " (porque es una batería de pruebas de alto rendimiento).

Para las pruebas de caja negra (no tiene acceso al código fuente), no puede probar que esté distribuido uniformemente (UD). Sin embargo, puede realizar pruebas estadísticas para encontrar la probabilidad de que sea UD. Ejecute el generador muchas veces (por ejemplo, N * X veces) y cada número entre 0 y N debería haber aparecido alrededor de X veces.

Esto ignora por completo si se trata de números aleatorios o no, solo se enfoca en la uniformidad. Sin embargo, solo probaría que el generador se distribuyó uniformemente si tuviera que ejecutar infinitas pruebas. En el mejor de los casos, es probable que el generador sea uniforme durante las primeras iteraciones de N * X, pero es simple y fácil de implementar.