Difference entre suite de variable aléatoire et quasi-aléatoire

Télécharger le fichier original (Mémoire de fin d’études)

Méthode de production de variable aléatoire et d’échantillonnag

Générateur de nombre aléatoire

Les nombres générés par les ordinateurs ne sont pas aléatoires mais pseudo-aléatoires ; ce qui signifie qu’ils sont faits pour avoir un grand nombre de propriétés de suite de nombres aléatoires. Alors que c’est un sujet bien développé, il y a des problèmes qui se produisent occassionelement, la plupart du temps avec de très longues séquences (N 109).
Les méthodes utilisées pour générer des nombres pseudo-aléatoires sont essen-tiellement des méthodes de congruences linéaire. Il y a une série de générateur de nombres pseudo-aléatoires fiables dans [12].
Pour les très grandes problèmes nécessitant de très grande valeur de N (aussi élevées que 1013), des séquences fiables peuvent être obtenues à partir de [15].
On va donner un exemple de méthode de génération des variables aléatoires par congruences linéaires donné par la relation qui suit.
Xn+1 (aXn + b) mod m
avec a; b; m sont des entiers positifs. Le modulo m implique que les séries générées soient périodiques . Il existe au plus (pas forcement exactement) m valeurs possibles diﬀérentes générées par le procédé. Il faut donc faire attention au choix de la valeur
CHAPITRE 1. METHODE DE MONTE CARLO 11
m. Comme par exemple si a = b = x0 = 3 et m = 5 alors la séquence obtenue a pour valeur : 3; 2; 4; 0.
Les valeurs qu’on obtient n’est pas encore dans l’intervalle [0; 1]. Pour l’obtenir, il suﬃt de diviser les nombres généré par m.

Méthodes d’échantillonnages

Les générateurs standard de nombres pseudo-aléatoires produisent des variables uniformément réparties sur un intervalle considéré. Les variables non-uniformes peuvent êtres échantillonnées par la transformation en variables uniformes.
Pour une variable aléatoire non- uniforme avec une densité de probabilité p(x), l’espérance d’une fonction f(x) est :
Z
E(f) = I(f) = f(x)p(x)dx (1.15)
I
avec I un intervalle où x est définie.
Pour une suite de nombres aléatoires (xn) distribuée avec la densité p, l’approxima-tion empirique de l’espérance est :
IN (f) = 1 N f(xn) (1.16)
X
N n=1
avec une erreur quadratique résultante :
« N [f] = I(f) IN (f) (1.17)
Comme dans le premier cas,
L 1 ; d’après le théorème central limite (1.18)
« N [f] ! N 2
où est une variable aléatoire qui suit la loi normale centrée réduite et
2 = ZI (f f)2p(x)dx (1.19)
Par la suite, on va voir comment transformer une variable aléatoire uniforme en une variable aléatoire de densité quelconque.
Procédé de transformation
Ceci est la méthode générale pour produire une variable aléatoire x de densité p(x) par l’intermédiaire de transformation de variable aléatoire uniforme.
Soit y une variable aléatoire uniforme . On cherche une fonction X(y) qui a la densité p(x) souhaitée.
On définit alors la fonction de répartition
Z x
P (x) = p(x0)dx0 (1.20)
La détermination de X(y) se fait par le calcul suivant :
Ep[f(x)] = Eu[f(X(y))] (1.21)
où Eu l’espérance associé à la loi uniforme et Ep l’espérance associé à la densité p. On peut donc utiliser un changement de variable
ZI f(x)p(x)dx = Z 1 f(X(Y ))dy = Z 0 1 f(x)dxdx (1.22)
0
dy
On a alors : dy 1
p(x) = =
dx X0(y)
Ceci implique que :
Z X(y) Z X(y) dy
p(x)dx = dx = y = P (X(y))
dx
donc 1(y) (1.23)
X(y) = P
Cette formulation est pratique et explicite mais n’est pas nécessairement facile a mettre en oeuvre , car la fonction inverse de la fonction de répartition peut être diﬃcile à calculer.
Maintenant, on va donner un exemple de transformation de variable aléatoire qui est la variable aléatoire gaussienne.

Variable aléatoire gaussienne

Comme exemple de procédé de transformation, la variable aléatoire gaussienne(normale centrée réduite) de densité p et de fonction de répartition P donné par :
1 x2 (1.24)
p(x) = (2 ) exp( )
2
2
1 Z x t2 (1.25)
P (x) = p exp( )dt
2
2
On définit alors la fonction d’erreur p Z0
erf(z) = z t2)dt
exp(
Donc, en eﬀectuant un changement de variable X = pt2 , on a :
Z x Z 0 Z x
1 p 1 1 p
2 2
P (x) = p exp( X2)dX = p exp( X2)dX + p exp( X2)dX
0
Or x
1 p 1 x
2
p Z0 exp( X2)dX = erf( p );
2
2
et Z 0 exp( X2)dX = Z + 1 y 2 exp( y)dy
1
0
= 12) = p
Ainsi 1 1 x
(1.26)
P (x) = + erf( p )
2 2
2
Pour échantillonner la variable aléatoire gaussienne en une variable aléatoire uni-forme y, on doit chercher la fonction inverse de la fonction de répartition P (x) .
On a alors : 1 + erf(p 2 ) (1.27)
y = P (x) = 2
1 x
et son inverse est p (1.28)
1(2y 1)
x = 2 erf
Les formules approximatives pour erf 1 ou P 1(y) se trouve dans [5]. Mais on va donner une exemple d’ approximation de P 1(y) car cela peut être utile. Cette formule est appelée la formule de Beasley Springer :
1P 3 ak(y 1 )2k+1
P 1 2 pour 0; 5 < y < 0; 92
k=0 k( 2 ) 2k
(y) ’ k=0 3 1
P
+ b y
Les coeﬃcients ak et bk sont donnés ci-dessous :
a0 = 2:50662823884 ; a1 = 18:61500062529; a2 = 41:39119773534 ; a3 = 25:44106049637
b0 = 8:47351093090 ; b1 = 23:08336743743 ; b2 = 21:06224101826 ; b3 = 3:13082909833
Pour une variable aléatoire gaussienne , ainsi que pour certain nombre de variable aléatoire, une transformation spéciale est une alternative utile pour la méthode générale de transformation. La méthode de Box-Muller est la plus simple de tout celà . Elle fournit un moyen direct de générer des variables aléatoires sans inverser la fonction d’erreur.
La méthode de Box-Muller consiste à avoir deux variables aléatoires normales x1 et x2 à partir de deux variables aléatoires uniformes y1 et y2 .

Table des matières

0 PRÉLIMINAIRES
0.1 Rappel de statistique
0.2 Rappel de probabilité
1 METHODE DE MONTE CARLO
1.1 Principe général :
1.2 La précision de Monté Carlo
1.3 Méthode de production de variable aléatoire et d’échantillonnage
1.3.1 Générateur de nombre aléatoire
1.3.2 Méthodes d’échantillonnages
1.3.3 Procédé de transformation
1.3.4 Variable aléatoire gaussienne
1.3.5 Méthode d’acceptation-rejet
1.4 Réduction des variances
1.4.1 Méthode de Variables Antithétiques
1.4.2 Variables Aléatoires de Contrôle
1.4.3 Méthode des moments correspondants
1.4.4 Méthode par stratification
1.4.5 Echantillonnage préférentiel
1.4.6 Exemple de la réduction de la variance
2 METHODE DE QUASI-MONTE CARLO
2.1 Nombres quasi-aléatoires
2.1.1 Difference entre suite de variable aléatoire et quasi-aléatoire
2.1.2 Discrépance
2.1.3 Inégalité de Koksma-Hlawka
2.1.4 Erreur quadratique moyenne
2.2 Générateur des nombres quasi-aléatoires
2.2.1 Suite de Van der Corput
2.2.2 Généralisation de la suite de Van der Corput
2.2.3 Suite de Halton
2.2.4 Suite de Hammersley
2.3 Limite de la Methode de quasi-Monte Carlo
TABLE DES MATIÈRES
3 CONCLUSION
4 Annexe
Bibliographie