Tests Diehard — Wikipédia
Les tests Diehard désignent une série de tests statistiques permettant de mesurer la qualité d'un générateur de nombres aléatoires. Ils ont été élaborés par George Marsaglia pendant plusieurs années puis publiés pour la première fois en 1995 sur un CD-ROM de nombres aléatoires[1].
Leur objectif est de différencier une série de chiffres aléatoires d'une série de chiffres déterminés par l'application d'une séquence d'opérations.
Test d'espacement des anniversaires
[modifier | modifier le code]Un nombre d'anniversaires est choisi dans une année de jours, en indiquant l'espacement entre les anniversaires. Si est le nombre de valeurs qui apparaissent plus d'une fois dans cette liste, alors peut-être approché par la loi de Poisson de moyenne . L'expérience montre que doit être assez grand, disons , pour comparer les résultats à la loi de Poisson avec cette moyenne. Ce test utilise et , de sorte que la loi sous-jacente pour est considérée comme étant de Poisson avec . Un échantillon de 500 valeurs est prélevé et un test d'ajustement du χ² fournit une valeur . Le premier test utilise les bits 1-24 (en comptant à partir de la gauche) à partir des nombres entiers du fichier spécifié. Ensuite, le fichier est fermé et rouvert. Ensuite, les bits 2-25 sont utilisés pour fournir les anniversaires, puis 3-26 et ainsi de suite jusqu'aux bits 9-32. Chaque ensemble de bits fournit une valeur et les neuf valeurs fournissent un échantillon pour réaliser un test de modèle de points par test de Kolmogorov-Smirnov en utilisant les valeurs de la fonction K (Ktest).
Test du chevauchement des permutations
[modifier | modifier le code]OPERM5 désigne le test du chevauchement à cinq permutations. Il examine une séquence d'un million d'entiers aléatoires codés sur 32 bits. Chaque ensemble de cinq entiers consécutifs peut se trouver dans l'un des 120 états, pour les 5 ordres possibles de cinq nombres. Ainsi, les 5e, 6e, 7e... nombres fournissent chacun un état. Comme plusieurs milliers de transitions d'états sont observés, des comptes cumulatifs du nombre d'occurrences de chaque état sont effectués. Ensuite, la forme quadratique dans l'inverse faible de la matrice de covariance 120×120 donne un test équivalent au test du rapport de vraisemblance selon lequel les 120 nombres de cellules proviennent de la loi normale spécifiée (asymptotiquement) avec la matrice de covariance 120×120 spécifiée (avec le rang 99). Cette version utilise 1 000 000 entiers, deux fois. Ce test peut présenter des biais systématiques se traduisant par des valeurs p constamment faibles.
La plupart des tests Diehard renvoient une valeur p, qui devrait être uniforme sur [0,1] si le fichier d'entrée contient des bits aléatoires vraiment indépendants. Ces p-valeurs sont obtenues par p = F(X), où F est la loi supposée de la variable aléatoire de l'échantillon X - souvent normale. Mais ce F supposé n'est qu'une approximation asymptotique, pour laquelle l'ajustement sera le plus mauvais dans les queues. D'occasionnelles valeurs de p proches de 0 ou 1, comme 0,0012 ou 0,9983, ne sont donc pas absurdes. Lorsqu'un flux binaire est vraiment grand[C'est-à-dire ?], on obtient des p de 0 ou 1 à six endroits ou plus. Comme il existe de nombreux tests, il n'est pas improbable qu'un p < 0,025 ou un p > 0,975 signifie que le RNG a « échoué le test au niveau 0,05 ». Il est probable qu'un certain nombre de ces événements se produisent parmi les centaines d'événements produits par Diehard, même à condition que le générateur de nombres aléatoires soit parfait.
Classements/rangs de matrices binaires
[modifier | modifier le code]On choisit les 31 bits les plus à gauche de 31 nombres entiers générés aléatoirement par le RNG et on forme ainsi une matrice binaire de 31 par 31 dont on détermine le rang. On comptabilise les rangs obtenus sur 40 000 matrices générées par le RNG (les rangs possibles vont de 0 à 31 mais il est rare d'obtenir un rang inférieur à 28 pour une matrice générée), on compte la fréquence des rangs obtenus et on opère un test du χ² sur ces résultats. On peut procéder de la même façon avec des matrices de 32 par 32 avec cette fois-ci les matrices générées avec un rang inférieur à 29 qui sont peu probables.
Test OPSO
[modifier | modifier le code]OPSO vient de l'anglais « Overlapping-pairs-sparse-occupancy » qui veut dire « cumul de paires éparpillées ». Ce test se base sur l'analyse de mots de 2 lettres provenant d'un alphabet particulier de 1024 lettres. Chacune de ces lettres est déterminée par 10 bits (d'où les 1024 lettres possibles car 210 = 1024) d'un entier de 32 bit donné par un générateur congruentiel.
Parmi tous les mots qu'il est possible de former avec un tel alphabet, le test va compter le nombre de mots qui n'apparaissent pas. Le déroulement est le suivant : le générateur à tester va générer une séquence de 221 entrées (lettres); cette séquence va donc contenir des mots de 2 lettres les uns à la suite des autres et le test OPSO va compter le nombre de mots manquants dans la séquence (on rappelle qu'il y a 1024×1024 = 1 048 576 mots de 2 lettres possibles). Le nombre de mots manquant devrait être en moyenne de 141 909 avec un écart type de 290 pour que le RNG donne effectivement des nombres aléatoires.
Test de flux binaire
[modifier | modifier le code]Le fichier testé est vu comme un flux binaire. On les appelle , … On considère un alphabet de deux « lettres », 0 et 1, et on imagine le flux binaire comme une succession de « mots » de 20 lettres se chevauchant.
Ainsi, le premier mot est , le second mot est , et ainsi de suite. Le test de flux binaire compte le nombre de mots de 20 lettres (20 bits) manquant dans une chaîne de caractères contenant des mots de 20 caractères se chevauchant.
Il y a mots de 20 lettres possibles. Pour une chaîne de caractères vraiment aléatoire de bits, le nombre de mots manquants devrait être très proche d'une loi normale de moyenne 141 909 et d'écart type 428. Par conséquent, la variable aléatoire devrait suivre une loi normale centrée réduite. Le test est répété 20 fois.
Test des places de parking
[modifier | modifier le code]Dans un carré de côté 100, on place de manière aléatoire une "voiture" (un cercle de rayon 1). Ensuite, on essaie d'en garer une deuxième, puis une troisième, et ainsi de suite, en veillant à bien placer au hasard chacun de ces points. Si une tentative de garer une voiture cause un "accident" (superposer un point sur un autre), on retente de placer ce point autre part dans le carré. Chaque tentative mène donc soit à un échec soit à une voiture garée correctement. Si on représente deux nombres n et k, respectivement le nombre de tentatives et le nombre de voitures garées correctement, on obtient une courbe qui devrait être similaire à celle que donnée par un générateur de nombres aléatoires parfait. La théorie pour le comportement d'une telle courbe aléatoire étant hors de notre compréhension La théorie pour le comportement d'une telle courbe aléatoire étant hors de notre compréhension[pas clair], et la représentation graphique n'étant pas possible dans la batterie de test Diehard, on utilise une caractérisation simple de cette expérience aléatoire: k, le nombre de voitures garées correctement après n = 12000 essais.
La simulation montre que k devrait être en moyenne égal à 3523 avec un écart type sigma = 21.9, et se trouve très proche d'une loi normale. De ce fait, (k-3523) ÷ 21.9 devrait être une loi normale, centrée et réduite. Une fois convertie en variable uniforme, elle peut fournir des données d'input à un KSTEST fondé sur un échantillon de 10.
Test des distances minimales
[modifier | modifier le code]On effectue 100 fois l'opération suivante :
- choisir points aléatoires dans un carré de côté 10 000 ;
- trouver , la distance minimale entre les paires de points (soit 31 996 000 si on considère toujours ).
Si tous les points ainsi générés sont totalement indépendants, alors , le carré de la distance minimale calculée précédemment, devrait être très proche d'une loi exponentielle de médiane 0.995. De ce fait, devrait être uniforme sur et un KSTEST sur les 100 valeurs obtenues sert de test d'uniformité pour les points aléatoires dans le carré. Les nombres du test valant 0 modulo 5 sont retenues mais le KSTEST est basé sur l'ensemble complet des 100 générations des 8 000 points aléatoires dans un carré de 10 000 × 10 000.
Test des sphères aléatoire
[modifier | modifier le code]On prend 4 000 points aléatoires dans un cube de côté 1 000. À chaque point, on centre une sphère assez large pour atteindre le prochain point le plus proche. Ensuite, le volume de la plus petite de ces sphères est (très proche de) exponentiellement avec une moyenne de . Ainsi le rayon au carré est exponentiel avec une moyenne de 30. La moyenne est obtenue par simulation étendue. Le test des sphères 3D génère 4 000 de ces sphères 20 fois. Chaque rayon minimal au carré mène à une variable uniforme par moyenne de . Ensuite un test de Kolmogorov-Smirnov est réalisé sur les 20 valeurs de p.
Test de compression
[modifier | modifier le code]Des nombres entiers aléatoires sont transformés en nombres décimaux pour obtenir des valeurs uniformes dans l'intervalle . En commençant avec , le test détermine , le nombre d’itérations nécessaires pour réduire à 1 en utilisant la formule de réduction , où est un nombre décimal extrait du fichier testé. Cette procédure est répétée 100000 fois. Les occurrences des valeurs de (≤ 6, 7, ..., 47, ≥ 48) sont ensuite comptabilisées pour réaliser un test du χ², permettant de vérifier la fréquence des différentes catégories.
Test du craps
[modifier | modifier le code]Dans ce test, 200 000 parties de craps sont jouées. Le nombre de victoires et le nombre de lancers nécessaires pour terminer chaque partie sont ensuite comptabilisés. Le nombre de victoires devrait suivre une distribution normale avec une moyenne de et une variance de , où . Le nombre de lancers nécessaires pour terminer une partie peut varier de 1 à l'infini, mais tous les lancers supérieurs à 21 sont regroupés dans une seule catégorie. Un test du khi carré est effectué sur les comptes des nombres de lancers. Chaque entier de 32 bits du fichier de test est converti en une valeur comprise entre [0 et 1), multipliée par 6, puis ajustée en ajoutant 1 à la partie entière de la valeur calculée pour simuler un lancer de dé.
Notes et références
[modifier | modifier le code]- (en) « The Marsaglia Random Number CDROM including the Diehard Battery of Tests », sur web.archive.org, (consulté le ).
Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- « The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness » [archive du ], Florida State University,
- Robert G. Brown, « Dieharder: A Random Number Test Suite »
- Alfréd Rényi, « On the theory of order statistics », Acta Mathematica Hungarica, vol. 4, nos 3–4, , p. 191–231 (DOI 10.1007/BF02127580)