Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode de rejet
Résumé
La méthode du rejet est une méthode utilisée dans le domaine des probabilités.
La méthode de rejet est utilisée pour engendrer indirectement une variable aléatoire , de densité de probabilité lorsqu'on ne sait pas simuler directement la loi de densité de probabilité (c'est le cas par exemple si n'est pas une densité classique, mais aussi pour la loi de Gauss).
Soit un couple de variables aléatoires indépendantes tirées selon une loi uniforme, i.e. est un point tiré uniformément dans le carré unité. On peut alors montrer que la distribution de est la loi conditionnelle de sachant l'événement
Autrement dit,
Pour simuler une suite de variables aléatoires réelles de distribution identique à celle de il suffit donc, dans une suite de tirages de couples uniformes indépendants, de sélectionner les correspondant aux tirages vérifiant et de rejeter les autres.
On voudrait simuler une variable aléatoire réelle de densité de probabilité . On suppose
qu'il existe une autre densité de probabilité telle que le ratio soit borné, disons par (i.e. ),
qu'on sache simuler de densité
La version basique de la méthode de rejet prend la forme suivante:
Boucler:
Tirer de densité
Tirer selon la loi uniforme U(0;1), indépendamment de
Tant que reprendre en 1;
Accepter comme un tirage aléatoire de densité de probabilité
On remarque que l'algorithme comporte une boucle dont la condition porte sur des variables aléatoires. Le nombre d'itérations, notons-le est donc lui-même aléatoire. On peut montrer que suit la loi géométrique de paramètre c'est-à-dire
En effet,
est la probabilité, lors d'une itération, de terminer la boucle, et, par conséquent, d'accepter Y. Par suite, l'espérance de (c.-à-d. le nombre moyen d'itérations à effectuer avant d'obtenir une réalisation de la densité f ) vaut .
On a donc tout intérêt à choisir c le plus petit possible. En pratique, une fois la fonction g choisie, le meilleur choix de c est donc la plus petite constante qui majore le ratio f/g, c'est-à-dire:
Notons que, soit c est supérieur strict à 1, soit f=g, la deuxième solution étant assez théorique : en effet, comme
On a donc intérêt à choisir c le plus proche de 1 possible, pour que le nombre d'itérations moyen soit proche de 1 lui aussi.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.