connu)
inconnu)
connu)
Les algorithmes de la section précédente ne résolvent pas totalement
le problème de l'échantillonage, c'est à dire la sélection aléatoire
uniforme de 
éléments (différents) parmi . Dans bien des situations
concrètes, il est absolument hors de question d'enregistrer la totalité
d'un processus pour sélectionner ensuite l'échantillon voulu. Il faut
au contraire "sélectionner au vol" c'est à dire décider en temps
réel d'enregistrer ou non l'événement qui est en train de se produire,
et cela de façon à obtenir directement l'échantillon voulu, tout en
s'assurant que tout autre échantillon aurait eu une égale chance d'être
sélectionné.
Il est clair qu'il ne suffit pas de sélectionner chaque événement
avec une probabilité 
, car la taille de l'échantillon obtenu
ne vaudrait qu'en moyenne seulement (avec une variance 
rendant peu probable que cette taille soit effectivement ). Une
méthode effective est donnée par l'algorithme 17
(Fan 1962) : si 
est le nombre d'événements qui sont déjà
passés et 
le nombre de ceux qui ont été déjà sélectionnés,
nous sélectionnons l'événement à venir avec la probabilité 
.
Dans notre description de l'algorithme, 
est le processus à
échantilloner, tandis que l'échantillon retenu se retrouve dans le
fichier 
. Les fonctions 
pour leur part effectuent ce que l'on imagine, à savoir lire l'événement
en cours, l'écrire dans le fichier ou sauter l'événement en cours.
Il est tout à fait remarquable que cet algorithme (1) arrive toujours
à sélectionner les événements voulus (2) se termine le plus souvent
avant que le processus à échantillonner soit lui-même terminé (3)
assure une probabilité de sélection égale à chacun des événements.
inconnu)
Le problème se complique lorsque n'est pas connu d'avance, car
l'algorithme de Fan devient inutilisable. Il convient alors d'utiliser
l'algorithme 18 (Waterman) : on commence par sélectionner
les premiers événements, puis on décide de temps en temps d'abandonner
l'un des événements déjà retenus, et d'en retenir un autre. Comme
on se place toujours dans l'hypothèse où le processus à échantilloner,
mais aussi l'échantillon lui-même est trop vaste pour pouvoir tenir
en mémoire centrale, on est amené à stocker "au vol" les événements
retenus dans un fichier intermédiaire 
, tout en gérant en mémoire
centrale une table d'index pointant vers les événements qui seront
effectivement retenus lorsque le processus à échantillonner sera terminé
(condition 
).
La méthode de sélection proposée par Waterman (pour les événements
de numéro 
) est la suivante. Lorsque le -ième événement
se produit, la probabilité pour qu'il soit immédiatement rejeté est
. Dans le cas contraire, il vient prendre la place de
l'un des éléments précédemment sélectionnés, l'élément à supprimer
étant choisi uniformément parmi les éléments faisant partie,
à ce moment là, de la sélection provisoire.
Vérifions par récurrence la correction de cet algorithme : supposons
qu'une fois les premiers événements lus, ces événements aient
eu une égale probabilité de faire partie des sélectionnés à cette
date. Une telle situation se produit avec certitude lorsque 
.
A l'étape suivante, le 
-ième événement est sélectionné avec
la probabilité 
tandis que les premiers
ont désormais la probabilité 
d'être encore sélectionnés. On voit donc que l'équiprobabilité se
généralise étape par étape.
Il reste à estimer la praticabilité de l'algorithme, c'est à dire
la taille potentielle du fichier temporaire. Une analyse à l'aide
de séries génératrice montre que 
.
Si donc 
, on a 
. Bien entendu, si la taille
mémoire est suffisante pour contenir l'échantillon tout entier, il
suffit de stocker les événements retenus dans une table et d'écraser
directement l'événement abandonné par l'événement retenu pour le remplacer.
Intéressons nous maintenant aux algorithmes permettant de déterminer
une permutation aléatoire d'un ensemble de éléments, donné dans
un certain ordre, c'est à dire sous la forme d'une liste. Pour cela,
il est commode de disposer d'une façon de numéroter ces permutations.
L'algorithme 19 (Moses, 1963) répond à cette question
en déterminant une transposition après l'autre quelle est la permutation
qui permet d'ordonner cette liste dans l'ordre croissant.
Le cardinal de la liste est déterminé (
),
puis une copie de cette liste est faite dans une 
, à la fois
pour ne pas modifier la liste d'origine et pour accélérer le processus.
Puis la place 
de l'élément maximal est déterminée. Cette place
est nécessairement unique, puisque nous sommes en train de trier un
ensemble. La transposition 
est donc
telle que 
est
une permutation des 
plus petits éléments de l'ensemble, le
plus grand étant revenu à la dernière place.
Si l'on pose 
(le nombre 
étant déterminé récursivement) on
obtient un nombre compris entre 0 et 
, et on vérifie aisément
que ce nombre caractérise la permutation . Pour 
et
, cet algorithme donne les résultats suivants :
colonnes le dernier élément
est à la même place, tandis que chaque ligne correspond à la même
permutation des premiers éléments.
Pour obtenir une permutation aléatoire de éléments lorsque 
est nettement inférieur à la période du générateur uniforme dont on
dispose, il suffit de tirer au sort le numéro de la permutation et
d'inverser l'algorithme précédent. On obtient l'algorithme 20.
Dans le code proposé, le résultat fourni par la commande 
est le reste de la division de 
par 
, c'est à dire la quantité
, mais en outre, par effet de bord, le quotient de la
division est affecté à la variable fournie en troisième paramètre
: est donc automatiquement mis à jour.
Lorsque augmente, la précision du générateur uniforme ne permet
plus de procéder en une seule étape, et il convient maintenant de
l'utiliser pour déterminer chaque transposition l'une après l'autre.
On obtient l'algorithme 21 (Moses 1963).
La figure 2.2 donne l'histogramme de la répartition
de 
instanciations de 
, obtenues par composition
de 
et de 
. On vérifie
que les nombres obtenus se comportent effectivement comme autant d'instanciations
d'une variable entière uniformément répartie dans 
(le score au test du 
est de 
).
