Simulation sur ordinateur

A. Buys

Département d’Informatique
Université de Mons
Intro Loi uniforme Tests Loi non uniforme

A. Buys (Dpt Informatique) Simulation sur ordinateur 2 / 110

Intro Loi uniforme Tests Loi non uniforme

1 Introduction

2 Génération de nombres aléatoires suivant une loi uniforme

3 Tests des séries générées

4 Génération de nombres aléatoires suivant des lois non uniformes

5 Divers

A. Buys (Dpt Informatique) Simulation sur ordinateur 3 / 110

Intro Loi uniforme Tests Loi non uniforme

Un nombre aléatoire n'existe pas (3 est aléatoire ? Non). C'est en fait une variable aléatoire. Bien
distinguer car discret et continu.
Introduction Equiprobable : La proba entre a et b est b - a ?
Uniforme :

Qu’est-ce qu’un nombre aléatoire ?

Qu’est-ce qu’une variable aléatoire ?
Qu’est-ce qu’une séquence de nombres aléatoires ?
uniformité (toutes les valeurs sont équiprobables)
indépendance (dimensions) On groupe les nombres par le nombre de dimensions et ça forme
des points. Si sur une ligne droite (en 2D), pas uniforme.
A quoi servent des nombres pseudo-aléatoires ?
La roulette, si on arrive à contrôler toutes les paramètres comme
Problèmes non déterministes le lancer, la vitesse, ... Cela devient déterministe
Problèmes avec trop de variables

Référence: Donald E. Knuth “The Art of Computer programming” (Addison Wesley), Vol. 2.

A. Buys (Dpt Informatique) Simulation sur ordinateur 4 / 110

Intro Loi uniforme Tests Loi non uniforme

(...)
Rb
Calcul de a
f (x)dx

(rarement à 2 dimensions, plutôt 6-7)

A. Buys (Dpt Informatique) Simulation sur ordinateur 5 / 110

Intro Loi uniforme Tests Loi non uniforme

(...)
Physique (interactions entre particules, efficacité d’un détecteur, etc)
Echantillonnage (sondage, ...)
Programmation (tests de programme)
Génération de mots de passe
Prise de décision (avec facteurs non quantifiables)
Jeux (débuts de partie)

A. Buys (Dpt Informatique) Simulation sur ordinateur 6 / 110

Intro Loi uniforme Tests Loi non uniforme

A quoi reconnaı̂t-on une séquence de nombres “aléatoires” ?

Quelle est la séquence la plus probable ?
1 1 1 1 1 1 1 1 1 La probabilité d'obtenir chacune des suites est la même
146987235
123456789
On veut une séquence qui ait les mêmes caractéristiques qu’une
séquence réellement aléatoire
046987635
004466998877663355
−→ notion de dimension

A. Buys (Dpt Informatique) Simulation sur ordinateur 7 / 110

Intro Loi uniforme Tests Loi non uniforme

Comment obtenir des nombres “aléatoires” ?

Fichier de nombres aléatoires (Roulette à Monte-Carlo)
−→ Inconvénient: toujours les mêmes, lenteur
Machine du lotto (périphérique qui génère des nombres aléatoires)
−→ Inconvénient: jamais les mêmes, lenteur
Nombres pseudo-aléatoires seed

−→ obtenus à partir d’un nombre “semence” de façon déterministe

même semence → même séquence

semence différente → séquence différente

A. Buys (Dpt Informatique) Simulation sur ordinateur 8 / 110

Intro Loi uniforme Tests Loi non uniforme

Génération de nombres aléatoires suivant une loi uniforme

Middle-square (Von Neuman, 1946)

... historique
Congruence linéaire
Autres méthodes (parfois plus modernes)

A. Buys (Dpt Informatique) Simulation sur ordinateur 9 / 110

Intro Loi uniforme Tests Loi non uniforme

Middle-square (Von Neuman, 1946)

On part d’un nombre de 10 chiffres (par exemple)
(7548962587)2 = 56986836139925732569
Dangereux car possibles dégénérescences Si à un moment donné, par exemple, le
dernier chiffre vaut 0 alors le carré sera
multiple de 100 et donc il peut y avoir des
xxxxx00000 −→ xxxxx00000 pattern.
On peut obtenir des centaines de milliers de nombres qui satisfont une
batterie de tests avant dégénérescence
Pour les curieux ... (3792)2 = 14379264
3792 = 3 79 24

Si le nombre se fini par n zéro

alors le nombre au carré se
finira par 2n zéro

A. Buys (Dpt Informatique) Simulation sur ordinateur 10 / 110

 Intro Loi uniforme Tests Loi non uniforme

Congruence linéaire (Lehmer, 1948)

On raisonne sur des entiers, mais si 0 ≤ Xi < m alors 0 ≤ Xi /m < 1
(loi uniforme dans [0,1[)
De façon générale, on considère une fonction y = f (x) sur des entiers
f (X0 ) = X1 ; f (X1 ) = X2 ; ...
X0 est la seed
Soit 0 ≤ X0 ≤ m, 0 ≤ f (x) = y < m, alors on a une période maximale
égale à m (après avoir généré m valeurs, on va forcément retomber sur
l’une d’elles).
Soit λ la période, µ, l’amorce (1 ≤ λ ≤ m, 0 ≤ µ < m, µ + λ ≤ m)
X0 X1 X2 ...Xµ−1 Xµ ...Xµ+λ−1 Xµ+λ (Xµ = Xµ+λ )
∀i, j tel que (i 6= j) ∧ (i < µ + λ) ∧ (j < µ + λ) : Xi 6= Xj
Comment déterminer µ et λ pour une série quelconque ?
On va rechercher la plus petite valeur de n telle que Xn = X2n

A. Buys (Dpt Informatique) Simulation sur ordinateur 11 / 110

Intro Loi uniforme Tests Loi non uniforme

A démontrer
∃ n tel que Xn = X2n et µ ≤ n ≤ µ + λ


(r − n) multiple de λ
Xr = Xn (r ≥ n) ⇐⇒
n≥µ
⇓

n multiple de λ
X2n = Xn ⇐⇒
n≥µ
⇓
Le plus petit multiple n de λ (n ≥ µ) est tel que Xn = X2n
Or, entre µ et µ + λ, il existe un multiple de λ. Si on part de X0 , c’est
le premier qu’on va rencontrer (pas d’égalité avant µ).

A. Buys (Dpt Informatique) Simulation sur ordinateur 12 / 110

Intro Loi uniforme Tests Loi non uniforme

On a donc n tel que Xn = X2n , il faut maintenant trouver µ, λ.

X0 ...Xµ−1 Xµ ...Xn ...X2n

On va comparer Xi et Xn+i (i ≥ 0), X0 avec Xn , X1 avec Xn+1 , etc.

La première égalité donne i = µ.
On pourrait partir de Xn = X2n , Xn−1 = X2n−1 , etc, mais on ne connaı̂t
pas f −1 .

Si un des Xn+i vaut Xn , alors λ = i, sinon, λ = n

On peut aussi partir de Xn pour trouver Xn+λ

Question : Trouver la période et l'amorce

On utilise le modulo pour être sûr d'avoir des valeurs en dessous d'un certain nombre

A. Buys (Dpt Informatique) Simulation sur ordinateur 13 / 110

Intro Loi uniforme Tests Loi non uniforme

Fonction généralement utilisée

f (x) = (ax + c) mod m (congruence linéaire)

m : module
a : multiplicateur
c : incrément
X0 : valeur de départ (semence)
Méthode congruentielle “mixte”. Si c = 0, méthode multiplicative.
A démontrer
Si a et m sont premiers entre eux, alors µ = 0.

(Par l’absurde)
Si µ 6= 0, ∃ Xµ précédé de Xµ−1 et ∃ α tel qu’on trouve dans la
séquence ... Xα Xµ ... avec Xα 6= Xµ−1 .
On va montrer qu’on ne peut pas avoir un nombre avec deux
prédécesseurs différents si a et m sont premiers entre eux.

A. Buys (Dpt Informatique) Simulation sur ordinateur 14 / 110

Intro Loi uniforme Tests Loi non uniforme

Soient r , s tels que

(a Xr −1 + c)mod m = (a Xs−1 + c)mod m et Xr −1 6= Xs−1
⇓
a (Xr −1 − Xs−1 ) = αm

Or, −m + 1 ≤ (Xr −1 − Xs−1 ) ≤ m − 1

... mais doit être multiple de m si α 6= 0. CQFD.

Il suffit alors de regarder X0 , X1 , ... pour déterminer λ.

Exemple: a = c = 7, m = 10, X0 = 7 =⇒ 7, 6, 9, 0, 7, 6, 9, 0, ...

A. Buys (Dpt Informatique) Simulation sur ordinateur 15 / 110

Intro Loi uniforme Tests Loi non uniforme

A démontrer
ak −1
Xk+n = (ak Xn + a−1 c) mod m

(Par récurrence)
k = 1 évident
ak −1
Xk+n+1 = a(ak Xn + a−1 c) + c mod m
k+1 ak+1 −a
=a Xn + ( a−1 + 1)c mod m
k+1
=a k+1
Xn + ( a −a+a−1
a−1 )c mod m
CQFD.

Xk+n = (a0 Xn + c 0 ) mod m avec

(
a0 = ak
k −1
c 0 = aa−1 c

A. Buys (Dpt Informatique) Simulation sur ordinateur 16 / 110

Intro Loi uniforme Tests Loi non uniforme

Choix du module m
m limite la période qu’on peut obtenir
Exemple extrême : simulation de pile ou face avec m=2.
On a intérêt à choisir m grand
Rapidité de calcul
Xn+1 = (aXn + c) mod m ; On choisit 0 ≤ a, c ≤ m − 1
Lors du calcul, le plus grand nombre est de
(m − 1)(m − 1) + m − 1 = m2 − m < m2
On prend m = 2e où e est le nombre de bits d’un mot d’ordinateur
m2 est représenté par 2e bits et la division par m est un décalage de e
positions.
=⇒ Pas de division à effectuer, maximalisation de la période.

A. Buys (Dpt Informatique) Simulation sur ordinateur 17 / 110

Intro Loi uniforme Tests Loi non uniforme

A démontrer
Soit d qui divise m, Yi = Xi mod d, alors Yn+1 = (a0 Yn + c 0 ) mod d
avec a0 = a mod d, c 0 = c mod d

Xn+1 = aXn + c − qm
Yn+1 = ((a0 + αd)(Yn + βd) + c 0 + γd) mod d
Yn+1 = (a0 Yn + c 0 + (...)d) mod d

Pour m = 2e , d = 2, le dernier bit des Xi a une période de 2 (pas bon

pour générer un pile ou face)
Si 4 divise m, période de 4, par exemple 00,01,10,11,...
Caractère aléatoire moins bon pour les bits moins significatifs.
Peu important pour générer une loi uniforme.
Alternatives : m = 2e − 1, plus grand premier < 2e .
A. Buys (Dpt Informatique) Simulation sur ordinateur 18 / 110
Intro Loi uniforme Tests Loi non uniforme

Choix de a et c
Théorème
(Hull et Dobel, 1962)
La congruence définie par m, c, a et X0 est de période m si et seulement si
- c est premier avec m
- b = a − 1 est multiple de p, ∀p premier diviseur de m
- b est multiple de 4 si 4 divise m

Assure une période maximum mais pas forcément une bonne

génération aléatoire (a = 1, c = 1)
Si a = 1 et c = 1 alors on va générer la suite 1, 2, 3, 4, 5, ... m-1. La période est
maximale mais ils sont dans l'ordre
Congruence multiplicative (c = 0)
Xk+n = ak Xn mod m
Si Xn est multiple d’un diviseur de m, tous les nombres générés le sont.
On prend X0 premier avec m et on essaie de conserver des nombres
premiers avec m.
La période maximum sera ϕ(m) (fonction d’Euler).

A. Buys (Dpt Informatique) Simulation sur ordinateur 19 / 110

Intro Loi uniforme Tests Loi non uniforme

En général m = p1e1 p2e2 ...pnen

Soit m = p e , si a est un multiple de p,
Xn+e = ae Xn mod p e = 0 et la période vaut 1.
Soit a premier avec p, la période est le plus petit λ tel que
aλ Xn mod p e = Xn+λ = Xn =⇒ aλ = 1 mod p e
λ est l’ordre de a modulo p e
Un élément a pour lequel cet ordre est le plus élevé est un “élément
primitif”
On choisit alors a comme étant un des éléments primitifs.
La période maximale λ(m) (pour c = 0) est obtenue avec X0 premier
avec m et est le PPCM des λi relatifs aux piei .

A. Buys (Dpt Informatique) Simulation sur ordinateur 20 / 110

Intro Loi uniforme Tests Loi non uniforme

Reste à trouver les éléments primitifs ...

Théorème
(Carmichael, 1910)
Le nombre a est un élément primitif modulo p e si et seulement si
i) p e = 2, a est impair; ou p e = 4, a mod 4 = 3; ou p e = 8, a mod 8 = 3, 5, 7;
ou p = 2,e ≥ 4, a mod 8 = 3, 5
ii) p est impair, e = 1, a 6= 0 mod p, et a(p−1)/q 6= 1 mod p pour aucun diviseur
premier q de p − 1
iii) p est impair, e > 1, a satisfait (ii) et ap−1 6= 1 mod p 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 21 / 110

Intro Loi uniforme Tests Loi non uniforme

Autres méthodes
Comment obtenir une période > m ?

On peut par exemple partir de X0 , X1 et

(Xn+1 = aXn + bXn−1 + c) mod m

(m2 doublets différents au maximum, période maximale : m2 + 1 )
c = 0,a = b = 1 “Mauvais exemple” Fibonacci
(Xn+1 = Xn−24 + Xn−55 ) mod m (n ≥ 55)
Méthodes quadratiques
Fibonnaci avec décalages de registre
“Mersenne Twister” (Makoto Matsumoto et Takuji Nishimura, 1997)
Congruence linéaire (produit matriciel) et décalages de registre
basé sur m = 219937 − 1 (nombre de Mersenne)
“uniformément distribué sur un grand nombre de dimensions (623 pour
les nombres de 32 bits)”
Pas très bon pour de la cryptographie.

A. Buys (Dpt Informatique) Simulation sur ordinateur 22 / 110

Intro Loi uniforme Tests Loi non uniforme

Nombres remarquables (π, e, ...)

e = 2.71828182845904523536028747135266249...
π = 3.14159265358979323846264338327950288...
“The Quest for Pi”, David H. Bailey, Jonathan M. Borwein, Peter B. Borwein and Simon Plouffe,
June 25, 1996, Mathematical Intelligencer, vol. 19 , no. 1 (Jan. 1997), pp. 50–57
[Link]

Section suivante : comment juger du caractère pseudo-aléatoire d’une

séquence de nombres ?
Et si on vous demandait de générer des nombres à la main ?
π = 3.141592653589793238462643383279...

A. Buys (Dpt Informatique) Simulation sur ordinateur 23 / 110

Intro Loi uniforme Tests Loi non uniforme

Tests des séries générées

Rappel d’analyse
Rappels de théorie des probabilités (et statistique)
Test du χ2
Test de Kolmogorov-Smirnov
Test du gap
Test du poker
Test du collectionneur de coupons
Test de permutation
Méthode des “runs”
Test du maximum

A. Buys (Dpt Informatique) Simulation sur ordinateur 24 / 110

Intro Loi uniforme Tests Loi non uniforme

Rappel d’analyse

Soit une fonction F de Rn dans Rm :

   
x1 f1 (x1 , ..., xn )
 .   . 
   
 . →
F : .
  

 .   . 
xn fm (x1 , ..., xn )
 ∂f1 ∂f1  Matrice carrée
∂x1 ... ∂xn donc on peut
 . . .  calculer le
∂(f1 , ..., fm )   déterminant
alors JF = = . . . 
∂(x1 , ..., xn )  
 . . . 
Dérivée partielle des fonctions par la dérivée partielle des variables ∂fm ∂fm
∂x1 ... ∂xn

est la matrice jacobienne de F.

Si m = n, on peut calculer son déterminant det JF (“Jacobien”), dont
la valeur absolue intervient lors d’un changement de variables dans les
intégrales multiples.
A. Buys (Dpt Informatique) Simulation sur ordinateur 25 / 110
Intro Loi uniforme Tests Loi non uniforme

Soit par exemple une fonction F de R2 dans R2 :

   
u x = f1 (u, v )
F : → F (u, v ) =
v y = f2 (u, v )

alors Z Z Z Z
g (x, y )dx dy = g (F (u, v )) |detJF | du dv

Soit
coordonnées polaires
∂x ∂x
 
  
x = r cos θ ∂r ∂θ cos θ −r sin θ
→ JF =  =
y = r sin θ ∂y ∂y sin θ r cos θ
∂r ∂θ

et det JF = r .

A. Buys (Dpt Informatique) Simulation sur ordinateur 26 / 110

Intro Loi uniforme Tests Loi non uniforme

Donc
Z +∞ Z +∞ Z +∞ Z 2π
g (x, y )dx dy = g (F (r , θ)) r dr dθ
−∞ −∞ 0 0

Z +∞ 2 Z +∞ Z +∞
x2 x 2 +y 2
e − 2 dx = e− 2 dx dy
−∞ −∞ −∞
Z +∞ Z 2π
r2
= e − 2 r dr dθ
0 0
Z +∞
r2
= 2π e − 2 r dr
0
h r2
i+∞
= 2π −e − 2 = 2π
0

A. Buys (Dpt Informatique) Simulation sur ordinateur 27 / 110

Intro Loi uniforme Tests Loi non uniforme

Rappels de théorie des probabilités

n! k n−k
Loi binomiale PX (k) = (n−k)!k! p (1 − p) E (X ) = np, σ 2 (X ) = np (1 − p)
k
Loi de Poisson PX (k) = λk! e −λ E (X ) = σ2 (X ) = λ
(x−m)2
Loi 1
normale f (x) = √2πσ 2
e − 2σ2
−λx
Loi exponentielle f (x) = λe 1 2 1 −λt
E (X ) = λ , σ (X ) = 2 , P(x ≥ t) = e
λ

Somme de variables aléatoires indépendantes (convolution des densités)

Fonction de partition : primitive de la distribution Z +∞
Important à savoir
fX +Y (z) = fX (z − y ) fY (y ) dy
−∞

Changement de variables : Y = g (X )
Z +∞
fY (y ) = δ(y − g (x)) fX (x) dx
−∞

avec la distribution (fonctionnelle) δ de Dirac :

R +∞
−∞
δ(x − y ) f (x) dx = f (y )
A. Buys (Dpt Informatique) Simulation sur ordinateur 28 / 110
Intro Loi uniforme Tests Loi non uniforme

P δ(x−xi )
Au sens des fonctionnelles, δ(g (x)) = i |g 0 (xi )| où g (xi ) = 0 et
g 0 (xi ) 6= 0.

Par exemple, X 2 avec X de loi N(0,1)

Z +∞
1 2
fX 2 (x) = dy δ(x − y 2 ) √ e −y /2
−∞ 2π
Z +∞
1 √ √ 1 2
e −y /2

= dy δ(y + x) + δ(y − x) √
−∞ 2|y | 2π
1 1
= √ √ e −x/2
2π x
1
= √ x −1/2 e −x/2 (x > 0)
2π

χ2 à 1 degré de liberté.

A. Buys (Dpt Informatique) Simulation sur ordinateur 29 / 110

Intro Loi uniforme Tests Loi non uniforme

Autre exemple, W (t) densité de probabilité de X 2 + Y 2 avec X , Y de

lois N(0,1) indépendantes

Z +∞ Z +∞
1 2 /2 2 /2
W (t) = dx dy e −x e −y δ(t − x 2 − y 2 )
2π −∞ −∞

1 n p p o
δ(t − x 2 − y 2 ) = p δ(x − t − y 2 ) + δ(x + t − y 2 )
2 t − y2
√ 2
+ t
e −y /2 +∞
Z Z
1 2 /2
W (t) = √ dy p dx e −x {...}
2π − t 2 t − y2 −∞
Z + √t 2
1 e −y /2 2 2
= √ dy p (e −(t−y )/2 + e −(t−y )/2 )
2π − t 2 t − y2
√
Z + t
1 −t/2 dy
= e √ p
2π − t t − y2
A. Buys (Dpt Informatique) Simulation sur ordinateur 30 / 110
Intro Loi uniforme Tests Loi non uniforme

√
Z + t
1 −t/2 dy
W (t) = e √ p
2π − t t − y2
Z +1
1 −t/2 1 y
= e q d( √ )
2π −1 1 − ( √yt )2 t

1 −t/2 +1
Z
dx
= e √
2π −1 1 − x2
Z +1
1 −t/2 dx
= e √
π 0 1 − x2
Z +1
1 −t/2 1 π
= e d(arcsinx) = e −t/2
π 0 π 2
1 −t/2
= e
2

χ2 à 2 degrés de liberté.
A. Buys (Dpt Informatique) Simulation sur ordinateur 31 / 110
Intro Loi uniforme Tests Loi non uniforme

On peut généraliser pour n variables aléatoires indépendantes de lois

N(0,1)
1 n
fn (x) = n n x 2 −1 e −x/2 Θ(x)
2 2 Γ( 2 )

où Θ est la fonction de Heaviside (Θ(x) = 0 si x < 0, 1 si x ≥ 0).

médiane = n - 2/3
(au sens des fonctionnelles, Θ0 (x) = δ(x))

Pour χ2n , E (X ) = n, σ 2 (X ) = 2n

A. Buys (Dpt Informatique) Simulation sur ordinateur 32 / 110

Intro Loi uniforme Tests Loi non uniforme

Probabilité conditionnelle

P(A ∩ B)
P(A|B) =
P(B)

Par exemple, pour la loi exponentielle P(x ≥ t) = e −λt et

P(x ≥ t + h ∩ x ≥ t)
P(x ≥ t + h|x ≥ t) =
P(x ≥ t)
P(x ≥ t + h)
=
P(x ≥ t)
e −λ(t+h)
= = e −λh
e −λt
= P(x ≥ h)

(Loi dite “sans mémoire”)

A. Buys (Dpt Informatique) Simulation sur ordinateur 33 / 110

Intro Loi uniforme Tests Loi non uniforme

Théorême de Bayes (“théorême sur la probabilité des causes”)

Soient {Bj } un ensemble d’événements tels que la somme de leurs

probabilités vaut 1,

P(A|Bi )P(Bi )
P(Bi |A) = P
j P(A|Bj )P(Bj )

En pratique, les probabilités “a priori” P(Bj ) ne sont pas toujours

connues.

A. Buys (Dpt Informatique) Simulation sur ordinateur 34 / 110

Intro Loi uniforme Tests Loi non uniforme

Tests d’hypothèse (version courte et adaptée à ce qui suit)

Le but est de déterminer si une hypothèse H0 (hypothèse “nulle”) est
raisonnable en fonction d’une observation O par rapport à une
hypothèse alternative H1 (Exemple : les nombres générés sont-ils distribués uniformément ou pas
?).

On ne va pas essayer de calculer la probabilité de H0 (probabilité a

priori inconnue) mais déterminer si la probabilité conditionnelle par
rapport à H0 de ce qu’on observe P(O|H0 ) dépasse un certain seuil
fixé. C’est ce qu’on appelle l’erreur de première espèce α qui est la
probabilité de rejeter une hypothèse H0 alors qu’elle est vraie (l’erreur
de seconde espèce β à l’inverse est la probabilité d’accepter H0 fausse).
Si on considère la distribution théorique d’une grandeur observée (sur
base de l’hypothèse H0 ), on obtient par exemple la courbe représentée
sur la figure suivante :

A. Buys (Dpt Informatique) Simulation sur ordinateur 35 / 110

Intro Loi uniforme Tests Loi non uniforme

On peut alors rejeter l’hypothèse H0 si notre observation se trouve dans

la zone d’exclusion (hachuré sur la figure). NB: dans l’exemple, on a
choisi une grandeur toujours positive et le test est unilatéral.

A. Buys (Dpt Informatique) Simulation sur ordinateur 36 / 110

Intro Loi uniforme Tests Loi non uniforme

Test du χ2
On crée un histogramme (r intervalles) en comptant le nombre de
valeurs générées dans chaque intervalle (ni ).
On s’attend à avoir “à peu près” le même nombre de points dans
chaque intervalle (probabilités pi égales).

A. Buys (Dpt Informatique) Simulation sur ordinateur 37 / 110

Intro Loi uniforme Tests Loi non uniforme

On construit
r
(ni − ( rj=1 nj )pi )2 Xr 
ni − Npi 2
P 
X
Kr = = √
( rj=1 nj )pi
P
i=1
Npi i=1
Pr
Dans l’exemple, r = 10, N = j=1 nj = 1000, pi = 0.1, Kr = 17.72
La distribution des effectifs ni suit une loi multinomiale
Pr :
N! n1 nr si
P(X1 = n1 , ..., Xr = nr ) = n1 !...n p
r! 1
...p r j=1 n j = N, 0 sinon.
i −Npi
√   2
X√
−→ N(0, 1 − pi ), ri=1 X√i −Np −→ χ2r −1
P i
Np i N→∞ Np i loi
Les Npi sont des variances poissonniennes.
On obtient unePloi de χ2 à r − 1 degrés de liberté (on a une
contrainte sur rj=1 nj ).
On se donne une probabilité α telle  que l’hypothèse examinée est
2
rejetée si elle a une probabilité P χ ≥ valeur obtenue < α de se
produire (voir table).
A. Buys (Dpt Informatique) Simulation sur ordinateur 38 / 110
Intro Loi uniforme Tests Loi non uniforme

k \α 0.10 0.05 0.025 0.01 0.001

1 2.706 3.841 5.024 6.635 10.828
2 4.605 5.991 7.378 9.210 13.816
3 6.251 7.815 9.348 11.345 16.266
4 7.779 9.488 11.143 13.277 18.467
5 9.236 11.070 12.833 15.086 20.515
6 10.645 12.592 14.449 16.812 22.458
7 12.017 14.067 16.013 18.475 24.322
8 13.362 15.507 17.535 20.090 26.125
9 14.684 16.919 19.023 21.666 27.877
10 15.987 18.307 20.483 23.209 29.588
11 17.275 19.675 21.920 24.725 31.264
12 18.549 21.026 23.337 26.217 32.910
13 19.812 22.362 24.736 27.688 34.528
14 21.064 23.685 26.119 29.141 36.123
Figure: Valeurs critiques χ2α du χ2 pour une probabilité α et par nombre k de
degrés de liberté
A. Buys (Dpt Informatique) Simulation sur ordinateur 39 / 110
Intro Loi uniforme Tests Loi non uniforme

On n’a pas de méthode pour décider à coup sûr si l’hypothèse doit

être rejetée. On a juste une probabilité.
petite question d'examen

On pourrait multiplier les expériences pour voir si on reproduit la

courbe.

A. Buys (Dpt Informatique) Simulation sur ordinateur 40 / 110

Intro Loi uniforme Tests Loi non uniforme

Test de Kolmogorov-Smirnov
On compare les fonctions de répartition des distributions
Z x
F (x) = f (y ) dy = P {X ≤ x}
−∞

On compare la fonction de répartition théorique F (x) à la fonction de

répartition expérimentale Fn (x) = nombre de nvaleurs ≤x .
De façon générale, F (−∞) = 0, F (+∞) = 1.
F (x) doit être continue.

Proba d'être entre a et b :

b-a
Proba d'avoir un nombre entre 0 et 1
c'est 1 = la longueur de l'intervalle.
(Cas loi uniforme)

A. Buys (Dpt Informatique) Simulation sur ordinateur 41 / 110

Intro Loi uniforme Tests Loi non uniforme

Pour une loi uniforme [0, 1[, F (x ≤ 0) = 0, F (x ≥ 1) = 1,

F (0 ≤ x ≤ 1) = x.

Soit Dn = sup |Fn (x) − F (x)|

x∈R

Théorème
(Kolmogorov-Smirnov)
√ P+∞ 2 2
P nDn < x −→ K (x) = k=−∞ (−1)k e −2k n (x > 0)
n→∞
Comme précédemment, on utilisera une valeur critique α:

P {Dn > Dα } = α
ou bien, de façon équivalente,
√ √
P nDn > nDα = α

A. Buys (Dpt Informatique) Simulation sur ordinateur 42 / 110

Intro Loi uniforme Tests Loi non uniforme

n\α 0.20 0.15 0.10 0.05 0.01

3 .565 .597 .642 .708 .828
4 .494 .525 .564 .624 .733
5 .446 .474 .510 .565 .669
6 .410 .436 .470 .521 .618
7 .381 .405 .438 .486 .577
8 .358 .381 .411 .457 .543
9 .339 .360 .388 .432 .514
10 .322 .342 .368 .410 .490
15 .266 .283 .304 .338 .404
20 .231 .246 .264 .294 .356
25 .210 .220 .240 .270 .320
30 .190 .200 .220 .240 .290
35 .180 .190 .210 .230 .270
1.07 1.14 1.22 1.36 1.63
≥ 35 √
n
√
n
√
n
√
n
√
n

Figure: Valeurs critiques Dα de KS pour une probabilité α et pour une taille n

d’échantillon
A. Buys (Dpt Informatique) Simulation sur ordinateur 43 / 110
Intro Loi uniforme Tests Loi non uniforme

Contrairement au χ2 , on ne fait pas de classes (intervalles) et on ne

perd pas d’information.
Le calcul est aussi plus gourmand (mémoire, classement).
Dans la littérature, on trouve des variantes
√
Kn+ = n sup (Fn (x) − F (x))
√ x∈R
Kn− = n sup (F (x) − Fn (x))
x∈R

Dα → Kα (et table correspondante)

Avec cette formulation, il existe des algorithmes qui évitent de devoir

classer les données.

A. Buys (Dpt Informatique) Simulation sur ordinateur 44 / 110

Intro Loi uniforme Tests Loi non uniforme

n\α 0.25 0.05 0.01

3 0.7539 1.1017 1.3589
4 0.7642 1.1304 1.3777
5 0.7674 1.1392 1.4024
10 0.7845 1.1658 1.4440
15 0.7926 1.1773 1.4606
20 0.7975 1.1839 1.4698
30 0.8036 1.1916 1.4801
√ √ √
> 30 0.8326−1/(6 n) 1.2239−1/(6 n) 1.5174−1/(6 n)
Figure: Valeurs critiques Kα de Kn+ /Kn− pour une probabilité α et pour une taille
n d’échantillon

A. Buys (Dpt Informatique) Simulation sur ordinateur 45 / 110

Intro Loi uniforme Tests Loi non uniforme

Test du gap n nombres

On se donne 0 ≤ a < b ≤ 1 et on génère u1 , u2 , u3 , u4 , u5 , u6 , u7 , ...un
On marque ceux qui tombent dans [a, b], probabilité p = b − a.
On s’intéresse aux distances entre deux nombres marqués.
(uj ,uj+1 ,...,uj+r ) avec uj+r ∈ [a, b] et uj ,uj+1 ,...,uj+r −1 ∈
/ [a, b] est de
longueur r .
Soit lr la probabilité d’avoir une séquence de longueur r .
l0 = p
l1 = (1 − p)p
...
li = (1 − p)i p
l>i = (1 − p)i+1
On compte les nombres d’occurrences de chacune des longueurs et on
compare aux valeurs attendues Np,Np(1 − p),... (où N est le nombre
de gaps ≈ np) =⇒ χ2 .
Pour un temps de calcul optimal, choisir a ou b = 0 ou 1, par exemple
(a = 0, b = 12 ) ou (a = 12 , b = 1).
A. Buys (Dpt Informatique) Simulation sur ordinateur 46 / 110
Intro Loi uniforme Tests Loi non uniforme

Test du poker
On joue avec k = 5 dés à d = 6 faces.
5 faces identiques : poker
4 faces identiques : carré
3 + 2 faces identiques : full
3 faces identiques : brelan
2 + 2 faces identiques : double paire
2 faces identiques : paire
On divise [0, 1[ en d = 6 intervalles, 5 nombres dans le même intervalle
donnent un poker, etc ... et, pour simplifier
Poker → une seule case
Carré ou full → 2 cases différentes
Brelan ou double paire → 3 cases différentes
Paire → 4 cases différentes
Rien (ici) → 5 cases différentes
Soit r le nombre de cases différentes, on peut calculer la probabilité Pr
d’une de ces configurations.

A. Buys (Dpt Informatique) Simulation sur ordinateur 47 / 110

Intro Loi uniforme Tests Loi non uniforme

Le nombre de manières de constituer r paquets avec k nombres est le

nombre de Stirling
     
k k−1 k−1
= +r
r r −1 r

avec    
k k
= =1
1 k

k \r 1 2 3 4 5
1 1
2 1 1
3 1 3 1
4 1 7 6 1
5 1 15 25 10 1
Jusque là, on distingue les objets mais pas les paquets (indiscernables).
Il faut encore affecter les intervalles aux paquets.
Par exemple, on a une paire, on vient de distinguer qu’elle était formée
du dé no 1 et du dé no 5 mais on ne sait pas encore si c’est une paire
d’as ou de valets.
A. Buys (Dpt Informatique) Simulation sur ordinateur 48 / 110
Intro Loi uniforme Tests Loi non uniforme

On multiplie alors par le nombre de façons d’affecter les paquets aux

intervalles et on divise par le nombre total de manières de répartir les
k nombres dans les intervalles :
 
k
d(d − 1)...(d − r + 1)
r
Pr = (r ≤ d)
dk
On va donc générer n k-tuples, chaque fois déterminer les nombres de
cases différentes et faire un comptage =⇒ χ2 . Au besoin (P1 est
petit), on peut regrouper des classes.

A. Buys (Dpt Informatique) Simulation sur ordinateur 49 / 110

Intro Loi uniforme Tests Loi non uniforme

Test du collectionneur de coupons

On a un dé à d = 6 faces.
On va lancer le dé tant qu’on n’a pas obtenu les d faces au moins une
fois chacune.
Sr : probabilité de devoir lancer le dé r fois (r < d → Sr = 0).
Après r lancers, la probabilité d’avoir au moins d faces différentes vaut
 
r d!
pr =
d dr
et la probabilité qr de ne pas encore avoir toutes les faces vaut
   
r d!
qr = 1 −
d dr
Alors, si on note que l’événement “pas toutes les faces après r jets” est
un sous-ensemble de “pas toutes les faces après r − 1 jets”
   
r d! r −1 d!
Sr = qr −1 − qr = −
d dr d d r −1

A. Buys (Dpt Informatique) Simulation sur ordinateur 50 / 110

Intro Loi uniforme Tests Loi non uniforme

Et par la formule de récurrence donnée plus haut

     
d! r r −1 d! r −1
Sr = r −d = r
d d d d d −1

Si on s’arrête à un nombre de jets t > r , on peut alors former un

dernier intervalle “pas toutes les faces après t jets” avec pour
probabilité  
t −1 d!
1−
d d t−1
La comparaison avec les comptages conduit à un test de χ2 .

A. Buys (Dpt Informatique) Simulation sur ordinateur 51 / 110

Intro Loi uniforme Tests Loi non uniforme

triplets = 3! permutations
6-uples = 6! = 720
Test de permutation
Pour un k-tuple X1 , X2 , ..., Xk , on va regarder l’ordre relatif des
nombres par rapport à une séquence triée (on suppose qu’on n’a pas
deux fois le même nombre dans le k-tuple).
On a k! permutations possibles et on s’attend à ce qu’elles soient
également représentées.
Exemple (k=3):
   
0.1 0.3 0.2 1 3 2
 0.4 0.5 0.6  =⇒  1 2 3 
0.05 0.01 0.99 2 1 3
On veut un compteur pour chacune des k! permutations.
A chaque permutation 1 5 6 3 4 2 , on va faire correspondre un
nombre 0 ≤ f ≤ 6! (de façon générale k!)
On numérote les positions de 0 à 5 (0 à k − 1):

0 1 2 3 4 5
1 5 6 3 4 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 52 / 110

Intro Loi uniforme Tests Loi non uniforme

0 1 2 3 4 5
1 5 6 3 4 2 0
2 5 6 3 4 1 0
4 5 6 3 2 1 3
4 5 6 3 2 1 0
6 5 4 3 2 1 1
6 5 4 3 2 1 0 d'office un 0 pour le dernier

On commence par noter la position du plus petit et on le met de côté.

On l’échange avec le dernier et on recommence. Notons
bn sont les nombres en rouges

0 ≤ b1 = 0 ≤ k − 1 Valeurs possible pour b1

0 ≤ b2 = 0 ≤ k − 2
0 ≤ b3 = 3 ≤ k − 3
0 ≤ b4 = 0 ...
0 ≤ b5 = 1
0 ≤ b6 = 0

A. Buys (Dpt Informatique) Simulation sur ordinateur 53 / 110

Intro Loi uniforme Tests Loi non uniforme

A partir des bi , on peut reconstruire la permutation d’origine.

On a une base variable dans laquelle on peut représenter 0 ≤ f ≤ k! :

b1 → ?1
b2 → ?k
b3 → ?k(k − 1)
b4 → ?k(k − 1)(k − 2)
...
bk → ?k! bk = 0

f = k! bk +k(k−1)...3 bk−1 +k(k−1)...4 bk−2 +...+k(k−1) b3 +k b2 +b1

Comment calculer f intelligemment ?

A. Buys (Dpt Informatique) Simulation sur ordinateur 54 / 110

Intro Loi uniforme Tests Loi non uniforme

Méthode analogue à Horner pour les polynômes:

6 ? (5 ? (4 ? (3 ? (2 ? b6 + b5 ) + b4 ) + b3 ) + b2 ) + b1
On devrait avoir b6 d’abord au lieu de b1 , On va changer l’ordre des
poids dans la base et calculer (on peut montrer que la méthode est
équivalente): (((((b1 ? 5 + b2 ) ? 4 + b3 ) ? 3 + b4 ) ? 2 + b5 )?1) + b6
Algorithme :
1 r ← k; f ← 0
2 Trouver le minimum des {X1 , ..., Xr } → Xs
f ← f ? r + s − 1 (car les positions sont numérotées de 0 à k − 1)
3 Xr ↔ Xs
4 r ←r −1
5 Si r > 1, aller en (2)
On peut évidemment utiliser le maximum au lieu du minimum.
On génère n k-tuples et pour chacune des k! permutations, on compare
le compteur avec la valeur attendue =⇒ χ2 .

A. Buys (Dpt Informatique) Simulation sur ordinateur 55 / 110

Intro Loi uniforme Tests Loi non uniforme

Méthode des “runs” (séries croissantes)

1298536704
On va étudier la fréquence des runs de chaque longueur (dans
l’exemple 2 de 3, 1 de 2, 2 de 1).
Problème : la fréquence des runs successifs n’est pas indépendante. Un
run long a de bonnes chances d’être suivi d’un run plus court.
rmax
2
X (ri − rith )2
χ =
i=1
σ 2 (rith )

n’est pas applicable et doit être généralisé par

rmax
X
χ2 = (ri − rith )(rj − rjth ) aij
i,j=1

où (aij ) est l’inverse de la matrice de covariance.

A. Buys (Dpt Informatique) Simulation sur ordinateur 56 / 110

Intro Loi uniforme Tests Loi non uniforme

Soit Zpi = 1 si la position i est le début d’un run de longueur ≥ p,

0 sinon.
1298536704
1 = Z11 = Z21 = Z31 = Z14 = Z15 = Z16 = Z26 = Z36 = Z19 = Z29
Soit n la longueur totale de la séquence générée, le nombre de runs de
longueur ≥ p est donné par (Zpi = 0 pour i > n − p + 1)
Rp0 = Zp1 + Zp2 + ... + Zpn = Zp1 + Zp2 + ... + Zp,n−p+1
Le nombre de runs de longueur p est Rp = Rp0 − Rp+1 0

Les nombres moyens pour toutes les permutations possibles de la

0
1 (perm) 1 (perm)
et Rp0 = n!
P P
séquence sont Rp = n! (perm) Rp (perm) Rp .
h i
1
Pn (perm) 1
Pn
Rp0 = n!
P
(perm) i=1 Zpi = n! i=1 { nombre de permutations pour lesquelles
commence en i un run de longueur ≥ p }

A. Buys (Dpt Informatique) Simulation sur ordinateur 57 / 110

Intro Loi uniforme Tests Loi non uniforme

Considérons les p + 1 nombres suivants

. > = < < < ?
. i −1 i . . i +p−1 .
Cas (i 6= 1)

Pour 1 < i ≤ n − p + 1, on a
n! n!p
{...} = p=
(p + 1)!(n − p − 1)! (p + 1)!
(l’ordre relatif dans le run est sans importance)
(i − 1 ne peut pas être le plus petit des p + 1, p possibilités)

Ce terme est indépendant de i et apparaı̂t n − p fois

Cas (i = 1)
n!
{...} =
p!

A. Buys (Dpt Informatique) Simulation sur ordinateur 58 / 110

Intro Loi uniforme Tests Loi non uniforme

En rassemblant les 2 cas (i = 1, i 6= 1)

 
0
1 n! (n − p)p n! (n + 1)p p−1
Rp = + = −
n! p! (p + 1)! (p + 1)! p!
et
Rp = Rp0 − R 0 p+1
Le calcul de la covariance est un peu plus long mais suit le même
principe

cov (Rp , Rq ) = (Rp − Rp )(Rq − Rq )

cov (Rp , Rq ) = cov (Rp , Rq0 ) − cov (Rp , Rq+1
0
)
cov (Rp , Rq0 ) = cov (Rp0 , Rq0 ) − cov (Rp+1
0
, Rq0 )

 
n
1 X X (perm) (perm)
cov (Rp0 , Rq0 ) =  Zpi Zqj  − R 0p R 0q
n!
(perm) i,j=1

A. Buys (Dpt Informatique) Simulation sur ordinateur 59 / 110

Intro Loi uniforme Tests Loi non uniforme

Pn
cov (Rp0 , Rq0 ) = 1
n! i,j=1 { nombre de permutations pour lesquelles commencent en i un run de
longueur ≥ p et en j un de longueur ≥ q } −R 0 p R 0 q

et après avoir distingué les différents cas où les runs sont contigus
(j = i + p) ou disjoints, on obtient :
 0
0 0 Rt + f (p, q, n) (p + q ≤ n)
cov (Rp , Rq ) =
Rt0 − R 0 p R 0 q (p + q > n)
où t = max(p, q), s = p + q et

   
s(1 − pq) + pq 2s s −1
f (p, q, n) = (n + 1) − +2
(p + 1)!(q + 1)! (s + 1)! s!
(s 2 − s − 2)pq − s 2 − p 2 q 2 + 1
+
(p + 1)!(q + 1)!
Si des classes sont trop peu remplies, on peut les grouper (par exemple,
1, 2, 3, 4, 5, ≥ 6)
Neutraliser le nombre qui suit un run ? (indépendance ?)
A. Buys (Dpt Informatique) Simulation sur ordinateur 60 / 110
Intro Loi uniforme Tests Loi non uniforme

Test du maximum
Pour un k-tuple X1 , X2 , ..., Xk , soit Y = max(X1 , X2 , ..., Xk )

{Y ≤ y } = {x1 ≤ y } ∧ {x2 ≤ y } ∧ ... ∧ {xk ≤ y }

P {Y ≤ y } = P {x1 ≤ y } P {x2 ≤ y } ... P {xk ≤ y } = y k
(loi uniforme)
< y car probabilité d'être dans
l'interval

Ceci permet de faire un test de Kolmogorov-Smirnov

A. Buys (Dpt Informatique) Simulation sur ordinateur 61 / 110
Intro Loi uniforme Tests Loi non uniforme

Génération de nombres aléatoires suivant des lois non

uniformes
A. Loi discrète Comment générer des nombres suivant
Exemple : jet de 2 dés cette loi ?
1 2 3 1
2 → 36 , 3 → 36 , 4 → 36 , ..., 12 → 36 .

A. Buys (Dpt Informatique) Simulation sur ordinateur 62 / 110

Intro Loi uniforme Tests Loi non uniforme

Acceptance - Rejet

On génère des couples de valeurs dans [2, 13[ (abscisse) et [0, 16 [

(ordonnée).
x, y dans [0, 1[
x 0 = 2. + 11. ? x
y 0 = 0.166666667 ? y
Si un point est sous le diagramme, on prend la partie entière de son
abscisse, sinon on le rejette.
C’est le rapport des surfaces qui compte.
Peu efficace si on a des variations brusques.

A. Buys (Dpt Informatique) Simulation sur ordinateur 63 / 110

Intro Loi uniforme Tests Loi non uniforme

Fonction de répartition

probabilité d'avoir un nombre plus petit que ...

Escalier à “11 marches”

On génère y dans [0, 1[ (ordonnée)
La probabilité de se trouver en face d’une contre-marche est égale à la
probabilité de l’abscisse correspondant.
Pas de rejet car on se trouve
1 , P {X ≤ 3} = 3 , P {X ≤ 4} = 6 ,P {X ≤ 5} = 10
P {X ≤ 2} = 36 forcement en face d'une
36 36 36
marche
15 ,P {X ≤ 7} = 21 ,...
P {X ≤ 6} = 36 36
Pas de rejet mais recherche dans une table (dichotomique).
A. Buys (Dpt Informatique) Simulation sur ordinateur 64 / 110
Intro Loi uniforme Tests Loi non uniforme

Méthode des aliases (Walker, 1974)

On construit les deux tableaux Pj ,Yj suivants (j = 0, k − 1;k = 16) :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Pj 0 0 4 8 1 7 1 1 1 7 7 8 4 0 0 0
9 9 9 9 9 9 9

Yj 5 9 7 4 ? 6 ? ? ? 8 4 7 10 6 7 8
* si valeur qui n'a
On génère U dans [0, 1[, K = [kU], V = kU − K . pas d'impact
Soit N le nombre à générer Partie non entière

1 j ←K
2 Si V ≤ Pj alors N ← j, sinon N ← Yj

Si j = 0, 1, 13, 14, 15, V ≥ Pj = 0, 1 cas sur 16

1 1 7 5 ou 9 c'est les chiffres tout au dessus donc 1 chance sur
N = 5, 9 → 16 + 16 9
= 19 16 ou alors quand on génère 0 on peut avoir 5 ou 9
1 5 1 1 24
N = 7 → 16 ( 9 + 1 + 9 + 1) = 16 9
= 16 5/9 car proba d'être au dessus de 4/9 pour
1 4 1 générer 2. Le 1/16 d'avant c'est pour la
N = 2, 12 → 16 9 = 36 chance d'avoir le 7 tout au dessus
1 8 2
N = 3 → 16 9
= 36
1 1
N = 4 → 16 ( 9 + 1 + 29 ) = 16 1 12
9
= 363
1 2 1 20 5
N = 6, 8 → 16 ( 9 + 1 + 1) = 16 9 = 36
1 7 5 1 12 3
N = 10 → 16 ( 9 + 9 ) = 16 9 = 36
1 8 2
N = 11 → 16 9
= 36

A. Buys (Dpt Informatique) Simulation sur ordinateur 65 / 110

Intro Loi uniforme Tests Loi non uniforme

Miracle ? On égalise la courbe en déplaçant ce qui est au-dessus en

dessous.

Par exemple, on est trop bas pour 3, on prend un morceau du 4.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Pj 0 0 4 8 1 7 1 1 1 7 7 8 4 0 0 0
9 9 9 9 9 9 9

Yj 5 9 7 4 ? 6 ? ? ? 8 4 7 10 6 7 8
On s’arrange pour n’avoir que 2 morceaux par colonne (2 tableaux).
On part d’une colonne sous la barre et on égalise avec une colonne
A. Buys
au-dessus, même si onSimulation
(Dpt Informatique)
prend de trop, et ainsi de suite.
sur ordinateur 66 / 110
Intro Loi uniforme Tests Loi non uniforme

Génération de nombres aléatoires suivant des lois non

uniformes
B. Loi continue

Acceptance - Rejet
Même principe que pour une loi discrète.
Si la loi est définie sur (0, +∞), peu efficace pour la queue de la
distribution.

A. Buys (Dpt Informatique) Simulation sur ordinateur 67 / 110

Intro Loi uniforme Tests Loi non uniforme

P1 + P2 + P3 + P4 = 1
On génère un abscisse en fonction des Pi (on suppose connaı̂tre
l’intégrale sur chaque intervalle), ce qui donne un intervalle.
Dans cet intervalle, on génère des points jusqu’au moment où on en
accepte un.
A priori, les taux d’acceptance dépendent de l’intervalle.
A n’utiliser que si on ne peut pas faire autrement.

A. Buys (Dpt Informatique) Simulation sur ordinateur 68 / 110

Intro Loi uniforme Tests Loi non uniforme

Inversion de la fonction de répartition

Ry Ry
F (y ) = −∞ f (x) dx = 0 f (x) dx est strictement croissante.
On génère z dans [0, 1[ et on a alors z = F (y ) =⇒ y = F −1 (z).
En effet, F (y ) = P {Y ≤ y } = P {Z ≤ z} = z

A. Buys (Dpt Informatique) Simulation sur ordinateur 69 / 110

Intro Loi uniforme Tests Loi non uniforme

On peut encore le voir autrement. Soit FX0 (x) = fX (x), HY0 (y ) = hY (y )

et y = G (x) (G strictement monotone → (x − G −1 (y )) a 1 ! racine).

δ(x − G −1 (y ))
Z Z
hY (y ) = dx fX (x)δ(y − G (x)) = dx fX (x) 0
|G (x)|x=G −1 (y )

Or G (G −1 (y )) = y =⇒ G 0 (x)|x=G −1 (y ) d
dy G
−1
(y ) =1
Z
d −1 d
hY (y ) = dx fX (x)δ(x −G −1 (y )) G (y ) = fX (G −1 (y )) G −1 (y )
dy dy

Soit maintenant fX (x) = 1 dans [0, 1[, alors hY (y ) = (G −1 )0 (y ) et

HY (y ) = G −1 (y ).

A. Buys (Dpt Informatique) Simulation sur ordinateur 70 / 110

Intro Loi uniforme Tests Loi non uniforme

Exemple : loi exponentielle Méthode pas satisfaisante

−αx
f (x) = αe densité
Z y
y
F (y ) = f (x)dx = −e −αx 0
= 1 − e −αy = z
0

1
−αy = ln(1 − z) =⇒ y = − ln(1 − z)
α
On peut donc prendre y = − α1 ln z 6 0).
(z =
Lien avec la loi de Poisson Prend bcp de temps de calcul
k
Pk = λk! e −λ
On veut étudier le nombre d’appels téléphoniques (ou le nombre de
voitures qui passent dans la rue) dans un intervalle de temps ]0, t].
On va faire les hypothèses suivantes :
1 Le nombre d’appels dans ]t, t + h] est indépendant de ]0, t] et ne
dépend que de h.
2 La probabilité d’avoir un appel dans ]t, t + h] est de la forme
αh + O(h).
3 La probabilité d’avoir plusieurs appels dans ]t, t + h] est de la forme
O(h) (rare).
A. Buys (Dpt Informatique) Simulation sur ordinateur 71 / 110
Intro Loi uniforme Tests Loi non uniforme

En résumé
1 appel : αh + O(h)
≥ 2 appels : O(h)
0 appel : 1 − αh + O(h)
Soit Pn (t + h) la probabilité d’avoir n appels dans ]0, t + h], on peut la
décomposer en
n − 1 appels dans ]0, t] et 1 appel dans ]t, t + h] (1)
n appels dans ]0, t] et 0 appel dans ]t, t + h] (2)
k appels dans ]0, t] et n − k ≥ 2 appels dans ]t, t + h] (3)
P(1) = Pn−1 (t).[αh + O(h)]
P(2) = Pn (t).[1 − αh + O(h)]
P(3) = Pk (t).O(h)
Pn (t + h) = αh Pn−1 (t) + (1 − αh) Pn (t) + O(h)
Pn (t + h) − Pn (t) = αh (Pn−1 (t) − Pn (t)) + O(h)
Pn0 (t) = α (Pn−1 (t) − Pn (t))
Pour n = 0, P0 (t + h) − P0 (t) = −αh P0 (t) + O(h) et
P00 (t) = −αP0 (t) =⇒ P0 (t) = Ce −αt

A. Buys (Dpt Informatique) Simulation sur ordinateur 72 / 110

Intro Loi uniforme Tests Loi non uniforme

On peut continuer pour n = 1, ...

P10 (t) = α (P0 (t) − P1 (t)) = α C e −αt − α P1 (t)
P1 (t) = C αt e −αt
et par récurrence

(αt)n −αt
A retenir Pn (t) = e
n!
∞
X
C= Pn (t) = 1
0

Probabilité d’un intervalle de temps t entre deux appels (ou plus

généralement temps d’attente, cf. hypothèse 1 !)
P(T > t) = P0 (t) = e −αt
F (t) = P(T ≤ t) = 1 − e −αt
f (t) = F 0 (t) = αe −αt

A. Buys (Dpt Informatique) Simulation sur ordinateur 73 / 110

Intro Loi uniforme Tests Loi non uniforme

On va générer des temps ti suivant une loi exponentielle et on choisit

tα de telle façon quePα tα = λ.
n
On s’arrête lorsque i=1 ti > tα , alors k = n − 1 est distribué suivant
une loi de Poisson.
ti = − α1 ln zi Si il demande loi normale
Pn−1 Pn alors méthode exacte
i=1 ti ≤ tα < i=1 ti

Pn−1 Pn
− α1 i=1 ln zi ≤ tα < − α1 i=1 ln zi
Pn Pn−1
i=1 ln zi < −αtα ≤ i=1 ln zi
Qn Qn−1
i=1 zi < e −αtα ≤ i=1 zi
−αtα
Ceci revient à calculer
Qn  = e et à générer des zi suivant une loi
uniforme tant que i=1 zi > .
1 Z ← 1; N ← 0
2 Z ← Z ? zi ; N ← N + 1
3 Si Z ≥ , aller en (2)
4 k ←N −1

A. Buys (Dpt Informatique) Simulation sur ordinateur 74 / 110

Intro Loi uniforme Tests Loi non uniforme

Loi normale - méthode approchée

x2 Rx t2
Centrée, réduite : f (x) = √12π e − 2 , F (x) = √12π −∞
e − 2 dt
F
P(x) n’a pas d’expression analytique.
12
i=1 zi − 6, avec zi uniformes dans [0, 1[
R1
σ 2 (z) = 0 (x − 12 )2 dx = 12
1

A. Buys (Dpt Informatique) Simulation sur ordinateur 75 / 110

Intro Loi uniforme Tests Loi non uniforme

Loi normale - méthode polaire

1 U1 , U2 uniformes dans [0, 1[, V1 = 2U1 − 1 et V2 = 2U2 − 1 uniformes

sur [−1, +1[.
2 S ← V12 + V22
3 Si S > 1, aller en (1)
q q
4 X1 ← V1 − 2 lnS S ,X2 ← V2 − 2 lnS S

(V1 , V2 ) uniforme sur le carré.

S = R2
V1 = R cos θ
V2 = R sin θ
√
R0 = −2
√ ln S
V1
X1 = R √−2 ln S = R 0 cos θ
V2
X2 = R −2 ln S = R 0 sin θ

A. Buys (Dpt Informatique) Simulation sur ordinateur 76 / 110

Intro Loi uniforme Tests Loi non uniforme

0
Loi de probabilité
√ de R 2 2
P(R ≤ r ) = P( −2 ln S ≤ r ) = P(S ≥ e −r /2 ) = 1 − e −r /2
0
2
D’où la densité fR 0 (r ) = r e −r /2

Z
1 2
P(X1 ≤ x1 ∧ X2 ≤ x2 ) = dθdr r e −r /2
r cos θ≤x1 ∧r sin θ≤x2 2π
X12 +X22
Z
1
= dX1 dX2 e − 2
2π X1 ≤x1 ∧X2 ≤x2
Z x1 X12
Z x2 X22
1 1
= √ dX1 e − 2 √ dX2 e − 2
2π −∞ 2π −∞

X1 et X2 sont bien indépendantes et de lois N(0, 1).

A. Buys (Dpt Informatique) Simulation sur ordinateur 77 / 110

Intro Loi uniforme Tests Loi non uniforme

Méthode paire-impaire
Soit
C e −h(x) si a ≤ x ≤ b

f (x) =
0 sinon
avec 0 ≤ h(x) ≤ 1 si a ≤ x ≤ b.
1 U uniforme dans [0, 1[, X = a + (b − a)U uniforme sur [a, b[.
2 V0 ← h(X ).
3 Générer V1 , V2 , V3 , ... uniformes dans [0, 1[ aussi longtemps que
Vi−1 ≥ Vi .
4 Si i est pair, retourner en (1), sinon, accepter X .

P(i) = P {(V0 ≥ V1 ≥ ... ≥ Vi−1 ) ∧ (Vi−1 < Vi )}

i−1
[h(X )]
P {V0 ≥ V1 ≥ ... ≥ Vi−1 } =
(i − 1)!

Les Vi sont indépendants et tous plus petits que V0 .

Un seul ordre convient.
i−1 i
[h(X )] [h(X )]
P(i) = −
(i − 1)! i!
A. Buys (Dpt Informatique) Simulation sur ordinateur 78 / 110
Intro Loi uniforme Tests Loi non uniforme

La probabilité de s’arrêter à une valeur de i impaire vaut

∞ i−1 i ∞ j
X [h(X )] [h(X )] X [h(X )]
− = (−1)j
(i − 1)! i! j!
i=1,3,5,... j=0
∞ j
X [−h(X )]
= = e −h(X )
j!
j=0

Combien de nombres à générer en moyenne ?

∞ ∞
( )
k−1 k
X X [h(X )] [h(X )]
k= k P(k) = k −
(k − 1)! k!
k=1 k=1
∞ k ∞ k
X [h(X )] X [h(X )]
= (k + 1) − k
k! k!
k=0 k=1
∞ k
X [h(X )]
= + 0 = e h(X ) ≤ e
k!
k=0

A. Buys (Dpt Informatique) Simulation sur ordinateur 79 / 110

Intro Loi uniforme Tests Loi non uniforme

Exemple : loi normale q

x2
On va se contenter la partie droite de la distribution f (x) = π2 e − 2
(le signe peut être tiré au sort par la suite).
Pour 1 ≤ j ≤ n + 1 (“n + 1 bits de précision”), on a une table des
dj = aj − aj−1 avec aj qui est donné par
Z +∞
1
f (x)dx = j
aj 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 80 / 110

Intro Loi uniforme Tests Loi non uniforme

j dj aj j dj aj
1 0.674489750 0.674489750 16 0.155349717 4.324919039
2 0.475859630 1.150349380 17 0.150409384 4.475328423
3 0.383771164 1.534120544 18 0.145902577 4.621231000
4 0.328611323 1.862731867 19 0.141770033 4.763001033
5 0.291142827 2.153874694 20 0.137963174 4.900964207
6 0.263684322 2.417559016 21 0.134441762 5.035405969
7 0.242508452 2.660067468 22 0.131172150 5.166578119
8 0.225567444 2.885634912 23 0.128125965 5.294704084
9 0.211634166 3.097269078 24 0.125279090 5.419983174
10 0.199924267 3.297193345 25 0.122610883 5.542594057
11 0.189910758 3.487104103 26 0.120103560 5.662697617
12 0.181225181 3.668329284 27 0.117741707 5.780439324
13 0.173601400 3.841930684 28 0.115511892 5.895951216
14 0.166841909 4.008772593 29 0.113402349 6.009353565
15 0.160796729 4.169569322 30 0.111402720 6.120756285

A. Buys (Dpt Informatique) Simulation sur ordinateur 81 / 110

Intro Loi uniforme Tests Loi non uniforme

t 2 −aj2
Soit, pour aj ≤ t ≤ aj+1 , h(t) = 2
t 2 −a2
h(t) = 2 j est-elle une bonne fonction pour la méthode
paire-impaire, i.e. h(t) ≤ 1 sur tout l’intervalle ?
Il faut montrer que sur tout l’intervalle t 2 − aj2 ≤ 2 ou encore que
2
aj+1 − aj2 ≤ 2
x 2 R +∞ t2
Considérons la fonction m(x) = e 2 x e − 2 dt

+∞ t2 +∞ Z +∞ t2
e− 2 −t e − 2
Z
1 − t2
dt = − e 2 − dt
x t2 t x x −t
x2 Z +∞
e− 2 t2
= − e − 2 dt
x x
+∞ t2
e− 2
Z
x2 1
e 2 dt = − m(x)
x t2 x
Z +∞ − t 2
1 x2 e 2 1
Donc m(x) = −e 2 dt <
x x t2 x

A. Buys (Dpt Informatique) Simulation sur ordinateur 82 / 110

Intro Loi uniforme Tests Loi non uniforme

m(x) est une fonction décroissante :

x2
h t2
ix
m0 (x) = x m(x) + e 2 −e − 2 = x m(x) − 1 <0
−∞
√
Soit alors y = x 2 + 2 ln 2 > x.
r Z +∞ r r r
2 2
− t2 2 − y2 1 2 − x2 1 2 − x2
e dt = e 2 m(y ) = e 2 m(y ) < e 2 m(x)
π y π 2 π 2 π

Posons x = aj .
r Z +∞ r r Z +∞
2 2
− t2 1 2 − aj2 11 2 t2
e dt < e 2 m(aj ) = j
= e − 2 dt
π y 2 π 22 π aj+1

Finalement y > aj+1 =⇒ aj2 + 2 ln 2 > aj+1

2 2
=⇒ aj+1 − aj2 < 2 ln 2 < 2.

A. Buys (Dpt Informatique) Simulation sur ordinateur 83 / 110

Intro Loi uniforme Tests Loi non uniforme

Algorithme
1 Générer un nombre aléatoire suivant la loi uniforme
U = (b0 , b1 , b2 , ...bn ) (en binaire).
2 B ← b0 , j ← 1, a ← 0.
3 Si bj = 1, a ← a + dj , j ← j + 1. Si j < n + 1, répéter (3).
4 (On arrive en j avec une probabilité 2−j ).
On va générer x dans [aj−1 , aj [ avec
h(x) = x 2 − a2 = y 2 + 2 a y (y = x − a).
5 Générer Y dans [0, dj [, V ← ( 21 Y + a)Y
(On peut prendre Y = dj .(bj+1 , ..., bn ))
6 Générer U dans [0, 1[. Si U > V , aller en (7), sinon (on continue la
séquence) regénérer V dans [0, 1[.
Si U < V (cas pair), aller en (5), sinon répéter (6).
7 X ← a + Y . Si B = 1, X ← −X .

A. Buys (Dpt Informatique) Simulation sur ordinateur 84 / 110

Intro Loi uniforme Tests Loi non uniforme

Méthode de Kinderman et Monahan (1976)

On se donne le rectangle suivant : 0 ≤ u ≤ umax , −vmax ≤ v ≤ vmax .
Soit x le coefficient angulaire du segment (0, 0) → (u, v ).
A l’intérieur du rectangle, on définit une courbe telle qu’on rejette les
points qui tombent en dehors.
On veut que les points acceptés soient tels que x est distribué suivant
la loi f (x).

Rx
−∞
f (t)dt = rapport des
surfaces (surface
turquoise/surface colorée).

A. Buys (Dpt Informatique) Simulation sur ordinateur 85 / 110

Intro Loi uniforme Tests Loi non uniforme

A démontrer
La courbe voulue est définie par u 2 = f ( vu ) ou u = f ( vu ).
p

Dénominateur : u > 0, u 2 ≤ f ( vu ).
Soit v = tu, dv = udt,
Z Z Z +∞ Z √f (t)
u>0 du dv = u du dt = dt u du
... −∞ 0
2
u ≤ f (t)
√
+∞  f (t) +∞
u2
Z Z
f (t) 1
= dt = dt =
−∞ 2 0 −∞ 2 2
Numérateur : u > 0, u ≤ f 2
( vu ), vu
≤ x.
x Z √f (t)
1 x
Z Z Z
u>0 du dv = dt u du = f (t)dt
−∞ 0 2 −∞
u 2 ≤ f (t)
t≤x
CQFD (NB: Encore valable même si f n’est pas normalisée).
A. Buys (Dpt Informatique) Simulation sur ordinateur 86 / 110
Intro Loi uniforme Tests Loi non uniforme

Exemple : loi normale

t2
v2
f (t) = e − 2 , u2
≤ −4 ln u.

Soit umax = 1,

∂v u2
2v = −8u ln u − 4 =0
∂u u
1
ln u = −
2
1
u = e− 2
2
v 2 = −4u 2 ln u =
r e
2
vmax =
e

A. Buys (Dpt Informatique) Simulation sur ordinateur 87 / 110

Intro Loi uniforme Tests Loi non uniforme

Ceci nécessite chaque fois le calcul d’un logarithme.

On va encadrer la courbe avec des courbes plus simples et on ne devra
faire le calcul que si on génère un point entre les deux.

∀x, e x ≥ 1+x
−1+cu
∀c, e ≥ cu ⇒ ln c + ln u ≤ cu − 1
⇒ ln c − cu + 1 ≤ − ln u
1
−1+ cu 1 1
∀c, e ≥ ⇒ −1 + ≥ − ln c − ln u
cu cu
1
⇒ − ln u ≤ ln c + −1
cu
1
ln c − cu + 1 ≤ − ln u ≤ ln c + −1
cu
On peut donc
1 Accepter systématiquement (u, v ) si 41 ( vu )2 ≤ ln c − cu + 1
2 Refuser systématiquement (u, v ) si 14 ( vu )2 ≥ ln c 0 + c 10 u − 1

A. Buys (Dpt Informatique) Simulation sur ordinateur 88 / 110

Intro Loi uniforme Tests Loi non uniforme

Il reste à determiner c pour avoir une surface la plus grande possible

et c 0 ... la plus petite possible.
Cas (1)

v
( )2 ≤ 4(1 + ln c) − 4cu
u p √
|v | ≤ |u| 4(1 + ln c) − 4cu = u a − bu

avec b = 4 c et a = 4 (1 + ln c).
Quand v = 0 (les bornes de u sont atteintes), u = ba ou 0
Ra R √ Ra √
Il faut donc maximiser R = 2 0b du 0 u a−bu dv = 2 0b u a − bu du
√ 2
− 12
Soit t = a − bu, u = a−t 1
b , − 2 b (a − bu) du = dt → du = − b2 t dt.
0  0  0
4a t 3 4 t5
Z
4 2 2
R = − 2 √
t (a − t )dt = − 2 +
b a b 3 √a b 2 5 √a
5 5 5 5
4a 2 4a 2 8a 2 (1 + ln c) 2
R = − 2 = = ... à maximiser.
3b 2 5b 15b 2 c2
A. Buys (Dpt Informatique) Simulation sur ordinateur 89 / 110
Intro Loi uniforme Tests Loi non uniforme

On dérive par rapport à c :

3 5 3  
0 5(1 + ln c) 2 2(1 + ln c) 2 (1 + ln c) 2 5
R = ... 3
− 3
= − 2(1 + ln c)
2c c c3 2

Comme (1 + ln c) n’est pas un maximum (R = 0), il reste le second

1
facteur et (1 + ln c) = 54 =⇒ ln c = 41 et c = e 4 .
1
Acceptance inconditionnelle : ( vu )2 ≤ 5 − 4u e 4

Cas (2)
La même intégration ne peut pas être faite de façon analytique. Des
tests ont montré que la meilleure valeur de c 0 est approximativement
e 1.35
−1.35
Rejet inconditionnel : ( vu )2 ≥ 4 e u + 1.4

A. Buys (Dpt Informatique) Simulation sur ordinateur 90 / 110

Intro Loi uniforme Tests Loi non uniforme

Rectangles et coins (Marsaglia, 1964)

“Rectangle-wedge-tail method” (Loi normale)

Comme pour la méthode “paire-impaire” appliquée à la loi normale

(somme de fonctions sur des intervalles donnés par les aj ), on va
considérer la distribution voulue comme une somme pondérée de
fonctions
X X
f (x) = pi fi (x) avec pi = 1
i i

On va encore
q se contenter la partie droite de la distribution
2
2 − x2
f (x) = π e
Les fi “difficiles” auront une probabilité pi faible.
Les {fi , i = 1, 15} sont des rectangles → distributions uniformes.

A. Buys (Dpt Informatique) Simulation sur ordinateur 91 / 110

Intro Loi uniforme Tests Loi non uniforme

r 15
1 j 2 − j2 X
pj = f ( ) = e 50 pour 1 ≤ j ≤ 15, pi = 0.9183
5 5 25π
i=1

A. Buys (Dpt Informatique) Simulation sur ordinateur 92 / 110

Intro Loi uniforme Tests Loi non uniforme

On peut générer U suivant une loi uniforme sur [0, 1[ et prendre

1 j −1
X = U +S avec S=
5 5
Les {fi , i = 16, 30} sont des “coins”.

A. Buys (Dpt Informatique) Simulation sur ordinateur 93 / 110

Intro Loi uniforme Tests Loi non uniforme

On va entourer la courbe par 2 droites

Pour x > 1 (i = 21, 30, concavité vers le haut), on joint les deux points
extrêmes et on prend la tangente parallèle.
Pour x < 1,(i = 16, 20, concavité vers le bas), on prend la tangente au
point de droite et sa parallèle qui passe par l’autre point.
On a alors
(x − s) (x − s)
a−b ≤ f (x) ≤b−b
h h
a (x − s)
≤ f ? (x) = b1 f (x) + ≤1
b h
On peut générer U et V suivant une loi uniforme sur [0, 1[ avec
V > U (sinon, on les échange).
Si V ≤ ba , on accepte U, sinon, on teste si V > U + b1 f (s + hU). Si
c’est le cas, on accepte U, sinon, on recommence. A la fin,
X ← s + hU.

A. Buys (Dpt Informatique) Simulation sur ordinateur 94 / 110

Intro Loi uniforme Tests Loi non uniforme

Vérification : Probabilité d’avoir X ≤ s + hx avec 0 ≤ x ≤ 1 (rapport

de la surface à gauche de U = x avec la surface totale) :
Rx 1
R s+hx s+hx
b f (s + hu)du f (t)dt
Z
R01 1 = Rs s+h = f (t)dt
0 b
f (s + hu)du s
f (t)dt s

A. Buys (Dpt Informatique) Simulation sur ordinateur 95 / 110

Intro Loi uniforme Tests Loi non uniforme

f31 est la queue de la distribution (environ une fois sur 370).

Cas général

Soit f (x) une densité de probabilité suivant laquelle on génère des

nombres aléatoires. Soit g (x) une densité de probabilité suivant
laquelle il est facile de génèrer des nombres aléatoires.
Soit f (x) ≤ c g (x) avec c le plus petit possible (c ≥ 1).

L’algorithme suivant va générer des nombres selon f (x):

1 Générer X selon g(x).
f (X )
2 Générer U uniforme dans [0, 1[. Si c g (X )
> U, accepter X , sinon
retourner en (1).
Probabilité de rejeter X quel qu’il soit :
Z +∞  
f (x) 1
dx g (x) 1 − =1−
−∞ c g (x) c

A. Buys (Dpt Informatique) Simulation sur ordinateur 96 / 110

Intro Loi uniforme Tests Loi non uniforme

Probabilité d’accepter X quel qu’il soit : c1

f (x)
Probabilité d’accepter X généré suivant g (x) (2) : c g (x) (probabilité
conditionnelle).
Densité de probabilité de X :
g (X ). c f g(X(X) )
1 = f (x)
c

- Probabilité de générer X (densité)

- Probabilité d’accepter en (2)
Soient
t2
e− 2 t2
f (t) = R 2 et g (t) = a t e − 2
+∞ − u2
3 e du
On doit déterminer a et c.
Z +∞ Z +∞
a +∞ − t 2 2
Z
2 x +∞
h i
− t2
g (t)dt = 1 = a te dt = e 2 dt = a −e − 2
3 3 2 9 9

A. Buys (Dpt Informatique) Simulation sur ordinateur 97 / 110

Intro Loi uniforme Tests Loi non uniforme

9 9−t 2
D’où on tire : a = e 2 , g(t) = t e 2 .
Fonction de répartition G(x) de g(x):
x x2 Z 2
1 9 x −t
Z Z
9−t 2 1 9−t 2
2
G (x) = t e 2 dt = e 2 dt = e 2 e 2 dt
3 9 2 2 9
x2 9−x 2
9
h 9
i
= e 2 −e − 2 + e− 2 = 1 − e 2 = y

9−x 2
On génère
√ alors z = 1 − y = e 2 dans [0, 1[ et on trouve
x = 9 − 2 ln z.
t2 9
f (t) e− 2 e− 2
= hR u2
i 9−t 2
= R +∞ − u2 ≤1
c g (t) c
+∞
e − 2 du t e 2 c t 3 e 2 du
3
9 9
e− 2 e− 2
c ≥ R +∞ u2
⇒ On peut prendre c = R +∞ u2
t 3
e − 2 du 3 3
e − 2 du
f (X ) 3
On accepte alors X si U < c g (X ) = X

A. Buys (Dpt Informatique) Simulation sur ordinateur 98 / 110

Intro Loi uniforme Tests Loi non uniforme

Loi exponentielle - minimisation aléatoire

On a déjà vu une méthode (inversion de la fonction de répartition),
mais on voudrait éviter le logarithme.
2 3 k
Soit Q [k] = ln1!2 + (ln2!2) + (ln3!2) + ... + (lnk!2) (k ≥ 1).
(Q [k] −→ 1 quand k −→ +∞)

En pratique, on s’arrête quand Q [k] > 1 − 21−n pour des mots sur n
bits.

Algorithme
1 Générer un nombre aléatoire suivant la loi uniforme
V = (b0 , b1 , b2 , ...bn ) (en binaire). Soit j le premier bit dans l’état 1
1
(P {j = J} = 2J+1 ). Soit alors U = (bj+1 , ..., bn ).
2 Si U < ln 2, alors X ← µ(j ln 2 + U) et on s’arrête là.
3 Trouver la plus petite valeur de k telle que Q [k] > U, générer k
nombres aléatoires U1 , U2 , ..., Uk . V ← min(U1 , U2 , ..., Uk ).
4 X ← µ(j + V ) ln 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 99 / 110

Intro Loi uniforme Tests Loi non uniforme

Calcul de la fonction de répartition de X

P {X ≤ X0 } = (ln 2)P {µ(j ln 2 + U) ≤ X0 } (2)

+∞
X (ln 2) k
+ P {µ(j + V ) ln 2 ≤ X0 } (4)
k!
k=2
 
U X0
= (ln 2)P j + ≤
ln 2 µ ln 2
+∞ k
 
X (ln 2) X0
+ P (j + V ) ≤
k! µ ln 2
k=2

h i
X0 U X0
Soit X = . Dans (2), < 1. Si
 
j ≤X + −X − lnU2 ⇒ j ≤ X
µ ln 2 ln 2 µ ln 2

 
U X0 
P j+ ≤ = P j <X
ln 2 µ ln 2
  
 U X0
+ P j =X P ≤ −X
ln 2 µ ln 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 100 / 110

Intro Loi uniforme Tests Loi non uniforme

   
U X0 1 1 1 1
P j+ ≤ = + + + ... +
ln 2 µ ln 2 2 22 23 2X
 
1 X0
+ −X
2X +1 µ ln 2
1
− 12 1

X0

2X +1
= 1
+ −X
2 −1 2X +1 µ ln 2
   
1 1 X0
= 1− + −X
2X 2X +1 µ ln 2

De la même manière,
 
X0 
P (j + V ) ≤ = P j <X
µ ln 2
  
 X0
+ P j =X P V ≤ −X
µ ln 2
A. Buys (Dpt Informatique) Simulation sur ordinateur 101 / 110
Intro Loi uniforme Tests Loi non uniforme

   
X0 1
P (j + V ) ≤ = 1−
µ ln 2 2X
 
1 X0
+ P V ≤ −X
2X +1 µ ln 2
   
X0 X0
P V ≤ −X = P min(U1 , U2 , ..., Uk ) ≤ −X
µ ln 2 µ ln 2
 
X0
= 1 − P min(U1 , U2 , ..., Uk ) > −X
µ ln 2
k  
Y X0
= 1− P Ui > −X
µ ln 2
i=1
 k
X0
= 1− 1− +X
µ ln 2

A. Buys (Dpt Informatique) Simulation sur ordinateur 102 / 110

Intro Loi uniforme Tests Loi non uniforme

 +∞
1 X (ln 2)k
  
1
P {X ≤ X0 } = ln 2 1 − + 1−
2X 2X k=2 k!
+∞
(
(ln 2)k

1 X0 X
+ − X ln 2 +
2X +1 µ ln 2 k!
k=2
h ik 
+∞ ln 2 (1 + X ) − X0 
µ
X 
−
k! 
k=2 
  
1 1 X0
= 1− + −X ln 2 + 1 − ln 2
2X 2X +1 µ
h i 
X
ln 2 (1+X )− µ0 X0
− e + 1 + ln 2 (1 + X )−
µ
   
1 1 −
X0 X
− 0
= 1− + 2 − 21+X e µ = 1 − e µ
2X 2X +1
A. Buys (Dpt Informatique) Simulation sur ordinateur 103 / 110
Intro Loi uniforme Tests Loi non uniforme

Divers

Autres lois continues

Permutations
Echantillonnage
Simulations par événements discrets (DES)

A. Buys (Dpt Informatique) Simulation sur ordinateur 104 / 110

Intro Loi uniforme Tests Loi non uniforme

Autres lois continues

Nous avons vu des méthodes pour générer des nombres suivant une loi
uniforme, non uniforme et discrète ou continue (normale,
exponentielle). Il y en a évidemment d’autres.

Z x Z +∞
1 a−1 −t
F (x) = t e dt (x ≥ 0) ; Γ(a) = t a−1 e −t dt
Γ(a) 0 0
Γ(n) = (n − 1)!

Cas particuliers : a = 1 (exponentielle), a = 12 (2 fois un χ21 ) et a = k

correspond à une somme de k exponentielles indépendantes de
moyenne 1.
Si k est grand, générer des exponentielles est lourd mais il y a des
méthodes plus efficaces (cfr. référence).

A. Buys (Dpt Informatique) Simulation sur ordinateur 105 / 110

Intro Loi uniforme Tests Loi non uniforme

Permutations
Soient X1 , X2 , ..., Xn un ensemble d’éléments à mélanger. On pourrait
s’inspirer du test de permutation et générer n valeurs dans [0, 1[ et
donner à chaque Xi la position de la i ème valeur par ordre croissant ou
décroissant dans la séquence générée.

Algorithme d’une autre méthode (plus simple)

1 j ← n.
2 Générer U dans [0, 1[.
3 k ← [jU + 1], Xk ↔ Xj .
4 j ← j − 1. Si j > 1, aller en (2).

A. Buys (Dpt Informatique) Simulation sur ordinateur 106 / 110

Intro Loi uniforme Tests Loi non uniforme

Echantillonnage
On veut extraire n éléments d’un fichier qui en contient N en le
parcourant une seule fois. Chaque élément a une probabilité Nn d’être
pris.
Solution : le (t + 1)ème élément est choisi avec la probabilité n−m
N−t si on
a déjà m éléments.
Sur toutes les manières de choisir n parmi N éléments avec m parmi les
t premiers, il y en a

   
N −t −1 N −t
/
n−m−1 n−m
(N − t − 1)!(N − t − n + m)!(n − m)!
=
(N − t)!(N − t − 1 − n + m + 1)!(n − m − 1)!
n−m
=
N −t

avec le (t + 1)ème élément choisi.

A. Buys (Dpt Informatique) Simulation sur ordinateur 107 / 110

Intro Loi uniforme Tests Loi non uniforme

Simulations par événements discrets (DES)

Système à événements discrets = Système dont l’état change de façon
discontinue en un certain nombre d’instants qui peuvent être aléatoires.

Guichets d’un bureau de poste, chaı̂nes de montage

Pas le système circulatoire sanguin du postier
La DES traite de la modélisation de ces systèmes.
Dans la simulation (en fonction des objectifs), certains éléments seront
pris en compte, d’autres pas. On rencontre des éléments de types
suivants:
Des clients (clients du bureau de poste, automobiles)
Des ressources (éléments du système qui offrent un service, les postiers,
les ouvriers)
Des éléments de contrôle (heure d’ouverture, pause de midi)
Des opérations par ou sur les entités (traitement d’un client par un
postier, peinture des portes)
Des unités de stockage (les files d’attente, la réserve de rétroviseurs)
Des unités de transport (tapis roulant)
...

A. Buys (Dpt Informatique) Simulation sur ordinateur 108 / 110

Intro Loi uniforme Tests Loi non uniforme

Différentes approches existent, par

activité (intervalle de temps pendant lequel l’état d’une ressource ne
change pas)
événement (instant précis de l’état de changement d’une ressource)
processus (succession d’un nombre fini d’états d’une ressource)
Gestion des événements
Dans l’ordre chronologique
Horloge propre par entité ou ordonnanceur (échéancier)
Liste d’événements à simuler
Lois de probabilité (arrivées de clients poissoniennes ? temps de
traitement par le postier gaussien ?)
Gestion des files d’attente
Probablement FIFO pour les clients
Peut-être LIFO pour les pièces d’automobile
Utilisation des résultats
Régime stationnaire - régime transitoire (e.g. réaction à une
perturbation)

A. Buys (Dpt Informatique) Simulation sur ordinateur 109 / 110

Intro Loi uniforme Tests Loi non uniforme

Ordonnancement - structures de données

Files de priorité
Représentation par tas
Temps de recherche, d’insertion et de suppression courts
Arbres binaires
Arbres binaires “équilibrés”
Arbres binaires “gauchers” (leftist binary trees/leftist heaps)

A. Buys (Dpt Informatique) Simulation sur ordinateur 110 / 110