Méthode de rejet

Méthode de rejet

Sommaire

But

La méthode de rejet est utilisée pour engendrer indirectement une variable aléatoire \scriptstyle\ X\ , de densité de probabilité \scriptstyle\ f, lorsqu'on ne sait pas simuler directement la loi de densité de probabilité \scriptstyle\ f\ (c'est le cas par exemple si \scriptstyle\ f\ n'est pas une densité classique, mais aussi pour la loi de Gauss).

Soit \scriptstyle\ (Y,U)\ un couple de variables aléatoires indépendantes tirées selon une loi uniforme, i.e. \scriptstyle\ (Y,U)\ est un point tiré uniformément dans le carré unité. On peut alors montrer que la distribution de \scriptstyle\ X\ est la loi conditionnelle de \scriptstyle\ X\ sachant l'événement

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

Autrement dit,

fX(x) = fY(x | M).

Pour simuler une suite de variables aléatoires réelles \scriptstyle\ \left(X_n\right)_{n\ge 1}\ de distribution identique à celle de \scriptstyle\ X, il suffit donc, dans une suite de tirages de couples \scriptstyle\ (Y_i,U_i)\ uniformes indépendants, de sélectionner les \scriptstyle\ Y_i\ correspondant aux tirages \scriptstyle\ (Y_i,U_i)\ vérifiant \scriptstyle\ M, et de rejeter les autres.

Algorithme

La méthode de rejet


On voudrait simuler une variable aléatoire réelle \scriptstyle\ X\ de densité de probabilité \scriptstyle\ f\ . On suppose

  • qu'il existe une autre densité de probabilité \scriptstyle\ g\ telle que le ratio \scriptstyle\ \frac{f}{g}\ soit borné, disons par \scriptstyle\ c\ (bref, \scriptstyle\ f \le c g),
  • qu'on sache simuler \scriptstyle\ Y\ de densité \scriptstyle\ g.

La version basique de la méthode de rejet prend la forme suivante:

  1. Boucler:
    • Tirer \scriptstyle\ Y\ de densité \scriptstyle\ g;
    • Tirer \scriptstyle\ U\ selon la loi uniforme U(0;1), indépendamment de \scriptstyle\ Y;
  2. Tant que \scriptstyle\ U> \tfrac{f(Y)}{c\,g(Y)},\ reprendre en 1;
  3. Accepter \scriptstyle\ Y\ comme un tirage aléatoire de densité de probabilité \scriptstyle\ f.

On remarque que l'algorithme comporte une boucle dont la condition porte sur des variables aléatoires. Le nombre d'itérations, notons-le \scriptstyle\ N, est donc lui-même aléatoire. On peut montrer que \scriptstyle\ N\ suit la loi géométrique de paramètre \scriptstyle\ \frac{1}{c}, i.e.

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

En effet,

\frac{1}{c}\ =\ \int_{\mathbb{R}}\,\tfrac{f(y)}{c\,g(y)}\ g(y)\,dy\ =\ \int_{\mathbb{R}}\,\mathbb{P}\left(U\le \tfrac{f(y)}{c\,g(y)}\right)\ g(y)\,dy\ =\ \mathbb{P}\left(U\le \tfrac{f(Y)}{c\,g(Y)}\right)

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 \scriptstyle\ N\ (c.-à-d. le nombre moyen d'itérations à effectuer avant d'obtenir une réalisation de la densité f ) vaut c.

\mathbb{E}\left[N\right]\ =\ 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:

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

Notons que, soit c est supérieur strict à 1, soit f=g, la deuxième alternative étant assez théorique : en effet, comme \scriptstyle\ cg-f\ge 0,

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

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 f(x) \le c g(x) 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:

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; en particulier, il ne faut pas imposer que h_2(x) \leq c g(x). L'algorithme prend alors la forme suivante:

  1. Suite := vrai
  2. 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
  3. fin tant que
  4. 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

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 Portail des probabilités et des statistiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de rejet de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Methode du rejet — Méthode de rejet Sommaire 1 But 2 Algorithme 3 Généralisations 4 Voir aussi 5 Références …   Wikipédia en Français

  • Méthode Du Rejet — Méthode de rejet Sommaire 1 But 2 Algorithme 3 Généralisations 4 Voir aussi 5 Références …   Wikipédia en Français

  • Méthode du rejet — Méthode de rejet Sommaire 1 But 2 Algorithme 3 Généralisations 4 Voir aussi 5 Références …   Wikipédia en Français

  • Methode Ziggourat — Méthode Ziggourat La méthode Ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniformes. Il s agit d une méthode de rejet et pour être choisie pour simuler une variable aléatoire ayant une densité strictement monotone …   Wikipédia en Français

  • Rejet de Dieu — Rejet Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Rejet de l'ordre — Rejet Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Rejet de la société — Rejet Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Rejet sexuel — Rejet Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Methode de la transformee inverse — Méthode de la transformée inverse La méthode de la transformée inverse est une méthode informatique pour produire une suite de nombres aléatoires de distribution donnée, à partir de l expression de sa fonction de répartition. Le problème auquel s …   Wikipédia en Français

  • Méthode De La Transformée Inverse — La méthode de la transformée inverse est une méthode informatique pour produire une suite de nombres aléatoires de distribution donnée, à partir de l expression de sa fonction de répartition. Le problème auquel s adresse cette méthode est le… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”