1.7 Le test des triplets (Marsaglia)

1.7.1 Un échec notoire : générateur additif simple

Les tests précédents (longueur de la période, paramètres de dispersion, test du , structure réticulaire) ont été conduits de façon "commutative" c'est à dire ne prenant pas en compte l'ordre dans lequel les différentes instanciations sont obtenues. Or, de toute évidence, cet ordre n'est pas indifférent : on souhaite que les instanciations successives se comportent comme autant de variables aléatoires indépendantes et cela en dépit du fait que les générateurs pseudo aléatoires usuels sont fondés sur des processus tout à fait déterministes.

Les tests précédents constituent un premier filtre, mais ne constituent pas à eux seuls une garantie contre d'énormes déconvenues. Reprenons l'étude du "générateur de Fibonacci" dont nous avons précédemment examiné la période (section 1.2.4).

La figure 1.9 (gauche) donne l'histogramme des moyennes par lots pour une génération de 100 lots de 100 instanciations, tandis que la figure 1.9 (droite) donne l'histogramme correspondant aux variances par lots. Le test du donne un score de 78% pour l'histogramme des fréquences (non représenté), et des scores de 43% et 93% pour les histogrammes de la figure 1.9. Si l'on compare avec les histogrammes et les scores obtenus par le générateur lgm de l'algorithme 2, on peut certes constater que les histogrammes de rand_fib sont un peu moins réguliers, mais cela ne va pas jusqu'à provoquer un rejet par le test du .

Figure 1.9: 'Etude statistique du générateur additif simple.

[Moyennes par lots][Variances par lots]

Considérons maintenant les triplets formés par trois instanciations successives de notre générateur. Nous dirons qu'un triplet est du type lorsque , et ainsi de suite pour les 6 façons dont peuvent s'ordonner 3 nombres distincts. Il est clair que les probabilités de ces divers ordonnancements sont exactement égales pour des instanciations indépendantes d'une variable aléatoire uniformément répartie, et on peut donc s'attendre à ce que les fréquences de ces 6 ordres possibles soient à peu près égales.

Or on constate au contraire sur la figure 1.10 que les triplets formés à partir des instanciations précédentes ne sont jamais du type ou , les 4 autres types ayant à peu près la même fréquence. Supposons en effet que . On ne peut avoir et on aurait par conséquent . Mais en même temps, et on aurait donc donc également ! On en conclut que le générateur rand_fib est un très mauvais générateur, et ne doit pas être utilisé.

Figure 1.10: Les 6 types d'ordre ne sont pas tous obtenus.

1.7.2 Le test du singe

Le problème que nous devons résoudre est donc celui de vérifier si les valeurs fournies par un générateur sont non seulement uniformément réparties, mais présentent également une inter-indépendance suffisante. Rappelons que cette vérification est d'autant plus indispensable que la plupart des générateurs non uniformes utilisent à chaque étape plusieurs valeurs successives issues du même générateur uniforme, en supposant acquise l'inter-indépendance de ces valeurs.

Une façon de tester cette inter-indépendance est le "test du singe" [44][44] : si nous imaginons un singe tapant au hasard sur un clavier de touches, il doit engendrer tous les triplets de trois lettres possibles, avec une probabilité égale à pour chacun d'eux. Nous pouvons par exemple utiliser comme "formule du singe dactylographe", c'est à dire recourir à l'algorithme 9. Il est clair qu'une telle formule ne teste que les bits de poids fort du générateur. Pour tester aussi les bits suivants, on peut soit augmenter , soit décaler la "fenêtre d'examen", par exemple en utilisant la formule .

Le test se déroule alors de la façon suivante (algorithme 10) : on choisit le nombre de "lettres du clavier" (ici ), on choisit une espérance pour le nombre d'apparitions d'un triplet donné, et on utilise le générateur pour engendrer triplets de lettres.

On obtient les histogrammes de la figure 1.11 : celui de gauche donne, pour chaque mot de deux lettres, le quotient de son nombre d'occurences effectives par la valeur attendue (ici ), tandis que celui de droite donne, pour chaque mot de trois lettres, le quotient de son nombre d'occurences effectives par la valeur attendue (ici ).

Figure 1.11: Avec 6 lettres : histogrammes des 36 doublets et des 216 triplets.

[Les doublets]

[Les triplets.]

On constate que chaque mot est apparu au moins une fois, et plus précisément au moins fois (pour une espérance de ). Pour une analyse statistique plus précise, il faut commencer par remarquer que l'on ne peut appliquer directement le test du à chacun des histogrammes de la figure 1.11. En effet, une apparition plus fréquente que la moyenne d'un triplet donné influe sur les fréquences d'apparition des triplets ayant le même doublet initial que le triplet donné.

En fait, une analyse statistique précise (Marsaglia) permet d'aboutir au résultat suivant. Appelons et les nombres d'apparitions d'un doublet ou d'un triplet donné, et posons

alors la quantité doit vérifier la loi du avec degrés de libertés. Pour notre exemple, on trouve , et un score de au test du .