math - the - Cómo probar la aleatoriedad(caso en punto-Mezcla)

math logic problems with answers

Question

En primer lugar, esta pregunta está arrancada de this pregunta. 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.

Suponga 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 barajar un mazo 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 barajar, obtengas A, K, Q, J ... de cada palo en una secuencia? Respuesta 1/52!

Entonces, simplemente barajar una vez y mirar el resultado no le dará absolutamente ninguna información sobre la aleatoriedad de los algoritmos de mezcla. Dos veces y tienes más información, Tres más ...

¿Cómo probarías la caja negra un algoritmo de barajado para la aleatoriedad?

Answer 1

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 realizaría para verificar la aleatoriedad.

Otra cosa que puede verificar es la desviación estándar 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 2

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

Lo que se puede hacer es tomar una secuencia de resultados y verificar varias mediciones 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 mezclas 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 esta ad 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 aparecen las tarjetas X, Y, Z 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 3

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

En cuanto a los algoritmos de mezcla, use un algoritmo conocido como Fisher-Yates (también conocido como "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 (explicado here ).

Answer 4

Hay mucha teoría sobre probar la 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 5

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 tratar de predecir datos futuros y luego mostrar la incertidumbre o entropía de sus predicciones. tender hacia el máximo (es decir, la distribución uniforme) a lo largo del 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 podría usar su modelo de manera generativa , para realmente crear los datos que desea. Y si haces eso, entonces estás de vuelta en el punto uno.

Answer 6

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 verdaderamente aleatorio, el gráfico será mayormente par.

Answer 7

No estoy siguiendo completamente tu pregunta. Tu dices

Suponga 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 permutación aleatoria (por ejemplo, llame a sus tarjetas del 1 al 52. Genere 52 números aleatorios asignándoles cada uno a una tarjeta 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 puedes confiar en tu RNG. Here''s un enlace de muestra para las personas que debaten sobre ese tema en un contexto específico.

Answer 8

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

Lo intenté más duro, pero se niega a trabajar para mezclar. Todas las pruebas fallan También es muy pesado, no le permite especificar el rango de valores que desea ni nada de eso.

Answer 9

Probando 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 10

Reflexionando sobre esto, 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 matriz de 52x52 que indica cuántas veces una 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).

Analiza la matriz

Si tenemos una aleatoriedad perfecta y realizamos la reproducción aleatoria un número infinito de veces, para cada carta y para cada posición, la cantidad de veces que la tarjeta terminó en esa posición es la misma que para cualquier otra carta. 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

Sin código hasta el momento, por lo tanto copio y pego una parte de prueba de mi respuesta 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.