Probabilités de l'ingénieur : algorithmes stochastiques et simulation/Simulation de la loi uniforme
Générateurs pseudo-aléatoires[modifier | modifier le wikicode]
Principe : comment simuler le hasard ?[modifier | modifier le wikicode]
L'objectif principal de ce chapitre est d'apprendre comment on peut simuler une variable aléatoire par ordinateur. Ou en d'autres mots : comment faire en sorte qu'un ordinateur donne des chiffres au hasard ?
La réponse est claire : c’est impossible. Une machine a besoin d'un algorithme pour fonctionner, et ne peut donc pas générer de lui-même des nombres sans instruction.
Néanmoins, on peut lui donner un code qui permettrait de générer des chiffres de sorte qu'on puisse avoir des nombres approchant un tirage hasardeux. Il suffirait que les nombres obtenus donnent des résultats satisfaisants à divers tests statistiques pour qu'on puisse supposer qu’ils sont aléatoires. On parle dans ce cas de générateurs pseudo-aléatoires, puisque malgré tout, un algorithme, forcément déterministe, est utilisé.
Propriétés[modifier | modifier le wikicode]
- Périodicité
- La plupart des générateurs présentent un biais majeur : à cause de l'état déterministe d'un tel algorithme et des ressources limitées de la machine, le générateur sera forcément périodique, c'est-à-dire que toute séquence qu’il engendrera atteindra le même état au moins deux fois.
On peut néanmoins pallier à ce problème en utilisant pour le même algorithme, différentes graines (le premier terme) ou utiliser des défauts techniques (imprécision de la machine,...)
- Biais
- Du fait de l'état déterministe, un test statistique, du moment qu’il a suffisamment de données, devrait en théorie montrer justement que les tirages obtenus par un générateur pseudo-aléatoire n'ont justement rien d'aléatoire. Seulement, les crypto-analystes considèrent qu'actuellement, aucune machine n'offre assez de puissance et de mémoire pour y parvenir. Cependant, un test statistique peut mettre en lumière des défauts tels que :
- période plus courte avec certaines graines
- qualité du générateur qui varie fortement selon la graine
- distribution imparfaite, manque d'uniformité
- mauvaise distribution dans un espace de dimension supérieure à 1
- ou au contraire : distribution trop idéale, uniformité trop parfaite
- valeurs successives qui ne sont pas indépendantes (ce qui est toujours le cas, sauf si on injecte des données, issues de sources aléatoires, dans une étape de la génération)
- certains bits dans les sorties sont moins aléatoires (par exemple, le bit no8 reste souvent à 1)
|
Avant utilisation d'un générateur, il convient toujours de lui faire subir un test statistique avalisant son caractère pseudo-aléatoire. |
Exemples[modifier | modifier le wikicode]
Générateur de Von Neumann[modifier | modifier le wikicode]
Cette méthode, connue également connue sous le nom de middle-square, est une des premières utilisées comme générateur pseudo-aléatoire.
L'algorithme utilisé est simple :
- Prendre un nombre de n chiffres
- L'élever au carré
- Prendre les n chiffres du milieu
et ainsi de suite.
Simple, il présente un grand défaut : il est de période très faible, quelle que soit la graine. Il montra donc ses limites lors des applications dans la méthode de Monte-Carlo.
Méthode de Fibonacci[modifier | modifier le wikicode]
Cette méthode est basée sur la construction de la suite de Fibonacci. Elle utilise l'algorithme :
avec donnés.
![{\displaystyle X_{n}\equiv X_{n-1}+X_{n-2}[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e82afe068db13c1b30a77b8d3b6ce45bee9c238)
On peut généraliser en écrivant :
avec donnés.
![{\displaystyle X_{n}\equiv X_{n-1}+X_{n-k}[M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29705070e84f2b7061f1f4d3f3046ccfc776e838)
Simple d'implémentation, la qualité de ce générateur dépend de k et des graines utilisées.
