Tests Diehard

Les tests Diehard consistent en une batterie de tests statistiques permettant de mesurer la qualité d'un générateur de nombres aléatoires. Ils ont été élaborés par George MarsagliaGeorge Marsaglia pendant plusieurs années et publiés pour la première fois en 1995 sur un CD-ROM de nombres aléatoires.

Vue d'ensemble des tests

Plusieurs types de tests Diehard sont associés^{[réf. nécessaire]} :

• le test d'espacements des anniversaires : choix de points au hasard sur un grand intervalle. L'espacement entre les points doit être réparti de manière exponentielle et asymptotique. Le nom du test est inspiré du paradoxe des anniversaires ;
• le test de chevauchement des permutations : analyse des séquences de cinq nombres aléatoires consécutifs. Les 120 ordres possibles doivent se produire avec une probabilité statistiquement égale ;
• le test de rangs de matrices : calcul du rang de matrices composées de bits provenant des nombres générés par le générateur de nombre aléatoire à tester et comptage de la fréquence des rangs de matrice ;
• le test OPSO : traiter des séquences de bits comme des mots. Compter le nombre de mots superposés dans une même « phrase ». Le nombre de mots qui n'apparaissent pas dans ce compte devraient suivre une loi connue. Le nom de ce test vient du théorème du singe infini ;
• le test de flux binaire : on compte le nombre de mots qui "manquent" dans un alphabet de deux lettres (0 et 1). Le nombre de mots manquants devrait suivre une loi normale connue ;
• le test de la place de parking : placer de manière aléatoire des cercles unitaires dans un carré de côté 100. Un cercle est « garé » correctement s'il n'est superposé à aucun autre cercle correctement garé. Après 12 000 essais, le nombre de cercles garés correctement devrait suivre une loi normale;
• le test de la distance minimale : Placer de manière aléatoire 8 000 points dans un carré de côté 10 000. Ensuite, déterminer la plus petite distance entre une paire de points. Le carré de cette distance devrait suivre une loi exponentielle, d'une certaine manière^{[C'est-à-dire ?]} ;
• le test de compression : multiplier 231 par des nombres décimaux aléatoires compris entre 0 et 1. Répéter le procédé 100 000 fois. Le nombre de calculs nécessaires pour atteindre 1 devrait suivre une certaine loi ;
• le test du craps : Faire 200 000 parties de craps. Compter le nombre de parties gagnées et le nombre de lancers par partie. Chacun des deux comptes (le nombre de parties jouées et le nombre de dés lancés) devrait suivre une certaine loi.

Descriptions des tests

Test d'espacement des anniversaires

Un nombre m d'anniversaires est choisi dans une année de n jours, en indiquant l'espacement entre les anniversaires. Si j est le nombre de valeurs qui apparaissent plus d'une fois dans cette liste, alors j peut-être approché par la loi de Poisson de moyenne m³ ÷ (4n). L'expérience montre que n doit être assez grand, disons n ≥ 2¹⁸, pour comparer les résultats à la loi de Poisson avec cette moyenne. Ce test utilise n = 2²⁴ et m = 2⁹, de sorte que la loi sous-jacente pour j est considérée comme étant de Poisson avec λ = 2¹⁷ ÷ 2²⁶ = 2. Un échantillon de 500 valeurs est prélevé et un test d'ajustement du χ² fournit une valeur p. 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 p et les neuf valeurs p 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

Le test du chevauchement à cinq permutations : c'est le test OPERM5. Il examine une séquence d'un million d'entiers aléatoires de 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 5^e, 6^e, 7^e... nombres fournissent chacun un état. Comme plusieurs milliers de transitions d'états sont observées, des comptes cumulatifs sont faits du nombre d'occurrences de chaque état. 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. Vous ne devriez donc pas être surpris par des valeurs p occasionnelles proches de 0 ou 1, comme 0,0012 ou 0,9983. Lorsqu'un flux binaire est vraiment GRAND, vous obtiendrez 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 ». Nous nous attendons à ce qu'un certain nombre de ces événements ps 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

On choisit le bit le plus à gauche de 31 nombres entiers générés aléatoirement par le GNR et on forme une matrice binaire de 31 par 31 et on détermine le rang. Ainsi on va compter quels sont les rangs obtenus sur 40 000 matrices générées par le GNR (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

OPSO vient de l'anglais Overlapping-pairs-sparse-occupancy qui veut dire « cumul de paires éparpillées ». 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 2¹⁰ = 1024) d'un entier de 32 bit donné par notre générateur congruentiel.

Et parmi tous les mots qu'il est possible de former avec un tel alphabet, notre test va compter le nombre de mots qui n'apparaissent pas. Cela se déroule comme suit :

Le générateur à tester va générer une séquence de 2²¹ entrées (lettres) ; cette séquence va donc contenir des mots de 2 lettres les uns à la suite des autres et notre 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 GNR donne effectivement des nombres aléatoires.

Test de flux binaire

Le fichier testé est vu comme un flux binaire. On les appelle $b_{1}$, $b_{2}$… 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 $b_{1}b_{2}\dots b_{20}$, le second mot est $b_{2}b_{3}\dots b_{21}$, 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 $2^{21}$ caractères contenant des mots de 20 caractères se chevauchant.

Il y a $2^{20}$ mots de 20 lettres possibles. Pour une chaîne de caractère vraiment aléatoire de $2^{21}+19$ bits, le nombre de mots manquants $X$ 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 $Y=(X-141909)/428$ devrait suivre une loi normale centrée réduite. Le test est répété 20 fois.

Test des places de parking

Dans un carré de côté 100, on "gare" (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, 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 basé sur un échantillon de 10.

Test des distances minimales

On effectue 100 fois l'opération suivante :

- choisir $n=8000$ points aléatoires dans un carré de côté 10000 ;

- trouver $d$, la distance minimale entre les $(n^{2}-n)/2$ paires de points (soit 31 996 000 si on considère toujours $n=8000$).

Si tous les points ainsi générés sont totalement indépendants, alors $d^{2}$, 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, $1-\exp(-d^{2}/0.995)$ devrait être uniforme sur $[0,1)$ 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 8000 points aléatoires dans un carré de 10000x10000.

Test des sphères aléatoire

On prend 4000 points aléatoires dans un cube de 1000 côté. À 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 $120\pi /3$. 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 4000 de ces sphères 20 fois. Chaque rayon minimal au carré mène à une variable uniforme par moyenne de $1-\exp(-r^{3}/30)$. Ensuite un test de Kolmogorov-Smirnov est réalisé sur les 20 valeurs de p.

Test de compression

On prend des nombres entiers aléatoires, on les transforme en décimaux pour obtenir des uniformes $[0,1)$. On commence avec $k=2^{31}=2147483648$, le test trouve $j$, le nombre d’itérations nécessaires pour réduire $k$ à 1 en utilisant la réduction $k=\lceil k\cdot U\rceil$, avec $U$ donné par entier décimal du fichier qui est testé. De tels $j$ sont trouvés 100000 fois, ensuite les comptes du nombre de fois où $j$ était ≤ 6, 7, …, 47, ≥ 48 sont utilisés pour donner un test du χ² pour la fréquence des cellules.

Test du craps

Dans ce test, on joue 200000 parties de craps. On compte ensuite le nombre de victoires et le nombre de lancers nécessaires pour terminer chaque partie. Le nombre de victoires devrait être très proche d'une loi normale de moyenne $200000p$ et de variance $200000p(1-p)$, avec $p=244/495$. Le nombre de lancers nécessaires pour compléter/gagner une partie peut varier de 1 à l'infini, mais tous les comptages supérieurs à 21 sont regroupés dans les comptes de parties à 21 lancers. Un test du chi-carré est effectué sur les comptes de nombres de lancers. Chaque entier de 32 bits du fichier de test donne une valeur pour le lancer d'un dé, qui est une décimale comprise entre [0 et 1), que l'on multiplie par 6, et on prend ensuite 1 + la partie entière de la valeur calculée.

Articles connexes

• Test spectral
• George MarsagliaGeorge Marsaglia
• Randomness test (en)

Liens externes

• « The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness » [archive du 25 janvier 2016], Florida State University, 1995
• Robert G. Brown, « Dieharder: A Random Number Test Suite »
• Alfréd Rényi, « On the theory of order statistics », Acta Mathematica Hungarica, vol. 4, n^os 3–4,‎ 1953, p. 191–231 (DOI 10.1007/BF02127580)