La dernière méthode que  je présenterais est est celle des générateurs congruentiels linéaires. On retrouve l’idée de linéarité que l’on avait pas exemple dans le premier générateur proposé (ici), la notion de congruence est liée à des problèmes d’arithmétique et d’écriture de nombres dans les bases. On retiendra une fonction de récurrence de la forme suivante

Pour que l’algorithme marche bien, on essaye de partir d’une valeur initiale correspondant à un nombre premier.
Prenons un premier exemple simple (inspiré par wikipedia). Si on prend des valeurs un peu au hasard, par exemple on obtient

• avec X₀ = 10, la suite : 10, 10, 10, 10, 10, …
• avec X₀ = 11, la suite : 11, 35, 123, 19, 235, 3, 91, 243, 203, 227, 59, 211, 171, 195, 27, 179, 139, 163, 251, 147, 107, 131, …
• avec X₀ = 12, la suite : 12, 60, 236, 28, 204, 252, 172, 220, 140, 188, 108, 156, 76, 124, 44, 92, 12, 60, 236, 28, 204, 252, 172, …

Bref, on notera déjà qu’il est effectivement intéressant de partir d’un nombre premier, car on boucle alors beaucoup moins vite. Ah oui, et pour se ramener sur l’intervalle [0,1], on divise par m. On a alors intérêt à avoir m assez grand.
Prenons un second exemple simple (inspiré du générateur proposé par Robert Sedgewick). On prend , et on part de 0.

[1]         0        1 31415822 40519862 31536702 84962343
[7]  59428603 54128063 38284723  4802584 19281465 53057765
[13] 47900065 67928365 55662665 20022965 84329266 25717386
[19] 95163907 67972648 42464008 74270568 69856328 96165288
[25] 74221448 24728808  5671369 13328949 75902129 98182909

La série a l’allure suivante,
Et si on regarde l’histogramme et la fonction d’autocorrélation sur les 10 000 premières valeurs, on a gardé l’uniformité (ou tout du moins on ne doit pas en être trop loin), et on n’a plus d’autocorrélation.

Parmi les générateurs ultra-classiques, mais mauvais, on retiendra le RANDU, datant des années 60, implémenté alors sur les IBM, Mais cet algorithme présente de très gros défauts numériques. Je n’aborderais pas ici les problèmes de ce générateur (je l’avais fait dans le chapitre sur les simulations dans le tome 2 du livre avec Michel Denuit).
Bref, voilà ce qu’on peut raconter rapidement sur les méthodes de construction de nombres aléatoires, ou comme on dit généralement pseudo-aléatoires. Pour quelques réflexions sur l’utilisation de méthodes déterministes pour générer du hasard, je renvoie au très beau petit livre d’Ivar Ekeland intitulé Chaos. Et histoire d’insister un peu lourdement, ces billets (comme la plupart de ceux présent sur ce blog) n’ont pas grande prétention, si ce n’est présenter des concepts parfois compliqués “avec les mains” (et des dessins). Pour aller plus loin, on trouvera de très bons résumés de ces techniques sur le net, ici ou là. Je laisse les plus curieux continuer. Sinon le chapitre 7 du Monte Carlo de Fishman propose une analyse poussée de ces méthodes. Et je voulais aussi noter que ce que j’ai proposé dans ces billets, c’est simplement de tirer des nombres aléatoires uniformément répartis sur [0,1]. Pour générer autre chose que de l’uniformité, je renvoie à la bible de Luc Devroye, non-uniform random variate generation, épuisé chez Springer, mais en ligne ici.

Bon l’idée de récurrence les dernières fois (ici et là) n’était pas forcément mauvaise, mais telle qu’elle était présentée, ça ne marchait pas très bien… Une autre méthode peut être celle proposée par John von Neumann, parfois appelée middle square. On prend un nombre à 4 chiffres, on l’élève au carré, et on prend les 4 chiffres du “milieu“.  Par exemple à partir de 1234, dont le carré est 1522756, puis on prend le carré de 2275, c’est à dire 5175625… etc. On prend alors comme nombre cette suite de nombres divisés par 10000 (pour revenir entre 0 et 1). Sur cette exemple on note que l’on peut assez rapidement boucler, et retomber sur la même suite (ceci reste le problème central de tous les algorithmes récursifs).

Bref, on n’y est toujours pas… Pourtant, de loi, la suite des nombres peut  sembler aléatoires (en oubliant le fait que l’on s’est restreint à 4 chiffres),

[1]  0.2756 0.5536 0.7296 0.1616 0.1456 0.9936 0.4096 0.7216
[9]  0.7065 0.4225 0.5062 0.3844 0.6336 0.4896 0.7081 0.4056
[17] 0.1136 0.0496 0.6016 0.2256 0.9536 0.5296 0.7616 0.3456
[25] 0.3936 0.2096 0.3216 0.2656 0.4336 0.8008 0.8064 0.8096
[33] 0.5216 0.6656 0.2336 0.6896 0.4816 0.3856 0.8736 0.7696

Mais si on regarde cet exemple de plus prêt, on note que le chiffre 6 apparaît très fréquemment à la fin, par exemple…. Même si cette méthode est souvent présentée (par exemple dans la page de wikipedia consacrée aux méthodes de simulations, ici), elle marche beaucoup moins bien que les méthodes que j’avais présentées auparavant (ici et là) et que l’on cite assez peu.