function - superponer - ¿Cómo "verificar" si una función realmente da un resultado aleatorio?

superponer graficas en r ggplot

Question

¿Cómo podemos estar seguros de que una función es realmente aleatoria o lo más cercana posible a la noción? Además, ¿cuál es la distinción entre aleatorio y pseudoaleatorio? Finalmente, ¿qué algoritmos / fuentes pueden usarse para generar números aleatorios?

PD: También pregunte esto porque una declaración de MySQL que usa ORDER BY RAND() LIMIT 1 no está dando resultados convincentes.

Answer 1

Aloha!

Hay varios métodos y herramientas para probar la aleatoriedad. Estos se aplican en un conjunto de números recopilados del generador para ser probado. Es decir, prueba el generador basándose en un conjunto de datos generados.

En computación, especialmente para seguridad de TI, normalmente queremos tener un generador que se ajuste a un proceso aleatorio uniforme. Hay muchos procesos diferentes, pero supongo que es un proceso uniforme al que apunta.

NIST ha publicado varios documentos con recomendaciones sobre ambos generadores de números pseudoaleatorios y sobre cómo probarlos. Mire los documentos NIST SP 800-22 y SP 800-20.

Como alguien más señaló. Si desea un generador de números aleatorios verdaderos (TRNG), debe reunir la entropía física. Ejemplos de tales fuentes son la descomposición radioactiva, la radiación cósmica, las lámparas de lava, etc. Preferiblemente, las fuentes son difíciles de manipular. IETF tiene una RFC que tiene algunas buenas recomendaciones, consulte RFC 4086 - Fuente de aleatoriedad para la seguridad: http://tools.ietf.org/html/rfc4086

Lo que normalmente hace es recolectar entropía de una fuente o más (preferiblemente más de una). Los datos recopilados se filtran (blanqueando) y, finalmente, se utilizan para sembrar periódicamente un buen PRNG. Con diferentes semillas, naturalmente.

Así es como funciona la mayoría de los generadores aleatorios buenos y modernos. Un colector de entropía que alimenta un PRNG creado utilizando primitivas criptográficas como cifrados simétricos (AES, por ejemplo) o funciones hash. Véase, por ejemplo, el generador aleatorio Yarrow / Fortuna de Schneier, que en forma modificada se utiliza en FreeBSD.

Volviendo a su pregunta sobre las pruebas. Como alguien señaló, Marsaglia ha producido un buen conjunto de pruebas, que se codificó en las pruebas DIEHARD. Ahora hay un conjunto de pruebas aún más exhaustivo en las pruebas de Dieharder: http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder es una buena herramienta que le dará una buena confianza de que la gran cantidad de números que se le suministran (recopilados de su generador) es aleatoria (de buena calidad) o no. Correr Dieharder es fácil, pero tomará algún tiempo.

Las pruebas in situ de aleatoriedad son difíciles. Normalmente no quieres implementar Dieharder en tu sistema. Lo que puede hacer es implementar algunos detectores simples que deberían detectar casos patológicos. Por lo general sugiero:

• Longitud de igual valor. Un contador simple que se reinicia cada vez que difieren dos valores consecuentes generados por el RNG. Y luego debe definir un umbral cuando crea que el contador muestra que el RNG está roto. Si ve 10 millones de valores iguales y el espacio de valores es mayor que un valor (el que ve), su RNG probablemente no esté funcionando tan bien. Esp si el valor está viendo es uno de los valores de borde. Por ejemplo 0x00000 .... o 0xfffff ...

• Valor madiano. Si después de generar un millón de valores y tiene una distribución uniforme, tiene un valor mediano que está fuertemente inclinado hacia uno de los bordes del espacio de valores, no cerca del medio, es probable que algo no esté bien.

• Diferencia. Si después de generar un millón de valores no ha visto valores cercanos al MIN y MAX del espacio de valores, sino que tiene un espacio de valores reducido, entonces algo anda mal.

Finalmente. Como es de esperar que esté utilizando un buen PRNG (basado en AES, por ejemplo), las pruebas in situ sugeridas podrían aplicarse en la fuente de entropía.

Espero que haya ayudado de alguna manera.

Answer 2

El hecho de ser aleatorio es que no se puede saber si el retorno de una función aleatoria es aleatorio o no.

^...o...

dilbert.com/strips/comic/2001-10-25

El uso aleatorio apropiado utiliza algo que realmente puede ser aleatorio, como el ruido blanco . Los números pseudoaleatorios generalmente se calculan a partir de fórmulas matemáticas o tablas precomputadas. El generador congruente lineal es un método popular para generarlos.

Para obtener un número aleatorio real, generalmente se debe establecer una interfaz con una fuente externa donde se haya generado algo de forma orgánica. Esto se llama un verdadero generador de números aleatorios .

Answer 3

Es cierto que no podemos garantizar que el número aleatorio sea en realidad aleatorio.
sobre los números pseudoaleatorios: sí, parece que son aleatorios (originalmente utilizados en la criptografía) (funciones pseudoaleatorias), cuando envían texto cifrado y el mal entre las trampas, el mensaje cree que el texto cifrado que obtuvo es aleatorio, pero el mensaje se calculó a partir de alguna función, además, recibirá el mismo mensaje utilizando la misma función y la misma tecla (si las hay, de modo que no, donde no sean aleatorias, se verá como aleatoria porque no puede crear el texto / número original a partir del cual se genera). .Como funciones hash (md5, sha1) y técnicas de encriptación (des, aes, etc.).

Answer 4

Hay pruebas estadísticas que puede aplicar para ver qué tan probable es que una secuencia dada de números fueran independientes, distribuidas de manera idéntica (iid) variables aleatorias.

Eche un vistazo a Una vista actual de los generadores de números aleatorios por George Marsaglia. En particular, eche un vistazo a las secciones 6-12. Esto proporciona una introducción a tales pruebas seguidas de varias que puede aplicar.

Answer 5

La informática teórica enseña que una computadora es una máquina determinista. Cada algoritmo siempre se ejecuta de la misma manera, por lo que tiene que variar su semilla. ¿Pero de dónde debería obtener una computadora una semilla aleatoria? ¿Desde un dispositivo externo? ¿La temperatura de la CPU (que no variaría mucho)?

Answer 6

Para probar una función que devuelve números aleatorios, debe llamarla muchas veces y ver cuántas veces se devuelve cada número.

Por ejemplo

For i := 1 to 1000000 do // Test the function 1.000.000 times
begin
   RandomNumber := Rand(9); // Random numbers from 0 to 9
   case RandomNumber of
      1 : Returned0 := Returned0 + 1;
      1 : Returned1 := Returned1 + 1;
      1 : Returned2 := Returned2 + 1;
      1 : Returned3 := Returned3 + 1;
      1 : Returned4 := Returned4 + 1;
      1 : Returned5 := Returned5 + 1;
      1 : Returned6 := Returned6 + 1;
      1 : Returned7 := Returned7 + 1;
      1 : Returned8 := Returned8 + 1;
      1 : Returned9 := Returned9 + 1;
   end;
end

WriteLn(''0: '', Returned0);
WriteLn(''1: '', Returned1);
WriteLn(''2: '', Returned2);
WriteLn(''3: '', Returned3);
WriteLn(''4: '', Returned4);
WriteLn(''5: '', Returned5);
WriteLn(''6: '', Returned6);
WriteLn(''7: '', Returned7);
WriteLn(''8: '', Returned8);
WriteLn(''9: '', Returned9);

Una salida perfecta debe ser números iguales para cada salida aleatoria. Algo como:

0: 100000
1: 100000
2: 100000
3: 100000
4: 100000
5: 100000
6: 100000
7: 100000
8: 100000
9: 100000

Answer 7

Para que el número sea aleatorio , no debe ser posible predecirlo. Por lo tanto, cualquier algoritmo que genere números "aleatorios" genera números pseudoaleatorios, ya que siempre es posible generar la misma secuencia de números "aleatorios", utilizando semilla o valor previamente utilizado que se usa durante la "aleatorización". Se puede generar un número verdaderamente aleatorio, por ejemplo, dados, pero no un algoritmo de computadora.