Tests Diehard

Un article de Wikipédia, l'encyclopédie libre.

Les tests Diehard désigne 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 (en) 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 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 m3 ÷ (4n). L'expérience montre que n doit être assez grand, disons n ≥ 218, pour comparer les résultats à la loi de Poisson avec cette moyenne. Ce test utilise n = 224 et m = 29, de sorte que la loi sous-jacente pour j est considérée comme étant de Poisson avec λ = 217 ÷ 226 = 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[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ées, 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 ?], l'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]

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

Test du craps[modifier | modifier le code]

Dans ce test, on joue 200 000 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 et de variance , avec . 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 khi 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.

Notes et références[modifier | modifier le code]

  1. (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]