248
8 G´ en´ erateurs de nombres al´ eatoires
le hasard. Tous ont, dans leur programme, un segment produisant des nombres qui
apparaissent al´ eatoires ` a l’utilisateur, mais qui sont engendr´ es de fa¸ con compl` etement
d´ eterministe. Ces algorithmes, les g´ en´ erateurs de nombres al´ eatoires, jouent un rˆ ole
important dans plusieurs appareils. Outre les jeux de casino, les jeux vid´ eo en font
grand usage. Si le comportement de ces jeux ´ etait toujours le mˆ eme chaque fois que
l’appareil est d´ emarr´ e, le joueur s’en lasserait rapidement.
Les g´ en´ erateurs de nombres al´ eatoires sont aussi importants dans la vie de tous
les jours qu’en science. La mod´ elisation sur ordinateur des cours boursiers ou de la
propagation de virus (humains ou informatiques !) et le choix des quelques (malheureux) contribuables dont le gouvernement scrutera la d´ eclaration utilisent ´ egalement
ces g´ en´ erateurs de fa¸ con routini` ere. En science, il est parfois difficile de mod´ eliser un
syst` eme dont le comportement n’est connu qu’avec certaines probabilit´ es. Un exemple
d’un tel syst` eme est le promeneur impartial se baladant sur la grande toile du Web
d´ ecrite ` a la section 9.2. On pr´ esuppose l’existence de g´ en´ erateurs de nombres al´ eatoires
lorsqu’on ´ etudie les algorithmes probabilistes dans le chapitre 7 sur la cryptographie.
Les g´ en´ erateurs de nombres al´ eatoires sont utilis´ es explicitement (!) dans la construction
d’images fractales ` a l’aide de syst` emes de fonctions it´ er´ ees (voir le chapitre 11) et dans
le signal des satellites du syst` eme de positionnement GPS (voir le chapitre 1).
Ces g´ en´ erateurs ont donc de nombreuses applications dans notre soci´ et´ e, et il
n’est pas ´ etonnant qu’il se fasse beaucoup de recherche pour trouver de « meilleurs »
g´ en´ erateurs de nombres al´ eatoires. Que signifie « meilleurs » ? Cela d´ epend du contexte.
Quand les g´ en´ erateurs de nombres al´ eatoires servent dans les casinos, on veut que les
joueurs ne puissent pas deviner leur fonctionnement pour ajuster leur strat´ egie de jeu.
Les g´ erants de casinos veulent aussi que les distributions probabilistes des nombres
al´ eatoires suivent des lois de probabilit´ e choisies a priori pour ne pas ˆ etre accus´ es de
fraude et d’offrir un jeu in´ equitable.
Introduisons d’abord un g´ en´ erateur « m´ ecanique » de nombres al´ eatoires. Quoique
son utilisation soit impraticable `
a grande ´ echelle, il illustre tous les d´ efis que devront
relever les algorithmes informatiques de g´ en´ erateurs. Jouons donc `
a pile ou face en
lan¸ cant une pi` ece de monnaie un grand nombre de fois : en notant 0 pour PILE et
1 pour FACE, nous obtenons une suite al´ eatoire de 0 et de 1, c’est-` a-dire une suite
qui semble n’ob´ eir ` a aucune r` egle. Si plusieurs personnes r´ ep` etent l’exp´ erience, elles
obtiennent en g´ en´ eral des suites qui n’ont rien `
a voir les unes avec les autres.
Supposons maintenant que nous voulions g´ en´ erer une suite de nombres al´ eatoires
de l’ensemble S = {0, . . . , 31}. ´
Etant donn´ e que 32 = 2
5 , chacun des nombres n ∈ S
devient en base 2
n = a 0 + 2a 1 + 2
2 a 2 + 2
3 a 3 + 2
4 a 4 =
4
i=0
a i 2
i
o` u a i ∈ {0, 1}. On le repr´ esente par le quintuple (a 0 , a 1 , a 2 , a 3 , a 4 ). Par exemple, le
quintuple (0, 1, 1, 0, 1) repr´ esente 2 + 4 + 16 = 22.
8 G´ en´ erateurs de nombres al´ eatoires
le hasard. Tous ont, dans leur programme, un segment produisant des nombres qui
apparaissent al´ eatoires ` a l’utilisateur, mais qui sont engendr´ es de fa¸ con compl` etement
d´ eterministe. Ces algorithmes, les g´ en´ erateurs de nombres al´ eatoires, jouent un rˆ ole
important dans plusieurs appareils. Outre les jeux de casino, les jeux vid´ eo en font
grand usage. Si le comportement de ces jeux ´ etait toujours le mˆ eme chaque fois que
l’appareil est d´ emarr´ e, le joueur s’en lasserait rapidement.
Les g´ en´ erateurs de nombres al´ eatoires sont aussi importants dans la vie de tous
les jours qu’en science. La mod´ elisation sur ordinateur des cours boursiers ou de la
propagation de virus (humains ou informatiques !) et le choix des quelques (malheureux) contribuables dont le gouvernement scrutera la d´ eclaration utilisent ´ egalement
ces g´ en´ erateurs de fa¸ con routini` ere. En science, il est parfois difficile de mod´ eliser un
syst` eme dont le comportement n’est connu qu’avec certaines probabilit´ es. Un exemple
d’un tel syst` eme est le promeneur impartial se baladant sur la grande toile du Web
d´ ecrite ` a la section 9.2. On pr´ esuppose l’existence de g´ en´ erateurs de nombres al´ eatoires
lorsqu’on ´ etudie les algorithmes probabilistes dans le chapitre 7 sur la cryptographie.
Les g´ en´ erateurs de nombres al´ eatoires sont utilis´ es explicitement (!) dans la construction
d’images fractales ` a l’aide de syst` emes de fonctions it´ er´ ees (voir le chapitre 11) et dans
le signal des satellites du syst` eme de positionnement GPS (voir le chapitre 1).
Ces g´ en´ erateurs ont donc de nombreuses applications dans notre soci´ et´ e, et il
n’est pas ´ etonnant qu’il se fasse beaucoup de recherche pour trouver de « meilleurs »
g´ en´ erateurs de nombres al´ eatoires. Que signifie « meilleurs » ? Cela d´ epend du contexte.
Quand les g´ en´ erateurs de nombres al´ eatoires servent dans les casinos, on veut que les
joueurs ne puissent pas deviner leur fonctionnement pour ajuster leur strat´ egie de jeu.
Les g´ erants de casinos veulent aussi que les distributions probabilistes des nombres
al´ eatoires suivent des lois de probabilit´ e choisies a priori pour ne pas ˆ etre accus´ es de
fraude et d’offrir un jeu in´ equitable.
Introduisons d’abord un g´ en´ erateur « m´ ecanique » de nombres al´ eatoires. Quoique
son utilisation soit impraticable `
a grande ´ echelle, il illustre tous les d´ efis que devront
relever les algorithmes informatiques de g´ en´ erateurs. Jouons donc `
a pile ou face en
lan¸ cant une pi` ece de monnaie un grand nombre de fois : en notant 0 pour PILE et
1 pour FACE, nous obtenons une suite al´ eatoire de 0 et de 1, c’est-` a-dire une suite
qui semble n’ob´ eir ` a aucune r` egle. Si plusieurs personnes r´ ep` etent l’exp´ erience, elles
obtiennent en g´ en´ eral des suites qui n’ont rien `
a voir les unes avec les autres.
Supposons maintenant que nous voulions g´ en´ erer une suite de nombres al´ eatoires
de l’ensemble S = {0, . . . , 31}. ´
Etant donn´ e que 32 = 2
5 , chacun des nombres n ∈ S
devient en base 2
n = a 0 + 2a 1 + 2
2 a 2 + 2
3 a 3 + 2
4 a 4 =
4
i=0
a i 2
i
o` u a i ∈ {0, 1}. On le repr´ esente par le quintuple (a 0 , a 1 , a 2 , a 3 , a 4 ). Par exemple, le
quintuple (0, 1, 1, 0, 1) repr´ esente 2 + 4 + 16 = 22.