Méthode de rejet

La méthode de rejet est utilisée pour génèrer indirectement une variable aléatoire, de densité de probabilité quand on ne sait pas simuler directement la loi de densité de probabilité.

But

La méthode de rejet est utilisée pour génèrer indirectement une variable aléatoire, de densité de probabilité quand 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 également 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

$M=\{U \le f_{X}(Y)\}.$

C'est à dire,

f X (x) = f Y (x | M).

Pour simuler une suite de variables aléatoires réelles de distribution semblable à celle de il suffit par conséquent, 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

La méthode de rejet

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 (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
Tant que \tfrac{f (Y) }{c\, g (Y) }, \ " src="http ://upload. wikimedia. org/math/f/5/b/f5bc32ed3a2f842cd3æ60bd4705c472. png" /> 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 par conséquent lui-même aléatoire. On peut montrer que suit la loi géométrique de paramètre i. e.

$\mathbb{P}\left(N=k\right)\ =\ \left(1-\tfrac{1}{c}\right)ˆ{k-1}\,\tfrac{1}{c}\ 1_{k\ge 1}.$

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$ .

$\mathbb{E}\left[N\right]\ =\ c.$

On a par conséquent tout intérêt à choisir c le plus petit envisageable. En pratique, une fois la fonction g choisie, le meilleur choix de c est par conséquent la plus petite constante qui majore le ratio f/g, c'est-à-dire :

$c = \sup \frac{f(x)}{g(x)}.$

Notons que, soit c est supérieur strict à 1, soit f=g, la seconde alternative étant assez théorique : en effet, comme

$0\ \le\ \int_{\mathbb{R}}\left(cg-f\right)\ =\ c\ \int_{\mathbb{R}}g\ -\ \int_{\mathbb{R}}f\ =\ c-1.$

On a par conséquent intérêt à choisir c le plus proche de 1 envisageable, pour que le nombre d'itérations moyen soit proche de 1 lui aussi. Bref, le choix de l'enveloppe g est essentiel :

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 envisageable ;
la fonction cg doit majorer la densité f.

Les deux derniers points amènent à rechercher une fonction g dont le graphe "épouse" étroitement celui de f.

Généralisations

Le fait que $f(x) \le c g(x)$ peut être re-écrit comme $f (x) = c g (x) h (x)$ où h est une fonction à valeurs dans [0;1]. On remplace l'étape 4 de l'algorithme d'origine par la condition :

Tant que

U / h (X) > 1

, reprendre en 1;

Une autre généralisation peut être reconnue quand l'évaluation du ratio f/g est délicate. On cherche alors à encadrer la fonction f par deux fonctions aisément évaluables :

$h_1(x) \leq f(x) \leq h_2(x)$

tout en supposant qu'il existe une densité g telle que $f(x) \le c g(x)$ . Aucune autre hypothèse n'est nécessaire; surtout, il ne faut pas imposer que $h_2(x) \leq c g(x)$ . 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 ( $Z \le h_1(Y)$ , vrai, faux) ;
- Si Suite alors
  - Si $Z \leq h_2(Y)$ alors Suite := SI ( $Z \leq f(Y)$ , vrai, faux) fin 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 par conséquent son évaluation) que particulièrement 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

Recherche sur Amazon (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/M%C3%A9thode_de_rejet.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.