Comment tester le caractère aléatoire (cas de battement de points)

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 hasard, mais les RNGs pauvres ne font généralement pas bien sur elle (ils retourneront quelque chose comme 2,5 ou 3,8 plutôt ~3,14).

idéalement, ce ne serait que l'un des nombreux tests que vous effectueriez pour vérifier le caractère aléatoire.

autre chose que vous pouvez vérifier est le écart-type de la sortie. Attendus écart-type pour une population de valeurs uniformément répartie dans l'intervalle 0..n approches 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;
}

tout d'abord, il est impossible de savoir avec certitude si une certaine sortie finie est "vraiment aléatoire" puisque, comme vous le faites remarquer, n'importe quelle sortie est possible .

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

par exemple, vous pouvez vérifier la sortie de 10 différent mélange. Attribuer un numéro 0-51 à chaque carte, et prendre la moyenne de la carte en position 6 à travers les boutons. La moyenne convergente est de 25,5, donc vous seriez surpris de voir une valeur de 1 ici. Vous pouvez utiliser le théorème de la limite centrale pour obtenir une estimation de la probabilité de chaque moyenne est pour un poste donné.

mais on ne devrait pas s'arrêter là! Parce que cet algorithme pourrait être dupé par un système auquel alterne entre deux remaniements qui sont conçus pour donner l'exacte moyenne 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, à travers des mouvements différents. Donc, parmi les 10 shuffles, nous pourrions essayer de vérifier que les choix 'apparence uniforme.'Il s'agit essentiellement d'une version réduite du problème original. Vous pouvez vérifier que l'écart-type semble raisonnable, que le min est raisonnable, et la valeur max. Vous pouvez également vérifiez que d'autres valeurs, telles que les deux cartes les plus proches (par nos numéros assignés), ont aussi du sens.

mais nous ne pouvons pas non plus simplement ajouter diverses mesures comme cette Ad infinitum, puisque, avec suffisamment de statistiques, tout battement particulier apparaîtra hautement improbable pour une raison quelconque (par exemple,c'est l'un des très rares battements dans lequel les cartes X,Y, Z apparaissent dans l'ordre). Alors la grande question est: qui est le bon ensemble de mesures à prendre? Ici, je dois admettre que je ne sais pas le meilleur 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 ceux-là -- cela semble être la façon dont les cryptographes traitent les choses.

il y a beaucoup de théorie pour tester le hasard. Pour un test très simple sur un algorithme de brassage de carte vous pourriez faire beaucoup de brassage et ensuite exécuter un test de chi carré que la probabilité de chaque carte qui apparaît dans n'importe quelle position était uniforme. Mais cela ne teste pas que les cartes consécutives ne sont pas corrélées, donc vous voudriez aussi faire des tests sur cela.

Volume 2 de Knuth Art of Computer Programming donne un certain nombre de tests que vous pourriez utiliser dans les sections 3.3.2 (Essais empiriques) et 3.3.4 (essai Spectral) et la théorie qui les sous-tend.

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

S'il est vraiment aléatoire le graphique sera la plupart du temps Pair.

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 essayer de prédire les données Futures, et ensuite de montrer que l'incertitude, ou l'entropie, de ses prédictions tend vers le maximum (c.-à-d. la distribution uniforme) dans le temps. Bien sûr, vous serez toujours incertain si votre modèle a capturé ou non tout le contexte nécessaire; étant donné un modèle, il sera toujours possible de construire une seconde modèle qui génère des données non aléatoires qui semblent aléatoires à la première. Mais aussi longtemps que vous acceptez que L'orbite de Pluton a une influence insignifiante sur les résultats de l'algorithme de brassage, alors vous devriez être en mesure de vous assurer que ses résultats sont aléatoire acceptable.

bien sûr, si vous faites cela, vous pouvez aussi bien utiliser votre modèle de manière générale , pour créer les données que vous voulez. Et si tu fais ça, tu es de retour à la case départ.

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

supposons que vous avez un algorithme qui génère l'aléatoire. Maintenant, comment voulez-vous tester?

Que voulez-vous dire? Si vous supposez que vous pouvez générer l'aléatoire, il n'y a pas besoin de le tester.

une fois que vous avez un bon générateur de nombres aléatoires, la création d'une permutation aléatoire est facile (par exemple, appelez vos cartes 1-52. Générer 52 nombres aléatoires l'attribution à chacun d'une carte dans l'ordre, puis les trier en fonction de votre 52 randoms) . 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 pour les gens à discuter de cette question dans un contexte spécifique.

test 52! les possibilités sont évidemment impossibles. Au lieu de cela, essayez votre mélange sur de plus petits nombres de cartes, comme 3, 5, et 10. Ensuite, vous pouvez tester des milliards de shuffles et utiliser un histogramme et le test statistique du chi carré pour prouver que chaque permutation est à venir un nombre "pair" de fois.

pas de code jusqu'à présent, donc je copie-coller une partie de test de ma réponse à la question originale.

  // ...
  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 pseudorandom sous-jacent. Tester le caractère aléatoire de PRNG est une branche entière de la science.

pour un test rapide, vous pouvez toujours essayer la compression. Une fois qu'il ne comprime pas, vous pouvez passer à d'autres tests.

j'ai essayé dieharder mais il refuse de travailler pour un shuffle. Tous les tests échouent. Il est également très stodgy, il ne vous permettra pas de spécifier la gamme de valeurs que vous voulez ou quelque chose comme ça.

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

le programme d'Installation (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 a terminé à une certaine position. Répétez ceci un grand nombre de fois (je commencerais avec 1000, mais les gens mieux à la statistique que moi peuvent donner un meilleur nombre).

analyser la matrice

si nous avons le hasard parfait et exécutez le mélange un nombre infini de fois puis pour chaque carte et pour chaque position le nombre de fois où la carte a fini 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.

donc je calculerais à quelle distance de ce nombre nous sommes.