¿Por qué las pruebas de aleatoriedad estadística parecen tan ad hoc?

Question

Wikipedia describe Kendall y Smith 1938 aleatoriedad estadística pruebas como esta:

• La frecuencia de prueba, era muy básico: la comprobación para asegurarse de que había aproximadamente el mismo número de 0s, 1s, 2s, 3s, etc.

• La serie de la prueba, hizo lo mismo pero para las secuencias de dos dígitos en un tiempo (00, 01, 02, etc.), comparando las frecuencias observadas con sus predicciones hipotéticas eran igualmente distribuido.

• El poker de la prueba, la prueba para ciertas secuencias de cinco números en un tiempo (aaaaa, aaaab, será aaabb, etc.) basado en las manos en el juego de poker.

• La brecha de la prueba, miró a las distancias entre los ceros (00 sería una distancia de 0, 030 sería una distancia de 1, 02250 sería una distancia de 3, etc.).

No es obvio para mí que estas cuatro pruebas en particular fueron elegidos con cualquier comprensión profunda de la mejor manera de detectar la falta de aleatoriedad. Más bien, parece que cada uno probablemente fue escogido por su simplicidad.

Así, es fácil ver por qué los primeros trabajos en el campo iba a ser así. Pero el avance rápido de 1995 y George Marsaglia del Diehard pruebas parece, en la superficie, así como ad hoc:

• Cumpleaños espaciamientos: Elegir al azar los puntos en un gran intervalo. Las distancias entre los puntos deben ser asintóticamente Poisson distribuido. El nombre se basa en la paradoja de cumpleaños.

• La superposición de permutaciones: Analizar secuencias de cinco años consecutivos de números aleatorios. Los 120 posibles órdenes deben ocurrir con estadísticamente igual probabilidad.

(...y así sucesivamente)

No es obvio para mí que estas pruebas son realmente independientes (es decir, que ninguno es totalmente redundante, rechazando sólo secuencias que también fue rechazado por al menos una de las otras pruebas), o que no hay, obviamente, mejor generalizaciones de ellos, y mucho menos que se fueron elegidos como un conjunto para tratar de cubrir cualquier espacio de manera eficiente.

Idealmente, un conjunto de pruebas sería diseñado para rechazar como muchas secuencias de baja complejidad de Kolmogorov como sea posible con un mínimo de cálculo y las falsas alarmas. Es más una aproximación teórica a esto posible? Por qué no ha sucedido? —O hay más en el estado del arte que cumple el ojo?

Answer 1

No está claro que Marsaglia las pruebas son realmente lo suficientemente bueno. Ver este Stack Overflow de discusión.

Prueba de Kolmogorov complejidad no es el criterio de aleatoriedad estadística de las pruebas, ya que cualquier secuencia pseudoaleatoria de baja complejidad de Kolmogorov. Lo que realmente quieres en un generador de números aleatorios es para la secuencia a ser computacionalmente pseudo aleatorios; es decir, sin conocimiento de la semilla, no polinomio de tiempo de prueba puede distinguir la secuencia de una verdadera secuencia aleatoria.

De hecho, hay un número de generadores de números aleatorios que se cree que son computacionalmente pseudoaleatoria. Nadie usa estos, sin embargo, en parte debido a que son computacionalmente muy costoso, y en parte debido a la inercia y en parte porque el existente generadores pseudoaleatorios tenemos son lo suficientemente buenos como la mayoría del tiempo. Hace un tiempo, para uno de los más comunes métodos de generación de números pseudoaleatorios (lineal congruential), me encontré en los casos en que inesperadamente se produce la respuesta equivocada.

Marsaglia las pruebas se desarrollaron a través de un número de años, y creo que cada uno fue diseñado para detectar ciertos defectos que muchos de los generadores de números pseudoaleatorios contenidas en el tiempo. Una vez que suficientes generadores de números pseudoaleatorios estaban disponibles, nadie se molestó creación de una más estricta serie de pruebas.

Answer 2

En el Capítulo 2 del libro de Teoría de grupos en el Dormitorio, Brian Hayes menciona lo difícil que es para extraer el "verdadero" aleatoriedad del mundo físico (incluyendo la construcción de tablas de números aleatorios a la antigua usanza, y cómo Fisher y Yates había para "arreglar" sus tablas en el post-procesado para re-equilibrar los dígitos, causando que sus colegas comentario: "un procedimiento de este tipo puede causar que otros, como lo hizo con nosotros, algunas dudas").

El punto que hace es que la aleatoriedad es difícil de lograr, porque incluso si su origen es realmente aleatorio (lo que significa), el proceso de medición es conveniente introducir un sesgo, por lo que la pseudo-aleatoria de los generadores pueden realizar físico fuentes aleatorias en muchos estadísticos de prueba. [Voy a agregar una más precisa de la página de referencia tan pronto como la puedo encontrar.]

Dado este estado de cosas, el ideal de la suite de prueba parece poco probable que exista. Estoy de acuerdo con usted en que menos ad-hoc pruebas no parece deseable, sin embargo.

Answer 3

La complejidad de Kolmogorov es un universal de la cantidad de infinitas cadenas. Pero desde la aleatoriedad de las pruebas se ejecutan en finito de cadenas, en particular la elección de la arquitectura de la codificación o va a jugar un papel importante en cómo las cadenas será pedido. Un gol de buena aleatoriedad diseñador de pruebas es elegir una codificación que las cadenas de caracteres que viene a partir de la conocida fuentes aleatorias (como random.org) se considera más complejo de cadenas procedentes de conocidos de fuentes no aleatorias (como pseudo-aleatoria de los generadores). Buenas pruebas de incorporar el conocimiento de cómo típica, no al azar cadenas se generan, de ahí la aparente ad hockery.