2.4 Compléments sur la méthode de Monte-Carlo

2.4.1 Acceptation ou rejet simple

Considérons la variable aléatoire ayant pour densité de probabilité . Si nous la comparons avec la variable utilisée précédemment, ayant pour densité, nous constatons (figure 2.7) que avec . Considérons alors l'algorithme 26 dans lequel rand() désigne le générateur uniforme, tandis que spec() désigne un générateur de pseudo-instanciations de la loi , par exemple celui de l'algorithme 25.

La probabilité de sélection d'une valeur particulière de , c'est à dire la valeur de est le produit de la probabilité de choix de comme valeur de , c'est à dire , par la probabilité de non-rejet qui est : soit une probabilité de . Nous disposons donc d'un pseudo-générateur ayant la densité de probabilité requise.

Figure 2.7: La méthode de domination.

[Domination de par .][Histogramme expérimental.]

Son efficacité dépend de l'efficacité du générateur auxiliaire, de l'efficacité du tir (mesurée par ) et de la facilité de calcul du test de rejet. Cette facilité peut être améliorée en probabilité par l'emploi de fonctions auxiliaires.

2.4.2 Facteur de tir et loi du nombre d'essais

.

2.4.3 Méthode de Neumann

Supposons maintenant que la densité de probabilité donnée ait la propriété suivante : il existe tels que si tandis que et pour (figure 2.8(a)).

Figure 2.8: La méthode de Neumann.

[Hypothèse : le facteur .][La fonction auxiliaire.]

Considérons alors la fonction auxiliaire , ainsi que la zone du plan définie par et (figure 2.8(b)). Il est clair que cette zone est entièrement contenue dans la moitié supérieure gauche du carré , ce qui nous permet d'obtenir aisément des pseudo-instanciations uniformes des points de la zone.

Pour de tels points, la densité probabilité marginale d'une valeur , c'est à dire est égale à . Mais cette quantité n'est autre que : nous avons donc obtenu un générateur selon la loi . Pour la fonction , on peut prendre , ce qui conduit à l'algorithme 27.

On remarquera que l'on ne rejette pas les tirs pour lesquels : en pareil cas, on permute les valeurs obtenues. Et mieux encore, on utilise ce fait pour fabriquer une variable booléenne auxiliaire, de probabilité qui permet de gérer en même temps les valeurs négatives de la variable. Moyennant quoi, l'efficacité du tir est de . Par contre, le "test rapide" n'a lieu qu'une fois sur quatre, ce qui suggère d'utiliser une subdivision plus poussée de l'intervalle (cf paragraphe suivant). Quoiqu'il en soit, l'algorithme 27 se révèle fois plus rapide que l'algorithme du paragraphe précédent.

Dans le cas général, le "test rapide" c'est à dire le cas se produit avec la probabilité : une bonne efficacité suppose que les deux parallèles encadrant la fonction soient proches l'une de l'autre.