Cómo probar la aleatoriedad (caso en el punto Arrastrando los pies)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En primer lugar, esta pregunta es arrancado de este pregunta.Lo hice porque creo que esta parte es más grande que una sub-parte de un largo cuestión.Si se ofenda, por favor, perdóname.
Suponga que tiene un algoritmo que genera la aleatoriedad.Y ahora, ¿cómo probarlo?O para ser más directo, Supongamos que usted tiene un algoritmo que baraja un mazo de cartas, ¿cómo se prueba que es perfectamente aleatoria algoritmo?
Para añadir algo de teoría para el problema - Una baraja de cartas puede ser barajada de 52!(52 factorial) de diferentes maneras.Tome un mazo de cartas, barajar a mano y anotar el orden de todas las tarjetas.¿Cuál es la probabilidad de que se habría conseguido exactamente que shuffle?Respuesta:1 / 52!.
¿Cuál es la probabilidad de que, después de revolver, recibirá a, K, Q, J ...de cada palo en una secuencia?Respuesta 1 / 52!
Así que, simplemente arrastrando los pies una vez y a la vista del resultado va a dar absolutamente ninguna información sobre su revolver algoritmos de aleatoriedad.Dos veces y tiene más información, Tres, incluso más...
¿Cómo podría caja negra de prueba de un algoritmo de barajado para la aleatoriedad?
Solución
Estadísticas.El estándar de facto para las pruebas de generadores de números aleatorios es el Diehard suite (originalmente disponible en http://stat.fsu.edu/pub/diehard).Alternativamente, el Ent programa proporciona pruebas de que son más fáciles de interpretar, pero menos completa.
Como para mezclarse algoritmos, uso de un algoritmo conocido como Fisher-Yates (un.k.un "Knuth Shuffle").El shuffle será uniformemente al azar siempre y cuando el subyacente del generador de números aleatorios uniformemente al azar.Si usted está usando Java, este algoritmo está disponible en la biblioteca estándar (ver Las colecciones.shuffle).
Es probable que no importa para la mayoría de aplicaciones, pero hay que ser conscientes de que la mayoría de los generadores de números aleatorios no se proporcionan suficientes grados de libertad para producir cada permutación posible de una baraja de 52 cartas (que se explica aquí).
Otros consejos
He aquí una simple comprobación de que se pueden realizar.Se utiliza genera números aleatorios para calcular Pi.No es una prueba de aleatoriedad, pero pobre Rng que normalmente no hacen bien en ella (se devolverá algo así como 2.5 a 3.8 lugar ~3.14).
Idealmente, esto sería sólo una de las muchas pruebas que tendría que ejecutar para comprobar la aleatoriedad.
Otra cosa que se puede comprobar es el desviación estándar de la salida.A la espera de la desviación estándar para un distribuida uniformemente en la población de los valores 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;
}
En primer lugar, es imposible saber con certeza si un determinado finito de salida es "azar", ya que, como usted señala, cualquier resultado es posible.
¿Qué se puede hacer, es tomar una secuencia de salidas y comprobar varias mediciones de esta secuencia en contra de lo que es más probable.Se puede derivar una especie de puntuación de confianza que el algoritmo de generación está haciendo un buen trabajo.
Por ejemplo, se puede comprobar que la salida de 10 diferentes baraja.Asignar un número de 0-51 para cada tarjeta, y tomar el promedio de la tarjeta en la posición 6 a través de la baraja.El convergente promedio es de 25.5, por lo que se sorprendió al ver a un valor de 1 a continuación.Usted podría utilizar el teorema del límite central para obtener una estimación de la probabilidad de cada media es para una posición dada.
Pero no debemos parar aquí!Debido a que este algoritmo podría ser engañados por un sistema que sólo se alterna entre dos baraja que están diseñados para dar la exacta promedio de 25.5 en cada posición.Cómo podemos hacer mejor?
Esperamos una distribución uniforme (la misma probabilidad para cualquier tarjeta) en cada posición, a través de diferentes baraja.Así que entre el 10 baraja, podríamos tratar de verificar que las opciones de 'look uniforme.' Esto es básicamente una versión reducida del problema original.Se puede comprobar que la desviación estándar parece razonable, que el minuto es razonable, y el máximo valor.Usted puede también comprobar que otros valores, tales como la más cercana de las dos tarjetas (por nuestros números asignados), también tiene sentido.
Pero también podemos no basta con agregar varias medidas como esta ad infinitum, ya que, dada la suficiente cantidad de estadísticas, cualquier particular shuffle aparecerá muy poco probable que por alguna razón (por ejemplo,este es uno de los pocos baraja en la que las cartas X,Y,Z aparecen en orden).Así que la gran pregunta es:que es el conjunto de medidas a tomar?Aquí tengo que admitir que no conozco a la mejor respuesta.Sin embargo, si usted tiene una cierta aplicación en mente, usted puede elegir un buen conjunto de propiedades/medidas a probar y trabajar con esos ... este parece ser el camino a codificadores de manejar las cosas.
Hay un montón de teoría en las pruebas de aleatoriedad.Por una sencilla prueba en una de barajar algoritmo se podría hacer un montón de baraja y, a continuación, ejecute un chi-cuadrado de la prueba de que la probabilidad de cada tarjeta de inflexión en cualquier posición uniforme.Pero eso no prueba que cartas consecutivas no se correlaciona de modo que también se quiere hacer pruebas en que.
El volumen 2 de Knuth del Arte de la Programación de la Computadora da una serie de pruebas que usted podría utilizar en las secciones 3.3.2 (pruebas Empíricas) y 3.3.4 (El espectro de la Prueba) y la teoría detrás de ellos.
Shuffle mucho, y, a continuación, registro de los resultados (si estoy leyendo correctamente).Recuerdo ver las comparaciones de "generadores de números aleatorios".Simplemente probarlo, a continuación, un gráfico de los resultados.
Si es verdaderamente aleatoria el gráfico va a ser en su mayoría aún.
La única manera de prueba para la aleatoriedad es escribir un programa que intenta construir un modelo predictivo de los datos de prueba, y luego utilizar ese modelo para intentar predecir el futuro de los datos y, a continuación, muestra que la incertidumbre o entropía, de sus predicciones tienden hacia el máximo (es decir,la distribución uniforme) a lo largo del tiempo.Por supuesto, siempre vas a estar seguro de si o no su modelo ha capturado todo el contexto necesario;dado un modelo, siempre será posible construir un segundo modelo que genera datos no aleatorios que parece aleatorio a la primera.Pero mientras usted acepta que la órbita de Plutón tiene una influencia insignificante sobre los resultados de la transposición de algoritmo, entonces usted debería ser capaz de asegurarse de que sus resultados son aceptablemente al azar.
Por supuesto, si usted hace esto, usted podría utilizar el modelo generativamente, para crear los datos que desea.Y si lo haces, entonces estás de vuelta en la plaza de una.
No estoy totalmente siguientes a su pregunta.Usted dice
Suponga que tiene un algoritmo que genera la aleatoriedad.Y ahora, ¿cómo probarlo?
¿A qué te refieres?Si estás suponiendo que usted puede generar aleatoriedad, no hay necesidad de probarlo.
Una vez que usted tiene un buen generador de números aleatorios, la creación de una permutación aleatoria es fácil (por ejemplo,Llame a su tarjetas de 1-52.Generar 52 números aleatorios de asignación a cada uno a una tarjeta en orden, y, a continuación, ordenar de acuerdo a sus 52 randoms) .No vas a destruir la aleatoriedad de su buen generador de números aleatorios mediante la generación de su permutación.
La difícil pregunta es si se puede confiar en su RNG. Aquí un ejemplo de enlace a la gente hablar sobre ese problema en un contexto específico.
Pruebas de 52!posibilidades es imposible, por supuesto.En su lugar, pruebe su shuffle en pequeños números de tarjetas, como 3, 5, y 10.A continuación, puede probar los miles de millones de baraja y el uso de un histograma y el test de la chi-cuadrado estadístico de prueba para demostrar que cada permutación se avecina una "incluso" el número de veces.
Ningún código hasta el momento, por lo tanto puedo copiar-pegar una prueba de parte 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 de aleatoriedad de los subyacentes generador de números pseudoaleatorios.Pruebas de PRNG aleatoriedad es toda una rama de la ciencia.
Para realizar una prueba rápida, siempre se puede intentar comprimirlo.Una vez que no comprimir, a continuación, puede pasar a otras pruebas.
He intentado dieharder pero se niega a trabajar para un shuffle.Todas las pruebas fallan.También es muy aburrido, no lo puedo dejar de especificar el rango de valores que usted desea, o algo como eso.
Reflexionando sobre mí mismo, lo que quiero hacer es algo como:
El programa de instalació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 se ha quedado en una posición determinada.Repita este un gran número de veces (me gustaría empezar con 1000, pero la gente mejor en las estadísticas que me puede dar un mejor número).
Analizar la matriz de
Si tenemos perfecto aleatoriedad y realizar la reproducción aleatoria un número infinito de veces, a continuación, para cada tarjeta y para cada posición del número de veces que la tarjeta terminó en esa posición es la misma que para cualquier otra tarjeta.Diciendo lo mismo de una manera diferente:
statMatrix[position][card] / numberOfShuffle = 1/52.
Así que me gustaría calcular cómo lejos de ese número que somos.
