Méthodes de Simulation

Youssef, Bennani

Séances 1 et 2
14 avril 2025
Objectifs de ce cours

1. Méthode de Bootrstrap

2. Génération de variables aléatoires

3. Intégration de Monte Carlo

4. Control de la convergence

5. Optimisation

6. Introduction aux algorithmes de Metropolis-hastings

7. Introduction aux échantillonneurs de Gibbs

Qu’est-ce que le ”hasard”?

▶ Le hasard : une expérience, l’interprétation de ce qui nous est

advenu à un moment donné.
▶ Quelque chose est intervenu, que nous avons pu identifier ou
non, mais que nous n’avions pas pris en compte, et qui a
modifié le cours que nous avions prévu.
▶ Nous appelons ”fortuit” l’élément interruptif qui a déjoué
notre prévision.
▶ Mais cet aspect ”fortuit” n’est qu’une illusion qui masque
notre ignorance.
▶ Rien ne se produit vraiment au hasard ou fortuitement; tout a
une cause, que nous choisissons de rechercher ou d’ignorer.
▶ Depuis longtemps, la science occidentale a adopté cette vérité
en tant que dogme.
Qu’est-ce que le ”hasard”?

▶ Pierre-Simon Laplace l’exprime dans son introduction à la

Théorie Analytique des Probabilités, parue en 1829:
”Une intelligence qui pour un instant donné, connaı̂trait
toutes les forces dont la nature est animée, et la situation
respective des êtres qui la composent, si d’ailleurs elle était
assez vaste pour soumettre ces données à l’analyse,
embrasserait dans la même formule, les mouvements des plus
grands corps de l’univers et ceux du plus léger atome: rien ne
serait incertain pour elle, et l’avenir comme le passé serait
présent à ses yeux.”
▶ C’est dans ce contexte que nous tentons de cerner divers
concepts liés à la notion de variable aléatoire.
Qu’est-ce que le ”hasard”?
▶ On trouve partout des phénomènes présentant une part
d’imprévisible.
▶ Lancez une pièce de monnaie en l’air: sur quelle face
retombera-t-elle?
▶ Mariez deux jeunes personnes: combien d’années vivront-elles
ensemble?
▶ Prescrivez de l’antibiotique à 100 patients atteints d’une
même infection microbienne: combien et lesquels s’en
sortiront?
▶ Ce sont tous des phénomènes dits stochastiques, que nous ne
pouvons prédire exactement.
▶ Les modèles qui sont mis au point pour étudier ces
phénomènes sont des modèles stochastiques.
▶ Par contraste avec les modèles plus classiques en physiques,
l’opération d’un modèle stochastique intègre des éléments de
fluctuation qui représentent notre part d’ignorance.
Qu’est-ce que le ”hasard”?
▶ L’objet d’étude principal des méthodes de simulation est les
phénomènes stochastiques.
▶ L’étude du phénomène se fait par la mesure du comportement
du modèle associé.
▶ Même s’il présente des aspects aléatoires, on peut décrire le
phénomène en question, d’établir des régularités, de fixer
certaines caractéristiques à travers les mesures.
▶ Pour la plupart des phénomènes, leur complexité commande
que l’on s’intéresse à plusieurs mesures.
▶ C’est cette mesure d’un phénomène qu’on désigne sous le
nom de ”variable aléatoire”
▶ C’est une quantité susceptible de présenter des valeurs
différentes, et elle est ”aléatoire” en ce sens qu’elle redonne
les mesures présumément changeantes d’un phénomène
stochastique.
Le méthode de Bootstrap
▶ Le bootstrap est une procédure statistique de
rééchantillonnage.
▶ Elle a de nombreuses applications en statistique.
▶ Elle se fonde sur le fait que la distribution empirique d’un
échantillon X1 , · · · , Xn converge avec n vers la distribution
véritable. (La distribution empirique est une loi discrète qui
met un poids de 1/n en chaque point Xi de l’échantillon et 0
partout ailleurs.)
▶ L’idée de base du bootstrap est d’utiliser cette distribution
empirique comme substitut de la distribution véritable pour en
déduire des estimateurs de la variance et des intervalles de
confiance pour les quantités d’intérêt.
▶ Du fait du support fini mais très grand de la loi d’un
échantillon tiré de la loi empirique, puisque ce support
comprend nn points, des approximations sont nécessaires pour
évaluer toute espérance suivant cette loi.
Une méthode pour estimer la variance d’un échantillon
▶ Soit Tn = g(X1 , · · · , Xn ) une statistique (n’importe quelle
fonction des données).
▶ Supposons que nous voulions connaı̂tre VF (Tn ), la variance de
Tn (On écrit VF car la variance dépend généralement de la
distribution inconnue F ).
▶ Le bootstrap se base sur deux étapes :
1. Estimer VF (Tn ) par VFbn (Tn ) .
2. Simuler une approximation de VFbn (Tn ) .
▶ Exemple : Si Tn = X n , alors VF (Tn ) = σ 2 /n où
σ 2 = (x − µ)2 dF (x) et µ = xdF (x).
R R

b2 = n−1 ni=1 (Xi − X n ).

b2 /n, avec σ
▶ Donc on a VFb(T ) = σ
P
n
▶ Dans ce cas l’étape 1 suffit.
▶ Dans d’autres cas où l’on peut pas écrire une formule simple
pour VFbn (Tn ) , on passe par l’étape de simulation (étape 2).
Simulation
▶ Soit Y1 , · · · , YB i.i.d. tirées selon une distribution G.
▶ Lorsque B → ∞ (loi des grands nombre):

B Z
1 X P
Yn = Yj → ydG(y) = E(Y ).
B
j=1

▶ Ainsi, si nous tirons un grand échantillon selon la loi G, nous

pouvons utiliser la moyenne de l’échantillon Y n pour
approximer E(Y ).
▶ Plus généralement, si h est une fonction de moyenne finie
alors lorsque B → ∞:
B Z
1 X P
h(Yj ) → h(y)dG(y) = E(h(Y ))
B
j=1
Simulation

▶ En particulier :
 2
B B B
1 X 1 X 1 X
(Yj − Y )2 = Yj2 −  Yj 
B B B
j=1 j=1 j=1
Z Z 2
P 2
−→ y dF (y) − ydF (y) = V(Y )

▶ Par conséquent, nous pouvons utiliser la variance d’échantillon

des valeurs simulées pour approximer V(Y ).
Estimation de la variance

▶ Donc nous pouvons approximer VFb (T ) par simulation.

n n
▶ Or, VFb (T ) signifie ”la variance de Tn si la distribution des
n n

données est Fbn ”.

▶ Comment pouvons-nous simuler à partir de la distribution de
Tn lorsque les données sont supposées avoir une distribution
Fbn ?
▶ La réponse est de simuler X1∗ , · · · , Xn∗ à partir de Fbn puis
calculer Tn∗ = g(X1∗ , · · · , Xn∗ ).
▶ Ceci constitue un tirage de la distribution de Tn .
▶ L’idée est illustrée dans le schéma suivant :

monde réel : F ⇒ X1 , · · · , Xn ⇒ Tn = g(X1 , · · · , Xn )

bootstrap : Fbn ⇒ X1∗ , · · · , Xn∗ ⇒ Tn∗ = g(X1∗ , · · · , Xn∗ )
Estimation de la variance

▶ Comment simuler X1∗ , · · · , Xn∗ à partir de Fbn ?

▶ Fbn met la masse de probabilité 1/n pour chaque observation
Xi .
▶ On note alors que tirer une observation à partir de Fbn
équivaut à tirer un point au hasard dans l’ensemble de
données d’origine.
▶ Ainsi, pour simuler X1∗ , · · · , Xn∗ ∼ Fbn , il suffit de tirer n
observations avec remplacement de X1 , · · · , Xn .
Estimation de la variance

Voici un résumé de l’estimation de la variance par bootstrap:

1. Tirer X1∗ , · · · , Xn∗ ∼ Fbn .

2. Calculer Tn∗ = g(X1∗ , · · · , Xn∗ ).
∗ ,··· ,T∗ .
3. Répéter les étape 1 et 2, B fois, pour avoir Tn,1 n,B
4. Calculer
B B
!2
1 X ∗ 1 X ∗
vboot = Tn,b − Tn,r .
B B
b=1 r=1
Estimation de la variance

Exemple : Le pseudo code suivant montre comment utiliser le

bootstrap pour estimer l’erreur-type de la médiane:

T = médiane(X)
Tboot = vecteur de longueur B
pour (i dans 1:B)
Xstar = échantillon de taille n de X
(avec remplacement)
Tboot[i] = médiane (Xstar)
se = sqrt(variance(Tboot))
Estimation de la variance

Exemple :
▶ On considère le coefficient d’asymétrie
Z
θ = T (F ) = (x − µ)3 dF (x)/σ 3

▶ L’estimateur pulg-in de l’asymétrie est :

1 Pn 3
(x − µ)3 dFbn (x)
R
n i=1 (Xi − Xn )
θ = T (Fn ) =
b b = .
b3
σ b3
σ
▶ Pour estimer l’erreur-type avec le bootstrap, nous suivons les
mêmes étapes qu’avec l’exemple de la médiane, sauf que nous
calculons l’asymétrie à partir de chaque échantillon bootstrap.
Intervalles de confiance

▶ Il existe plusieurs façons pour construire des intervalles de

confiance bootstrap.

▶ Nous discutons ici de trois méthodes:

1. l’intervalle normal

2. les intervalles pivots

3. méthode de Jacknife
Intervalles de confiance : l’intervalle normal

▶ La méthode la plus simple est :

Tn ± zα/2 se
b boot ,
√
avec se
b boot = vboot est l’estimation bootstrap de l’erreur
type.
▶ Cet intervalle n’est précis que si la distribution de Tn est
proche de la normale.
Intervalles de confiance : les intervalles pivots
▶ Soit θ = T (F ) et θbn = T (Fbn ).
▶ On définit le pivot : Rn = θbn − θ.
∗ ,··· ,θ
▶ Soient θbn,1 b∗ les répliques de θbn par bootstrap.
n,B
▶ Soit H(r) la FCD du pivot :

H(r) = PF (Rn ≤ r).

▶ On définit Cn∗ = (a, b) où

 α α
a = θbn − H −1 1 − et b = θbn − H −1
2 2
▶ On peut vérifier que :

P(a ≤ θ ≤ b) = P(θbn − b ≤ Rn ≤ θbn − a)

= H(θbn − a) − H(θbn − b)
=1−α
Intervalles de confiance : les intervalles pivots

▶ a et b dépendent de la distribution inconnue de H.

▶ Mais on peut construire une estimation par bootstrap de la
distribution H:
B
1 X ∗
H(r) =
b I(Rn,b ≤ r),
B
b=1

∗ =θ
où Rn,b b∗ − θbn .
n,b
▶ Soit rβ∗ le β-ième quantile échantillonné de (Rn,1
∗ , · · · , R∗ )
n,B
et θ∗ le β-ième quantile échantillonné de (θb∗ , · · · , θb∗ ).
β n,1 n,B
▶ On remarque que rβ∗ = θβ∗ − θbn .
Intervalles de confiance : les intervalles pivots
▶ On déduit une approximation de l’intervalle de confiance à
1 − α est Cn = (ba, bb) avec:

b −1 1 − α ∗ ∗


a = θbn − H
b 2 = θbn − r1−α/2 = 2θbn − θ1−α/2
b −1 α ∗ ∗ .


bb = θbn − H = θbn − rα/2 = 2θbn − θα/2
2

▶ En résumé, l’intervalle de confiance pivot du bootstrap à

1 − α est :
 
∗ ∗
Cn = 2θbn − θ1−α/2 , 2θbn − θα/2 .

▶ Théorème : Sous certaines conditions faibles sur T (F ),

PF (T (F ) ∈ Cn ) → 1 − α,

lorsque n → ∞.
Intervalles de confiance : Jacknife

▶ Les intervalles de Jacknife (ou intervalles percentiles) sont

définis par :  
∗ ∗
Cn = θα/2 , θ1−α/2 .
▶ Soit Tn = T (X1 , · · · , Xn ) une statistique.
▶ T(−i) indique la statistique appliquée à l’échantillon en
écartant la i-ème observation.
▶ Soit T n = n−1 ni=1 T(−i) .
P

▶ L’estimation de V(Tn ) par Jacknife est donnée par:

n
n−1X
vjack = (T(−i) − T n )2 ,
n
i=1
√
et l’estimation de l’erreur-type est se
b jack = vjack .
Intervalles de confiance : Jacknife

▶ Sous certaine conditions sur T , on peut montrer que vjack est

un estimateur consistent de V(Tn ) dans le sens où
p
vjack /V(Tn ) → 1.
▶ Cependant, contrairement au bootstrap, le jackknife ne
produit pas d’estimations consistantes de l’erreur-type des
quantiles d’échantillon.
Génération de v.a. : Simulation d’une loi uniforme
▶ Les méthodes de simulation reposent toutes sur la capacité à
produire une suite de variables aléatoires indépendantes
suivant une distribution f donnée.
▶ La production d’une telle suite dépend elle-même de la
capacité que l’on a à produire une séquence de variables
aléatoires uniformes et indépendantes.
▶ En pratique, la production par des moyens informatiques d’une
suite de variables uniformes i.i.d. est impossible
▶ toute suite de nombres résulte de la mise en œuvre d’un
algorithme, et par conséquent est déterministe.
▶ L’objectif que l’on s’assigne n’est donc pas la production de
véritables variables aléatoires, mais la production de séquences
déterministes imitant le mieux possible le comportement d’une
suite de variables aléatoires uniformes i.i.d. : on parle de
nombres pseudo-aléatoires.
Génération de v.a. : Simulation d’une loi uniforme
▶ L’utilisation de tout algorithme destiné à produire des suites
de nombres aléatoires uniformément répartis sur [0, 1] doit
donc être validée par la mise en œuvre de tests statistiques
dont l’hypothèse nulle H0 est :
H0 : U1 , U2 , · · · , UN sont i.i.d. de loi uniforme sur [0, 1].
▶ On peut pour cela considérer des tests classiques d’adéquation
à une loi donnée (test du Khi-deux, test de
Kolmogorov-Smirnov, test de Cramer-von Mises) ou tout
autre type de tests reposant sur H0.
▶ On peut par exemple utiliser les tests de la batterie Diehard.
▶ Dans la pratique, un générateur de nombres pseudo-aléatoire
peut sembler correct car validé par un ensemble de tests, mais
il est toujours possible de construire un nouveau test
invalidant l’hypothèse d’uniformité.
▶ Il convient donc d’être pragmatique lors du choix d’un
générateur de nombres pseudo-aléatoire : ce choix doit tenir
compte des caractéristiques de l’application envisagée.
Génération de v.a. : Simulation d’une loi uniforme

▶ Nous nous intéressons dans un premier temps aux générateurs

congruentiels linéaires.
▶ Ce type de générateur est fréquemment rencontré car :
1. sa mise en œuvre est très simple
2. il présente des propriétés statistiques satisfaisantes pour la
plupart des applications classiques.
▶ Dans un deuxième temps, nous exposons quelques exemples
de tests statistiques pouvant être menés pour valider
l’utilisation d’un générateur de nombres pseudo-aléatoires.
▶ La troisième partie de cette section présente succinctement
une autre méthode permettant de simuler une suite de
nombre pseudo-aléatoires.
Générateurs congruentiels linéaires

▶ On se propose d’étudier les principales caractéristiques des

générateurs congruentiels linéaires.
▶ Ce type de générateur produit des suites de nombres
pseudo-aléatoires sur [0, 1] à partir de l’algorithme suivant :
Algorithme :
▶ Etant donnés deux paramètres entiers A et M ,
1. Choisir une racine x0
2. à l’étape n > 0, construire xn = Axn−1 [M ] et retourner
un = xMn
▶ Ce type de générateur est périodique, de période P
strictement inférieure à M .
▶ Si l’on souhaite s’approcher le plus possible d’une distribution
continue uniforme sur [0, 1], il convient donc de choisir A et
M de sorte que la période P soit la plus grande possible.
Choix des paramètres A et M
▶ Dans le cas où M est un nombre premier, le choix de A
repose sur le résultat suivant : Théorème : Si M est un
nombre premier, alors la suite xn , n ≥ 0, obtenue à partir de
l’algorithme précédant est de période M − 1 si et seulement si
A est une racine primitive de M :
AM −1 = 1[M ] et Ak−1 ̸= 1[M ] ∀k < M
▶ Dans la mesure où un générateur de nombres
pseudo-aléatoires est très fréquemment appelé au cours d’une
expérience de simulation, un autre critère intervenant dans le
choix de M est le temps de calcul qu’il induit pour chaque
élément de la suite (un) produite par l’algorithme.
▶ La représentation interne des nombres sous la forme de
séquences binaires conduit à s’intéresser aux paramètres M
s’écrivant sous la forme M = 2β :
▶ la division modulo M consiste alors à mettre à 0 l’ensemble
des bits de rang supérieur à β;
▶ la division par M est réalisée en décalant le bit représentatif de
la virgule de β bits vers la gauche.