Génération de nombres aléatoires
La génération de nombres aléatoires produit des séquences de nombres qui se comportent comme s'ils étaient tirés d'une distribution de probabilité cible, fournissant les entrées stochastiques dont dépendent la simulation de Monte Carlo, le rééchantillonnage et les algorithmes randomisés.
Definition
La génération de nombres aléatoires est la construction et l'analyse d'algorithmes qui génèrent des nombres approximant des tirages indépendants d'une distribution de probabilité spécifiée, à partir d'une source uniforme sur l'intervalle unitaire.
Scope
Ce domaine couvre les algorithmes déterministes qui produisent des séquences pseudo-aléatoires uniformes, les transformations qui convertissent des variables uniformes en échantillons issus de distributions arbitraires, les schémas d'acceptation-rejet pour les densités qui ne peuvent être inversées sous forme close, et les dispositifs de réduction de variance qui améliorent l'efficacité des estimateurs de simulation. Les sources d'entropie matérielles et les générateurs cryptographiques sont mentionnés comme des cas limites, mais l'accent est mis sur les générateurs pour la simulation statistique.
Sub-topics
Core questions
- Comment un algorithme déterministe peut-il produire des séquences qui réussissent les tests statistiques de caractère aléatoire et d'uniformité ?
- Étant donné un générateur uniforme, comment obtient-on des échantillons à partir d'une distribution cible arbitraire ?
- Lorsque l'inversion directe est irréalisable, comment l'échantillonnage par acceptation-rejet permet-il d'échantillonner à partir d'une densité ?
- Comment la variance d'un estimateur de simulation peut-elle être réduite sans augmenter la taille de l'échantillon ?
Key theories
- Génération uniforme pseudo-aléatoire
- Une récurrence avec une longue période et une bonne structure de réseau produit des séquences déterministes qui sont statistiquement indiscernables de tirages uniformes indépendants ; la qualité est évaluée par la longueur de la période, l'équidistribution et des batteries de tests empiriques.
- Méthodes de transformation
- La transformation intégrale de probabilité et ses variantes mappent les variables uniformes à une distribution cible : l'application de la fonction de répartition inverse produit des échantillons exacts chaque fois qu'elle peut être évaluée.
- Échantillonnage par acceptation-rejet
- En proposant à partir d'une enveloppe facile à échantillonner qui domine la densité cible et en acceptant les propositions avec une probabilité égale au rapport de densité, on obtient des échantillons exacts à partir de densités qui ne peuvent être inversées, à un coût déterminé par la qualité de l'ajustement de l'enveloppe.
Clinical relevance
Une génération fiable de nombres aléatoires est le fondement de l'intégration de Monte Carlo, de l'inférence par bootstrap et permutation, de l'échantillonnage a posteriori bayésien, des expériences randomisées et des études de simulation dans toutes les sciences ; des générateurs de mauvaise qualité avec des périodes courtes ou des artefacts de réseau peuvent biaiser silencieusement les résultats de simulation, de sorte que la qualité du générateur est une préoccupation fondamentale en matière de reproductibilité.
History
Les premiers travaux de Monte Carlo à Los Alamos reposaient sur de simples schémas congruents et du milieu du carré ; les décennies suivantes ont révélé leurs défauts et produit une théorie rigoureuse de la structure de réseau et de l'équidistribution, aboutissant à des générateurs à longue période et à des suites de tests standardisées pour évaluer le caractère aléatoire.
Key figures
- Luc Devroye
- Donald Knuth
- Pierre L'Ecuyer
- John von Neumann
Related topics
Seminal works
- devroye1986
- knuth1997
Frequently asked questions
- Les nombres aléatoires générés par ordinateur sont-ils vraiment aléatoires ?
- La plupart sont pseudo-aléatoires : un algorithme déterministe produit une séquence reproductible à partir d'une graine (seed). Les générateurs bien conçus ont de très longues périodes et réussissent les tests statistiques, de sorte que la sortie est indiscernable d'un véritable caractère aléatoire à des fins de simulation, tout en restant exactement reproductible lorsque la graine est fixée.
- Pourquoi la fonction de répartition inverse est-elle si centrale ?
- Si U est uniforme sur (0,1), alors l'application de la fonction de répartition inverse de n'importe quelle distribution à U produit un échantillon de cette distribution. Cette transformation intégrale de probabilité est exacte et constitue la méthode par défaut chaque fois que l'inverse peut être calculé.