Comment tester le caractère aléatoire (exemple concret - Shuffling)

Question

Tout d'abord, cette question est extraite de ce question.Je l'ai fait parce que je pense que cette partie est plus grande qu'une sous-partie d'une question plus longue.Si cela vous offense, veuillez m'excuser.

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

Pour ajouter une théorie au problème - un jeu de cartes peut être mélangé en 52!(factorielle 52) de différentes manières.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épondre:1/52 !.

Quelle est la chance qu'après avoir mélangé, vous obteniez A, K, Q, J...de chaque costume dans une séquence ?Réponse 1/52 !

Ainsi, le simple fait de mélanger une fois et de regarder le résultat ne vous donnera absolument aucune information sur le caractère aléatoire de vos algorithmes de brassage.Deux fois et vous avez plus d'informations, Trois même plus...

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

Answer 1

Statistiques.La norme de facto pour tester les RNG est le Suite irréductible (à l'origine disponible sur http://stat.fsu.edu/pub/diehard).Alternativement, le Programme Ent 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 (voir Collections.shuffle).

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

Answer 2

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

Idéalement, ce ne serait qu’un des nombreux tests que vous exécuteriez 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 uniformément distribuée de valeurs dans la plage 0..n s'approche 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

Premièrement, il est impossible de savoir avec certitude si une certaine sortie finie est « vraiment aléatoire » puisque, comme vous le soulignez, n'importe quelle sortie est possible.

Ce qui peut être fait, c'est prendre une séquence de sorties et vérifier diverses mesures de cette séquence par rapport à ce qui est plus probable.Vous pouvez dériver 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 numéro de 0 à 51 à chaque carte et faites la moyenne de la carte en position 6 au fil des mélanges.La moyenne convergente est de 25,5, vous seriez donc surpris de voir ici une valeur de 1.Vous pouvez utiliser le théorème central limite pour obtenir une estimation de la probabilité que chaque moyenne soit pour une position donnée.

Mais il ne faut pas s'arrêter là !Parce que cet algorithme pourrait être trompé par un système qui n'alterne qu'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 une carte donnée) à chaque position, sur différents mélanges.Ainsi, parmi les 10 agriculteurs, nous pourrions essayer de vérifier que les choix ont "l'air uniforme". Il s'agit essentiellement d'une version réduite du problème d'origine.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 (par les numéros attribués), ont également un sens.

Mais nous ne pouvons pas non plus simplement ajouter diverses mesures comme celle-ci à l'infini, car, avec suffisamment de statistiques, tout mélange particulier semblera hautement improbable pour une raison quelconque (par ex.c'est l'un des rares mélanges dans lesquels les cartes X, Y, Z apparaissent dans l'ordre).La grande question est donc :quelle est la bonne série de mesures à prendre ?Ici, je dois admettre que je ne connais pas la meilleure réponse.Cependant, si vous avez une certaine application en tête, 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 existe de nombreuses théories sur les tests du caractère aléatoire.Pour un test très simple sur un algorithme de mélange de cartes, vous pouvez effectuer de nombreux mélanges, puis exécuter un test du chi carré pour vérifier que la probabilité que chaque carte apparaisse dans n'importe quelle position est uniforme.Mais cela ne vérifie pas que les cartes consécutives ne sont pas corrélées, vous voudriez donc également faire des tests à ce sujet.

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

Answer 5

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

Si c'est vraiment aléatoire, le graphique sera en grande partie pair.

Answer 6

La seule façon de tester le caractère aléatoire est d'écrire un programme qui tente de construire un modèle prédictif pour les données testées, puis d'utiliser ce modèle pour tenter de prédire les données futures, puis de montrer que l'incertitude, ou l'entropie, de ses prédictions tendent vers le maximum (c'est-à-direla distribution uniforme) au fil du temps.Bien entendu, vous ne saurez toujours pas si votre modèle a capturé ou non tout le contexte nécessaire ;étant donné un modèle, il sera toujours possible de construire un deuxième modèle qui génère des données non aléatoires qui semblent aléatoires par rapport au premier.Mais tant que vous acceptez que l’orbite de Pluton a une influence insignifiante sur les résultats de l’algorithme de brassage, vous devriez alors pouvoir vous assurer que ses résultats sont suffisamment aléatoires.

Bien sûr, si vous faites cela, autant utiliser votre modèle de manière générative, pour créer réellement les données souhaitées.Et si vous faites cela, vous revenez à la case départ.

Answer 7

Je ne suis pas entièrement votre question.Vous dites

Supposons que vous disposiez d’un algorithme qui génère du hasard.Maintenant, comment le tester ?

Que veux-tu dire?Si vous pensez pouvoir générer du hasard, il n’est pas nécessaire de le tester.

Une fois que vous disposez d’un bon générateur de nombres aléatoires, créer une permutation aléatoire est facile (par ex.Appelez vos cartes 1-52.Générez 52 nombres aléatoires en attribuant chacun à une carte dans l'ordre, puis triez en fonction de vos 52 nombres aléatoires).Vous n'allez pas détruire le caractère aléatoire de votre bon RNG en générant votre permutation.

La question difficile est de savoir si vous pouvez faire confiance à votre RNG. Voici un exemple de lien vers des personnes discutant de ce problème dans un contexte spécifique.

Answer 8

Test 52 !les possibilités sont bien sûr impossibles.Essayez plutôt de mélanger un plus petit nombre de cartes, comme 3, 5 et 10.Ensuite, vous pouvez tester des milliards de mélanges et utiliser un histogramme et le test statistique du chi carré pour prouver que chaque permutation apparaît un nombre « pair » de fois.

Answer 9

Pas de code pour l'instant, donc je copie-colle une partie test de ma réponse à la question initiale.

  // ...
  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;    
  }

Ce code ne teste pas le caractère aléatoire du générateur de nombres pseudo-aléatoires sous-jacent.Tester le caractère aléatoire du PRNG est toute une branche de la science.

Answer 10

Pour un test rapide, vous pouvez toujours essayer de le compresser.Une fois qu'il n'est pas compressé, vous pouvez passer à d'autres tests.

J'ai essayé plus fort mais il refuse de fonctionner pour un mélange.Tous les tests échouent.C'est aussi très lourd, il ne vous permettra pas de spécifier la plage de valeurs que vous souhaitez ou quelque chose comme ça.

Answer 11

En y réfléchissant moi-même, ce que je ferais serait quelque chose comme :

Configuration (Pseudo-code)

// 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]++;
}

Cela nous donne une matrice 52x52 indiquant combien de fois une carte s'est retrouvée à une certaine position.Répétez cette opération un grand nombre de fois (je commencerais par 1000, mais des personnes meilleures que moi en statistiques peuvent donner un meilleur chiffre).

Analyser la matrice

Si nous avons un caractère aléatoire parfait et effectuons le mélange un nombre infini de fois, alors pour chaque carte et pour chaque position, le nombre de fois où la carte s'est retrouvée dans cette position est le même que pour toute autre carte.Dire la même chose d'une manière différente :

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

Je calculerais donc à quelle distance nous sommes de ce chiffre.