ALGORITHMES DE TIRAGE

Philippe Périé, Sylvie Rousseau & Gilbert Saporta

STA108, 9 novembre 2012

 NOMBRES ALEATOIRES et
PSEUDO-ALEATOIRES

 Utiles pour réaliser des tirages et simuler des

phénomènes aléatoires
 Nombres aléatoires: suite de réalisations
indépendantes d’une variable uniforme sur [0;1]
 Peuvent être obtenus par des procédés physiques:
 roues de loterie,
 éclairage à intervalles irréguliers d'un disque divisé en 10
secteurs isométriques et numérotés de 0 à 9 : table de
Kendall et Babington Smith

2
 Nombres pseudo aléatoires
 Procédés déterministes mais fournissant
une suite de nombres en apparence iid sur
[0; 1]
 Suites mathématiques
 décimales de π, des tables de logarithmes
 Procédés arithmétiques
 Milieu du carré de Von Neumann (1946)

3
 On part d'un nombre entier
 On l’élève au carré
 On extrait les chiffres du centre comme nombres aléatoires.

 Exemple : x0 = 7534
(7534)2 = 56 7611 56
(7611)2 = 57 9273 21
(9273)2 = 85 9885 29
(9885)2 = 97 7132 25
....
 d'où la suite 7611 9273 9885 7132
 Inconvénients majeurs : dépendance au nombre de départ et
régularités nombreuses (permanence de 0 ou de séries
particulières).

4
 Méthodes de congruence
Elles reposent sur des suites récurrentes :

 choix arbitraire d’un entier x 0 appelé germe (ou seed ou graine)

 génération d’une séquence (x1 ,..., xn ) d’entiers :
Xi+1 =a xi +b (modulo m) pour i = 1, ..., n ,
où a, b et m sont des entiers appelés respectivement multiplicateur,
incrément et modulo.

On vérifie : 0< xi < m pour i 1, ..., n .

xi
 Intérêt : les nombres u1 ...,un où u=
m
forment un échantillon pseudo-aléatoire de la loi uniforme sur [0,1] si
les entiers a, b et m sont « bien » choisis.

Intuition de l’horloge : les heures

9h et 21 sont congrues modulo 12
5
 Le procédé étant déterministe, ces nombres sont
dits pseudo-aléatoires.
 Exemple : x0 = 1 ; a = 6 ; b = 0 ; m = 25
x0 = 1 x1 = 6 [25] = 6 x2 = 36[25] =11
x3 = 66[25] = 16 x4 = 21 x5 = 1 = x0
Ce cycle a pour longueur 5.
 Remarque :
 La séquence xi i=1,...,n contient au plus m
termes distincts.
 Cette suite est donc périodique de période p
avec p≤ m Si p = m, la période est dite pleine.

6
 Choix des entiers a, b et m :
Ils sont déterminés de telle sorte que la séquence ait les
meilleures propriétés possibles.
En particulier, m est pris aussi grand que possible pour
assurer une grande variété de valeurs dans la suite xi
 Hull et Dobell (1962) ont montré que les séquences de
période pleine sont obtenues si et seulement si :
 b et m sont premiers entre eux,
 (a-1) est un multiple de chaque nombre premier qui divise m
 si m est un multiple de 4 alors (a-1) aussi

Un algorithme très usité est la méthode congruentielle de

Lehmer (1948) qui pose b = 0.

7
 Méthode de Lehmer :
xi+1=axi (m)
(Sur machines 32 bits m aussi grand que possible  m=231-1)
 choix classiques:
 a=75 =16807 m=231-1
 a= 216+3=65539 m=231-1
 a=279470273 m=4294967291

Remarque : a= 216+3=65539 m=231-1 : RANDU

(introduit dans les années 1960, sur des machines IBM. Il est très
impopulaire car il possède de nombreux biais auxquels ont dû faire face les
personnes qui l'ont utilisé).

8
 RANDU

 a= 216+3=65539 m=231-1
 m = 216 + 3  m²=6m-9 mod
231

9
 Pb : trois nombres successifs Xn Xn + 1 et Xn + 2 vérifient
toujours la relation Xn + 2= 6Xn + 1 -9 Xn

 Cette relation donne un caractère ‘prédictif’ à la série

pseudo aléatoire: par exemple, une modification des
valeurs de Xn et Xn + 1 de l'ordre de 0,01, change la
valeur de Xn + 2 d'au plus 0,15.

 Pour avoir un "bon" générateur, on souhaite une relation

avec des coefficients beaucoup plus grands, de telle
manière qu'une petite modification de Xn et Xn + 1 change
complètement Xn + 2
10
 http://en.wikipedia.org/wiki/Image:Lcg_3d.gif#file

http://en.wikipedia.org/wiki/Image:Lcg_3d.gif#file

11
 Solutions variées: congruences avec retard
xi = a xi -r +b [m]
 Exemple: ri+1 =(1664525ri+1013904223) m = 232
(Numerical Recipes in C )

 Nombreux tests pour valider le caractère

uniforme et l’indépendance des
réalisations
 Chi-deux, Kolmogorov, tests de séquences, de non
corrélation

12
 estimation de π

 http://www-
sop.inria.fr/mefisto/java/tutorial1/node15.html#SECTION00033120000000
000000

13
Calcul d’intégrales: méthode de Monte Carlo

Première méthode : 1
on simule n valeurs de U=I ∫=
0
g (t )dt E ( g (U ))

n
1
Iˆ = ∑ g (ui )
n i =1
 Deuxième méthode: fonction d’importance
T variable sur [0 ;1] de densité p(t)

n
1 g (t )  g (T )  ˆI = ∑ g (ti )
1
I ∫=
0 p (t )
p (t )dt E  
 p (T )  n i =1 p (ti )
14
 Générateurs pseudo-aléatoires
cryptographiques

 Doivent être capable de produire des séries dont le

caractère pseudo aléatoire est moins discernable pour
mériter ce titre
 … Mais plus lents

 Un générateur congruenciel rapide et possédant de

bonnes propriétés : Mersenne Twister (1997)
 Mais n’est pas considéré comme générateur
cryptographique
 Utilisé dans SPSS à partir de la version 12

15
 ALGORITHMES DE TIRAGE
 Qualités souhaitées:
 Sans remise
 Séquentiel
 Rapide
 Respecte les probabilités d’inclusion
 De taille fixe
 Utilisable si N est inconnu
 Etc.

16
 Une méthode inefficace : énumération puis
sélection
(Yves Tillé, ‘Sampling Algorithms’ p 31)

 Si le plan de sondage est connu, et que la population n’est pas trop

grande, une méthode pour sélectionner un échantillon est
l’approche énumérative : énumérer tous les échantillons possibles,
puis en sélectionner 1 au hasard.
 … méthode pure et simple conceptuellement mais impossible dès
que la population dépasse quelques dizaines

 L’objectif des algorithmes de tirage est de tirer un échantillon en

respectant le plan de sondage et en évitant une énumération complète
au préalable

17
 Classes de méthodes (Yves Tillé pp 32 – 39)

 Martingales
 Algorithmes séquentiels
 Sélection pas à pas
 Par élimination
 Sondages réjectifs

18
 Notion d’entropie

On montre aisément que I(p) est toujours positif.

 Plus l’entropie est élevée, plus le plan de sondage est en un certain

sens aléatoire

 A défaut d’information auxiliaire, on peut chercher le plan le plus

aléatoire (au sens de l’entropie) qui vérifie les probabilités
d’inclusion fixées

19
Plans à probabilités égales sans remise

20
Plans à probabilités égales sans remise

 Tirage de Bernoulli:
on tire N nombres aléatoires. L’unité i est retenue si Ui<π .

21
 Tirage de Bernoulli

22
 Tri aléatoire

23
 Sélection-rejet
si U1<n/N on prend l’unité 1. Puis n=n-1 et N=N-1. On sélectionne
l’unité 2 si U2<n-1/N-1
Si U1>n/N, on passe à l’unité 2 avec N=N-1. On sélectionne l’unité
2 si U2<n/N-1 etc.

j= nb d’unités
déjà sélectionnées

24
 Méthode de mise à jour de l’échantillon

25
26
 Pas aléatoires
Tirer U et trouver s tel que
CNn − s −1
U ≤ 1−
CNn
sélectionner l’unité s+1, faire N=N-s-1 et n=n-1 etc.

 et aussi le tirage systématique…

27
 Tirage systématique
 Définir un pas de tirage = N/n (entier par arrondi)
 Tirer une unité au hasard au début du fichier entre 1
et pas
 Sélectionner une unité tous les pas

 Avantages: simplicité, N pas nécessairement connu a

priori, peut être plus efficace que le tirage aléatoire si
le fichier est trié selon une variable bien corrélée à la
variable d’intérêt (cf cours sur le sondage en grappes)

28
 Inconvénients
 Si périodicité dans le fichier (Ardilly)

29
 Probabilités inégales sans remise
 Infinité de plans de sondage pour des π i fixés
 Plus de 50 méthodes de tirage! Aucune ne satisfait tous les
critères.
 Quelques techniques simples:
 Tirage avec remise et conservation des unités distinctes mais
taille non fixe
 Rejet de l’échantillon si il y a des doublons mais probabilités
d’inclusion non proportionnelles aux xi

30
 Tirage successif sans remise:
 Onrecalcule les probas d’inclusion après tirage de
πi
chaque individu. Si j est tiré: π =
'

1−π j
i

 Ne respecte pas les probas d’inclusion d’ordre 1

 Tirage poissonnien: sélectionner i si Ui<πi
 πij=πi πj variance simple
 Mais taille non fixe

31
Tirage poissonnien (S.Rousseau, 2004)

32
 Méthode de Sunter (généralisation de la méthode de
sélection-rejet)

33
34
 Méthode RHC (Rao, Hartley,Cochran)

 Pour un tirage à probabilités proportionnelles à la

taille X
 Trier les unités dans un ordre alétaoire
 Tronçonner le fichier en n groupes successifs de N/n
unités
 Tirer dans chaque groupe une unité
proportionnellement à la taille

 Simple et performant
 Remarque: procédé « inexactement proportionnel à la
taille » car les groupes ne sont pas de même taille

35