Cómo probar la aleatoriedad (caso en punto - Mezclar)

Question

En primer lugar, esta pregunta está arrancada de la pregunta this. Lo hice porque creo que esta parte es más grande que una subparte de una pregunta más larga. Si ofende, por favor perdóname.

Supongamos que tiene un algoritmo que genera aleatoriedad. ¿Ahora cómo lo pruebas? O para ser más directo: supongamos que tiene un algoritmo que baraja una baraja de cartas, ¿cómo se prueba que es un algoritmo perfectamente aleatorio?

Para agregar algo de teoría al problema - ¡Se puede mezclar una baraja de cartas en 52! (52 factorial) formas diferentes. Toma una baraja de cartas, baraja a mano y escribe el orden de todas las cartas. ¿Cuál es la probabilidad de que haya obtenido exactamente ese shuffle? Respuesta: 1/52 !.

¿Cuál es la probabilidad de que, después de arrastrar los pies, consigas A, K, Q, J ... de cada palo en una secuencia? Respuesta 1/52!

Por lo tanto, simplemente arrastrando los pies una vez y mirando el resultado no obtendrá absolutamente ninguna información sobre la aleatoriedad de los algoritmos de mezcla. Dos veces y usted tiene más información, Tres más ...

¿Cómo podría probar la caja negra un algoritmo de mezcla aleatoria?

Answer 1

Estadísticas. El estándar de facto para probar los RNG es el Diehard suite. Alternativamente, el Ent program proporciona pruebas que son más simples de interpretar pero menos completas.

En cuanto a los algoritmos de mezcla, utilice un algoritmo conocido como Fisher-Yates (a.k.a "Knuth Shuffle"). La mezcla aleatoria será uniformemente aleatoria siempre que el RNG subyacente sea uniformemente aleatorio. Si está utilizando Java, este algoritmo está disponible en la biblioteca estándar (consulte Collections.shuffle).

Probablemente no importe para la mayoría de las aplicaciones, pero tenga en cuenta que la mayoría de los RNG no proporcionan suficientes grados de libertad para producir cada permutación posible de un mazo de 52 cartas (here explicado).

Answer 2

Mezcle mucho, y luego registre los resultados (si estoy leyendo esto correctamente). Recuerdo haber visto comparaciones de "generadores de números aleatorios". Simplemente lo prueban una y otra vez, luego grafican los resultados.

Si es realmente aleatorio, el gráfico será casi uniforme.

Answer 3

La única manera de probar la aleatoriedad es escribir un programa que intente construir un modelo predictivo para los datos que se prueban, y luego usar ese modelo para intentar predecir datos futuros, y luego mostrar que la incertidumbre o entropía , de sus predicciones tienden hacia el máximo (es decir, la distribución uniforme) en el tiempo. Por supuesto, siempre tendrá dudas sobre si su modelo ha capturado todo el contexto necesario; dado un modelo, siempre será posible construir un segundo modelo que genere datos no aleatorios que se vean al azar al primero. Pero mientras aceptes que la órbita de Plutón tiene una influencia insignificante en los resultados del algoritmo de barajado, entonces deberías ser capaz de asegurarte de que sus resultados son aceptablemente aleatorios.

Por supuesto, si hace esto, también puede usar su modelo generativamente, para realmente crear los datos que desea. Y si haces eso, entonces estás de vuelta en el punto uno.

Answer 4

No estoy siguiendo completamente su pregunta.Usted dice

Supongamos que tiene un algoritmo que genera aleatoriedad. ¿Ahora cómo lo pruebas?

¿Qué quieres decir? Si está asumiendo que puede generar aleatoriedad, no hay necesidad de probarlo.

Una vez que tiene un buen generador de números aleatorios, es fácil crear permutaciones aleatorias (por ejemplo, llame a sus tarjetas 1-52. Genere 52 números aleatorios asignándolas a cada una en orden y luego ordene según sus 52 randoms) . No vas a destruir la aleatoriedad de tu buen RNG generando tu permutación.

La pregunta difícil es si puede confiar en su RNG. Here's un enlace de ejemplo para las personas que debaten sobre ese tema en un contexto específico.

Answer 5

En primer lugar, es imposible saber con certeza si una determinada salida finita es "verdaderamente aleatoria" ya que, como usted señala, any output is possible.

Lo que se puede hacer es tomar una secuencia de salidas y verificar varias medidas de esta secuencia contra lo que es más probable. Puede derivar un tipo de puntaje de confianza que el algoritmo de generación está haciendo un buen trabajo.

Por ejemplo, puede verificar la salida de 10 combinaciones diferentes. Asigne un número 0-51 a cada tarjeta, y tome el promedio de la tarjeta en la posición 6 a través de las barajaduras. El promedio convergente es 25.5, por lo que te sorprendería ver un valor de 1 aquí. Podría usar el teorema del límite central para obtener una estimación de la probabilidad de cada promedio para una posición determinada.

¡Pero no deberíamos parar aquí! Debido a que este algoritmo podría ser engañado por un sistema que solo alterna entre dos mezclas que están diseñadas para dar el promedio exacto de 25.5 en cada posición. ¿Cómo podemos hacerlo mejor?

Esperamos una distribución uniforme (igual probabilidad para cualquier carta dada) en cada posición, a través de diferentes mezclas. Entonces, entre los 10 cambios aleatorios, podríamos tratar de verificar que las opciones 'se vean uniformes'. Esto es básicamente una versión reducida del problema original. Puede verificar que la desviación estándar sea razonable, que el valor mínimo sea razonable y el valor máximo también. También puede verificar que otros valores, como las dos tarjetas más cercanas (según nuestros números asignados), también tengan sentido.

Pero tampoco podemos simplemente agregar varias medidas como este anuncio infinitum, ya que, dadas las estadísticas suficientes, cualquier mezcla en particular aparecerá altamente improbable por alguna razón (por ejemplo, esta es una de las pocas barajas en las que X, Y , Z aparece en orden). Entonces, la gran pregunta es: ¿cuál es el conjunto correcto de medidas a tomar? Aquí tengo que admitir que no sé la mejor respuesta. Sin embargo, si tiene una determinada aplicación en mente, puede elegir un buen conjunto de propiedades/medidas para probar y trabajar con ellas: esta parece ser la forma en que los criptógrafos manejan las cosas.

Answer 6

Hay una gran cantidad de teoría sobre la prueba de aleatoriedad. Para una prueba muy simple en un algoritmo de barajado de cartas, podrías hacer muchas barajaduras y luego ejecutar una prueba de Chi cuadrado que mostrara que la probabilidad de que cada carta aparezca en cualquier posición era uniforme. Pero eso no prueba que las cartas consecutivas no estén correlacionadas, por lo que también querrás hacer pruebas al respecto.

El Volumen 2 de Knuth's Art of Computer Programming ofrece una serie de pruebas que puede usar en las secciones 3.3.2 (Pruebas empíricas) y 3.3.4 (La prueba espectral) y la teoría detrás de ellas.

Answer 7

Pruebas 52! las posibilidades son por supuesto imposibles.En su lugar, pruebe su reproducción aleatoria en números más pequeños de tarjetas, como 3, 5 y 10. Luego puede probar miles de millones de combinaciones y usar un histograma y la prueba estadística de chi-cuadrado para probar que cada permutación aparece como un número "par" de veces

Answer 8

Sin código hasta el momento, por lo tanto copio y pego una parte de prueba de my answer a la pregunta original.

// ... 
    int main() { 
    typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map; 
    Map freqs;  
    Deck d; 
    const size_t ntests = 100000; 

    // compute frequencies of events: card at position 
    for (size_t i = 0; i < ntests; ++i) { 
     d.shuffle(); 
     size_t pos = 0; 
     for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) 
     ++freqs[std::make_pair(pos, *j)]; 
    } 

    // if Deck.shuffle() is correct then all frequencies must be similar 
    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j) 
     std::cout << "pos=" << j->first.first << " card=" << j->first.second 
       << " freq=" << j->second << std::endl;  
    } 

Este código no prueba la aleatoriedad del generador de números pseudoaleatorio subyacente. Probar la aleatoriedad de PRNG es una rama completa de la ciencia.

Answer 9

Aquí hay una verificación simple que puede realizar. Utiliza números aleatorios generados para estimar Pi. No es una prueba de aleatoriedad, pero los RNG pobres normalmente no funcionan bien (devolverán algo así como 2.5 o 3.8 en vez de ~ 3.14).

Idealmente, esta sería solo una de las muchas pruebas que se ejecutarían para verificar la aleatoriedad.

Algo más que usted puede verificar es el standard deviation de la salida. La desviación estándar esperada para una población de valores uniformemente distribuida en el rango 0..n se aproxima a n/sqrt (12).

/** 
* This is a rudimentary check to ensure that the output of a given RNG 
* is approximately uniformly distributed. If the RNG output is not 
* uniformly distributed, this method will return a poor estimate for the 
* value of pi. 
* @param rng The RNG to test. 
* @param iterations The number of random points to generate for use in the 
* calculation. This value needs to be sufficiently large in order to 
* produce a reasonably accurate result (assuming the RNG is uniform). 
* Less than 10,000 is not particularly useful. 100,000 should be sufficient. 
* @return An approximation of pi generated using the provided RNG. 
*/ 
public static double calculateMonteCarloValueForPi(Random rng, 
                int iterations) 
{ 
    // Assumes a quadrant of a circle of radius 1, bounded by a box with 
    // sides of length 1. The area of the square is therefore 1 square unit 
    // and the area of the quadrant is (pi * r^2)/4. 
    int totalInsideQuadrant = 0; 
    // Generate the specified number of random points and count how many fall 
    // within the quadrant and how many do not. We expect the number of points 
    // in the quadrant (expressed as a fraction of the total number of points) 
    // to be pi/4. Therefore pi = 4 * ratio. 
    for (int i = 0; i < iterations; i++) 
    { 
     double x = rng.nextDouble(); 
     double y = rng.nextDouble(); 
     if (isInQuadrant(x, y)) 
     { 
      ++totalInsideQuadrant; 
     } 
    } 
    // From these figures we can deduce an approximate value for Pi. 
    return 4 * ((double) totalInsideQuadrant/iterations); 
} 

/** 
* Uses Pythagoras' theorem to determine whether the specified coordinates 
* fall within the area of the quadrant of a circle of radius 1 that is 
* centered on the origin. 
* @param x The x-coordinate of the point (must be between 0 and 1). 
* @param y The y-coordinate of the point (must be between 0 and 1). 
* @return True if the point is within the quadrant, false otherwise. 
*/ 
private static boolean isInQuadrant(double x, double y) 
{ 
    double distance = Math.sqrt((x * x) + (y * y)); 
    return distance <= 1; 
} 

Answer 10

Reflexionando yo mismo, lo que haría es algo así como:

configuración (Pseudo código)

// A card has a Number 0-51 and a position 0-51 
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values 
ShuffleCards(); 
ForEach (card in Cards) { 
    StatMatrix[Card.Position][Card.Number]++; 
} 

Esto nos da una 52x52 matriz que indica cuántas veces a la tarjeta ha terminado en una posición determinada. Repita esto una gran cantidad de veces (comenzaría con 1000, pero la gente mejor en las estadísticas que yo puede dar un número mejor).

Analizar la matriz

Si tenemos aleatoriedad perfecta y realizar la reproducción aleatoria un número infinito de veces y luego para cada tarjeta y para cada posición el número de veces que la tarjeta terminó en esa posición es la misma que para cualquier otra tarjeta. Diciendo lo mismo de otra manera:

statMatrix[position][card]/numberOfShuffle = 1/52. 

Así que calculo qué tan lejos de ese número estamos.

Answer 11

Simplemente vea su resultado en comparación con su out put antes de aleatorizar las cosas. Aquí hay un ejemplo de lo que hice.

public void testShuffleRemainingDeck() 
{ 
    System.out.println("ShuffleRemainingDeck"); 
    Deck instance = new Deck(true);    //create new deck 
    System.out.println(instance.toString()); //print unshuffled deck. 
    instance.ShuffleRemainingDeck();   //shuffle the deck. 
    System.out.println(instance.toString()); //print shuffled deck. 
               //now visually compare the outputs. 
} 

Answer 12

Para una prueba rápida, siempre puede intentar comprimirlo. Una vez que no se comprime, puede pasar a otras pruebas.

He intentado con dieharder pero se niega a funcionar para una mezcla. Todas las pruebas fallan También es muy pesado, no le permite especificar el rango de valores que desea ni nada de eso.