8.3 G´ en´ erateurs Fp-lin´ eaires
259
Le th´ eor` eme suivant montre qu’un registre ` a d´ ecalage a de bonnes propri´ et´ es statistiques quand on consid` ere des sous-suites de longueur k telles que k ≤ r.
Th´ eor` eme 8.13 Consid´ erons un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 sont choisis tels que le polynˆ ome Q(x) de (8.5) est primitif sur F 2 . Soit
(a 0 , . . . , a r−1 ) une suite de conditions initiales telle que les a i ne sont pas tous nuls et
soit k ≤ r. Alors, dans une fenˆ etre de longueur 2
r
− 1 de la suite g´ en´ er´ ee par le registre
(la fenˆ etre ´ etant consid´ er´ ee comme une suite cyclique), toute sous-suite de longueur k
apparaˆ ıt 2
r−k fois, sauf la sous-suite nulle qui apparaˆ ıt (2
r−k
− 1) fois.
Preuve Dans le corollaire 8.12, on a montr´ e que toutes les sous-suites de longueur
r apparaissent exactement une fois, sauf la sous-suite nulle. Prenons une sous-suite
b 0 , . . . , b k−1 de longueur k et consid´ erons toutes les mani` eres de la transformer en une
sous-suite de longueur r en ajoutant des symboles b k , . . . , b r−1 ` a sa droite : il existe
2
r−k mani` eres diff´ erentes de l’allonger, puisqu’on a deux choix pour chacun des b j ,
j = k, . . . , r − 1. Si au moins un des b i , i = 0, . . . , k − 1 est non nul, toutes ces mani` eres
d’allonger la sous-suite existent dans la suite cyclique, puisque toutes les sous-suites
non identiquement nulles de longueur r existent. De plus, chacune de ces 2
r−k mani` eres
apparaˆ ıt exactement une fois, puisque chaque sous-suite non identiquement nulle de
longueur r apparaˆ ıt exactement une fois. Ainsi la sous-suite b 0 , . . . , b k−1 apparaˆ ıt exactement 2
r−k fois.
Au contraire, si la sous-suite b 0 , . . . , b k−1 est la sous-suite nulle, on doit exclure la
transformation en sous-suite nulle de longueur r. Toutes les autres mani` eres d’allonger la sous-suite apparaissent exactement une fois. Donc, la sous-suite nulle apparaˆ ıt
exactement 2
r−k
− 1 fois.
8.3.2 Une le¸ con pour les jeux de hasard
Les th´ eor` emes 8.9 et 8.13 nous offrent la cl´ e de l’histoire du joueur appr´ ehend´ e au
Casino de Montr´ eal. Le joueur en question connaissait, de par son travail, le m´ ecanisme
des g´ en´ erateurs de nombres al´ eatoires. Il savait que les algorithmes sous-jacents sont
d´ eterministes et donc, qu’un algorithme donn´ e, pour des conditions initiales identiques,
g´ en` ere des suites identiques. Lors de pr´ ec´ edentes visites, il avait remarqu´ e que les
nombres des appareils de keno sortaient, soir apr` es soir, dans le mˆ eme ordre. Il nota
donc ces nombres et les joua avec le r´ esultat d´ ecrit au d´ ebut du chapitre. Mais sachant
que ce probl` eme existe, pourquoi le Casino de Montr´ eal a-t-il accept´ e de r´ eouvrir le
jeu sur ces machines ? La raison officielle a ´ et´ e que ces machines avaient ´ et´ e mal programm´ ees et que l’erreur avait ´ et´ e corrig´ ee. Une autre raison (moins honorable pour le
casino, mais ´ egalement possible) est que les machines ´ etaient ´ eteintes tous les soirs par
un employ´ e, par exemple celui qui fait le m´ enage. Alors, au moment du red´ emarrage,
les machines r´ eutilisaient les mˆ emes conditions initiales a i , produisant soir apr` es soir
les mˆ emes nombres dans le mˆ eme ordre.
Cette histoire soul` eve en fait une autre question ! Comment peut-on changer les
conditions initiales pour que les suites a i ne soient pas toujours les mˆ emes ` a chaque
259
Le th´ eor` eme suivant montre qu’un registre ` a d´ ecalage a de bonnes propri´ et´ es statistiques quand on consid` ere des sous-suites de longueur k telles que k ≤ r.
Th´ eor` eme 8.13 Consid´ erons un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 sont choisis tels que le polynˆ ome Q(x) de (8.5) est primitif sur F 2 . Soit
(a 0 , . . . , a r−1 ) une suite de conditions initiales telle que les a i ne sont pas tous nuls et
soit k ≤ r. Alors, dans une fenˆ etre de longueur 2
r
− 1 de la suite g´ en´ er´ ee par le registre
(la fenˆ etre ´ etant consid´ er´ ee comme une suite cyclique), toute sous-suite de longueur k
apparaˆ ıt 2
r−k fois, sauf la sous-suite nulle qui apparaˆ ıt (2
r−k
− 1) fois.
Preuve Dans le corollaire 8.12, on a montr´ e que toutes les sous-suites de longueur
r apparaissent exactement une fois, sauf la sous-suite nulle. Prenons une sous-suite
b 0 , . . . , b k−1 de longueur k et consid´ erons toutes les mani` eres de la transformer en une
sous-suite de longueur r en ajoutant des symboles b k , . . . , b r−1 ` a sa droite : il existe
2
r−k mani` eres diff´ erentes de l’allonger, puisqu’on a deux choix pour chacun des b j ,
j = k, . . . , r − 1. Si au moins un des b i , i = 0, . . . , k − 1 est non nul, toutes ces mani` eres
d’allonger la sous-suite existent dans la suite cyclique, puisque toutes les sous-suites
non identiquement nulles de longueur r existent. De plus, chacune de ces 2
r−k mani` eres
apparaˆ ıt exactement une fois, puisque chaque sous-suite non identiquement nulle de
longueur r apparaˆ ıt exactement une fois. Ainsi la sous-suite b 0 , . . . , b k−1 apparaˆ ıt exactement 2
r−k fois.
Au contraire, si la sous-suite b 0 , . . . , b k−1 est la sous-suite nulle, on doit exclure la
transformation en sous-suite nulle de longueur r. Toutes les autres mani` eres d’allonger la sous-suite apparaissent exactement une fois. Donc, la sous-suite nulle apparaˆ ıt
exactement 2
r−k
− 1 fois.
8.3.2 Une le¸ con pour les jeux de hasard
Les th´ eor` emes 8.9 et 8.13 nous offrent la cl´ e de l’histoire du joueur appr´ ehend´ e au
Casino de Montr´ eal. Le joueur en question connaissait, de par son travail, le m´ ecanisme
des g´ en´ erateurs de nombres al´ eatoires. Il savait que les algorithmes sous-jacents sont
d´ eterministes et donc, qu’un algorithme donn´ e, pour des conditions initiales identiques,
g´ en` ere des suites identiques. Lors de pr´ ec´ edentes visites, il avait remarqu´ e que les
nombres des appareils de keno sortaient, soir apr` es soir, dans le mˆ eme ordre. Il nota
donc ces nombres et les joua avec le r´ esultat d´ ecrit au d´ ebut du chapitre. Mais sachant
que ce probl` eme existe, pourquoi le Casino de Montr´ eal a-t-il accept´ e de r´ eouvrir le
jeu sur ces machines ? La raison officielle a ´ et´ e que ces machines avaient ´ et´ e mal programm´ ees et que l’erreur avait ´ et´ e corrig´ ee. Une autre raison (moins honorable pour le
casino, mais ´ egalement possible) est que les machines ´ etaient ´ eteintes tous les soirs par
un employ´ e, par exemple celui qui fait le m´ enage. Alors, au moment du red´ emarrage,
les machines r´ eutilisaient les mˆ emes conditions initiales a i , produisant soir apr` es soir
les mˆ emes nombres dans le mˆ eme ordre.
Cette histoire soul` eve en fait une autre question ! Comment peut-on changer les
conditions initiales pour que les suites a i ne soient pas toujours les mˆ emes ` a chaque