2.1 Sélection dans un ensemble fini

2.1.1 Choix uniforme d'éléments d'un ensemble

Pour obtenir des pseudo-instanciations d'une variable entière uniformément répartie dans l'intervalle à partir d'un générateur congruentiel, il serait mathématiquement possible d'utiliser . Mais, en fait, les chiffres de plus fort poids ont une meilleure distribution, et il est préférable d'utiliser l'algorithme suivant :

Pour que la séquence engendrée soit de bonne qualité, il convient d'utiliser un module au moins égal au carré du nombre d'éléments à sélectionner () ou bien de n'utiliser qu'une très faible partie de la période (). En effet, la séquence issue du générateur est "sans aucune répétition" tandis que la probabilité pour qu'une séléction non exhaustive de éléments parmi soit "sans répétitions" est . D'où et pour . Un développement limité donne : lorsque , la probabilité d'au moins une collision lors d'un tirage effectivement aléatoire vaut environ 40% !

2.1.2 De la bonne programmation des aiguillages

Demandons-nous maintenant comment sélectionner un objet parmi , avec des probabilités proportionnelles à une liste de nombre positifs donnés, que nous appellerons les chances de sélection. On a donc, par définition, . Considérons par exemple, la sélection d'un nombre entier dans l'intervalle , avec des chances proportionnelles aux nombres .

Ce problème a été totalement résolu par l'algorithme de Walker, que nous présenterons en fin de cette section. Mais il existe bien d'autres façons de procéder, moins efficaces certes, mais plus susceptibles de généralisation à d'autres situations.

Une première possibilité est la suivante. On dresse la table des chances cumulées, soit . Ces nombres découpent en sous-intervalles adjacents l'intervalle . Il est immédiat que le numéro (soit ) du sous-intervalle dans lequel tombe une instanciation (uniforme) de constitue une instanciation d'une variable aléatoire ayant la loi voulue.

Cette méthode consiste en fait à utiliser la fonction inverse de la fonction de répartition (en modifiant adéquatement la signification du mot inverse, puisque la fonction n'est pas bijective). Une implémentation immédiate conduit à l'algorithme 12.

Cette implémentation par choix successifs, va engendrer tests par appel. Il est clair qu'un tri par chances décroissantes ne peut qu'améliorer les performances (dans l'exemple considéré, on passe à une moyenne de tests). Mais on reste encore avec une complexité en , tandis qu'une implémentation arborescente, conduisant à l'algorithme 13, permet d'obtenir un nombre de comparaisons en .

2.1.3 Méthode de tir (Monte-Carlo)

Examinons maintenant la "méthode de tir", qui est un algorithme probabiliste en ce sens que le déroulement des calculs n'est pas fixé d'avance. En particulier, le nombre d'accès effectifs au générateur uniforme change d'une instanciation à l'autre. L'idée de base, illustrée figure 2.1(a), consiste à inscrire l'histogramme des chances dans un rectangle.

Si nous sélectionnons uniformément des points dans ce rectangle jusqu'à obtenir un point dans l'histogramme et que nous répétons ce processus, nous obtiendrons des points uniformément répartis dans cet histogramme. Par conséquent, chaque barre de l'histogramme sera visitée proportionnellement à sa hauteur, conduisant à la loi de répartition voulue.

Figure 2.1: Sélection par la méthode de tir.

[Histogramme des chances.][Histogramme expérimental.]

Le nombre moyen de points qu'il faut sélectionner dans le rectangle pour obtenir une instanciation est visiblement égal au rapport des surfaces et vaut ici . Nous appelerons cette quantité le "facteur de tir" de l'algorithme. Dans le cas général, chaque essai nécessite deux appels au générateur uniforme, le premier servant à déterminer le candidat, et le deuxième servant à rendre le verdict.

Lorsque est petit, l'algorithme 14 permet d'éviter ce deuxième appel. En effet la détermination de en tant que partie entière de (la relation exacte étant ) laisse inutilisée la quasi-totalité des "chiffres aléatoires" de . On peut donc rendre le verdict en utilisant comme instanciation de au lieu d'obtenir cette instanciation par un nouvel appel du générateur uniforme.

La figure 2.1(b) donne un exemple d'histogramme obtenu en instanciations du générateur. Cette simulation a engendré appels au générateur uniforme (valeur théorique ), et le score de l'histogramme obtenu est de .

2.1.4 Choix pondéré dans un ensemble fini (Walker)

Pour choisir un élément parmi avec des probabilités proportionnelles à des nombres donnés, il existe une méthode tout à fait extraordinaire, puisqu'elle est à temps constant. L'algorithme 15 en donne le principe (dû à Walker, 1974).

La variable uniformément répartie dans nous sert en premier lieu à choisir uniformément une méthode de tir parmi les possibles, puis la "partie inutilisée" de , c'est à dire la partie fractionnaire de , fournit le verdict utilisé par la méthode de tir sélectionnée. Toute l'affaire consiste à construire les deux tables et , contenant l'une les seuils de rejet (nombres de ) et l'autre des entiers dans indiquant qui est choisi à la place du candidat par défaut lorsque celui-ci est rejeté. Illustrons ce problème en considérant un exemple, avec et

ce vecteur ayant été normé pour que la somme de ses éléments soit égale à . Nous allons trier les éléments de par valeur croissante, tout en mémorisant l'indice d'origine, ce qui conduit à la liste :

A chaque étape de l'algorithme, nous allons supprimer le premier élément de et modifier le dernier (et donc le replacer à l'endroit nécessaire pour que reste triée par ordre croissant). Par construction, le premier élément est inférieur ou égal à 1, et le dernier est supérieur ou égal à 1. Nous posons donc et , nous supprimons le couple et nous remplacons la valeur par . Autrement dit, le couple est remplacé par le couple , qui vient s'intercaller entre et . Nous obtenons donc une nouvelle liste de nombres positifs et de somme : il est clair que le procédé peut être répété tant que n'est pas vide. On obtient l'algorithme 16 et les listes :

Le codage donné ci-dessus pour l'initialisation de l'algorithme de Walker n'a pas été optimisé outre mesure. En effet, c'est le nombre d'instanciations fournies par le générateur qui est susceptible de devenir important, bien plus que le nombre d'objets à choisir. Le fait d'utiliser une liste pour représenter , et de la retrier () à chaque fois que l'on a supprimé le premier élément () donne une complexité (approximativement) quadratique en : une meilleure implémentation peut se révéler utile lorsque augmente. En pareil cas, il peut devenir nécessaire d'utiliser une nouvelle instanciation du générateur uniforme comme verdict dans l'algorithme principal.