Comment tester le caractère aléatoire (exemple : le mélange des cartes) ?

Question

Tout d'abord, cette question est tirée de este question. Je l'ai fait parce que je pense que cette partie est plus importante qu'une sous-partie d'une question plus longue. Si cela vous choque, veuillez me pardonner.

Supposons que vous ayez un algorithme qui génère du hasard. Maintenant, comment le tester ? Ou, pour être plus direct, supposons que vous ayez un algorithme qui mélange un jeu de cartes. Comment pouvez-vous vérifier qu'il s'agit d'un algorithme parfaitement aléatoire ?

Pour ajouter un peu de théorie au problème - Un jeu de cartes peut être mélangé en 52 ! (52 factorielles) différentes. Prenez un jeu de cartes, mélangez-le à la main et notez l'ordre de toutes les cartes. Quelle est la probabilité que vous ayez obtenu exactement ce mélange ? Réponse : 1 / 52 !.

Quelle est la probabilité que vous obteniez, après avoir mélangé les cartes, des A, K, Q, J ... de chaque couleur dans une séquence ? Réponse 1 / 52 !

Ainsi, le fait de mélanger les cartes une seule fois et de regarder le résultat ne vous donnera absolument aucune information sur le caractère aléatoire de votre algorithme de mélange. Deux fois et vous avez plus d'informations, trois encore plus...

Comment tester en boîte noire le caractère aléatoire d'un algorithme de brassage ?

Answer 1

Statistiques. Le standard de facto pour tester les RNG est le Suite de Diehard (disponible à l'origine sur http://stat.fsu.edu/pub/diehard ). Par ailleurs, le Programme d'entrée fournit des tests plus simples à interpréter mais moins complets.

Quant aux algorithmes de brassage, utilisez un algorithme bien connu tel que Fisher-Yates (alias "Knuth Shuffle"). Le mélange sera uniformément aléatoire tant que le RNG sous-jacent est uniformément aléatoire. Si vous utilisez Java, cet algorithme est disponible dans la bibliothèque standard (cf. Collections.shuffle ).

Cela n'a probablement pas d'importance pour la plupart des applications, mais sachez que la plupart des RNG ne fournissent pas suffisamment de degrés de liberté pour produire toutes les permutations possibles d'un jeu de 52 cartes (expliqué aquí ).

Answer 2

Voici un contrôle simple que vous pouvez effectuer. Il utilise des nombres aléatoires générés pour estimer Pi. Ce n'est pas une preuve du caractère aléatoire, mais les RNG médiocres ne s'en sortent généralement pas bien (ils renvoient quelque chose comme 2,5 ou 3,8 plutôt que ~3,14).

Dans l'idéal, il s'agirait d'un des nombreux tests à effectuer pour vérifier le caractère aléatoire.

Une autre chose que vous pouvez vérifier est le écart type de la sortie. L'écart-type attendu pour une population de valeurs uniformément distribuées dans l'intervalle 0..n est proche de 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 3

Tout d'abord, il est impossible de savoir avec certitude si une certaine sortie finie est "véritablement aléatoire" puisque, comme vous le soulignez, toute sortie est possible .

Ce qui peut être fait, c'est de prendre une séquence de sorties et de vérifier diverses mesures de cette séquence par rapport à ce qui est le plus probable. Vous pouvez en déduire une sorte de score de confiance indiquant que l'algorithme de génération fait du bon travail.

Par exemple, vous pouvez vérifier le résultat de 10 mélanges différents. Attribuez un nombre de 0 à 51 à chaque carte, et prenez la moyenne de la carte en position 6 dans tous les mélanges. La moyenne convergente est de 25,5, vous seriez donc surpris de voir une valeur de 1 ici. Vous pourriez utiliser le théorème de la limite centrale pour obtenir une estimation de la probabilité de chaque moyenne pour une position donnée.

Mais nous ne devons pas nous arrêter là ! Car cet algorithme pourrait être trompé par un système qui ne fait qu'alterner entre deux mélanges conçus pour donner la moyenne exacte de 25,5 à chaque position. Comment pouvons-nous faire mieux ?

Nous nous attendons à une distribution uniforme (probabilité égale pour toute carte donnée) à chaque position, à travers différents mélanges. Ainsi, parmi les 10 mélanges, nous pourrions essayer de vérifier que les choix "semblent uniformes". Il s'agit en fait d'une version réduite du problème original. Vous pouvez vérifier que l'écart type semble raisonnable, que la valeur minimale est raisonnable, ainsi que la valeur maximale. Vous pouvez également vérifier que d'autres valeurs, telles que les deux cartes les plus proches (selon les numéros qui nous ont été attribués), ont également un sens.

Mais nous ne pouvons pas non plus ajouter des mesures de ce type à l'infini, car, si l'on dispose de suffisamment de statistiques, tout mélange particulier semblera hautement improbable pour une raison ou une autre (par exemple, il s'agit de l'un des très rares mélanges dans lesquels les cartes X, Y, Z apparaissent dans l'ordre). La grande question est donc la suivante : quel est le bon ensemble de mesures à prendre ? Je dois admettre que je ne connais pas la meilleure réponse. Cependant, si vous avez une certaine application à l'esprit, vous pouvez choisir un bon ensemble de propriétés/mesures à tester, et travailler avec celles-ci - cela semble être la façon dont les cryptographes gèrent les choses.

Answer 4

Il y a beaucoup de théorie sur le test du caractère aléatoire. Pour un test très simple sur un algorithme de mélange de cartes, vous pourriez effectuer un grand nombre de mélanges et ensuite effectuer un test du chi carré pour vérifier que la probabilité que chaque carte se retrouve dans une position quelconque est uniforme. Mais cela ne permet pas de vérifier que les cartes consécutives ne sont pas corrélées, et il faudrait donc également effectuer des tests sur ce point.

Le volume 2 de Knuth's Art of Computer Programming donne un certain nombre de tests que vous pourriez utiliser dans les sections 3.3.2 (Tests empiriques) et 3.3.4 (Le test spectral) et la théorie qui les sous-tend.

Answer 5

Mélangez beaucoup, puis enregistrez les résultats (si je lis correctement). Je me souviens avoir vu des comparaisons de "générateurs de nombres aléatoires". Ils le testent juste encore et encore, puis font un graphique des résultats.

S'il est vraiment aléatoire, le graphique sera en grande partie régulier.