8

Generateurs de nombres aleatoires

Ce chapitre peut etre utilise de deux manieres : on peut soit en tirer une ou deux heures

de « flash-science », avec un bagage minimum comprenant neanmoins une certaine fa-

miliarite avec l’arithmetique modulo p, soit traiter le sujet plus en profondeur. Dans ce

cas, il est preferable d’etre deja familier avec les corps finis ou la congruence modulo

2, parce qu’on a au prealable regarde le chapitre 6 (ou le chapitre 7), par exemple. Les

sections faisant reference a ces chapitres sont clairement indiquees. Dans ce chapitre,

nous traiterons longuement des registres a decalage qui sont aussi etudies a la sec-

tion 1.4 du chapitre 1, mais les deux traitements sont independants. Certains exercices

font appel aux probabilites et peuvent etre sautes si on n’a pas de bagage suffisant de

ce cote-la.

8.1 Introduction

Le 10 avril 1994, un joueur est apprehende par la police au Casino de Montreal.Son crime ? Il vient de battre toutes les statistiques possibles en remportant trois lotsconsecutifs au jeu de keno, amassant ainsi plus d’un demi-million de dollars1. Il estclairement soupconne d’avoir enfreint les lois des jeux de hasard interdisant la collu-sion avec les employes du casino, la manipulation des appareils electroniques, etc. Uneenquete est menee et, apres quelques semaines, le joueur est relache et son lot, capitalet interets, lui est remis. Et le Casino de Montreal a appris une lecon rapide sur lesgenerateurs de nombres aleatoires.

Il reste fort peu d’appareils mecaniques dans les casinos modernes. Seule peut-etrela roulette demeure. Les autres jeux ont ete remplaces par des ordinateurs qui simulent

1Au keno, le joueur doit choisir une dizaine de nombres dans l’ensemble {1, 2, . . . , 80}. Lecasino tire alors 20 boules parmi 80 boules numerotees de 1 a 80. Ce tirage peut egalementetre fait electroniquement, comme c’est le cas maintenant dans la plupart des casinos. Le lotgagne depend de la mise du joueur et du nombre de coıncidences entre les nombres choisis parle joueur et les numeros des boules tirees au sort.

248 8 Generateurs de nombres aleatoires

le hasard. Tous ont, dans leur programme, un segment produisant des nombres quiapparaissent aleatoires a l’utilisateur, mais qui sont engendres de facon completementdeterministe. Ces algorithmes, les generateurs de nombres aleatoires, jouent un roleimportant dans plusieurs appareils. Outre les jeux de casino, les jeux video en fontgrand usage. Si le comportement de ces jeux etait toujours le meme chaque fois quel’appareil est demarre, le joueur s’en lasserait rapidement.

Les generateurs de nombres aleatoires sont aussi importants dans la vie de tousles jours qu’en science. La modelisation sur ordinateur des cours boursiers ou de lapropagation de virus (humains ou informatiques !) et le choix des quelques (malheu-reux) contribuables dont le gouvernement scrutera la declaration utilisent egalementces generateurs de facon routiniere. En science, il est parfois difficile de modeliser unsysteme dont le comportement n’est connu qu’avec certaines probabilites. Un exempled’un tel systeme est le promeneur impartial se baladant sur la grande toile du Webdecrite a la section 9.2. On presuppose l’existence de generateurs de nombres aleatoireslorsqu’on etudie les algorithmes probabilistes dans le chapitre 7 sur la cryptographie.Les generateurs de nombres aleatoires sont utilises explicitement (!) dans la constructiond’images fractales a l’aide de systemes de fonctions iterees (voir le chapitre 11) et dansle signal des satellites du systeme de positionnement GPS (voir le chapitre 1).

Ces generateurs ont donc de nombreuses applications dans notre societe, et iln’est pas etonnant qu’il se fasse beaucoup de recherche pour trouver de « meilleurs »generateurs de nombres aleatoires. Que signifie « meilleurs » ? Cela depend du contexte.Quand les generateurs de nombres aleatoires servent dans les casinos, on veut que lesjoueurs ne puissent pas deviner leur fonctionnement pour ajuster leur strategie de jeu.Les gerants de casinos veulent aussi que les distributions probabilistes des nombresaleatoires suivent des lois de probabilite choisies a priori pour ne pas etre accuses defraude et d’offrir un jeu inequitable.

Introduisons d’abord un generateur « mecanique » de nombres aleatoires. Quoiqueson utilisation soit impraticable a grande echelle, il illustre tous les defis que devrontrelever les algorithmes informatiques de generateurs. Jouons donc a pile ou face enlancant une piece de monnaie un grand nombre de fois : en notant 0 pour PILE et1 pour FACE, nous obtenons une suite aleatoire de 0 et de 1, c’est-a-dire une suitequi semble n’obeir a aucune regle. Si plusieurs personnes repetent l’experience, ellesobtiennent en general des suites qui n’ont rien a voir les unes avec les autres.

Supposons maintenant que nous voulions generer une suite de nombres aleatoiresde l’ensemble S = {0, . . . , 31}. Etant donne que 32 = 25, chacun des nombres n ∈ Sdevient en base 2

n = a0 + 2a1 + 22a2 + 23a3 + 24a4 =4∑

i=0

ai2i

ou ai ∈ {0, 1}. On le represente par le quintuple (a0, a1, a2, a3, a4). Par exemple, lequintuple (0, 1, 1, 0, 1) represente 2 + 4 + 16 = 22.

8.1 Introduction 249

Si on genere une suite de 0 et de 1 en lancant une piece, on peut ensuite regrouperceux-ci en quintuples de bits dans {0, 1} et les transformer en nombres de S. Par exemple,supposons qu’on ait obtenu la suite

10000 00101 11110 01001 01001 11011. (8.1)

Elle genere la suite

10000︸ ︷︷ ︸

1

00101︸ ︷︷ ︸

20

11110︸ ︷︷ ︸

15

01001︸ ︷︷ ︸

18

01001︸ ︷︷ ︸

18

11011︸ ︷︷ ︸

27

,

soit1, 20, 15, 18, 18, 27

de nombres de S.Si, au lieu de 31, on avait pris N = 2r−1 et S = {0, . . . , N}, on aurait pu transformer

une suite aleatoire de 0 et de 1 en une suite aleatoire d’elements de S.Mais, pour peu que r soit grand ou que l’on veuille une longue suite de nombres

aleatoires, on voit bien que le processus decrit ci-dessus, a savoir lancer la piece un grandnombre de fois, ne convient plus. La solution retenue est de programmer un ordinateurpour qu’il genere une suite de 0 et de 1 de telle sorte que la suite ait l’air aussi aleatoirequ’une vraie suite de resultats du jeu de pile ou face. Un tel programme ou algorithmeest un generateur de nombres aleatoires. En fait, comme l’algorithme qui genere cesnombres est deterministe, la suite de nombres generee n’a que l’apparence d’une suitede nombres aleatoires. C’est pour cela que les specialistes appellent ces algorithmes desgenerateurs de nombres pseudo-aleatoires.

Leur utilisation est egalement tres repandue dans des simulations de toutes sortes.Dans beaucoup de ces cas, on veut generer au hasard des nombres reels de l’intervalle[0, 1]. Dans ce cas-ci, on peut ecrire un nombre reel de [0, 1] a l’aide de son developpementbinaire. Pour differencier le developpement binaire du developpement decimal, on metun indice 2 a la fin de l’ecriture du nombre. Ainsi, (0,a1a2 . . . an)2 represente

(0a1a2 . . . an)2 = a12−1 + a22−2 + · · ·+ an2−n =n∑

i=1

ai

2i.

En general, un nombre reel a un developpement binaire infini, mais comme un ordinateurne peut calculer avec une precision infinie, on se limite a un developpement fini ayantla precision voulue. Ainsi, la suite (8.1) genere la suite de nombres de [0, 1]

0,100002 0,001012 0,111102 0,010012 0,010012 0,110112.

250 8 Generateurs de nombres aleatoires

Les nombres de cette suite sont⎧

⎪⎪⎪⎪⎪⎪⎪⎪⎨

⎪⎪⎪⎪⎪⎪⎪⎪⎩

0,100002 = 2−1 = 12 = 0,5,

0,001012 = 2−3 + 2−5 = 0,15625,0,111102 = 2−1 + 2−2 + 2−3 + 2−4 = 0,9375,0,010012 = 2−2 + 2−5 = 0,28125,0,010012 = 2−2 + 2−5 = 0,28125,0,110112 = 2−1 + 2−2 + 2−4 + 2−5 = 0,84375,

la derniere ecriture etant l’ecriture decimale.Qu’est-ce qu’un bon generateur de nombres aleatoires ? A quels criteres doit-il sa-

tisfaire ? Lorsqu’on lance une piece plusieurs fois, le resultat de chaque lancer estindependant des precedents, et chacun des deux resultats possibles a une probabilitede 1

2 . Cela a comme consequence que, si on lance un grand nombre de fois, on devraitavoir PILE (note 0) une fois sur deux a peu pres et FACE (notee 1) environ une foissur deux : c’est la loi des grands nombres. Si notre experience consiste plutot a lancerla piece deux fois, on a quatre resultats possibles :

00 01 10 11.

Si on repete souvent cette experience de deux lancers consecutifs, on s’attend a obtenirchaque resultat environ une fois sur quatre. De meme, si l’experience consiste a lancerla piece trois fois, on a 23 = 8 resultats possibles equiprobables :

000 001 010 011 100 101 110 111.

Dans le cas d’un generateur de nombres aleatoires, on voudrait que les memes pro-prietes soient respectees. Pour verifier que les generateurs de nombres aleatoires quel’on construit ont bien ces proprietes, on les soumet a une batterie de tests statistiques.

Tous les generateurs de nombres pseudo-aleatoires sont des algorithmes qui generentdes suites periodiques de nombres a partir de conditions initiales en nombre fini.Penchons-nous sur ces suites.

Definition 8.1 Une suite {an}n≥0 est periodique s’il existe un entier M > 0 tel que,pour tout n ∈ N, an = an+M . Le nombre N > 0 minimum ayant cette propriete estappele la periode de la suite. Lorsqu’on voudra mettre l’accent sur cette propriete, onpourra, a l’occasion, appeler N la periode minimale de la suite.

Lemme 8.2 Soit {an}n∈N∪{0} une suite periodique de periode minimale N et soit M ∈N tel que, pour tout n ∈ N, an = an+M . Alors, N divise M .

Preuve Divisons M par N : il existe des entiers q et r tels que M = qN + r et0 ≤ r < N . Montrons que, pour tout n, on a an = an+r.

En effet,

8.1 Introduction 251

an = an+M = an+qN+r = an+r.

Comme N est le plus petit entier tel que an = an+N , necessairement r = 0. Donc, Ndivise M . �

Exemple 8.3 Un generateur de nombres aleatoires tres populaire est le generateurlineaire congruentiel. Il genere des nombres appartenant a E = {1, . . . , p − 1} par laregle

xn = axn−1 (mod p),

ou p premier et a est une racine primitive de Fp, c’est-a-dire un element de E tel que{

ak �≡ 1 (mod p), k < p− 1,ap−1 ≡ 1.

(Rappelons que Fp (aussi appele Zp au chapitre 7) est l’ensemble des entiers {0, . . . , p−1}muni de l’addition et de la multiplication modulo p. Fp est un corps si p est premier ;ceci signifie (voir la definition 6.1 du chapitre 6) que l’addition et la multiplication sontcommutatives et associatives et ont chacune un element neutre, que la multiplication estdistributive sur l’addition, que tout element a un inverse additif et que tout element nonnul a un inverse multiplicatif. L’existence d’un inverse multiplicatif pour tout elementnon nul est la propriete qui nous interesse : elle est demontree a l’exercice 24 du cha-pitre 6, mais on peut l’admettre pour comprendre la suite.)

Prenons comme exemple le cas p = 7. Alors, 2 n’est pas une racine primitive, car23 = 8 ≡ 1 (mod 7), mais 3 en est une, car

⎧

⎪⎪⎪⎪⎪⎪⎨

⎪⎪⎪⎪⎪⎪⎩

32 ≡ 2 (mod 7),33 ≡ 6 (mod 7),34 ≡ 18 ≡ 4 (mod 7),35 ≡ 12 ≡ 5 (mod 7),36 ≡ 15 ≡ 1 (mod 7).

La preuve qu’une racine primitive a existe toujours se trouve au theoreme 7.22 duchapitre 7. (A nouveau, vous pouvez tenir ce resultat pour acquis et poursuivre votrelecture.)

Ce generateur produit une suite periodique de periode exactement p− 1. Les genera-teurs lineaires congruentiels sont employes dans de nombreux logiciels et, par exemple,on utilise souvent p = 231− 1 et a = 16 807, mais ces generateurs ne sont pas juges tresfiables par les experts, car ils ne passent pas les tests statistiques (voir les exercices 2 et4).

D’autres criteres entrent en ligne de compte, notamment des criteres economiques.Dans nombre de cas, on cherche a minimiser le temps de calcul et l’espace-memoire.On se contentera alors de generateurs de nombres aleatoires imparfaits du point de vuestatistique, mais suffisants pour les buts vises.

252 8 Generateurs de nombres aleatoires

8.2 Le registre a decalage

Le registre a decalage (aussi etudie au chapitre 1) est un bon generateur de nombresaleatoires. Il est constitue d’un ruban de r cases contenant des entrees an−1, . . . , an−r,lesquelles sont des 0 ou des 1 (figure 8.1). Sur chacune de ces cases opere un qi ∈ {0, 1}

Fig. 8.1. Un registre a decalage

par multiplication, et les resultats sont ensuite additionnes modulo 2. Les qi sont fixes etcaracterisent le generateur de nombres aleatoires. On genere une suite pseudo-aleatoirede la facon suivante.• On se donne des nombres initiaux a0, . . . , ar−1 ∈ {0, 1} non tous nuls.• Etant donne an−r, . . . , an−1, le registre calcule l’element suivant comme suit :

an ≡ an−rq0 + an−r+1q1 + · · ·+ an−1qr−1 =r−1∑

i=0

an−r+iqi (mod 2). (8.2)

• On decale chacune des entrees vers la droite en oubliant an−r. Le an calcule occupedonc la case de gauche.• On itere le procede.Dans la section 1.4 du chapitre 1, on montre que, si on choisit bien les qi et les

conditions initiales a0, a1, . . . , ar−1, alors on genere une suite de periode 2r − 1. Nousreviendrons plus bas sur cette propriete pour montrer comment on choisit les qi.

Exemple 8.4 Prenons le registre a decalage de quatre cases tel que (q0, q1, q2, q3) =(1, 1, 0, 0). Posons les conditions initiales (a0, a1, a2, a3) = (0, 0, 0, 1). Alors, le registregenere la suite de periode 15

000100110101111︸ ︷︷ ︸

15

0001 . . .

Dans ce cycle de 15 entrees, 0 est sorti sept fois et 1, huit fois. Regardons maintenantles 15 sous-suites possibles de deux entrees : 00 est sortie trois fois

8.2 Le registre a decalage 253

⎧

⎪⎪⎪⎨

⎪⎪⎪⎩

︷︸︸︷

00 0100110101111

0︷︸︸︷

00 100110101111

0001︷︸︸︷

00 110101111,

et les trois autres, soit 01, 10 et 11, sont sorties exactement quatre fois. Dans le cas dela sous-suite 10, la quatrieme occurrence est a cheval sur deux periodes :

⎧

⎪⎪⎪⎪⎪⎪⎨

⎪⎪⎪⎪⎪⎪⎩

000︷︸︸︷

10 0110101111

0001001︷︸︸︷

10 101111

000100110︷︸︸︷

10 1111

00010011010111︷︸︸︷

1 0 001 . . .

De meme, nous laissons le lecteur verifier que chaque sous-suite de trois symboles estsortie deux fois sauf 000 qui n’est sortie qu’une fois. Quant aux sous-suites de quatresymboles, elles sont toutes sorties exactement une fois sauf 0000. Pouvons-nous conti-nuer avec des sous-suites de cinq symboles ? Non, notre registre n’a que quatre cases, sibien que chaque fois que les quatre premiers symboles sont determines, le cinquieme etles suivants le sont aussi. Nous pouvons aussi expliquer pourquoi les sous-suites n’ayantque des 0 apparaissent moins souvent : nous ne pouvons nous permettre d’avoir unesous-suite de la forme 0000 parce que la regle de fonctionnement du registre a decalageforcerait tous les symboles suivants de la suite a etre des zeros.

Cet exemple montre que ce registre a de bonnes proprietes statistiques tant qu’on neconsidere pas des sous-suites trop longues (ici, on se limite a des sous-suites de quatresymboles). Ceci n’est pas un hasard, et nous le montrerons plus bas au theoreme 8.13.

Si l’on veut pouvoir beneficier des bonnes proprietes de ce type de registre pour dessous-suites plus longues, il faudra prendre un nombre r de cases assez grand.

Nous allons decrire le fonctionnement du registre a decalage sous une autre formequi se pretera a des generalisations. A un instant donne, que l’on appellera l’instantj, les entrees dans les cases sont aj , . . . , aj+r−1. Reecrivons ces entrees sous la formexj,0, . . . , xj,r−1, ou xj,i = ai+j . L’avantage de cette ecriture est que l’indice j indiquel’instant et l’indice i, la case ou se trouve le symbole. Appelons xj le vecteur-colonnedont les entrees sont xj,0, . . . , xj,r−1, c’est-a-dire les symboles apparaissant dans les casesa l’instant j. Soit A la matrice

A =

⎛

⎜⎜⎜⎜⎜⎜⎜⎝

0 1 0 0 . . . 00 0 1 0 . . . 00 0 0 1 . . . 0...

......

.... . .

...0 0 0 0 . . . 1q0 q1 q2 q3 . . . qr−1

⎞

⎟⎟⎟⎟⎟⎟⎟⎠

(8.3)

254 8 Generateurs de nombres aleatoires

ou toutes les operations sont effectuees modulo 2. Alors, le vecteur representant lessymboles des cases a l’instant j + 1 est donne par

xj+1 = Axj . (8.4)

(Exercice : verifier !)Avant de passer a des generalisations, voyons deja un avantage de cette nouvelle

presentation. Supposons que l’on veuille passer directement de xj a xj+k sans calculerles etapes intermediaires. On a xj+k = Akxj . Donc, si on calcule la matrice Ak, on peutautomatiser le calcul de xj+k en fonction de xj . Le fait de pouvoir automatiser avec descalculs raisonnables le passage de xj a xj+k est une propriete recherchee dans les bonsgenerateurs de nombres aleatoires.

Comment calculer Ak si k est grand ? En general, si on prend une matrice A acoefficients reels, les coefficients de Ak peuvent devenir tres grands en valeur absolue.Ici, toutes les entrees de A sont des elements de {0, 1}, et les operations sont l’additionet la multiplication modulo 2. Donc, les entrees de Ak sont aussi des elements de {0, 1}.Mais si k est grand, il faut user d’astuce pour faire les calculs en temps raisonnable.Decomposons k en base 2 :

k = b0 + b12 + b222 + · · ·+ bs2s.

Alors, on pose A0 = A et on calcule

A1 = A2,A2 = A4 = A2

1,...

As = A2s

= A2s−1,

et finalementAk =

∏

{i|bi=1}Ai.

Remarquons que chacune des Ai est le produit de deux matrices. Il faudra donc faires produits matriciels pour calculer toutes les matrices Ai. Finalement,

∏

{i|bi=1}Ai

contient au plus s + 1 facteurs. Ainsi, Ak peut etre calcule en au plus 2s ≤ 2 log2 kproduits matriciels.

On voit aussi qu’on peut obtenir d’autres generateurs de nombres aleatoires en gar-dant l’etape de recurrence (8.4) et en permettant d’autres formes de matrice A.

8.3 Le contexte general des generateurs Fp-lineaires

8.3.1 Le cas p = 2

Commencons par le cas p = 2. Le corps F2 est l’ensemble {0, 1} muni des operationsd’addition et de multiplication modulo 2.

8.3 Generateurs Fp-lineaires 255

Definition 8.5 Un generateur F2-lineaire est un generateur de la forme

xn+1 = Axn,

yn = xn,

un =k∑

i=1

yn,i2−i,

ou A et B sont des matrices a coefficients dans F2, A est une matrice r×r et B est unematrice k×r. La matrice A est la matrice de transition pour passer de xn a xn+1, alorsque la matrice B transforme le vecteur xn de longueur r en un vecteur de sortie yn delongueur k, yn = (yn,1, . . . , yn,k), dont les entrees sont les elements du developpementen binaire d’un nombre un ∈ [0, 1]. La derniere etape transforme le vecteur yn en lenombre un.

Exemple 8.6 On peut agencer le registre a decalage considere ci-dessus avec un telgenerateur. Pour cela, il faut transformer des sous-suites de longueur k de la suite an,k < r, en elements de [0, 1]. Prendre des sous-suites de longueur k revient a prendre lamatrice B dont les k lignes sont les k premieres lignes de la matrice identite r × r.

Apres application de B, toutes les sous-suites de longueur k deviennent des sorties.Ainsi,

yn = (xn,0, . . . , xn,k−1) = (an, . . . , an+k−1).

Revenons a l’exemple 8.4, soit le registre a decalage de quatre cases, de coefficients(q0, q1, q2, q3) = (1, 1, 0, 0), et dote des conditions initiales (a0, a1, a2, a3) = (0, 0, 0, 1),qui genere la suite 000100110101111 . . . de periode 15, et prenons k = 2. Alors, lessorties seront les sous-suites (an, an+1) de longueur 2 repetees selon une une periode de15, soit

00 00 01 10 00 01 11 10 01 10 01 11 11 11 10.

On peut maintenant transformer chacune de ces sous-suites de longueur 2, (yn,1, yn,2),en un nombre un ∈ {0, 1

4 ,12 ,

34} tel que un = yn,1

2 + yn,24 . Ceci nous donne la suite de

periode 15 u0, . . . , u14 :

0 014

12

014

34

12

14

12

14

34

34

34

12.

Tout element de {0, 14 ,

12 ,

34} apparaıt quatre fois sauf 0 qui apparaıt trois fois.

La grande particularite des generateurs F2-lineaires est qu’ils sont tres economiques.Par contre, si on veut ameliorer leurs proprietes statistiques, il faut allonger la periode,ce qui leur fait perdre leur avantage economique. Dans ce cas, on peut faire mieux.Nous allons commencer par etudier en detail les generateurs F2-lineaires pour ensuite lesgeneraliser aux generateurs Fp-lineaires. Ensuite, plutot que de prendre des generateurs

256 8 Generateurs de nombres aleatoires

de grande periode, nous obtiendrons de meilleurs generateurs en combinant plusieursgenerateurs Fp-lineaires de periodes independantes.

Revenons sur le registre a decalage et montrons comment sont choisis les coefficientspour que la suite generee soit de periode 2r − 1. Quoique cela ne soit pas absolumentnecessaire, il est preferable d’avoir vu la section 1.4 du chapitre 1 pour lire la preuve de ceresultat (theoreme 8.9 ci-dessous). Pour memoire, le corps Fp est l’ensemble {0, 1, . . . , p−1} muni des operations d’addition et de multiplication modulo p. C’est un corps si etseulement si p est premier.

Definition 8.7 Un polynome

Q(x) = xr + qr−1xr−1 + · · ·+ q1x+ q0

a coefficients dans Fp est primitif s’il est irreductible et si l’ensemble des elements nonnuls de

Fpr = {b0 + b1x+ · · ·+ br−1xr−1 | bi ∈ Fp}

peut s’ecrire commeFpr \ {0} = {xi | i = 0, . . . , pr − 2}

ou les puissances xi de x sont prises modulo Q(x).

Exemple 8.8 Prenons p = 2. On va montrer que le polynome Q(x) = x3 + x + 1 estirreductible sur F2. En effet, supposons que Q(x) = Q1(x)Q2(x). Puisque Q(x) est dedegre 3, soit Q1(x) soit Q2(x) est de degre 1 et appartient a l’ensemble {x, x+ 1}. Si xdivise Q(x), alors on devrait avoir Q(0) = 0, ce qui n’est pas vrai. Si x+ 1 divise Q(x),alors on devrait avoir Q(1) = 0, ce qui n’est pas vrai non plus. Donc, ni x ni x+ 1 nedivise Q(x). Par consequent, Q(x) est irreductible. Les elements non nuls de F23 sontdonnes par {1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1}. Verifions que ce sont tous despuissances de x. En effet, Q(x) = 0 donne x3 = x+ 1, donc

x4 = x(x + 1) = x2 + x,x5 = x(x2 + x) = x3 + x2 = (x+ 1) + x2 = x2 + x+ 1,x6 = x(x2 + x+ 1) = x3 + x2 + x = (x+ 1) + x2 + x = x2 + 1,x7 = x(x2 + 1) = x3 + x = (x+ 1) + x = 1.

Theoreme 8.9 Si les coefficients q0, . . . , qr−1 d’un registre a decalage sont choisis telsque le polynome

Q(x) = xr + qr−1xr−1 + · · ·+ q1x+ q0 (8.5)

est primitif sur F2, alors, pour toute suite (a0, . . . , ar−1) de conditions initiales, telleque les ai ne sont pas tous nuls, la suite generee par le registre est periodique de periode2r − 1.

8.3 Generateurs Fp-lineaires 257

Preuve On a vu au chapitre 6 que l’ensemble

F2r = {b0 + b1x+ · · ·+ br−1xr−1 | bi ∈ {0, 1}}

muni de l’addition et de la multiplication modulo Q(x) est un corps lorsque le polynomeQ(x) est irreductible. On a aussi vu (section 1.4 du chapitre 1) que, pour la constructiondu corps F2r , il est toujours possible de choisir un polynome Q(x) primitif, c’est-a-diretel que l’ensemble des elements non nuls s’ecrit

{xi | i = 0, . . . , 2r − 2}et que x2r−1 = 1. Introduisons la fonction (lineaire) T : F2r → F2 definie par

T (b0 + b1x+ · · ·+ br−1xr−1) = br−1.

Nous allons montrer dans le lemme 8.10 ci-dessous que, pour toute suite non nulle(a0, . . . , ar−1), il existe un unique b = b0 + b1x + . . . br−1x

r−1 tel que ai = T (bxi),i = 0, . . . , r−1. La proposition 1.12 du chapitre 1 nous dit que, si an est la suite genereepar le registre a decalage avec les conditions initiales ai = T (bxi), alors, pour toutn, on a an = T (bxn). Puisque x2r−1 = 1, la suite an est periodique et, pour tout n,an = an+2r−1.

Mais N = 2r − 1 est-il la periode minimale ? Supposons qu’il existe m < 2r − 1 telque an = an+m pour tout n. Alors, a0 = am, . . . , ar−1 = ar+m−1. D’apres le lemme 8.10ci-dessous, il existe b′ tel que ai+m = T (b′xi), i = 0, . . . , r− 1, et a cause de l’unicite deb′ dans ce meme lemme, on a b′ = b, et d’autre part, b′ = bxm (cette egalite est bien surmodulo Q(x)). D’ou b(xm − 1) = 0 et, comme b �= 0, xm = 1. Comme x est une racineprimitive, on a xm �= 1 pour m < 2r − 1, d’ou la contradiction. �

Lemme 8.10 On considere le corps

F2r = {b0 + b1x+ · · ·+ br−1xr−1 | bi ∈ {0, 1}}

muni de l’addition et de la multiplication modulo Q(x), ou Q(x) est le polynomeirreductible donne en (8.5). Alors, pour toute suite (a0, . . . , ar−1), il existe un uniqueb = b0 + b1x+ . . . br−1x

r−1 tel que ai = T (bxi), i = 0, . . . , r − 1.

Preuve On considere le systeme d’equations lineaires T (bxi) = ai, i = 0, . . . , r − 1,aux inconnues b0, . . . , br−1. Regardons la premiere equation

T (b) = br−1 = a0.

Elle nous permet de trouver br−1. Maintenant,

bx = (b0 + b1x+ · · ·+ br−1xr−1)x

= b0x+ b1x2 + · · ·+ br−2x

r−1 + br−1(q0 + q1x+ . . . qr−1xr−1).

258 8 Generateurs de nombres aleatoires

Ainsi T (bx) = br−2 + qr−1br−1 = a1. Comme br−1 est deja connu, cela nous permet detrouver br−2.

On trouve ainsi tous les bi. En effet, supposons que bi+1, . . . , br−1 aient deja etetrouves. Considerons bxr−1−i. Alors,

bxr−1−i = (b0 + b1x+ · · ·+ br−1xr−1)xr−1−i

= b0xr−1−i + b1x

r−i + · · ·+ bixr−1 + xrP (x, bi+1, . . . , br−1),

ou P (x, bi+1, . . . , br−1) est un polynome en x dont les coefficients dependent seulementde bi+1, . . . , br−1, c’est-a-dire des coefficients deja connus. Alors,

T (bxr−1−i) = bi +R(bi+1, . . . br−1).

La formule deR(bi+1, . . . br−1) n’est pas simple, mais ce qui est important, c’est que cetteexpression ne depend que des bi+1, . . . , br−1 deja connus. Alors, on peut trouver le bi del’equation T (bxr−1−i) = ar−1−i, et ce processus determine uniquement le polynome b.�

Definition 8.11 On considere un registre a decalage de r cases dont les coefficientsq0, . . . , qr−1 et les conditions initiales sont choisis de telle sorte que la suite generee soitperiodique de periode 2r − 1. Alors, on apelle fenetre une sous-suite de longueur 2r − 1qui est repetee periodiquement.

Corollaire 8.12 Considerons un registre a decalage de r cases dont les coefficientsq0, . . . , qr−1 sont choisis tels que le polynome Q(x) de (8.5) est primitif sur F2. Alors,etant donne des conditions initiales (a0, . . . , ar−1) telles que les ai ne sont pas tous nuls,toutes les sous-suites de longueur r apparaissent exactement une fois dans la fenetre delongueur 2r−1, sauf la sous-suite nulle. (Dans ce contexte, on regarde la fenetre commeune suite cyclique, en identifiant l’indice n + 2r − 1 a l’indice n : ceci veut dire qu’onpermet aussi des sous-suites a cheval sur deux periodes.)

Preuve Etant donne une fenetre a0, . . . a2r−2 de longueur 2r − 1 representant uneperiode de la suite, il existe 2r − 1 sous-suites de longueur r commencant chacune enun ai distinct. (Si i ≥ 2r − r, alors en utilisant la periodicite, la sous-suite de la suiteinitiale commencant en ai coıncide avec ai, . . . , a2r−2, a0, . . . , ai−2r+r.) On a exactement2r suites distinctes de longueur r, car on a deux choix pour chaque entree. Parmi celles-ci, on en a exactement 2r − 1 dont au moins un element est non nul. Donc, chaquesous-suite de longueur r apparaıtra au moins une fois si elle apparaıt au plus une fois.Supposons qu’une sous-suite de longueur r apparaisse deux fois et commence en ai eten aj , 0 < j − i < 2r − 1. Alors, comme l’etat du registre est le meme en ai et en aj ,on aura, pour tout n ≥ j, an = an−j+i, ce qui contredit le fait que la periode minimalede la suite {an} est 2r − 1. Donc, chaque sous-suite non nulle de longueur r apparaıtexactement une fois dans une fenetre de longueur 2r − 1. �

8.3 Generateurs Fp-lineaires 259

Le theoreme suivant montre qu’un registre a decalage a de bonnes proprietes statis-tiques quand on considere des sous-suites de longueur k telles que k ≤ r.

Theoreme 8.13 Considerons un registre a decalage de r cases dont les coefficientsq0, . . . , qr−1 sont choisis tels que le polynome Q(x) de (8.5) est primitif sur F2. Soit(a0, . . . , ar−1) une suite de conditions initiales telle que les ai ne sont pas tous nuls etsoit k ≤ r. Alors, dans une fenetre de longueur 2r − 1 de la suite generee par le registre(la fenetre etant consideree comme une suite cyclique), toute sous-suite de longueur kapparaıt 2r−k fois, sauf la sous-suite nulle qui apparaıt (2r−k − 1) fois.

Preuve Dans le corollaire 8.12, on a montre que toutes les sous-suites de longueurr apparaissent exactement une fois, sauf la sous-suite nulle. Prenons une sous-suiteb0, . . . , bk−1 de longueur k et considerons toutes les manieres de la transformer en unesous-suite de longueur r en ajoutant des symboles bk, . . . , br−1 a sa droite : il existe2r−k manieres differentes de l’allonger, puisqu’on a deux choix pour chacun des bj ,j = k, . . . , r− 1. Si au moins un des bi, i = 0, . . . , k− 1 est non nul, toutes ces manieresd’allonger la sous-suite existent dans la suite cyclique, puisque toutes les sous-suitesnon identiquement nulles de longueur r existent. De plus, chacune de ces 2r−k manieresapparaıt exactement une fois, puisque chaque sous-suite non identiquement nulle delongueur r apparaıt exactement une fois. Ainsi la sous-suite b0, . . . , bk−1 apparaıt exac-tement 2r−k fois.

Au contraire, si la sous-suite b0, . . . , bk−1 est la sous-suite nulle, on doit exclure latransformation en sous-suite nulle de longueur r. Toutes les autres manieres d’allon-ger la sous-suite apparaissent exactement une fois. Donc, la sous-suite nulle apparaıtexactement 2r−k − 1 fois. �

8.3.2 Une lecon pour les jeux de hasard

Les theoremes 8.9 et 8.13 nous offrent la cle de l’histoire du joueur apprehende auCasino de Montreal. Le joueur en question connaissait, de par son travail, le mecanismedes generateurs de nombres aleatoires. Il savait que les algorithmes sous-jacents sontdeterministes et donc, qu’un algorithme donne, pour des conditions initiales identiques,genere des suites identiques. Lors de precedentes visites, il avait remarque que lesnombres des appareils de keno sortaient, soir apres soir, dans le meme ordre. Il notadonc ces nombres et les joua avec le resultat decrit au debut du chapitre. Mais sachantque ce probleme existe, pourquoi le Casino de Montreal a-t-il accepte de reouvrir lejeu sur ces machines ? La raison officielle a ete que ces machines avaient ete mal pro-grammees et que l’erreur avait ete corrigee. Une autre raison (moins honorable pour lecasino, mais egalement possible) est que les machines etaient eteintes tous les soirs parun employe, par exemple celui qui fait le menage. Alors, au moment du redemarrage,les machines reutilisaient les memes conditions initiales ai, produisant soir apres soirles memes nombres dans le meme ordre.

Cette histoire souleve en fait une autre question ! Comment peut-on changer lesconditions initiales pour que les suites ai ne soient pas toujours les memes a chaque

260 8 Generateurs de nombres aleatoires

demarrage du programme ? Doit-on laisser les machines de keno eternellement allumees ?Et comment font les jeux videos ? Voici deux solutions assez communes. La premierefacon necessite que l’appareil soit eteint « convenablement ». Si on l’eteint en pressantle bouton d’allumage (et non en debranchant le cable d’alimentation electrique), l’ap-pareil enregistre, juste avant de s’eteindre, les derniers ai qu’il vient de generer sur undisque ou une carte-memoire ; ils serviront alors comme conditions initiales au prochainallumage. La deuxieme solution suppose qu’une horloge soit integree aux circuits de l’ap-pareil. Au demarrage, le programme demande le nombre de secondes (ou de milliemesde secondes) ecoule depuis une date fixee, disons depuis minuit le 1er janvier de l’an2000. Les dernieres decimales de ce nombre seront utilisees comme conditions initiales.

8.3.3 Le cas general

Ici, nous supposerons que le lecteur connaıt le corps Fpr (voir, par exemple, la sec-tion 6.5 du chapitre 6).

Definition 8.14 1. Soit p un entier premier. Un generateur de nombres aleatoiresFp-lineaire est un generateur de la forme

an = q0an−r + q1a1 + · · ·+ qr−1an−1 (mod p), (8.6)

ou les q0, . . . , qr−1 et les conditions initiales a0, . . . , ar−1 sont des entiers de{0, 1, . . . , p− 1}, et les operations sont celles de Fp, c’est-a-dire modulo p.

2. Un generateur recursif multiple est defini par la recurrence lineaire{

an = q0an−r + q1a1 + · · ·+ qr−1an−1 (mod p),un = an

p .

On voit que, si on prend p = 2, alors un generateur de nombres aleatoires F2-lineaireest simplement un registre a decalage. Un generateur de nombres aleatoires Fp-lineairegenere des nombres aleatoires an ∈ {0, 1, . . . , p − 1}, alors que le generateur recursifmultiple associe genere des nombres aleatoires un ∈ [0, 1].

Les theoremes 8.9 et 8.13 se generalisent a un generateur Fp-lineaire. Dans le cas deF2, le fait de travailler modulo le polynome Q(x) donne en (8.5) permet d’ecrire

xr = q0 + q1x+ · · ·+ qr−1xr−1 (8.7)

parce que qi = −qi. Comme ceci n’est plus vrai dans Fp, il faut adapter le polynomeQ(x) pour que la relation (8.7) reste valable.

Theoreme 8.15 Si p est premier et que q0, . . . , qr−1 ∈ {0, 1, . . . , p−1} sont choisis telsque le polynome

Q(x) = xr − qr−1xr−1 − · · · − q1x− q0

8.4 Generateur recursif multiple combine 261

est primitif sur Fp, alors le generateur Fp-lineaire donne en (8.6) genere une suite deperiode pr − 1.

Si on prend une suite (a0, . . . , ar−1) de conditions initiales, telle que les ai ne sontpas tous nuls, alors, dans une fenetre de longueur pr − 1 de la suite generee par leregistre, toute sous-suite de longueur k avec k ≤ r apparaıt pr−k fois, sauf la sous-suitenulle qui apparaıt pr−k − 1 fois. (On considere la fenetre comme une suite cyclique, enidentifiant l’indice n+ pr − 1 a l’indice n.)

Preuve Comme la preuve est identique a celle des theoremes 8.9 et 8.13, nous lalaissons en exercice. �

En pratique, on travaille souvent avec des generateurs Fp-lineaires dans lesquels lepolynome Q(x) n’a que deux coefficients qi non nuls, soit q0 et qs, 0 < s ≤ r − 1. Cecirend les calculs tres simples.

Exemple 8.16 On considere p = 3 et le polynome Q(x) = x4 − x − 1. Nous allonsadmettre que ce polynome est primitif et laisser les details pour l’exercice 10. Si l’onprend les conditions initiales (a0, a1, a2, a3) = (0, 0, 0, 1), alors la suite {an} engendreepar le generateur F3-lineaire associe est de periode 34−1 = 80, et la fenetre de longueur80 qui est repetee est :

0 0 0 1 0 0 1 1 0 1 2 1 1 0 0 2 1 0 2 0 1 2 2 1 0 1 0 1 1 1 1 2 2 2 0 1 1 2 1 20 0 0 2 0 0 2 2 0 2 1 2 2 0 0 1 2 0 1 0 2 1 1 2 0 2 0 2 2 2 2 1 1 1 0 2 2 1 2 1. (8.8)

On peut verifier les bonnes proprietes statistiques de cette suite. En effet, 1 et 2 appa-raissent chacun 27 fois, alors que 0 apparaıt 26 fois. Toutes les sous-suites de longueur2 apparaissent chacune neuf fois, sauf 00 qui apparaıt huit fois. Toutes les sous-suitesde longueur 3 apparaissent chacune trois fois sauf 000 qui apparaıt deux fois. Toutes lessous-suites de longueur 4 apparaissent chacune une fois, sauf 0000.

8.4 Generateur recursif multiple combine

Les generateurs Fp-lineaires qui n’ont que deux coefficients non nuls, q0 et qs, 0 <s ≤ r−1, conduisent a des calculs tres simples. Par contre, ils ne se comportent pas tresbien statistiquement. Pour pallier cet inconvenient, on combine plusieurs generateurs dece type caracterises par des entiers premiers p distincts et des polynomes Q(x) distincts,mais de meme degre.

Definition 8.17 On considere m recurrences lineaires

an,j = q0,jan−r,j + q1,jan−r+1,j + · · ·+ qr−1,jan−1,j (mod pj),

j = 1, . . .m, satisfaisant aux hypotheses du theoreme 8.15, ou les pj sont des entierspremiers distincts. La fonction « sortie » transforme les vecteurs (an,1, . . . , an,m) ennombres reels de [0, 1] par la formule

262 8 Generateurs de nombres aleatoires

un =

⎧

⎨

⎩

m∑

j=1

δjan,j

pj

⎫

⎬

⎭,

dans laquelle les δj sont des entiers arbitraires relativement premiers avec les pj. Ici,{x} represente la partie fractionnaire d’un nombre reel x, c’est-a-dire le nombre

{x} = x− [x],

ou [x] est la partie entiere de x. Ce generateur de nombres aleatoires qui produit la suiteun est appele generateur recursif multiple combine.

Remarque Dans la litterature, on trouve aussi la notation x (mod 1) au lieu de {x}.Meme si x et {x} ne sont pas des entiers, ceci est en accord avec la definition selonlaquelle deux nombres a et b sont congrus modulo un entier n si leur difference a− b estde la forme mn pour un entier m ∈ Z.

Exemple 8.18 Nous considerons un generateur recursif multiple combine tel que r = 3,m = 2, p1 = 3, p2 = 2 et δ1 = δ2 = 1. Nous laissons le lecteur verifier que le polynomeQ1(x) = x3 − x− 2 est primitif sur F3. Alors, la premiere recurrence lineaire associee,sous les conditions initiales 001, genere la suite {an} de periode 26 dans laquelle lafenetre suivante est repetee :

00101211201110020212210222.

La deuxieme recurrence lineaire est celle qui est associee au polynome Q2(x) = x3−x−1,lequel est primitif sur F2, comme l’a montre l’exemple 8.8. Alors, la recurrence lineaireassociee, sous les conditions initiales 001 genere la suite {a′n} de periode 7 dans laquellela fenetre suivante est repetee :

0010111.

Le generateur combine a donc comme periode 7×26 = 182. Nous presentons ses sortiespar blocs de trois lignes : la premiere ligne de chaque bloc represente une periode de lapremiere recurrence lineaire. La deuxieme ligne represente la suite correspondante a′n :des traits verticaux separent les differentes fenetres repetant la periode. La troisiemeligne represente les sorties an

3 + a′n

2 . Toutes ces sorties ont ete ecrites en multiples de16 pour mettre en evidence le fait que les numerateurs forment une suite de nombresaleatoires de {0, 1, . . . , 5}. Ainsi, le premier bloc represente n = 0, . . . , 25, le secondn = 26, . . . , 51, etc.

On voit que, si les nombres pi sont petits, la regularite des sorties des differentsnombres ou sous-suites n’apparaıt pas aussi rapidement que dans les recurrences Fp-lineaires.

8.5 Conclusion 263

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 20 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 10 0 5

6 0 56

16

56

26

46

36

26

56

56

36 0 4

636

46

56

16

16

26 0 1

646

16

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 21 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 136

36

26 0 5

646

56

56

16 0 2

656

26

36

36

16 0 4

656

46

16

56

36

46

46

16

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 20 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 00 3

656

36

26

46

56

26

16

36

56

26

26

36 0 1

636

16

26

46

16

26

36

16

16

46

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 20 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 10 3

626

36

56

16

26

26

16 0 5

656

56 0 0 1

6 0 16

56

16

46

26

36

46

16

16

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 21 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 036 0 2

636

26

16

56

56

46 0 5

626

56

36

36

46 0 1

626

16

16

56 0 4

616

46

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 21 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 036

36

56 0 2

616

26

56

16

36

26

26

56 0 3

616

36

46

26

16

46

56

36

16

46

46

0 0 1 0 1 2 1 1 2 0 1 1 1 0 0 2 0 2 1 2 2 1 0 2 2 21 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 136 0 5

636

56

46

26

56

46

36

56

56

26 0 3

646

36

16

56

46

46

56 0 1

616

16

De tels generateurs sont excellents, meme si on prend m aussi petit que 3. On peutse permettre de prendre la plupart des coefficients qi,j nuls et des coefficients non nulsrelativement simples, ce qui fait que les calculs sont simples et economiques. L’article[4] donne des exemples de bons coefficients. Malgre la simplicite des calculs, commeles recurrences lineaires sont combinees, ces generateurs passent bien les tests statis-tiques. De plus, comme on peut choisir les coefficients pour que la periode du generateurcombine soit le produit des periodes des recurrences lineaires, on peut produire desgenerateurs ayant de tres grandes periodes sans que la periode de chaque recurrencelineaire soit elle-meme grande. Aussi le calcul pour passer d’un coup de un a un+N

est beaucoup plus facile que dans une unique recurrence lineaire avec des coefficientscompliques.

8.5 Conclusion

Presque tous les langages de programmation offrent un ou des generateurs denombres aleatoires de base. L’utilisateur n’a donc pas besoin de connaıtre la theoriede ces generateurs pour faire des simulations de nature probabiliste. Mais le domainedes generateurs pseudo-aleatoires est relativement recent, la recherche se poursuit, et lenombre de tests statistiques qu’un « bon » generateur doit reussir ne fait qu’augmenter.

264 8 Generateurs de nombres aleatoires

(Voir, par exemple, [1] pour la description de tests de base pour les generateurs denombres aleatoires.) Il n’est donc pas surprenant que certains generateurs offerts parles langages de programmation deviennent rapidement desuets. L’histoire du langageC est interessante sur ce point. Le langage a ete developpe au debut des annees 70, etle premier manuel de Kernighan et Ritchie, les peres du langage, a paru en 1978. Acause de son grand succes, la necessite d’un standard s’est vite fait sentir. Le processusa ete ardu mais, en 1989, l’American National Standards Institute (ANSI) etablissaitune norme standardisant le langage. Dans les premieres versions, la fonction rand()offerte par le langage avait un cycle de 215 − 1 = 32 767, une periode fort courte, cer-tainement trop courte pour l’utilisation dans les jeux de hasard. Le standard ANSIne fixait pas la fonction rand() ; il se limitait a demander que le generateur produisedes entiers dans l’ensemble {0, 1, . . . , RAND MAX} et que RAND MAX soit au moins egal a32 767. Ainsi les divers compilateurs C respectant le standard ANSI de 1989 peuventavoir des fonctions rand() differentes, ou de RAND MAX et de periodes differents et unmeme programme, compile sur diverses machines, peut produire des resultats differentsmeme pour des conditions initiales identiques. Les fonctions rand() de plusieurs compi-lateurs sont connues pour leurs pietres resultats, c’est-a-dire qu’elles echouent a certainstests statistiques juges fondamentaux. Les concepteurs de ces compilateurs ne sont pasnecessairement a condamner ; cet etat de fait montre plutot que la recherche dans cedomaine est encore active.

8.6 Exercices

1. Montrer que, si on genere une suite de bits independants (par exemple enlancant une piece de monnaie) et si on les regroupe par blocs de longueur r, les-quels representent l’expression binaire (de gauche a droite) de nombres entiers deS = {0, 1, . . . , 2r−1}, alors chaque entier apparaıt en moyenne une fois sur 2r.

2. Le generateur lineaire congruentiel genere des nombres de E = {1, . . . , p − 1} parla regle

xn = axn−1 (mod p),

ou p premier et a est tel que{

ak ≡/ 1 (mod p), k < p− 1,ap−1 ≡ 1.

(L’existence d’un tel a, appele racine primitive de Fp (Zp), est demontree autheoreme 7.22 du chapitre 7.)a) Soit p = 11. Trouver les racines primitives de F11 (il y en a quatre).b) Montrer que, quel que soit x0 ∈ S, ce generateur produit une suite periodiquede periode exactement p− 1.

8.6 Exercices 265

3. Le generateur lineaire congruentiel de l’exercice 2 genere une suite de nombresentiers uniformement distribues dans E = {1, . . . , p − 1}. Trouver une maniere detransformer cette suite en une suite de 0 et de 1 de telle sorte que 0 et 1 soientequiprobables.

4. L’exercice suivant est destine a montrer qu’un generateur lineaire congruentielcomme celui de l’exercice 2 n’a pas toujours de bonnes proprietes statistiques. Pre-nons p = 151, la racine primitive a = 30 et la condition initiale x0 = 1. Voici lesegment {xn}150n=1 de la suite :

30 145 122 36 23 86 13 88 73 76 15 148 61 18 8743 82 44 112 38 83 74 106 9 119 97 41 22 56 19

117 37 53 80 135 124 96 11 28 85 134 94 102 40 14362 48 81 14 118 67 47 51 20 147 31 24 116 7 59

109 99 101 10 149 91 12 58 79 105 130 125 126 5 150121 6 29 115 128 65 138 63 78 75 136 3 90 133 64108 69 107 39 113 68 77 45 142 32 54 110 129 95 13234 114 98 71 16 27 55 140 123 66 17 57 49 111 889 103 70 137 33 84 104 100 131 4 120 127 35 144 9242 52 50 141 2 60 139 93 72 46 21 26 25 146 1.

On le transforme en une suite de 0 et de 1 en posant

yn =

{

0, xn ≤ 75,1, xn ≥ 76,

ce qui nous donne la suite :

0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 01 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 01 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 01 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 01 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0.

a) Quelles sont les frequences respectives de 0 et de 1 ?b) Quelles sont les frequences respectives des differentes sous-suites de longueur2 : 00, 01, 10, 11 ? Dans un bon generateur de nombres aleatoires, elles devraientetre a peu pres egales. Que pouvez-vous conclure ?c) Meme question pour les sous-suites de longueur 3.

5. On considere un registre a decalage (c’est-a-dire un generateur F2-lineaire) decoefficients (q0, q1, q2, q3) = (1, 0, 0, 1) et les conditions initiales (a0, a1, a2, a3) =(0, 0, 0, 1). Verifier que la suite generee est periodique de periode 15, mais qu’ellen’est pas celle de l’exemple 8.4.

266 8 Generateurs de nombres aleatoires

6. Montrer que le polynome x4 +x3 +x2 +x+1 est irreductible, mais n’est pas primitifsur F2. Verifier d’autre part que, si on prend (q0, q1, q2, q3) = (1, 1, 1, 1) commecoefficients d’un registre a decalage, alors aucune suite generee par le registre adecalage n’est de periode 15.

7. On considere le registre a decalage de coefficients (q0, q1, q2, q3, q4) = (1, 0, 1, 0, 0) etconditions initiales (a0, a1, a2, a3, a4) = (0, 0, 0, 0, 1).a) Verifier que la suite generee est periodique de periode 31 en enumerant expli-citement ai, i = 0, . . . , 35 (s’assurer que a0 = a31, a1 = a32, a2 = a33, a3 = a34,a4 = a35).b) Verifier que 1 apparaıt 16 fois sur 31.c) Verifier que chaque sous-suite de longueur 2 apparaıt huit fois sur 31, sauf 00qui apparaıt sept fois sur 31.d) Verifier que chaque sous-suite de longueur 3 apparaıt quatre fois sur 31, sauf000 qui apparaıt trois fois sur 31.e) Verifier que chaque sous-suite de longueur quatre apparaıt deux fois sur 31,sauf 0000 qui apparaıt une fois sur 31.f) Verifier que chaque sous-suite de longueur 5 apparaıt une fois sur 31, sauf00000. En deduire qu’on aurait pu prendre n’importe quelle sous-suite non nulle delongueur 5 comme ensemble de conditions initiales.g) En deduire que, si on considere des sous-suites de longueur k ≤ r et si onelimine les suites qui ne contiennent que des zeros, on obtient un generateur donttoutes les sorties sont equiprobables.

8. Le registre de l’exercice 7 genere une suite {an}.a) Donner la fonction qui a an associe an+2. (Suggestion : utiliser la forme matri-cielle.)b) Donner la fonction qui a an associe an+10.

9. Trouver tous les polynomes irreductibles de degre 2 sur F3. Lesquels sont primitifs ?

10. Le but de l’exercice est de montrer que le polynome Q(x) = x4−x−1 est primitifsur F3.a) Montrer que Q(x) est irreductible sur F3. Pour cela, vous aurez besoin del’exercice 9.b) Montrer que Q(x) est primitif, c’est-a-dire que xk �= 1 si k < 80. Pour cela, ilfaut calculer les puissances xk en utilisant la regle x4 = x+ 1. Par exemple,

⎧

⎪⎨

⎪⎩

x5 = x(x + 1) = x2 + x,

x6 = x(x2 + x) = x3 + x2,

x7 = x(x3 + x2) = x4 + x3 = (x+ 1) + x3 = x3 + x+ 1.

(Le calcul peut sembler fastidieux. On peut le simplifier en utilisant le fait quex80 = 1 et le lemme 8.2 qui garantit que si xk = 1, k < 80, alors k | 80. Cecipermet de se limiter a calculer xk pour k, un diviseur de 80.)

8.6 Exercices 267

11. Choisir un polynome primitif de degre 2 sur F3 et utiliser ses coefficients pourconstruire le generateur F3-lineaire associe.a) Construire la suite de nombres aleatoires produite par ce generateur.b) Combien y a-t-il d’occurrences de 0, de 1 et de 2 dans une periode ?c) Verifier que chaque sous-suite de longueur 2 apparaıt exactement une fois,sauf 00.

12. Choisir un polynome primitif de degre 3 sur F3 et utiliser ses coefficients pourconstruire un generateur F3-lineaire associe.a) Construire la suite de nombres aleatoires produite par ce generateur.b) Combien y a-t-il d’occurrences de 0, de 1 et de 2 dans une periode ?c) Verifier que chaque sous-suite de longueur 2 apparaıt exactement trois fois,sauf 00 qui apparaıt deux fois.d) Verifier que chaque sous-suite de longueur 3 apparaıt exactement une fois,sauf 000.

13. Choisir un polynome primitif Q1 de degre 2 sur F2 et le generateur F2-lineaireassocie. Choisir un polynome primitif Q2 de degre 2 sur F3 et le generateur F3-lineaire associe.a) Quelle est la periode du generateur recursif multiple combine qu’on obtienten prenant δ1 = δ2 = 1 ?b) Choisir des conditions initiales et ecrire la suite des sorties pendant uneperiode.

14. Imaginer des generateurs de nombres aleatoires qui simulent le lancer d’un de.Vous voulez donc generer de maniere equiprobable des nombres de l’ensemble{1, . . . , 6}.

15. Lorsqu’on fait des simulations, on utilise souvent des suites de nombres aleatoiresqui obeissent a une loi de probabilite donnee. Ainsi nous avons donne desgenerateurs de nombres aleatoires de [0, 1] qui obeissent a une loi uniforme U [0, 1]sur [0, 1]. Montrer comment combiner un tel generateur avec une transformationaffine pour generer des nombres aleatoires qui obeissent a une loi uniforme U [a, b]sur un intervalle [a, b].

Note : la fonction de densite d’une variable aleatoire uniforme sur [a, b] estdonnee par

f(x) =

{1

b−a , x ∈ [a, b],0, x /∈ [a, b].

16. Lorsqu’on veut generer des nombres aleatoires obeissant a une loi de probabiliteplus generale, on doit considerer la fonction de repartition : si X est une variablealeatoire, alors sa fonction de repartition est donnee par

FX(x) = Prob(X ≤ x).

a) Montrer que, si X est une variable aleatoire uniforme sur [0, 1] (on ecrit X ∼U [0, 1]), de fonction de densite

268 8 Generateurs de nombres aleatoires

f(x) =

{

1, x ∈ [0, 1],0, x /∈ [0, 1],

sa fonction de repartition est donnee par

FX(x) =

⎧

⎪⎨

⎪⎩

0, x < 0,x, x ∈ [0, 1],1, x > 1.

b) Soit X ∼ U [0, 1] et g : [0, 1] → R une fonction strictement croissante. Onconsidere la variable aleatoire Y = g(X). Montrer que sa fonction de repartitionest donnee par

FY (y) = FX(g−1(y))

(ou g−1 denote la fonction inverse de g satisfaisant a g−1(g(x)) = x).c) Calculer la fonction de repartition d’une variable aleatoire Y qui suit une loiexponentielle de parametre λ pour laquelle la fonction de densite est donnee par

fY (y) =

{

0, y < 0,λe−λy, y ≥ 0.

d) Quelle fonction g doit-on prendre pour que, si X ∼ U [0, 1], alors Y = g(X)suive une loi exponentielle de parametre λ ? Expliquer comment on pourrait s’yprendre en pratique pour generer une suite de nombres aleatoires obeissant a uneloi de probabilite exponentielle de parametre λ.

17. Au bridge, 52 cartes sont distribuees entre quatre joueurs A,B,C,D.a) Expliquez pourquoi il y a 52!

(13!)4 facons de distribuer les cartes. (Au bridge,les joueurs sont numerotes de 1 a 4 suivant l’ordre dans lequel ils sont appelesa annoncer. L’ordre dans lequel se jouent les cartes est different et depend desannonces. Deux parties pour lesquelles on a les quatre memes mains attribuees ades joueurs differents sont considerees comme differentes.)b) Combien y a-t-il de secondes en un an ? Determiner combien d’annees sontrequises pour jouer toutes les parties de bridge possibles si on complete une partietoutes les secondes.c) On voit donc qu’il est impossible d’explorer toutes les parties de bridge pos-sibles. Cela signifie-t-il qu’il est impossible de faire des statistiques sur les par-ties possibles ? Les statistiques permettent de tirer des conclusions sur l’ensembled’une population (ici, la population des parties de bridge) a partir de l’analysed’un echantillon, a condition que l’echantillon soit representatif. Une maniere debatir un echantillon representatif serait de numeroter les cartes de 1 a 52. Pourchoisir les cartes du premier joueur, on demanderait a l’ordinateur de choisir unnombre parmi 52, puis un nombre parmi 51 (le numero choisi correspondant a

8.6 Exercices 269

l’ordre de la carte parmi les cartes restantes et non au numero de la deuxiemecarte choisie) . . . jusqu’a la derniere carte du premier joueur, qui serait choisie partirage au hasard d’un nombre parmi 40. On choisirait ensuite de la meme maniereles cartes du deuxieme joueur, puis du troisieme. Le quatrieme joueur recevraitles cartes restantes. Pour generer une deuxieme partie, on ferait executer le memealgorithme une deuxieme fois. Donner des conditions sur les differents generateursde nombres aleatoires pour que toutes les parties aient la meme probabilite d’etregenerees.d) Nous avons vu qu’il ne suffit pas que tous les evenements (ici, les parties)aient la meme probabilite d’etre generes. Il faut aussi que toutes les sous-suitesde k evenements aient la meme probabilite d’etre generees. Comme ce genre dequestion est trop difficile a trancher a cause de la taille de l’ensemble des suitesde k parties, on peut faire des tests statistiques partiels. Par exemple, quelle estla probabilite qu’une main de bridge contienne les quatre as ? On peut ensuitegenerer 1000 parties et verifier si le nombre de parties dans lesquelles une main debridge contient les quatre as se rapproche de la probabilite calculee.e) Calculer la probabilite de deux autres evenements pas trop rares que vouspourriez utiliser pour faire un test statistique.

References

[1] Knuth, Donald. The Art of Computer Programming, Volume 2 : Seminumerical Algorithms,Third Edition, Reading, Massachusetts, Menlo Park, California, London, Don Mills, On-tario, Addison-Wesley, 1997, 624 p.

[2] L’Ecuyer P., « Random numbers », dans The International Encyclopedia of the Socialand Behavioral Sciences, N. J. Smelser et Paul B. Baltes Eds., Pergamon, Oxford, 2002,p. 12735–12738.

[3] L’Ecuyer P. et Panneton F., « Fast random number generators based on linear recurrencesmodulo 2 : overview and comparison », Proceedings of the 2005 Winter Simulation Confe-rence, p. 110–119.

[4] L’Ecuyer P., « Good parameters and implementations for combined multiple recursiverandom number generators », Operations Research, vol. 47, 1999, p. 159–164.