# Tests Diehard

Les tests Diehard sont 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. En 2006, les tests diehard originaux ont été étendus pour former les tests dieharder. Cette extension intègre également les tests de Statistical Test Suite (STS) du NIST. 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. Les tests diehard ont également été utilisés pour examiner les performances des générateurs de nombres aléatoires eux-mêmes.

## Historique

Une première série de tests de hasard pour les générateurs de nombres aléatoires a été proposée en 1969 dans la première édition de The Art of Computer Programming par Donald Knuth. Ces tests de Knuth ont ensuite été remplacés par les 15 tests Diehard de George Marsaglia (1995). L’impossibilité de modifier les paramètres des tests ou d’en ajouter de nouveaux a conduit à la création de la bibliothèque TestU01 (en), introduite en 2007 par Pierre L'Ecuyer et Richard Simard de l'Université de Montréal.

## Ensemble des tests

Voici les principaux tests inclus dans cette batterie$^,$ :
* test d'espacement des anniversaires ;
* test du chevauchement des permutations ;
* classements/rangs de matrices binaires ;
* test OPSO ;
* test de flux binaire ;
* test des places de parking ;
* test des distances minimales ;
* test des sphères aléatoires ;
* test de compression ;
* test des sommes chevauchantes ;
* test de RUNS ;
* test du craps.
Chaque test Diehard applique une méthode pour évaluer différentes caractéristiques de l’aléatoire, telles que la distribution des valeurs, les séquences répétitives et les écarts dans la répartition des résultats.

## 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 ${\dfrac {m^{3}}{4n}}$. L'expérience montre que $n$ doit être assez grand, par exemple $n\geq 2^{18}$, pour comparer les résultats à la loi de Poisson avec cette moyenne. Ce test utilise $n=2^{24}$ et $m=2^{9}$, de sorte que la loi sous-jacente pour $j$ est considérée comme étant de Poisson avec $\lambda ={\frac {2^{27}}{2^{26}}}=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

OPERM5 est un 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, 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 générateur de nombres aléatoires (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

On choisit les 31 bits les plus à gauche de 31 nombres entiers générés aléatoirement par le générateur de nombres aléatoires (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

OPSO vient de l'anglais Overlapping-pairs-sparse-occupancy, qui veut dire « cumul de paires éparpillées ». Ce test repose sur l'analyse de mots de deux 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^{10}=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 compte 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 $2^{21}$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

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ères 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={\frac {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 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 du comportement d’une telle courbe est complexe, 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'entré à un KSTEST fondé 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é 10 000 ;
* 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 \left({\frac {-d^{2}}{0.995}}\right)$ 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 8 000 points aléatoires dans un carré de 10 000 × 10 000.

## Test des sphères aléatoire

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 ${\frac {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 4 000 de ces sphères 20 fois. Chaque rayon minimal au carré mène à une variable uniforme par moyenne de $1-\exp \left({\frac {-r^{3}}{30}}\right)$. Ensuite un test de Kolmogorov-Smirnov est réalisé sur les 20 valeurs de p.

## Test de compression

Des nombres entiers aléatoires sont transformés en nombres flottants pour obtenir des valeurs uniformes dans l'intervalle $[0,1)$. En commençant avec $k=2^{31}=2147483648$, le test détermine $j$, le nombre d’itérations nécessaires pour réduire $k$ à 1 en utilisant la formule de réduction $k=\lceil k\cdot U\rceil$, où $U$ est un nombre décimal extrait du fichier testé. Cette procédure est répétée 100000 fois. Les occurrences des valeurs de $j$ (≤ 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 des sommes chevauchantes

Les entiers sont convertis en nombres flottants pour obtenir une séquence de variables uniformes $U(1),U(2),\ldots$ dans l'intervalle $[0,1)$. Ensuite, des sommes chevauchantes sont formées de la manière suivante : $S(1)=U(1)+\ldots +U(100),\quad S(2)=U(2)+\ldots +U(101),\ldots$ Les valeurs de $S$ suivent une distribution approximativement normale avec une certaine matrice de covariance. Une transformation linéaire des $S$ les convertit en une séquence de variables normales standards indépendantes, qui sont ensuite converties en variables uniformes pour un test de Kolmogorov-Smirnov. Les p-valeurs obtenues de dix tests de Kolmogorov-Smirnov successifs sont soumises à un autre test de Kolmogorov-Smirnov pour l'évaluation finale.

## Test de RUNS

Le test des RUNS est un test statistique qui compte les séquences croissantes (« runs up ») et décroissantes (« runs down ») dans une suite de variables uniformes dans l’intervalle $[0,1)$, obtenues en convertissant en nombres flottants les entiers de 32 bits contenus dans le fichier spécifié. Voici un exemple de comptage des séquences : 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 contient une séquence croissante de longueur 3, une séquence décroissante de longueur 2 et une autre séquence croissante d’au moins 2 (selon les valeurs suivantes). Les matrices de covariance des séquences croissantes et décroissantes sont bien connues, ce qui permet d'effectuer des tests du chi-deux ($\chi ^{2}$) pour des formes quadratiques dans les inverses faibles de ces matrices de covariance. Les séquences sont analysées sur des segments de 10 000 nombres et cette opération est répétée dix fois. Ensuite, le test est de nouveau appliqué pour obtenir des données plus fiables sur la distribution des séquences.

## Test du craps

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 $200000p$ et une variance de $200000p(1-p)$, où $p={\frac {244}{495}}$. 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é.