- Méthode Du Rejet
-
Méthode de rejet
Sommaire
But
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, tellement classique).
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,
fX(x) = fY(x | M). 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.
Algorithme
On voudrait simuler une variable aléatoire réellede densité de probabilité
. On suppose
- qu'il existe une autre densité de probabilité
telle que le ratio
soit borné, disons par
(bref,
),
- 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
- Tirer
- Tant que
tfrac{f(Y)}{c\,g(Y)},\ " style="max-width : 98%; height: auto; width: auto;" src="/pictures/frwiki/102/f5bc32ed3a2f842cd3ae60bd4705c472.png" border="0"> 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
i.e.
Par suite, l'espérance de
(c.-à-d. le nombre moyen d'itérations à obtenir avant une réalisation de la loi f) vaut c.
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 alternative é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. Bref, le choix de l'enveloppe g est primordial:
- le tirage de la loi g doit être facile ;
- l'évaluation de f(x)/g(x) doit être aisée ;
- la constante c doit être la plus petite possible ;
- la fonction cg doit majorer la densité f.
Les deux derniers points conduisent à rechercher une fonction g dont le graphe "épouse" étroitement celui de f.
Généralisations
Le fait que
peut être re-écrit comme f(x) = cg(x)h(x) où h est une fonction à valeurs dans [0;1]. On remplace l'étape 4 de l'algorithme initial par la condition:
-
-
- Tant que U / h(X) > 1, reprendre en 1;
-
Une autre généralisation peut être considérée lorsque l'évaluation du ratio f/g est délicate. On cherche alors à encadrer la fonction f par deux fonctions facilement évaluables:
tout en supposant qu'il existe une densité g telle que
. Aucune autre hypothèse n'est nécessaire; en particulier, il ne faut pas imposer que
. L'algorithme prend alors la forme suivante:
- Suite := vrai
- Tant que Suite
- tirer Y selon g;
- tirer U selon la loi uniforme U(0;1), indépendamment de Y;
- Z := U c g(Y);
- Suite := SI(
, vrai, faux );
- Si Suite alors
- Si
alors Suite:= SI(
,vrai,faux) fin si
- Si
- Fin si
- fin tant que
- retourne Y comme un tirage de f.
Dans cet algorithme, les fonctions h permettent de recourir à une comparaison à f (et donc son évaluation) que très rarement.
Voir aussi
- Méthode de la transformée inverse et son graphe
Références
- Robert, C.P. and Casella, G. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
- J. von Neumann, "Various techniques used in connection with random digits. Monte Carlo methods", Nat. Bureau Standards, 12 (1951), pp. 36–38.
- Luc Devroye. Non-Uniform Random Variate Generation. New York: Springer-Verlag, 1986. (site) Voir le chapitre 2, section 3, p. 40
- Portail des probabilités et des statistiques
Catégorie : Probabilités - qu'il existe une autre densité de probabilité
Wikimedia Foundation. 2010.