18. I NTRODUCTION AUX M ÉTHODES TIF: MONTE-CARLO
l’ordre alphabétique la suite des chiffres à condition toutefois d’en ôter lc prtfixe. Ces chiffres
compris entre 0 et 9 sont apI>roxirnativcmcnt akatoires & distribution rectangulaire.
On peut obtenir des rksultats semblables en prélevant les chiffres successifs figurant sur les
plaques mineralogiques des automobiles immatriculées en France pourvu que l’on nc s’intéresse
qu’à ceux précédant les lcttrcs.
On peut kgalcment obtenir des suites intkressantes en choisissant, les chiffres de nombres
t,ranscendants tels que e et T. Le prockdk est coûteux car lc calcul d’un grand nombre de chiffres
demande un énorme travail prsalable, y compris la transcription qui doit gtre sans faille. Il est,
important de noter que les chiffres des nombres transcendants tels que e ct T n’ont aucune
périodicitk, mais: de plus, ils sont répartis aléatoirernent selon la loi rectangulaire. Par ailleurs;
on sait parfaitement calculer de trCs longues suites de chiffres exacts de ces nombres. En quoi
ces suites générées sont-elles aléatoires? Elles le sont, dans la mesure où connaissant, uniquement
les y premiers chiffres dc la suitc7 il n’est pas possible de dbterminer lc Q + le quel que soit y.
Avec l’apparition des calculateurs modernes, la nkessit@ de pouvoir gkkrer des suites dc
nombres pseudo-aléatoires s’est, tr& vite manifcstk. Il s’agit alors dc cri:cr une suite de nombres
telle que la periodicité générée soit très grande devant la taille dc l’khantillon à prtlever.
Une très bonne mPthode duc à L<:hmer-Greerlhergcr
(1951 et 1961) consiste à former la suite
à partir dc la rclat,ion de récurrence :
k Z+I = ak; + b modulo
m
avec les contraintes suivantes :
1. b et m sont premiers entre eux,
2. u E 1 r~~odulo p pour chaque facteur premier p de m,
3. n = 1 modula 4 si m est un multiple dc 4.
Ainsi la période de la suite générée est m.
Ces conditions sont très faciles à réaliser sur un calculateur binaire en arithmétique entière.
Prenons le cas classique de la représentation sur quatre octets. Alors on sait que l’arithmétique
entière est effectuée rnodulo m = 2”l. Attention en machine cc nombre est négatif, car lc premier
bit contient un 1. Ainsi lc seul facteur premier dc m est 2. Maintenant,, pour satisfaire les autres
conditions, il suffit de choisir b impair et a = 4k + 1, k entier quelconque. Pour que le modula ‘rn
fonct,ionnc dès les premkkes récurrences, il faut choisir des nombres ko, a et b de taille convenable.
Nous avons retenu :
k. = 223
a = 125 661
b = 95 783.
Remarque 1 : Il y a deux fa.Cons d’utiliser le générateur : en arithmétique flottante, on divise
les k, gi‘nérks par (-2”l) et l’on obtient des nombres compris entre -1 et +l. On peut aussi ne
former que des nombres positifs compris cntrc 0 et 1, ainsi quand on rencontre un k, négat,if. il
suffit alors dc lui ajouter (-2”l) pour le ramener dans les entiers positifs. Ensuite chaque k, c,st,
divisé par ( -2’i1).
Remarque 2 : Nous avons vérifié expérimentalement que la période etait bien 2’i’.
Remarque 3 : En utilisant le test du x”, nous avons vkrifié que l’hypothkc de la distribution
uniforme n’etait pas contrcditc par les donnkcs gknérées.
289
l’ordre alphabétique la suite des chiffres à condition toutefois d’en ôter lc prtfixe. Ces chiffres
compris entre 0 et 9 sont apI>roxirnativcmcnt akatoires & distribution rectangulaire.
On peut obtenir des rksultats semblables en prélevant les chiffres successifs figurant sur les
plaques mineralogiques des automobiles immatriculées en France pourvu que l’on nc s’intéresse
qu’à ceux précédant les lcttrcs.
On peut kgalcment obtenir des suites intkressantes en choisissant, les chiffres de nombres
t,ranscendants tels que e et T. Le prockdk est coûteux car lc calcul d’un grand nombre de chiffres
demande un énorme travail prsalable, y compris la transcription qui doit gtre sans faille. Il est,
important de noter que les chiffres des nombres transcendants tels que e ct T n’ont aucune
périodicitk, mais: de plus, ils sont répartis aléatoirernent selon la loi rectangulaire. Par ailleurs;
on sait parfaitement calculer de trCs longues suites de chiffres exacts de ces nombres. En quoi
ces suites générées sont-elles aléatoires? Elles le sont, dans la mesure où connaissant, uniquement
les y premiers chiffres dc la suitc7 il n’est pas possible de dbterminer lc Q + le quel que soit y.
Avec l’apparition des calculateurs modernes, la nkessit@ de pouvoir gkkrer des suites dc
nombres pseudo-aléatoires s’est, tr& vite manifcstk. Il s’agit alors dc cri:cr une suite de nombres
telle que la periodicité générée soit très grande devant la taille dc l’khantillon à prtlever.
Une très bonne mPthode duc à L<:hmer-Greerlhergcr
(1951 et 1961) consiste à former la suite
à partir dc la rclat,ion de récurrence :
k Z+I = ak; + b modulo
m
avec les contraintes suivantes :
1. b et m sont premiers entre eux,
2. u E 1 r~~odulo p pour chaque facteur premier p de m,
3. n = 1 modula 4 si m est un multiple dc 4.
Ainsi la période de la suite générée est m.
Ces conditions sont très faciles à réaliser sur un calculateur binaire en arithmétique entière.
Prenons le cas classique de la représentation sur quatre octets. Alors on sait que l’arithmétique
entière est effectuée rnodulo m = 2”l. Attention en machine cc nombre est négatif, car lc premier
bit contient un 1. Ainsi lc seul facteur premier dc m est 2. Maintenant,, pour satisfaire les autres
conditions, il suffit de choisir b impair et a = 4k + 1, k entier quelconque. Pour que le modula ‘rn
fonct,ionnc dès les premkkes récurrences, il faut choisir des nombres ko, a et b de taille convenable.
Nous avons retenu :
k. = 223
a = 125 661
b = 95 783.
Remarque 1 : Il y a deux fa.Cons d’utiliser le générateur : en arithmétique flottante, on divise
les k, gi‘nérks par (-2”l) et l’on obtient des nombres compris entre -1 et +l. On peut aussi ne
former que des nombres positifs compris cntrc 0 et 1, ainsi quand on rencontre un k, négat,if. il
suffit alors dc lui ajouter (-2”l) pour le ramener dans les entiers positifs. Ensuite chaque k, c,st,
divisé par ( -2’i1).
Remarque 2 : Nous avons vérifié expérimentalement que la période etait bien 2’i’.
Remarque 3 : En utilisant le test du x”, nous avons vkrifié que l’hypothkc de la distribution
uniforme n’etait pas contrcditc par les donnkcs gknérées.
289