2.3 Présentation du problème

2.3.1 Un exemple simplifié

Afin de ne pas masquer les principes mis en oeuvre par des détails techniques, nous allons commencer par un exemple volontairement simpliste. Considérons la variable aléatoire dont la pdf (densité de probabilité) est donné par la figure 2.3, c'est à dire :

Figure 2.3: Une densité de probabilité particulièrement simple.

Nous allons exposer plusieurs méthodes permettant de générer de pseudo-instanciations de cette variable, puis nous comparerons leurs efficacités respectives.

2.3.2 Inversion de la fonction de repartition

Considérons la fonction de répartition (cdf) de la variable , c'est à dire la fonction définie par , ainsi que sa fonction réciproque. On obtient la figure 2.4, c'est à dire :

Figure 2.4: Fonction de répartition.

Pour une fonction plus générale, la fonction serait seulement croissante et non pas continue strictement croissante comme pour cet exemple. En pareil cas, la fonction doit être définie par , et on a alors la propriété suivante : si la variable est uniformément répartie sur alors la variable est distribuée selon la loi , d'où l'algorithme 22:

On prendra garde à ne pas confondre ce résultat avec l'affirmation "si la variable est distribuée selon la loi alors la variable est uniformément distribuée" car cette affirmation est le plus souvent fausse.

Bien entendu, l'efficacité de l'algorithme 22 obtenu dépend de la facilité avec laquelle on peut calculer la fonction de répartition inverse pour la loi considérée.

2.3.3 Méthode de tir (Monte-Carlo)

Lorsque la fonction est bornée et à support fini, comme tel est le cas pour notre exemple, on peut utiliser l'algorithme suivant. On pose , et . On choisit alors uniformément un point dans le rectangle et on recommence jusqu'à ce que . On obtient donc un point uniformément réparti dans la portion de plan limitée par , . La probabilité marginale d'obtenir une valeur particulière est donc proportionnelle à , ce qui est précisément ce que l'on cherche. Pour notre exemple, on obtient l'algorithme 23.

L'efficacité de cet algorithme dépend du nombre moyen de tirs nécessaires pour atteindre un point utile, c'est à dire de la quantité , et de la facilité de calcul de la frontière. Dans notre exemple, il faut coder le test de façon à ce que la décision de rejet soit prise immédiatement si .

2.3.4 Méthode des quotients

Indiquons maintenant une troisième méthode, dont nous verrons ultérieurement l'efficacité. Définissons une région du plan par les conditions et . Pour l'exemple en cours, on obtient la figure 2.5, soit et comme équation du bord supérieur de la zone.

Figure 2.5: Zone en pour la méthode des quotients.

Si nous passons en polaire, avec et , nous obtenons . La section de cône définie par et a donc pour aire , soit . On a donc le résultat suivant : si les points sont choisis uniformément dans la zone grisée, la densité de probabilité du quotient est proportionnelle à . Comme , cette proportionalité est en fait une égalité, et l'on est conduit à l'algorithme 24.

Ici encore, l'efficacité de l'algorithme dépend du nombre moyens de tirs nécessaires pour atteindre un point utile et de la facilité de calcul de la frontière. Avec le programme indiqué ci-dessus, l'efficacité du tir est de 50%. On peut améliorer ce résultat en constatant que la valeur maximale de est et non . Il est donc préférable d'écrire : , portant l'efficacité du tir à 77%.

2.3.5 Un procédé spécifique

Il existe toujours une méthode plus rapide que les méthodes déja utilisées. Ainsi l'algorithme 25 donne avec probabilité une valeur positive puisque deux valeurs successives de rand() sont indépendantes. La densité de probabilité conditionnelle d'une telle valeur est alors proportionnelle à la probabilité de non rejet, c'est à dire . De même la densité de probabilité d'un résultat est . On en déduit que spec() est un pseudo-générateur pour la loi . Cet algorithme est très rapide puisqu'il n'utilise aucune fonction auxiliaire.

2.3.6 Bilan des diverses méthodes indiquées.

A titre d'illustration, nous avons exécuté pour chacun de ces quatres algorithmes, 900 lots de 900 appels. Nous avons obtenu les histogrammes par lots de la figure 2.6, et aux durées d'exécution suivantes :

algorithme	spécial	inv_frep	m_carlo	rapport
durée	165.600	268.902	468.505	498.110

Figure 2.6: Exemples d'histogrammes par lots.

On constate que, dans cet exemple où les calculs sont très réduits, le nombre d'appels au générateur uniforme est le principal critère de rapidité, mais il est clair que cette situation peut changer avec des fonctions de densité moins simplistes.