Annexe 5
503
Comme l’ordinateur représente un nombre réel avec une erreur finie, on génère des entiers
X n entre 0 et un nombre m. On obtient ensuite ζ n par la division :
La méthode congruentielle a été introduite par D.H. Lehmer en 1949 (Lehmer, 1951).
Une séquence de nombres entiers aléatoires X n est obtenue par la relation de récurrence :
X n = (
+ c) mod m n ≥ 0
Soit : X n =
+ c – m k n
où
≡ plus grand entier positif de cette division
m est le module : m > 0.
a est le multiplicateur : 0 ≤ a < m.
c est l’incrément : 0 ≤ c < m.
X o est la valeur d’initialisation (seed ≡ graine) : 0 ≤ X o < m.
{X i } définit une séquence congruentielle linéaire. Il est bien évident que, dans la pratique,
le générateur de nombres aléatoires doit posséder une périodicité la plus grande possible,
par exemple choix du module m : m = 2 48 .
La recherche sur les générateurs de nombres aléatoires se poursuit en liaison avec l’évolution des ordinateurs et la complexité croissante des études réalisées par simulation Monte
Carlo (L’Écuyer, 1988 ; 2003 ; 2005 ; Reuillon, 1988 ; 2004 ; 2005).
Exemple simple :
m = 5, a = c = X o = 3
signifie prendre le plus grand entier positif
X o = 3 ;
(mod 5)
X 1 = 3 X o + 3
(mod 5) =
X 2 = 3 X 1 + 3
(mod 5) =
X 3 = 3 X 2 + 3
(mod 5) =
X 4 = 3 X 3 + 3
(mod 5) =
On a
nombre aléatoire réel correspondant à X i .
;
;
;
…
␨ n
X n
m
----- -
ϭ
0 ␨ n 1
Յ Յ
aX n 1
Ϫ
aX n 1
Ϫ
k n
aX n 1
Ϫ
C
ϩ
m
----------------------------- -
ϭ
X n 1
ϩ
3X n 3
ϩ
ϭ
3 3
ϫ
3 5
3 3
ϫ
3
ϩ
5
------------------------- -
Ϫ
ϩ
2
ϭ
3 2
ϫ
3 5
3 2
ϫ
3
ϩ
5
------------------------- -
Ϫ
ϩ
4
ϭ
3 4
ϫ
3 5
3 4
ϫ
3
ϩ
5
------------------------- -
Ϫ
ϩ
0
ϭ
3 0
ϫ
3 5
3 0
ϫ
3
ϩ
5
------------------------- -
Ϫ
ϩ
3
ϭ
␨ i
X i
m
---- -
ϭ
␨ 0
X 0
m
----- -
3
5
-- -
0 6
,
ϭ
ϭ
ϭ
␨ 1
X 1
m
----- -
2
5
-- -
0 4
,
ϭ
ϭ
ϭ
␨ 2
X 2
m
----- -
4
5
-- -
0 8
,
ϭ
ϭ
ϭ
␨ 3
X 3
m
----- -
0
5
-- -
0
ϭ
ϭ
ϭ
␨ 4
X 4
m
----- -
3
5
-- -
0 6
,
ϭ
ϭ
ϭ