Échantillonnage de nombres
pseudo-aléatoires
L'échantillonnage de nombres pseudo-aléatoires ou la génération de variable aléatoire pseudo-aléatoire non uniforme est la pratique numérique consistant à générer des nombres pseudo-aléatoires qui sont distribués selon une donnée distribution de probabilité.
Les méthodes d'échantillonnage d'une distribution non uniforme sont généralement basées sur la disponibilité d'un générateur de nombres pseudo-aléatoires https://convertir.github.io/outils/generateur-chiffre-aleatoire.html , produisant des nombres X uniformément répartis. Des algorithmes de calcul sont ensuite utilisés pour manipuler une seule variable aléatoire, X, ou souvent plusieurs de ces variables, dans une nouvelle variable aléatoire Y telle que ces valeurs aient la distribution requise.
Historiquement, des méthodes de base pour l'échantillonnage de nombres pseudo-aléatoires ont été développées pour les simulations de Monte-Carlo dans le projet Manhattan.
Distributions discrètes finies
Pour une distribution de probabilité discrète avec un nombre fini "N" d'indices auxquels la fonction de masse de probabilité "F" prend des valeurs non nulles, l'algorithme d'échantillonnage de base est simple. L'intervalle [0, 1) est divisé en "N" intervalles [0, f (1)), [ f (1), f (1) + f (2)), ... La largeur de l'intervalle "I" est égale à la probabilité f ( i ). On prend un nombre pseudo-aléatoire X uniformément distribué et on cherche l'indice i de l'intervalle correspondant. Le si déterminé jeaura la distribution f ( i ).
Formaliser cette idée devient plus facile en utilisant la fonction de distribution cumulative.
Il est commode de définir F (0) = 0. Les n intervalles sont alors simplement [ F (0), F (1)), [ F (1), F (2)), ..., [ F ( n - 1), F ( n )). La tâche de calcul principale consiste alors à déterminer i pour lequel F ( i - 1) = X < F ( i ).
Cela peut être fait par différents algorithmes:
- Recherche linéaire, temps de calcul linéaire en "n".
- Recherche binaire, le temps de calcul va de pair avec log "n".
- Recherche Indexé, a également appelé la méthode de césure.
- Méthode alias, le temps de calcul est constant, en utilisant des tables pré-calculées.
Distributions continues
Méthodes génériques pour générer des échantillons indépendants :
Échantillonnage de rejet pour les fonctions de densité arbitraires
Échantillonnage par transformée inverse pour les distributions dont le CDF est connu
Échantillon de tranche
Algorithme de Ziggurat , pour les fonctions de densité décroissantes de façon monotone, ainsi que les distributions unimodales symétriques
Générateur de nombres aléatoires par convolution , pas une méthode d'échantillonnage en soi: il décrit l'utilisation de l'arithmétique en plus d'une ou de plusieurs méthodes d'échantillonnage existantes pour générer des distributions plus impliquées.
Méthodes génériques pour générer des échantillons corrélés (souvent nécessaires pour des distributions de formes inhabituelles ou de grandes dimensions):
- Chaîne de Markov Monte Carlo , le principe général
- Algorithme Metropolis – Hastings
- Échantillonnage de Gibbs
- Échantillon de tranche
- Chaîne de Markov à sauts réversibles, Monte Carlo, lorsque le nombre de dimensions n'est pas fixe (par exemple, lors de l'estimation d'un modèle de mélange et de l'estimation simultanée du nombre de composants du mélange)
- Filtres à particules , lorsque les données observées sont connectées dans une chaîne de Markov et doivent être traitées séquentiellement
Pour générer une distribution normale :
- Transformation de Box-Muller
- Méthode polaire Marsaglia
Bibliothèques de logiciels
La bibliothèque scientifique GNU comprend une section intitulée "Distributions de nombres aléatoires" avec des routines pour l’échantillonnage de plus de vingt distributions différentes.
