Méthode de rejet

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.