0% ont trouvé ce document utile (0 vote)

26 vues57 pages

Cours Quant If

Ce document présente des méthodes de quantification optimale et leurs applications en finance, en se concentrant sur la quantification vectorielle des lois de probabilité. Il aborde des concepts tels que la mosaïque de Voronoi, les algorithmes de recherche de quantifieurs optimaux, ainsi que des applications pratiques dans le calcul d'options européennes et américaines. Le texte inclut également des sections sur le filtrage et l'approximation par quantification.

Transféré par

lecoeur59

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

26 vues57 pages

Cours Quant If

Transféré par

lecoeur59

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Méthodes de quantification optimale

et Applications en Finance

Huyên PHAM
Université Paris 7
Laboratoire de Probabilités et
Modèles aléatoires, CNRS UMR 7599
pham@[Link]

Version : 2006-2007.

Master 2ème année, Paris 7, Statistique et Modèles Aléatoires en Economie et

Finance
Table des matières

Préface 3

1 Quantification vectorielle d’une loi de probabilité 4

1.1 Mosaique de Voronoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Quantification de Voronoi et distorsion optimale . . . . . . . . . . . . . 7
1.3 Asymptotique de l’erreur de quantification . . . . . . . . . . . . . . . . . 12
1.4 Algorithmes de recherche d’un quantifieur optimal de Voronoi . . . . . . 14
1.4.1 Méthode du point fixe de Lloyd (en dimension 1) . . . . . . . . . 14
1.4.2 Méthode du gradient déterministe (en dimension 1) . . . . . . . 15
1.4.3 Méthode du gradient stochastique : algorithme de Kohonen . . . 18
1.5 Application à l’intégration numérique et aux options européennes . . . . 23

2 Quantification d’une chaine de Markov et applications 26

2.1 Quantification marginale . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.1.3 Quantification optimale . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Application à l’arrêt optimal et aux options américaines . . . . . . . . . 31

3 Filtrage et quantification 35
3.1 Filtrage linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Rappel sur les variables gaussiennes . . . . . . . . . . . . . . . . 35
3.1.2 Filtre de Kalman-Bucy . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Filtrage non linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.1 Description du modèle . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.2 Equation du filtre . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.3 Approximation par quantification . . . . . . . . . . . . . . . . . . 46
3.3 Applications et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Application : Valorisation d’options européennes en information
partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

1
TABLE DES MATIÈRES 2

3.3.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Bibliographie 55
Préface

Le terme “quantification” a ses origines en théorie du signal et de l’information et

était utilisé par les ingénieurs depuis les années 50. Dans ce contexte, la quantification
signifie la discrétisation d’un signal continu par un nombre fini N de codes (ou quan-
tifieurs). Pour permettre une transmission efficiente du signal, il est donc primordial
d’optimiser la location géométrique de ces codes et d’évaluer l’erreur résultante. C’est
le problème mathématique dit de la quantification optimale : trouver la meilleure ap-
proximation d’une loi de probabilité continue par une loi de probabilité discrète avec
un nombre donné N de points supportant cette loi. D’un point de vue numérique, la
quantification optimale est longtemps restée limitée au cas de signals unidimensionnels
car les procédures d’optimisation, essentiellement déterministes, devenaient trop lourds
en dimension supérieure. Grâce à l’évolution et la puissance des ordinateurs permet-
tant une réduction drastique des temps de calcul par les méthodes de Monte-Carlo,
les méthodes de quantification optimale ont été récemment réétudiés dans le domaine
des probabilités numériques et plus particulièrement dans les applications en finance
où intervient naturellement des questions de grande dimension.
Ce cours est une introduction aux méthodes de quantification optimale avec en vue
les applications en finance. On commence par exposer les fondements mathématiques de
la quantification quadratique. On développera ensuite les algorithmes de recherche d’un
quantifieur optimal et on donnera plusieurs applications en finance : calcul d’options
européennes et d’options américaines. On étudiera aussi le filtrage et les méthodes
d’approximation par quantification, avec comme applications les modèles à volatilité
stochastique.

3
Chapitre 1

Quantification vectorielle d’une

loi de probabilité

Dans la suite, |.| est la norme euclidienne sur Rd et on note (.|.) ou parfois . le produit
scalaire associé. L’intérieur d’une partie A de Rd est notée int(A) et son adhérence
Adh(A). On note ]A le cardinal d’un ensemble A de Rd et 1A la fonction indicatrice de
A. Etant donné un espace de probabilité (Ω, A, P), on note L2 (Ω, P; Rd ) l’ensemble des
variables aléatoires X à valeurs dans Rd telles que E|X|2 < +∞ et on note kXk2 =
1
E|X|2 2 . On notera aussi PX la loi de probabilité de X et λd la mesure de Lebesgue de
Rd . On note Supp(µ) le support topologique d’une mesure µ sur Rd et Conv(Supp(µ))
son enveloppe convexe fermée.

1.1 Mosaique de Voronoi

Soit x = (x1 , . . . , xN ) un N -uplet de points xi dans Rd qu’on identifiera souvent
avec la grille (partie finie) {x1 , . . . , xN } de N points dans Rd . La famille d’ensembles
de Rd définis par :

d
C̄i (x) = u ∈ R : |u − xi | = min |u − xj | , i = 1, . . . , N,
j=1,...,N

est appelée mosaique (ou diagramme) de Voronoi de x. Les C̄i (x), i = 1, . . . , N , sont les
cellules fermées de Voronoi engendrées par x. Ainsi, C̄i (x) consiste en tous les points
u de Rd tels que xi est le plus proche de u parmi les points xj de x ; voir figure 1.1.

Il est clair qu’une mosaique de Voronoi couvre Rd , i.e.

∪N d
i=1 C̄i (x) = R ,

4
QUANTIFICATION VECTORIELLE 5

Fig. 1.1 – Une mosaique de Voronoi dans R2 avec N = 500 points..

et que les cellules de Voronoi C̄i (x) sont fermées dans Rd . On introduit aussi les cellules
ouvertes de Voronoi dans Rd :

o d
Ci (x) = u ∈ R : |u − xi | < min |u − xj | , i = 1, . . . , N,
xj 6=xi

qui sont clairement ouvertes dans Rd et disjointes deux à deux mais ne couvrent pas
Rd . On appelle partition de Voronoi de x toute partition Ci (x), i = 1, . . . , N , de Rd ,
i.e. ∪N d
i=1 Ci (x) = R et Ci (x) ∩ Cj (x) = ∅ si xi 6= xj , telle que :

Ci (x) ⊂ C̄i (x), i = 1, . . . , N. (1.1)

Notons qu’on a alors aussi

Cio (x) ⊂ Ci (x), i = 1, . . . , N. (1.2)

Nous montrons d’abord quelques propriétés intuitives sur les cellules de Voronoi.

Proposition 1.1.1 Les cellules de Voronoi vérifient

(a) C̄i (x) et Cio (x) sont convexes dans Rd .
(b) int(C̄i (x)) = Cio (x), Adh(Cio (x)) = C̄i (x), ∂Ci (x) = ∂ C̄i (x) = ∂Cio (x).
(c) λd (∂Ci (x)) = 0.

Preuve. (a) On définit le demi-espace médian entre xi et xj par :

n o
Hij (x) = u ∈ Rd : |u − xi | ≤ |u − xj | ,

et l’hyperplan séparateur entre xi et xj :

n o
Sij (x) = u ∈ Rd : |u − xi | = |u − xj | .
QUANTIFICATION VECTORIELLE 6

On a donc par définition

C̄i (x) = ∩N
j=1 Hij (x). (1.3)

En notant que par définition de la norme euclidienne, on a

d 1
Hij (x) = u ∈ R : xi − xj | u − (xi + xj ) ≥ 0 ,
2

il est clair que Hij (x) est convexe et donc aussi C̄i (x) d’après (1.3). De même, en
écrivant que
n o
Cio (x) = ∩xj 6=xi u ∈ Rd : |u − xi | < |u − xj |

1
= ∩xj 6=xi u ∈ Rd : xi − xj | u − (xi + xj ) > 0 ,
2
on a la convexité de Cio (x).
(b) Vérifions que pour tout xj 6= xi , λ ∈ ]0, 1[ et u ∈ Hij (x), on a
n o
λu + (1 − λ)xi ∈ v ∈ Rd : |v − xi | < |v − xj | . (1.4)

En effet, posons v = λu + (1 − λ)xi , i.e. v − xi = λ(u − xi ). v est dans Hij (x) par
convexité de cet ensemble. Supposons alors par l’absurde que |v − xi | = |v − xj |. Alors,
en utilisant le fait que pour tous vecteurs x 6= y avec |x| = |y|, on a |(1 − λ)x + λy| <
|x|, on en déduit :
1 1
|u − xj | = (v − xi ) − (xj − xi ) = |v − xi − λ(xj − xi )|
λ λ
1
= |(1 − λ)(v − xi ) + λ(v − xj )|
λ
1
< |v − xi | = |u − xi | ≤ |u − xj |,
λ
qui est la contradiction voulue.
? D’après (1.3), on a int(C̄i (x)) = ∩N
j=1 int(Hij (x)) et donc pour obtenir int(C̄i (x)) =
o
Ci (x), on doit montrer que pour tout xj 6= xi
n o
int(Hij (x)) ⊂ u ∈ Rd : |u − xi | < |u − xj | .

Soit u ∈ int(Hij (x)) et ε > 0 tel que B(u, ε) ⊂ Hij (x). Si u = xi , on a trivialement
|u − xi | < |u − xj |. Sinon, on pose t = 1 + ε/|u − xi | et w = xi + t(u − xi ). Alors on a :

|w − u| = |(t − 1)u − (t − 1)xi | = ε,

ce qui implique w ∈ Hij (x). Comme u = 1t w + (1 − 1t )xi avec 1/t < 1, on a d’après
(1.4) |u − xi | < |u − xj |.
QUANTIFICATION VECTORIELLE 7

? Soit u ∈ C̄i (x). Alors d’après (1.3), u ∈ Hij (x) pour tout j. Considérons la suite
un = (1 − 1/n)u + 1/nxi , n ≥ 1. D’après (1.4), on a pour tout xj 6= xi , |un − xi | <
|un − xj |, i.e. un ∈ Cio (x). Comme la suite (un )n converge vers u, ceci prouve que u ∈
Adh(Cio (x)) et donc C̄i (x) = Adh(Cio (x)).
? La dernière relation de l’assertion (a) découle de la définition de la frontière d’un
ensemble A de Rd : ∂A = Adh(A)∩(int(A))c et des relations précédentes :

∂Cio (x) = Adh(Cio (x)) ∩ (Cio (x))c = C̄i (x) ∩ int(C̄i (x)) = ∂ C̄i (x).

(c) Par définition de la frontière d’un ensemble et d’après (b), on a :

c
∂Ci (x) = C̄i (x) ∩ int(C̄i (x))
= C̄i (x) ∩ (Cio (x))c
= ∪xj 6=xi Sij (x) ∩ C̄i (x)

Puisque Sij (x) est un hyperplan de Rd , on a λd (Sij (x)) = 0 et l’assertion (c) est alors
une conséquence de la relation ci-dessus. 2

1.2 Quantification de Voronoi et distorsion optimale

Soit X ∈ L2 (Ω, P; Rd ) de loi de probabilité PX , x = (x1 , . . . , xN ) un N -uplet dans
Rd et Ci (x), i = 1, . . . , N , une partition de Voronoi de x. On appelle quantifieur de
Voronoi de X, la variable aléatoire X̂ x (notée simplement X̂ s’il n’y a pas d’ambiguité)
à valeurs dans la grille x, définie par :
N
X
X̂ x = Projx (X) := xi 1Ci (x) (X)
i=1

et donc de loi de probabilité discrète PX̂ caractérisée par :

pi := PX̂ (xi ) = P(X̂ = xi ) = P(X ∈ Ci (x)) = PX (Ci (x)), i = 1, . . . , N.

Autrement dit, X̂ x est la projection selon le plus proche voisin de la variable aléatoire
X sur la grille x. Les pi sont appelés aussi masses des cellules de Voronoi. L’erreur
résultante au carré de quantification quadratique est appelée distorsion (quadratique)
et s’écrit donc par définition d’une partition de Voronoi :
X
DN (x) := E|X − X̂ x |2
N
X
E |X − xi |2 1Ci (x) (X) = E 2

= min |X − xi |
i=1,...,N
i=1
Z
= dN (x, u)PX (du) (1.5)
Rd
QUANTIFICATION VECTORIELLE 8

où dN : (Rd )N × Rd → R+ est la distorsion locale définie par :

N
X
dN (x, u) = min |u − xi |2 = |u − xi |2 1Ci (x) (u) (1.6)
i=1,...,N
i=1

La distorsion ne dépend que du N -uplet x et de la loi de probabilité PX de X.

Le problème de la quantification optimale, à N fixé, consiste à minimiser sur les
∗
N -uplets x la distorsion. On dira que X̂ = X̂ x est un N -quantifieur optimal de X si :

E|X − X̂|2 = inf X

DN (x) =: DX
N.
x∈(Rd )N

En fait, comme le prouve le résultat suivant, la N -quantification optimale fournit la

meilleure approximation quadratique d’une variable aléatoire (loi de probabilité) par
une variable aléatoire discrète (loi de probabilité discrète) de support à au plus N
points.

Proposition 1.2.2 Pour tout x = (x1 , . . . , xN ) ∈ (Rd )N , on a :

n o
X
DN (x) = inf E|X − Y |2 : Y : Ω → Rd mesurable, Y (Ω) ⊂ {x1 , . . . , xN } (. 1.7)

et donc
n o
DX
N = inf E|X − Y |2 : Y : Ω → Rd mesurable, ]Y (Ω) ≤ N .

Preuve. Soit Y une variable aléatoire quelconque discrète dans Rd de support Y (Ω)
⊂ {x1 , . . . , xN }. On a alors par définition de la quantification de Voronoi :

|X − X̂ x |2 = min |X − xi |2 ≤ |X − Y |2 , p.s.
i=1,...,N

d’où DNX (x) ≤ E|X − Y |2 et donc l’inégalité ≤ dans (1.7).

Réciproquement, considérons Y = X̂ x un quantifieur de Voronoi de X qui est bien

une variable aléatoire discrète de support inclus dans {x1 , . . . , xN }. On a alors :
X
DN (x) = E[ min |X − xi |2 ] = E|X − Y |2
i=1,...,N
n o
≥ inf E|X − Y |2 : Y : Ω → Rd mesurable, Y (Ω) ⊂ {x1 , . . . , xN } .

2
L’existence et la caractérisation d’un quantifieur optimal requiert l’étude de la
distorsion DNX en fonction de x ∈ (Rd )N .

Proposition 1.2.3 La fonction x 7→ DN X est continue sur (Rd )N et atteint son mi-

nimum. De plus, si ]supp(PX ) > N , alors ce minimum est atteint en un N -uplet

(x∗1 , . . . , x∗N ) tel que x∗i ∈ Conv(Supp(PX )) et x∗i 6= x∗j pour i 6= j, et on a DX X
k+1 < D k
pour 1 ≤ k ≤ N .
QUANTIFICATION VECTORIELLE 9

Preuve. La continuité de la distorsion DN X est une conséquence immédiate de la conti-

nuité de x = (x1 , . . . , xn ) 7→ dN (x, u) = mini=1,...,N |u − xi |2 pour tout u ∈ Rd , et du

théorème de convergence dominée.
Il est clair que si ]supp(PX ) ≤ N avec donc supp(PX ) = {x̂1 , . . . , x̂k } où k ≤ N ,
X
DN atteint son minimum égal à zéro en tout N -uplet x = (x1 , . . . , xN ) avec xi = x̂i
pour i ≤ k.
On suppose donc ]supp(PX ) > N et on montre le résultat par récurrence pour DkX
avec k ≤ N :
Si k = 1, comme la fonction x ∈ Rd 7→ D1X (x) = E|X − x|2 est continue et tend
vers l’infini quand x tend vers l’infini, elle atteint son minimum.
Soit 1 ≤ k ≤ N et supposons qu’il existe x∗ = (x∗1 , . . . , x∗k ) ∈ (Rd )k atteignant
le minimum de DkX . Fixons y ∈ supp(PX )\{x∗1 , . . . , x∗k } = 6 ∅ et considérons le k + 1-
uplet x (k+1) ∗ ∗
= (x1 , . . . , xk , y). Notons alors que la k + 1 cellule ouverte de Voronoi de
x(k+1) est alors de mesure non nulle pour PX , i.e. PX (Ck+1 o (x(k+1) )) 6= 0., et qu’on a
(k+1)
pour tout u dans Rd , mini=1,...,k+1 u − xi ≤ mini=1,...,k |u − x∗i | avec une inégalité
o (x(k+1) ). On en déduit que
stricte pour u ∈ Ck+1

X (k+1) (k+1)
Dk+1 (x ) = E min X − xi
i=1,...,k+1

∗
< E min |X − xi | = DX k ,
i=1,...,k

ce qui prouve DX X
k+1 < D k . Considérons l’ensemble de (R )
d k+1 : K X
k+1 = {Dk+1 ≤
X
Dk+1 (x(k+1) X
)}. Kk+1 est fermé par continuité de Dk+1 . Il est aussi borné car d’après
le lemme de Fatou :

X 2
lim inf Dk+1 (x) ≥ E lim inf min |X − xi |
x=(x1 ,...,xk+1 )→+∞ x=(x1 ,...,xk+1 )→+∞ i=1,...,k+1

≥ DX
k
X
> Dk+1 (x(k+1) ).

Ainsi, Kk+1 est un compact de (Rd )k+1 dans lequel Dk+1 X atteint son minimum qui
est alors évidemment aussi un minimum absolu sur (R )k+1 . De plus, comme DX
d
k+1 <
X X
Dk , un minimum de Dk+1 a nécessairement toutes ses k + 1 composantes distinctes.
Finalement, en notant par Π la projection sur le convexe fermé Conv(Supp(PX )), on
a pour tout x ∈ (Rd )N et u ∈ Supp(PX ), |Π(xi ) − u| = |Π(xi ) − Π(u)| ≤ |xi − u| car Π
X ((Π(x ) X
est 1-Lipschitzienne et donc DN i 1≤i≤N ) ≤ DN (x). Ceci prouve qu’un minimum
de DNX a ses composantes dans Conv(Supp(P )).
X 2
On a le résultat suivant de différentiabilité de la fonction de distorsion.

Proposition 1.2.4 (a) La fonction x 7→ DN X est différentiable en tout point x =

(x1 , . . . , xN ) ∈ (Rd )N tel que xi 6= xj pour i 6= j et PX (∪Ni=1 ∂Ci (x)) = 0. De plus,

QUANTIFICATION VECTORIELLE 10

son gradient est donné par :

Z !
X
∇DN (x) = 2 (xi − u)PX (du) . (1.8)
Ci (x)
1≤i≤N

(b) En particulier, si PX est absolument continue par rapport à la mesure de Lebesgue,

alors DNX est différentiable en tout x = (x , . . . , x ) ∈ (Rd )N tel que x 6= x pour i 6=
1 N i j
j et on a
X X

arg min DN ⊂ ∇DN =0 .
(Rd )N

Preuve. Par définition (1.6) de la distorsion locale, pour tout x = (x1 , . . . , xN ) ∈

(Rd )N tel que xi 6= xj pour i 6= j et u ∈
/ ∪N
i=1 ∂Ci (x), on a :

∂dN
(x, u) = 2 (xi − u)1Ci (x) (u) 1≤i≤N ,
∂x
∂dN
et donc ∂x (x, u) existe PX (du) p.s. sous la condition PX (∪N
i=1 ∂Ci (x)) = 0. De plus,
pour tout x dans un compact K de (Rd )N avec xi 6= xj pour i 6= j, on a ∂d ∂x (x, u) ≤
N

2(|u| + cK ) où cK est une constante dépendant de K. La fonction u → 2(|u| + cK ) étant

PX intégrable, on obtient (1.8) d’après (1.5) et le théorème de Lebesgue. Finalement,
(b) découle de l’assertion (c) de la proposition 1.1.1 et de la proposition 1.2.3. 2
On dit qu’un quantifieur X̂ = X̂ x est stationnaire si le N -uplet x de points associés
satisfait
X
∇DN (x) = 0.

Un quantifieur optimal est donc stationnaire (la réciproque n’étant pas toujours vraie).
On a la propriété utile suivante sur les quantifieurs stationnaires.

Proposition 1.2.5 Si X̂ est un quantifieur stationnaire de X alors on a :

E[X|X̂] = X̂. (1.9)

Preuve. D’après (1.8), le N -uplet x = (x1 , . . . , xN ) associé à un quantifieur station-

naire X̂ = X̂ x satisfait :

E (X − xi )1Ci (x) (X) = 0, i = 1, . . . , N. (1.10)

Pour toute fonction ϕ Borélienne, bornée sur Rd , on a alors :

N
X
E[ϕ(X̂)X] = E[ϕ(xi )X1Ci (x) (X)]
i=1
XN
= E[ϕ(xi )xi 1Ci (x) (X)] = E[ϕ(X̂)X̂],
i=1
QUANTIFICATION VECTORIELLE 11

ce qui prouve le résultat voulu. 2

Examples
1. Soit N = 1. Alors D1X (x) = E|X − x|2 atteint son minimum en x∗ = E(X) et on a
DX1 = V ar(X).

2. Soit N = 2 et X de loi de probabilité discrète PX = 13 (δ0 + δ 1 + δ1 ). Pour tous

2
0 ≤ x1 < x2 ≤ 1, on a :
" 2 #
1 1
D2X (x1 , x2 ) = x2 + min xi − + (x2 − 1)2
3 1 i=1,2 2
 h i
 1 2 x1 − 1 2 + (x2 − 1)2 + 1

3 4 8 si x1 + x2 ≥ 1
= h 2 1 i
1 2 3
3 x1 + 2 x2 − 4 +8 si x1 + x2 < 1


On obtient donc

1 3 1
arg min D2X = {∇D2X = 0} = , 1 ; 0, et DX
2 = .
x∈R2 4 4 24
∗,1
Pour x∗,1 = (1/4, 1), on a C1/4 (x∗,1 ) = ] − ∞, 5/8[ et C1 (x∗,1 ) = [5/8, ∞[, d’où p1/4
= 2/3 et p∗,1
1 = 1/3. Pour x
∗,2 = (0, 3/4), on a C (x∗,2 ) = ] − ∞, 3/8[ et C
0
∗,1
3/4 (x ) =
∗,2 ∗,2
[3/8, ∞[, d’où p0 = 1/3 et p3/4 = 2/3.
3. Soit X de loi uniforme sur [0, 1] : U ([0, 1]). La recherche du minimum de la distorsion
DN X peut se restreindre aux N -uplets x = (x , . . . , x ) avec 0 ≤ x < x < . . . < x ≤
1 N 1 2 N
1. Pour de tels N -uplets, les cellules (fermées) de Voronoi sont :

x1 + x2 xi−1 + xi xi + xi+1
C̄1 (x) = −∞, , C̄i (x) = , , 2 ≤ i ≤ N − 1,
2 2 2

xN −1 + xN
C̄N (x) = , +∞ .
2
On calcule explicitement le gradient de la distorsion :
∂DNX Z
1
(x) = 2 (x1 − u)du = (3x1 − x2 )(x1 + x2 ),
∂x1 C̄1 (x)∩[0,1] 4
∂DNX Z
1
(x) = 2 (xi − u)du = (2xi − (xi−1 + xi+1 ))(xi+1 − xi−1 ), 2 ≤ i ≤ N − 1,
∂xi C̄i (x) 4
∂DNX Z
1
(x) = 2 (xN − u)du = (3xN − xN −1 − 2)(2 − (xN −1 + xN )).
∂xi C̄N (x)∩[0,1] 4

On vérifie alors aisément qu’il y a un unique x∗ = (x∗1 , . . . , x∗N ) tel que ∇DN
X (x∗ ) = 0 :

il est donné par

2i − 1
x∗i = , 1 ≤ i ≤ N.
2N
QUANTIFICATION VECTORIELLE 12

Cet unique quantifieur stationnaire est donc aussi l’unique minimum de DN X . Les ce-

llules fermées de Voronoi associées sont C̄1 (x∗ ) = ]−∞, 1/N ], C̄i (x∗ ) = [(i−1)/N, i/N ],
i = 2, . . . , N − 1, et C̄N (x∗ ) = [1 − 1/N, ∞[. Par symétrie et translation, on calcule
aisément la distorsion minimale :
N Z
X
X ∗
DN
X = DN (x ) = |x∗i − u|2 1[0,1] (u)du
i=1 Ci (x∗ )
Z
1 1
= N |u|2 du = ,
[−1/2N,1/2N ] 12 N 2

ainsi que les masses des cellules de Voronoi associées p∗i = PX [Ci (x∗ )] = 1/N , i =
1, . . . , N .
4. Soit X de loi uniforme sur le cube [0, 1]d : U ([0, 1]d ). Considérons la mosaique de
Voronoi de [0, 1]d construite avec les N = k d translations C1 , . . . , CN du cube [0, 1/k]d .
Notons xi , i = 1, . . . , N , les points centraux de ces cubes, voir figure. La distorsion
associée est
N Z
X
X
DN (x) = |xi − u|2 du.
i=1 Ci

Par translation et hométhie des cubes Ci , on a pour tout i = 1, . . . , N :

|u|2
Z Z Z
2 2
|xi − u| du = |u| du = 2+d
du.
Ci [− 1 , 1 ]d2k 2k
[− 1 , 1 ]d k 2 2

On obtient donc
Z
X 1 1 d
DN (x) = 2 |u|2 du = 2 .
N d [− 12 , 21 ]d N d 12

1.3 Asymptotique de l’erreur de quantification

On s’intéresse dans ce paragraphe au comportement asymptotique de la distorsion
minimale lorsque le nombre de points N tend vers l’infini.

Proposition 1.3.6

lim DX
N = 0.
N →+∞

Preuve. Soit (xn )n∈N∗ une suite dense dans Rd et considérons le N -uplet x(N ) =
(x1 , . . . , xN ). Alors la suite de variables aléatoires positives fN = mini=1,...,N |X − xi |2
est décroissante et converge p.s. vers 0. On en déduit par le théorème de convergence
QUANTIFICATION VECTORIELLE 13

X (x(N ) ) = E[f ] −→ 0 quand N tend vers +∞. Puisque 0 ≤ D X ≤

monotone : DN N N
X (N )
DN (x ), on a le résultat voulu. 2
La recherche de la vitesse de convergence de la distorsion minimale est un problème
beaucoup plus difficile. Elle a été résolue en plusieurs étapes par Zador [21], Buckley et
Wise [4] et finalement Graf et Lushgy [10]. Le premier résultat concerne la distorsion
de la loi uniforme sur [0, 1]d .

Théorème 1.3.1 Soit X de loi uniforme sur [0, 1]d : U ([0, 1]d ). Alors
2
Jd := lim N d DX
N existe dans ]0, +∞[.
N →+∞

Remarque 1.3.1 D’après l’exemple 4 du paragraphe précédent, on sait que Jd ≤

√
d/12. Pour d = 1 et 2, on connait J1 = 1/12 et J2 = 5/(18 3). Pour d ≥ 3, la valeur
exacte de Jd est inconnue. On a cependant un équivalent quand d tend vers l’infini :
Jd ∼ d/(2πe).

Dans un deuxième temps, on étend le résultat pour des lois non uniformes. On note
PX = PaX + PsX la décomposition de Lebesgue de PX par rapport à λd , i.e. PaX est la
partie absolument continue et PsX la partie singulière. On note dPaX /dλd la densité de
Radon-Nykodim de PaX par rapport à λd . Pour toute fonction borélienne mesurable de
Rd dans R et r ∈ ]0, +∞[, on note
Z 1
r
r
kf kr = |f | dλd .

Théorème 1.3.2 On suppose E|X|2+ε < +∞ où ε > 0. Alors

2 dPaX
lim N d DX
N = Jd . (1.11)
N →+∞ dλd d
d+2

Remarque 1.3.2 Si PX est une mesure purement singulière par rapport à λd alors le
théorème précédent montre que DX −2/d ). En fait, dans ce cas, la vitesse peut
N = o(N
être plus rapide. Par exemple, si PX est une mesure discrète alors DX N = 0 dès que N
≥ ]supp(PX ). Si ]supp(PX ) = N et la transformée de Laplace de X est finie sur tout
R+ , e.g. la loi de Poisson, alors :

X 2
≤ E 1X≥N |X − N + 1|2

DN ≤ E min |X − n|
n=0,...,N −1

≤ E 1X≥N |X|2 ≤ E |X|2 eαX e−αN , pour tout α > 0,

h i
≤ 2E e(α+1)X e−αN = O(e−αN ) pour tout α > 0.
QUANTIFICATION VECTORIELLE 14

Example
Soit X de loi normale N (m, Σ) sur Rd (Σ matrice de variance-covariance). Alors la
formule (1.11) donne
1+ d
2 2 2 1
lim N d DX
N = 2π 1 + (det(Σ)) d Jd .
N →+∞ d

Projet 1 : Mémoire sur la démonstration du théorème 1.3.2. Ref : Graf et Lushgy [10].

1.4 Algorithmes de recherche d’un quantifieur optimal de

Voronoi
A cette étape, le problème est d’obtenir numériquement un quantifieur N -optimal,
i.e. trouver un N -uplet x = (x1 , . . . , xN ) ∈ (Rd )N qui minimise la distorsion DNX . La

recherche des minima d’une fonction est un problème classique en analyse. Il est lié au
problème de la recherche des points à un niveau puisque argmin DN X ⊂ {∇D X = 0}.
N
On va donc en fait chercher les quantifieurs stationnaires i.e. solution de : ∇DN X (x∗ )

= 0 qui vont nous donner au moins des minimas locaux. Nous examinons dans ce
paragraphe les méthodes de point fixe et celles du gradient.

1.4.1 Méthode du point fixe de Lloyd (en dimension 1)

L’approche du point fixe de Lloyd est basée sur l’équation (1.10) de stationnarité
d’un quantifieur qui peut se réécrire comme :
Z
1
xi = uPX (du), i = 1, . . . , N.
PX (Ci (x)) Ci (x)

L’algorihme de Lloyd consiste à définir récursivement une suite (xn )n≥0 dans (Rd )N
partant d’un point initial x ∈ (Rd )N :

x0 = x Z
1
xn+1
i
n
= Fi (x ) := uPX (du), i = 1, . . . , N, (1.12)
PX (Ci (xn )) Ci (xn )

L’heuristique de la qualité d’un tel algorithme est donnée par l’argument suivant : en
n
notant X̂ n := X̂ x , la relation (1.12) implique X̂ 0 = X̂ x et

X̂ n+1 = E[X|X̂ n ], n ∈ N.

D’après la définition-caractérisation de l’espérance conditionnelle par rapport à X̂ n

comme projection orthogonale dans L2 sur l’espace L2 (σ(X̂ n )) des variables aléatoires
QUANTIFICATION VECTORIELLE 15

σ(X̂ n )-mesurables de carré intégrable, on a :

n o
kX − X̂ n+1 k2 = kX − E[X|X̂ n ]k2 = min kX − Y k2 : Y ∈ L2 (σ(X̂ n ))
< kX − X̂ n k2 avec égalité si X̂ n = E[X|X̂ n ].

En dimension d = 1, on montre (voir [11]) que lorsque PX admet une densité stric-
tement log-concave (e.g. la distribution normale), alors l’application x 7→ (Fi (x))1≤i≤N
est une contraction et donc admet un unique point fixe vers lequel la méthode de
Lloyd converge avec une vitesse exponentielle. En dimension d ≥ 2, les résultats de
convergence de la méthode de Lloyd ne sont pas clairement établis dans la littérature.
De plus, lorsque d ≥ 2, l’implémentation de la méthode de Lloyd n’est pas réaliste
car on doit calculer numériquement des intégrales multiples sur des mosaiques de Vo-
ronoi. En fait, l’algorithme de Lloyd ne s’utilise en pratique qu’en dimension d = 1 où
les mosaiques de Voronoi et le calcul d’intégrale simple sont explicites.
Projet 2 : Démonstration de la convergence de la méthode de Lloyd en dimension 1
et implémentation pour la loi normale.

1.4.2 Méthode du gradient déterministe (en dimension 1)

La méthode du gradient pour la recherche d’un quantifieur stationnaire x∗ , i.e.
∇DN X (x∗ ) = 0, est un algorithme qui corrige à chaque pas dans le bon sens, l’ampleur

des corrections diminuant petit à petit. Supposons ainsi que x∗ est un point attractif,
i.e.

(x − x∗ |∇DN
X
(x)) > 0, ∀x 6= x∗ ∈ (Rd )N . (1.13)

On considère alors l’algorithme

x0 = x
xn+1 = xn − γn ∇DN X n
(x ), (1.14)
P P 2
où la suite (γn ) des pas est une suite positive telle que n γn = +∞ et n γn < +∞.
Cet algorithme se présente de façon générale sous la forme :

x0 = x
xn+1 = xn − γn h(xn ), (1.15)

où h est une fonction continue et la suite (γn ) des pas est une suite positive telle que
P P 2
n γn = +∞ et n γn < +∞. La convergence de cet algorithme peut être étudiée selon
la technique de Robbins-Monro. C’est l’approche que nous considérons ici. Elle peut
être aussi approfondie avec la technique de Kushner-Clark, appelée encore méthode
de l’EDO, en étudiant l’équation différentielle ordinaire dx/dt = −h(x) associée à
l’algorithme.
QUANTIFICATION VECTORIELLE 16

Proposition 1.4.7 (Robbins-Monro déterministe)

Soit V une fonction auxiliaire (dite de Lyapounov) à valeurs positives de classe C 1
avec un gradient ∇V Lipschitzien et telle que : |h|2 ≤ Cte(1 + V ) et (h|∇V ) ≥ 0. Alors
la suite (V (xn ))n converge et n γn |(h|∇V )(xn )| < +∞.
P

La preuve de cette proposition repose sur le lemme suivant :

Lemme 1.4.1 (Robbins-Siegmund déterministe)

Soient (Vn ), (βn ), (χn ) et (ηn ) quatre suites positives telles que :
X X
Vn+1 ≤ Vn (1 + βn ) + χn − ηn , βn < +∞, χn < +∞.
n n
P
Alors (Vn ) converge dans R+ et n ηn < +∞.
Qn
Preuve. On pose αn = 1/ k=1 (1 + βk ), Vn0 = αn−1 Vn , χ0n = αn χn , ηn0 = αn ηn de telle
sorte que :
0
Vn+1 ≤ Vn0 + χ0n − ηn0 .

La suite Yn = Vn0 − n−1

P 0 0
Qn
Pn k=1 (χk −ηk ) est donc décroissante. De plus, comme ln k=1 (1+βk )
= k=1 ln(1 + βk ) converge quand n tend vers l’infini, alors (αn ) converge vers α > 0.
La convergence de la série n χn implique donc celle de n χ0n . La suite décroissante
P P

(Yn ) est donc minorée (par − n χ0n ) et converge. Notons aussi que n−1 0
P P
Pn−1 0 P 0 k=1 ηk ≤ Yn +
k=1 χk et donc la série à termes positifs n ηn converge. Ceci implique la convergence
0 2
P
de la suite (Vn ) et finalement celle de (Vn ) et de n ηn .
Preuve de la proposition 1.4.7.
Par la formule de Taylor, on a
Z 1
n+1 n
V (x ) = V (x ) + (∇V (txn + (1 − t)xn+1 ).(xn+1 − xn )dt.
0

D’après (1.15) et puisque ∇V est Lipschitzienne, on a :

V (xn+1 ) ≤ V (xn ) − γn (∇V (xn )|h(xn )) + Cte|xn+1 − xn |2

≤ V (xn ) 1 + Cteγn2 + Cteγn2 − γn (∇V |h)(xn ),

en utilisant l’hypothèse |h|2 ≤ Cte(1 + V ). On conclut avec le lemme 1.4.1. 2

Application à l’algorithme du gradient (1.14).

Il y a diverses variations autour du choix des fonctions de Lyapounov pour obtenir des
versions multiples de la convergence de l’algorithme de Robbins-Monro et en particulier
de l’algorithme du gradient (1.14) avec h = ∇DN X.
QUANTIFICATION VECTORIELLE 17

? Un premier choix est V (x) = |x−x∗ |2 . Alors ∇V (x) = 2(x−x∗ ). D’après l’expression
(1.8) de ∇DN X , on a |∇D X (x)|2 ≤ Cte(1 + |x|2 ) de sorte que sous (1.13), les hypothèses
N
de la proposition 1.4.7 sont vérifiées. On obtient alors que |xn − x∗ |2 converge vers une
X (xn )|xn − x∗ )| converge. Si par l’absurde δ 6=
P
constante δ ≥ 0 et la série n γn |(∇DN
0, alors à partir d’un certain rang n0 , on aurait pour tout n ≥ n0 , 0 < δ/2 ≤ |xn − x∗ |2
≤ 2δ et |(∇DN X (xn )|xn − x∗ )| > c avec c > 0 d’après (1.13). C’est en contradiction avec
P
la divergence de la série n γn .
? Un autre choix de fonction de Lyapounov est V (x) = DN X . Sous la condition que
X X 2 X
∇DN est Lipschitzienne et |∇DN | ≤ cte(1 + DN ), la proposition 1.4.7 implique que
X (xn )) converge vers D ∗ et la série X n 2
P
la suite (DN n n γn |∇DN (x )| converge. Si de plus
DNX (x) converge vers l’infini quand |x| tend vers l’infini, alors en utilisant la méthode

dite de l’EDO (équation différentielle ordinaire), on montre (voir Lemme [Link].8 dans
[5]) que xn converge vers une composante connexe de {∇DN X = 0} ∩ {D X = D ∗ }. En
N
particulier, si {∇DN X = 0} = {x∗ } alors xn converge vers x∗ .

Remarque 1.4.3 Les hypothèses ci-dessus requises pour assurer la convergence de la

méthode du gradient ne sont pas vérifiées par la fonction de distorsion. Cependant, il
existe des résultats partiels de convergence dans le cas unidimensionnel ou lorsque le
support de la loi de X est compact, cf [15]. De plus, l’implémentation pratique donne
des résultats satisfaisants (ce qui est souvent le cas dans les méthodes de gradient) et
on peut obtenir des estimations d’erreur de la distorsion (voir paragraphe suivant).

En pratique, la méthode du gradient déterministe est difficilement implémentable

au delà de la dimension d ≥ 2 car le calcul de ∇DN X fait intervenir des intégrales

multiples (sur des cellules de Voronoi). En dimension 1, comme pour la méthode de

Lloyd, les calculs d’intégrales et de cellules de Voronoi sont explicites, et la méthode
du gradient est efficace.

Exemple pour la loi normale unidimensionnelle

Soit X de loi normale N (0, 1). La recherche du minimum de la distorsion DN X peut se
N
restreindre aux N -uplets x = (x1 , . . . , xN ) ∈ R avec x1 < x2 < . . . < xN . Pour de tels
N -uplets, les cellules (fermées) de Voronoi sont Ci (x) = [xi−1/2 , xi+1/2 ] où on a posé
xi−1/2 = (xi + xi−1 )/2, xi+1/2 = (xi + xi+1 )/2 et par convention x1/2 = −∞ (lorsque
i = 1) et xN +1/2 = +∞ (lorsque i = N ). En notant par φ la fonction de distribution
Ry 2
de N (0, 1), i.e. φ(y) = √12π −∞ e−u /2 du, on calcule explicitement le gradient de la
distorsion :
∂DNX
(x) = xi φ(xi+1/2 ) − φ(xi−1/2 )
∂xi

1 1 2 1 2
+√ exp − xi+1/2 − exp − xi−1/2 .
2π 2 2
QUANTIFICATION VECTORIELLE 18

Projet 3 : Implémenter la méthode du gradient pour la loi normale scalaire et comparer

avec la méthode de Lloyd.

1.4.3 Méthode du gradient stochastique : algorithme de Kohonen

La méthode du gradient stochastique pour la recherche d’un quantifieur stationnaire
est basée sur le fait que le gradient de la distorsion admet une représentation intégrale
par rapport à la loi de probabilité X simulable :
Z
X
∇DN (x) = ∇x dN (x, u)PX (du) = E[∇x dN (x, Z)],

où Z est une variable aléatoire de loi de probabilité PX et ∇x dN : (Rd )N × Rd → Rd

est donné d’après (1.8) par :
1
∇x dN (x, u) = (xi − u)1Ci (x) 1≤i≤N . (1.16)
2
On considère alors l’algorithme stochastique définissant de façon récursive la suite de
variables aléatoires (xn ) dans (Rd )N par :
γn
xn+1 = xn − ∇x dN (xn , Zn+1 ), (1.17)
2
où la suite (γn ) des pas est une suite positive telle que n γn = +∞ et n γn2 < +∞
P P

et la suite (Zn ) est une suite de variables aléatoires i.i.d. de loi PX simulable choisie
indépendante de la variable initiale x0 . On peut réécrire (1.17) sous la forme :
γn
xn+1 = xn − X n
(x ) + ∇x dN (xn , Zn+1 ) − ∇DN X n

∇DN (x ) .
2
Les termes ∇x dN (xn , Zn+1 ) − ∇DN X (xn ), n ≥ 0, ont une espérance conditionnelle nulle

par rapport à FnZ = σ(x0 , Z1 , . . . , Zn ) filtration propre engendrée par Z (et x0 ).

Finalement, on est amené à étudier des algorithmes stochastiques généraux de la
forme :
xn+1 = xn − γn (h(xn ) + εn+1 ), (1.18)
où h est une fonction continue, la suite (γn ) des pas est une suite positive telle que
P P 2
n γn = +∞ et n γn < +∞ et la suite de variables aléatoires (εn ) vérifie

E[εn+1 |Fn ] = 0, n ∈ N, (1.19)

où Fn est la filtration engendrée par x0 , ε1 . . . , εn .

Proposition 1.4.8 (Robbins-Monro stochastique)

Soit V une fonction auxiliaire (dite de Lyapounov) à valeurs positives de classe C 1
avec un gradient ∇V Lipschitzien et telle que : |h|2 ≤ Cte(1 + V ), (h|∇V ) ≥ 0 et
E[|εn+1 |2 |Fn ] ≤ Cte(1 + V (xn )),
p.s. ∀n ≥ 0. (1.20)
Alors presque sûrement, la suite (V (xn ))n converge et n γn |(h|∇V )(xn )| < +∞.
P
QUANTIFICATION VECTORIELLE 19

Comme dans le cas déterministe, la preuve de cette proposition repose sur le lemme
suivant :

Lemme 1.4.2 (Robbins-Siegmund stochastique)

Soient (Vn ), βn ), (χn ) et (ηn ) quatre suites de variables aléatoires positives (Fn )-
adaptées telle que :

E[Vn+1 |Fn ] ≤ Vn (1 + βn ) + χn − ηn , p.s. ∀n ≥ 0.

Alors presque sûrement sur

( )
X X
Ω1 = βn < +∞ et χn < +∞ ,
n n
P
(Vn ) converge vers V∞ variable aléatoire positive finie et la série n ηn converge.
Qn
Preuve. On pose αn = 1/ k=1 (1 + βk ), Vn0 = αn−1 Vn , χ0n = αn χn , ηn0 = αn ηn de telle
sorte que :
0
E[Vn+1 |Fn ] ≤ Vn0 + χ0n − ηn0 .

La suite Yn = Vn0 − n−1 (χ0 − η 0 ) est donc une surmartingale. Pour tout m ∈ N∗ ,
P
k=1
Pn k 0 k 0
on note τm = inf{n : k=1 (χk − ηk ) ≥ m} de sorte que la surmartingale arrêtée
(Yn∧τm )n est minorée par −m et converge p.s. vers une variable aléatoire finie d’après
le théorème de Doob. Donc sur {τm = +∞}, (Yn ) converge p.s. vers une limite finie.
De plus, sur Ω1 , ln nk=1 (1 + βk ) = nk=1 ln(1 + βk ) converge quand n tend vers
Q P
P
l’infini et donc (αn ) converge vers α > 0. La convergence de la série n χn implique
donc celle de n χ0n sur Ω1 .
P
Pn−1 0 Pn−1 0
Puisque k=1 ηk ≤ Yn + k=1 χk , on en déduit que la série à termes positifs
P 0
n ηn converge sur Ω1 ∩ {τm P = +∞} et donc aussi (Vn0 ). Ceci implique la convergence
de la suite (Vn ) et de la série n ηn sur Ω1 ∩ {τm = +∞}. Or sur Ω1 , la série n χ0n
P

converge et donc il existe m ∈ N∗ tel que +∞ 0 0

P
k=1 (χk − ηk ) < m, i.e. τm = +∞. Ainsi
+∞
Ω1 = ∪m=1 Ω1 ∩ {τm = +∞} et la proposition est démontrée. 2
Preuve de la proposition 1.4.8.
Comme dans la preuve de la proposition 1.4.7, on a par la formule de Taylor, le fait
que ∇V est Lipschitzienne et l’hypothèse |h|2 ≤ Cte(1 + V ) :

V (xn+1 ) ≤ V (xn ) 1 + Cteγn2 − γn (∇V |h)(xn )

+Cteγn2 (1 + |εn+1 |2 ) − γn (∇V (xn )|εn+1 ).

D’après (1.19) et (1.20), on obtient alors

E[V (xn+1 )|Fn ] ≤ V (xn ) 1 + Cteγn2 + Cteγn2 − γn (∇V |h)(xn ).

QUANTIFICATION VECTORIELLE 20

On conclut avec le lemme 1.4.2. 2

Application à l’algorithme du gradient (1.17).

Il y a diverses variations autour du choix des fonctions de Lyapounov pour obtenir
des versions multiples de la convergence de l’algorithme du gradient (1.14) avec h =
1 X 1 n X n
2 ∇DN et εn+1 = 2 (∇x dN (x , Zn+1 ) − ∇DN (x )).
? Un premier choix est V (x) = |x−x∗ |2 . Alors ∇V (x) = 2(x−x∗ ). D’après l’expression
X et (1.16) de ∇ d (x, u), on a
(1.8) de ∇DN x N
Z
X
|∇DN (x)|2 + |∇x dN (x, u)|2 PX (du) ≤ Cte(1 + |x|2 )

Si on suppose de plus (1.13), alors les hypothèses de la proposition 1.4.8 sont vérifiées.
On obtient alors que |xn − x∗ |2 converge p.s. vers une variable aléatoire positive δ
X (xn )|xn − x∗ )| converge p.s. Soit ω un évènement tel que ces
P
et la série n γn |(∇DN
deux convergences aient lieu. Si par l’absurde δ(ω) 6= 0, alors à partir d’un certain
rang n0 = n0 (ω), on aurait pour tout n ≥ n0 , 0 < δ(ω)/2 ≤ |xn (ω) − x∗ |2 ≤ 2δ(ω) et
|(∇DN X (xn (ω))|xn (ω) − x∗ )| > c(ω) avec c(ω) > 0 d’après (1.13). C’est en contradiction
P
avec la divergence de la série n γn .
X . Sous la condition que
? Un autre choix de fonction de Lyapounov est V (x) = DN
∇DNX est Lipschitzienne et

Z
|∇DN (x)| + |∇x dN (x, u)|2 PX (du) ≤ cte(1 + DN
X 2 X
(x)),

X (xn ))
les hypothèses de la proposition 1.4.8 sont vérifiées et on obtient que la suite (DN n
∗ X n 2 X
P
converge p.s. vers D et la série n γn |∇DN (x )| converge p.s. Si de plus DN (x)
converge vers l’infini quand |x| tend vers l’infini, alors en utilisant la méthode dite de
l’EDO (équation différentielle ordinaire), on montre (voir Lemme [Link].8 dans [5]) que
xn converge p.s. vers une composante connexe de {∇DN X = 0} ∩ {D X = D ∗ }. En
N
particulier, si {∇DN X = 0} = {x∗ } alors xn converge vers x∗ p.s.

La méthode du gradient stochastique est efficiente en grande dimension d puisqu’elle

ne requiert pas le calcul d’intégrales multiples mais seulement la connaissance de la
fonction locale ∇x dN (x, u) et la simulation de la loi de probabilité PX :
Description explicite du gradient stochastique pour la distorsion : algo-
rithme de Kohonen
D’après l’expression (1.16) du gradient de la distorsion locale, l’algorithme du gradient
stochastique (1.17) s’exprime comme :

xn+1
i = xni − γn (xni − Z n+1 )1Ci (xn ) (Z n+1 ), i = 1, . . . , N

Cette procédure se décompose encore à chaque pas n de façon explicite selon :

QUANTIFICATION VECTORIELLE 21

• phase de compétition : sélectionner l’indice i(n + 1) tel que

Z n+1 ∈ Ci(n+1) (xn ) i.e. i(n + 1) ∈ arg min |xni − Z n+1 |.

i=1,...,N

• phase d’apprentissage :

xn+1
i = xni − γn (xni − Z n+1 ), si i = i(n + 1)
xn+1
i = xni , si i 6= i(n + 1)

Cette procédure en deux phases est connue dans la littérature comme l’algorithme
de Kohonen. D’un point de vue numérique, la principale activté est la phase de
compétition concernant la recherche à chaque étape du plus proche voisin de la nou-
velle variable simulée Z n+1 . La phase d’apprentissage est simplement la mise à jour de
la grille xn en modifiant la composante sélectionnée par la phase de compétition par
une homothétie avec Z n+1 de rapport (1 − γn ).

Estimation des masses des cellules de Voronoi et de la distorsion minimale

∗
Pour déterminer un quantifieur stationnaire X̂ ∗ = X̂ x , on doit obtenir, outre la grille
x∗ = (x∗1 , . . . , x∗N ) de son support, les masses PX (Ci (x∗ )), i = 1, . . . , N , des cellules
de Voronoi associées qui caractérisent sa loi de probabilité. Il est donc important
dans les applications numériques d’avoir une procédure de calcul des caractéristiques
PX (Ci (x∗ )) ainsi que de la distorsion associée DN X (x∗ ).

? Une première approche simple consiste, après avoir terminé l’algorithme de Kohonen
jusqu’au pas n et enregistré la grille limite x∗ = xn , à estimer les caractéristiques
voulues par une estimation standard de Monte-Carlo :
n n
1X 1X
pni = 1Zk ∈Ci (x∗ ) , i = 1, . . . , N, et D n
= min |Zk − x∗i |2 ,
n n i=1,...,N
k=1 k=1

où (Zk )1≤k≤n est un échantillon i.i.d. de loi PX . Par la loi standard des grands nombres,
on est assuré de la convergence quand n tend vers l’infini d’une telle procédure :

pni −→ PX (Ci (x∗ )) p.s., i = 1, . . . , N, et X ∗

Dn −→ DN (x ) p.s.

? Une autre approche plus pertinente et moins couteuse permet d’obtenir une estima-
tion des caractéristiques voulues de façon simultanée à la procédure de Kohonen :
n n
1X 1X
pni = 1Zk ∈Ci (xk−1 ) = 1i=i(k) , i = 1, . . . , N,
n n
k=1 k=1
n n
1 X 1X
D n
= min |Zk − xk−1
i |2 = k−1 2
|Zk − xi(k) |
n i=1,...,N n
k=1 k=1
QUANTIFICATION VECTORIELLE 22

Notons que les pni et Dn s’expriment aussi de manière récursive comme :

1 1
pn+1 = pni − (pn − 1i=i(n+1) ), p0i = , i = 1, . . . , N (1.21)
i
n+1 i N
1
Dn+1 = Dn − Dn − |Zn+1 − xni(n+1) |2 , D0 = 0. (1.22)
n+1
Proposition 1.4.9 On suppose PX absolument continue par rapport à λd et E|X|2+ε
< +∞ où ε > 0. Alors sur l’évènement {xn → x∗ }, on a

pni −→ PX (Ci (x∗ )) p.s., i = 1, . . . , N, et X ∗

Dn −→ DN (x ) p.s.

Preuve. On considère une fonction mesurable H : (Rd )N × Rd → R telle que

|H(x, u)| Cte|u|2

≤
Z
h(x) := H(x, u)PX (du) est bornée sur (Rd )N et continue en x∗ .

Alors les variables aléatoires H(xn , Zn+1 ) − h(xn ), n ≥ 0, sont centrées, non corrélées
deux à deux, et bornées dans L1+ε/2 . La loi forte des grands nombres dans L1+ε/2
implique alors que
n
1 X
H(xk−1 , Zk ) − h(xk−1 ) −→ 0 p.s.
n
k=1

quand n tend vers l’infini. De plus avec la continuité de h en x∗ , on a par le théorème

de Césaro : 1/n nk=1 h(xk−1 ) converge p.s. vers h(x∗ ) sur {xn → x∗ }. On en déduit
P

que
n
1X
H(xk−1 , Zk ) −→ h(x∗ ) p.s. sur {xn → x∗ }.
n
k=1

On applique ce résultat respectivement aux fonctions :

H(x, u) = 1Ci (x) (u) de fonction moyenne h(x) = PX (Ci (x)),
H(x, u) = ρ(x) mini=1,...,N |xi − u|2 de fonction moyenne h(x) = ρ(x)DN
X (x) où ρ est
d N ∗
une fonction continue positive à support compact sur (R ) et ρ(x ) = 1. 2

Remarque 1.4.4 Au lieu de prendre comme pas 1/n dans le calcul récursif (1.21)-
(1.22) des pin et Dn , on peut prendre le même pas (γn ) que pour l’algorithme de
Kohonen :
1
pn+1
i = pni − γn+1 (pni − 1i=i(n+1) ), p0i = , i = 1, . . . , N
N

Dn+1 = Dn − γn+1 Dn − |Zn+1 − xni(n+1) |2 , D0 = 0.

Projet 4 : Implémenter la quantification optimale de la loi normale sur Rd , d ≥ 2, par

l’algorithme de Kohonen.
QUANTIFICATION VECTORIELLE 23

1.5 Application à l’intégration numérique et aux options

européennes
L’idée est simplement d’approximer la loi de probabilité PX de la variable aléatoire
X sur Rd par la loi de probabilité PX̂ = N
P
i=1 pi δxi de la variable N -quantifiée X̂ =
X̂ à support discret dans la grille x = {x1 , . . . , xN } dans (Rd )N . Autrement dit, pour
x

toute fonction f intégrable par rapport à PX , notée f ∈ L1 (PX ), on approxime

Z Z N
X
E[f (X)] = f (u)PX (du) par E[f (X̂)] = f (u)PX̂ (du) = pi f (xi ).
i=1

L’objectif est d’évaluer la qualité de cette approximation en fonction de la distorsion

et donc d’un point de vue numérique d’avoir accès au quantifieur optimal x∗ et aux
masses p∗i des cellules de Voronoi pour obtenir la meilleure approximation possible.
On a le résultat basique suivant pour les fonctions Lipschitziennes. On note pour
toute fonction f Lipschitzienne sur Rd :

|f (y) − f (z)|
[f ]lip = sup < +∞.
y6=z∈Rd |y − z|

Proposition 1.5.10 Pour tout f ∈ L1 (PX ) et f Lipschitzienne, on a :

q
E[f (X)] − E[f (X̂)] ≤ [f ]lip DN X (x).

Preuve. Il suffit simplement d’écrire :

E[f (X)] − E[f (X̂)] ≤ E|f (X) − f (X̂)|

q
≤ [f ]lip E|X − X̂| ≤ [f ]lip X (x),
DN

par l’inégalité de Cauchy-Schwarz. 2

Remarque 1.5.5 Cette dernière proposition montre que si x∗ est un N -quantifieur

optimal alors |E[f (X)] − E[f (X̂ ∗ )]| converge vers 0 quand N tend vers l’infini avec une
vitesse de convergence en 1/N 1/d d’après le théorème de Zador.

Lorsque f possède un peu plus de régularité, la borne d’erreur peut être améliorée.

Proposition 1.5.11 Pour tout f ∈ L1 (PX ) telle que f soit de class C 1 avec ∇f
∗
Lipschitzienne et pour tout quantifieur stationnaire X̂ ∗ = X̂ x , on a :

E[f (X)] − E[f (X̂ ∗ )] X ∗

≤ [∇f ]lip DN (x ).
QUANTIFICATION VECTORIELLE 24

Preuve. D’après la formule de Taylor, on a

Z 1
∗
f (X) = f (X̂ ) + ∇f (tX̂ ∗ + (1 − t)X).(X − X̂ ∗ )dt
0
≤ f (X̂ ) + ∇f (X̂ ∗ ).(X − X̂ ∗ ) + [∇f ]lip |X − X̂ ∗ |2 .
∗

On en déduit que

E[f (X)] − E[f (X̂ ∗ )] − E[∇f (X̂ ∗ ).(X − X̂ ∗ )] ≤ [∇f ]lip E|X − X̂ ∗ |2 .

On conclut en notant que par la propriété de stationnarité (1.9), on a

h i h i
E ∇f (X̂ ∗ ).(X − X̂ ∗ ) = E ∇f (X̂ ∗ ). E[X − X̂ ∗ |X̂ ∗ ] = 0.

Remarque 1.5.6 Cette dernière proposition montre que si x∗ est un N -quantifieur

optimal, on a doublé la vitesse de convergence par rapport au cas de la proposition
1.5.10. Ainsi, |E[f (X)] − E[f (X̂ ∗ )]| converge vers 0 quand N tend vers l’infini avec une
vitesse de convergence en 1/N 2/d d’après le théorème de Zador.

Finalement, on a une propriété intéressante pour l’intégration numérique de fonc-

tions convexes.

Proposition 1.5.12 Pour tout f ∈ L1 (PX ) telle que f soit convexe et pour tout quan-
∗
tifieur stationnaire X̂ ∗ = X̂ x , on a :

E[f (X̂ ∗ )] ≤ E[f (X)].

Preuve. C’est une simple conséquence de la propriété de stationnarité (1.9) et de

l’inégalité de Jensen :

E[f (X̂ ∗ )] = E[f (E[X|X̂ ∗ ])] ≤ E[E[f (X)|X̂ ∗ ]] = E[f (X)].

Remarque 1.5.7 Ceci montre que l’intégration numérique de fonctions convexes avec
un quantifieur stationnaire fournit toujours une borne inférieure à la vraie valeur.
Symétriquement, on a toujours une borne supérieure avec un quantifieur stationnaire
pour les fonctions concaves.
QUANTIFICATION VECTORIELLE 25

Remarque 1.5.8 La méthode de quantification peut être comparée avec la méthode

de Monte-Carlo qui consiste pour approximer E[f (X)] à générer un N -échantillon
X1 , . . . , XN de copies i.i.d. de loi PX et à calculer
N
1 X
f (Xk ).
N
k=1

Il est bien connu que par la loi des grands nombres, cette quantité converge p.s. quand
N tend vers l’infini vers E[f (X)]. De plus par le théorème central limite, on a une
1
vitesse de convergence en 1/N 2 indépendante de la dimension d.

Projet 5 : Calculer dans le modèle de Black-Scholes multidimensionnel le put, le

spread-put européen par la méthode de quantification et comparer les résultats avec la
méthode de Monte-Carlo.
Chapitre 2

Quantification d’une chaine de

Markov et applications

Dans ce chapitre, on considère une chaine de Markov (Xk )0≤k≤n à valeurs dans Rd
de probabilités de transition Pk (x, dx0 ) (de k − 1 à k), k = 1, . . . , n, et de distribution
initiale µ pour X0 . Notons alors que la distribution jointe de (X0 , . . . , Xn ) est égale à
µ(dz0 )P1 (z0 , dz1 ) . . . Pn (zn−1 , dzn ).
On s’intéresse à l’approximation par quantification de cette chaine de Markov, i.e.
à l’approximation de la distribution du processus (Xk )0≤k≤n par la distribution d’un
processus (X̂k )0≤k≤n à valeurs dans un espace d’état fini et prenant en compte la
loi de probabilité du processus. Une approche naive consisterait en la quantification
du vecteur aléatoire (X0 , . . . , Xn ) dans Rd(n+1) selon la méthode décrite au chapitre
précédent. Mais d’après le théorème de Zador, pour un nombre total de points N dans
la grille temps-espace, on obtiendrait une erreur de quantification de l’ordre N −1/nd :
c’est bien évidemment très lent lorsque n est grand.
On propose une approche basée sur le fait qu’une chaine de Markov est complètement
caractérisée par sa distribution initiale et par ses probabilités de transition. L’idée est
alors de quantifier la loi initiale de X0 et les probabilités conditionnelles de Xk sa-
chant Xk−1 . On verra alors que cela conduit à une erreur d’approximation d’ordre
n1+1/d /N 1/d .
Dans la suite, on utilise les notations usuelles νf , P f , νP , P Q pour ν mesure, P, Q
probabilités de transition et f fonction mesurable, i.e.
Z Z
νf = f (x)ν(dx), P f (x) = f (x0 )P (x, dx0 )
Z Z
0 0
νP (dx ) = ν(dx)P (x, dx ), P Q(x0 , dx2 ) = P (x0 , dx1 )Q(x1 , dx2 ).

26
QUANTIFICATION D’UNE CHAINE DE MARKOV 27

Pour toute fonction borélienne f de Rd dans R, on note

On définit l’ensemble
n o
BL1 (Rd ) = f : Rd → R, k f k∞ ≤ 1 et [f ]lip ≤ 1 .

On dit qu’une probabilité de transition P sur Rd est Lipschitzienne de rapport [P ]lip

< +∞ si pour toute fonction Lipschitzienne f de rapport [f ]lip < +∞, on a

P f (x) − P f (x0 ) ≤ [P ]lip [f ]lip |x − x0 |, ∀x, x0 ∈ Rd .

2.1 Quantification marginale

2.1.1 Méthode
La méthode de quantification marginale consiste dans une première étape à quanti-
fier vectoriellement les marginales de la chaine de Markov. Précisément, à chaque date
k = 0, . . . , n, on se donne une grille xk = (x1k , . . . , xN k d
k ) de Nk points dans R à laquelle
est associée une partition de Voronoi Ci (xk ), i = 1, . . . , Nk . On considère alors pour
tout k le quantifieur de Voronoi de Xk sur la grille xk :
Nk
X
X̂k = Projxk (Xk ) := xik 1Ci (xk ) (Xk ).
i=1

Notons que l’application projection n’étant pas injective, le processus (X̂k ) construit
ainsi ne conserve pas la propriété de Markov de (Xk ). On définit cependant des matrices
de probabilité de transition P̂k = (pijk ), k = 1, . . . , n, de façon canonique à partir des
X̂k par :

βkij
pij
k := P[X̂k = xjk |X̂k−1 = xik−1 ] = , i = 1, . . . , Nk−1 , j = 1, . . . , Nk ,
pik−1

où

βkij = P[(X̂k , X̂k−1 ) = (xjk , xik−1 )] = P[(Xk , Xk−1 ) ∈ Cj (xk ) × Ci (xk−1 )]

pik−1 = P[X̂k−1 = xik−1 ] = P[Xk−1 ∈ Ci (xk−1 )].

sont les masses des cellules de Voronoi du couple (Xk−1 , Xk ) (resp. Xk−1 ). On définit
aussi la loi de probabilité discrète µ̂ (de poids µ̂i , i = 1, . . . , N0 ) de X̂0 quantifieur de
Voronoi de X0 de loi µ :

µ̂i = pi0 = P[X̂0 = xi0 ] = P[X0 ∈ Ci (x0 )], i = 1, . . . , N0 .

QUANTIFICATION D’UNE CHAINE DE MARKOV 28

On approxime alors la loi µP1 . . . Pn de (X0 , . . . , Xn ) par la loi discrète µ̂P̂1 . . . P̂n .
La qualité de cette approximation est estimée en fonction des erreurs de quantification
à chaque date et mesurée comme suit : on introduit l’ensemble
n o
d
Sn+1 = φ : (Rd )n+1 → R, φ(z0 , . . . , zn ) = f0 (z0 ) . . . fn (zn ) où fi ∈ BL1 (Rd )

et on fait l’hypothèse que les probabilités de transitions Pk de la chaine de Markov

(Xk ) sont Lipchitziennes. On pose alors

[P ]lip = max [Pk ]lip

k=1,...,n

Nous discuterons plus tard cette hypothèse (voir paragraphe 2.1.2).

Afin de mettre clairement en évidence les techniques de preuve utilisées, nous com-
mençons par regarder l’erreur d’approximation d’une probabilité de transition Pk par
P̂k à la date k.

Proposition 2.1.1 Pour tout φ Lipschitzienne sur Rd , on a

Pk+1 φ(Xk ) − P̂k+1 φ(X̂k ) ≤ [Pk+1 ]Lip [φ]Lip Xk − X̂k + [φ]Lip Xk+1 − X̂k+1 .
2 2 2

Preuve. On écrit
h i
Pk+1 φ(Xk ) − P̂k+1 φ(X̂k ) ≤ Pk+1 φ(Xk ) − E Pk+1 φ(Xk )| X̂k
2 2
h i
+ E Pk+1 φ(Xk )| X̂k − P̂k+1 φ(X̂k )
2
= I1 + I2 .

Par définition-caractérisation de l’espérance conditionnelle dans L2 , on a

I1 ≤ Pk+1 φ(Xk ) − Pk+1 φ(X̂k ) ≤ [Pk+1 ]Lip [φ]Lip Xk − X̂k ,

2 2

d’après la condition de Lipschitz sur Pk+1 . D’autre part, on a

h i h i
I2 = E E [ φ(Xk+1 )| Xk ]| X̂k − E φ(X̂k+1 ) X̂k
2
h i h i
= E φ(Xk+1 )| X̂k − E φ(X̂k+1 ) X̂k
2

≤ φ(Xk+1 ) − φ(X̂k+1 ) ≤ [φ]Lip Xk+1 − X̂k+1 ,

2 2

où on a utilisé dans la deuxième égalité le fait que X̂k est σ(Xk )-mesurable, et dans la
première inégalité la propriété de L2 -contraction de l’espérance conditionnelle (ici par
rapport à X̂k ). On obtient ainsi la relation voulue. 2
Plus généralement, on a l’erreur d’approximation suivante de µP1 . . . Pn par µ̂P̂1 . . . P̂n .
QUANTIFICATION D’UNE CHAINE DE MARKOV 29

d
Théorème 2.1.1 Pour tout φ ∈ Sn+1 on a
n
!
X [P ]n−k+1
lip
−1
µP1 . . . Pn − µ̂P̂1 . . . P̂n φ ≤ 1+ k Xk − X̂k k2 ,
[P ]lip − 1
k=0

avec la convention (um − 1)/(u − 1) = m quand u = 1.

Preuve. Pour tout φ = f0 . . . fn ∈ Sn+1 d , on introduit les fonctions measurables pour

k = 1, . . . , n sur Rd (resp. sur la grille xk ) par :

Z
vk (z) = fk (z) fk+1 (zk+1 ) . . . fn (zn )Pk+1 (z, dzk+1 ) . . . Pn (zn−1 , dzn ),
Z
v̂k (z) = fk (z) fk+1 (zk+1 ) . . . fn (zn )P̂k+1 (z, dzk+1 ) . . . P̂n (zn−1 , dzn ),

avec la convention que pour k = n, vn = v̂n = fn . Notons alors que ces fonctions
s’écrivent sous forme récursive par :

vk (z) = fk (z)Pk+1 vk+1 (z) = fk (z)E[vk+1 (Xk+1 )|Xk = z] (2.1)

v̂k (z) = fk (z)P̂k+1 v̂k+1 (z) = fk (z)E[v̂k+1 (X̂k+1 )|X̂k = z], (2.2)

pour k = 1, . . . , n − 1 et que
h i
µP1 . . . Pn − µ̂P̂1 . . . P̂n φ = E v0 (X0 ) − v̂0 (X̂0 ) .

On va montrer alors le résultat par induction sur vk (Xk ) − v̂k (X̂k ) .

Etape 1. On a clairement kvk k∞ ≤ 1. De plus, d’après (2.1), on a :

[vk ]lip ≤ [fk ]lip + [Pk+1 vk+1 ]lip

≤ 1 + [P ]lip [vk+1 ]lip .

Puisque [vn ]lip ≤ 1, on obtient par induction :

n
X
n−l
[P ]n−k+1
lip
−1
[vk ]lip ≤ [P ]lip = (2.3)
[P ]lip − 1
l=k

pour tous k = 0, . . . , n.
Etape 2. D’après (2.1)-(2.2), on peut écrire :

vk (Xk ) − v̂k (X̂k ) ≤ vk (Xk ) − E[vk (Xk )|X̂k ]

2 2
h i
+ E fk (Xk ) − fk (X̂k ) Pk+1 vk+1 (Xk ) X̂k
h 2 i
+ E fk (X̂k ) Pk+1 vk+1 (Xk ) − P̂k+1 v̂k+1 (X̂k ) X̂k
1

= I1 + I2 + I3 . (2.4)
QUANTIFICATION D’UNE CHAINE DE MARKOV 30

Par la définition même de l’espérance conditionnelle, on a :

I1 ≤ vk (Xk ) − vk (X̂k ) ≤ [vk ]lip Xk − X̂k .

2 2

Comme l’espérance conditionnelle (ici par rapport à X̂k ) est une L2 -contraction et vk+1
est bornée par 1, on a :

I2 ≤ fk (Xk ) − fk (X̂k ) ≤ Xk − X̂k .

2 2

Puisque X̂k est σ(Xk )-measurable et en rappelant que fk est bornée par 1, on a :

I3 ≤ vk+1 (Xk+1 ) − v̂k+1 (X̂k+1 ) .

En substituant ces estimations de I1 , I2 et I3 dans (2.4), on a

vk (Xk ) − v̂k (X̂k ) ≤ 1 + [vk ]lip Xk − X̂k + vk+1 (Xk+1 ) − v̂k+1 (X̂k+1 ) .
2 2 2

Comme vn (Xn ) − v̂n (X̂n ) ≤ Xn − X̂n , une récurrence immédiate donne :

2 2

n
X
vk (Zk ) − v̂k (Ẑk ) ≤ 1 + [vl ]lip Xl − X̂l .
1 2
l=k

On obtient le résultat voulu en prenant k = 0 et en substituant l’estimation (2.3). 2

2.1.2 Exemple
Un exemple courant de chaine de Markov est donné par la dynamique :

Xk+1 = F (Xk , εk+1 ), k = 0, . . . , n − 1.

où (εk )k est une suite de variables i.i.d. centrée et de carré intégrable (e.g. un bruit blanc
gaussien standard) indépendant de X0 et F est une fonction mesurable correspondant
au schéma d’Euler de pas δ = T /n d’une diffusion sur [0, T ] :
√
F (x, ε) = x + b(x)δ + σ(x) δε.

Notons P = Pk , k = 0, . . . , n, la probabilité de transition de cette chaine de Markov

homogène. Le résultat suivant montre la propriété de Lipschitz de P .

Proposition 2.1.2 Supposons que les coefficients b et σ soient Lipschitziens sur Rd .

Alors il existe une constante notée [F ]lip telle que

[P ]lip ≤ [F ]lip ≤ 1 + cδ, (2.5)

kF (x, ε1 ) − F (x0 , ε1 )k2 ≤ [F ]lip |x − x0 |, ∀x, x0 ∈ Rd (2.6)

où c est une constante (dépendant de T , [b]lip , [σ]lip , E|ε1 |2 ) mais indépendante de δ.
QUANTIFICATION D’UNE CHAINE DE MARKOV 31

Preuve. Pour tous x, x0 , on a

2
F (x, ε1 ) − F (x0 , ε1 ) = |x − x0 |2 + |b(x) − b(x0 )|2 δ 2 + |σ(x) − σ(x0 )|2 δε21
√
+ (x − x0 ).(b(x) − b(x0 ))δ + (x − x0 ).(σ(x) − σ(x0 )) δε1
+ (b(x) − b(x0 )).(σ(x) − σ(x0 ))δ 3/2 ε1 .
Sous la condition de Lipschitz sur b, σ et puisque E[ε1 ] = 0, E[|ε1 |2 ] < +∞, on en
déduit que
2
E F (x, ε1 ) − F (x0 , ε1 ) ≤ |x − x0 |2 (1 + cδ)
d’où (2.6) avec [F ]lip ≤ 1+cδ. Finalement, en notant que pour toute fonction mesurable
f sur Rd , on a P f (x) = E[f (F (x, ε1 ))], on en déduit [P ]lip ≤ [F ]lip 2

2.1.3 Quantification optimale

L’estimation d’erreur obtenue dans le théorème 2.1.1 est valable pour n’importe
quelle grille xk à chaque date k. Pour minimiser cette borne d’erreur sur l’approxima-
tion de la loi de (X0 , . . . , Xn ), on va chercher à minimiser à chaque date k l’erreur de
quantification, i.e. appliquer la quantification optimale à chaque marginale Xk . Cette
phase d’optimisation à chaque date k est menée selon la méthode décrite au chapitre
précédent. Un cas particulièrement intéressant pour les calculs est lorsque le processus
X est stationnaire et donc chaque marginale Xk est identiquement distribuée. En effet
dans ce cas une seule procédure d’optimisation pour X0 est requise. Sinon de façon
générale, les phases d’optimisation (sélection + apprentissage) de l’algorithme de Ko-
honen à chaque date k peuvent se conduire indépendamment dès lors qu’on a simulé
un échantillon de (X0 , . . . , Xn ). Les probabilités de transition pij
k sont estimées par
estimation de Monte-Carlo des probabilités jointes βkij et marginales pik−1 .
D’après le théorème de Zador, pour une quantification optimale de chaque mar-
ginale Xk , et avec un nombre total de points N à répartir entre les n + 1 dates k =
0, . . . , n, on obtient dans le cas typique de l’exemple 2.1.2 un taux de convergence de
l’ordre :
n1+1/d
.
N 1/d

2.2 Application à l’arrêt optimal et aux options américaines

On note Tn l’ensemble des temps d’arrêts par rapport à la filtration (Fk ) engendrée
par (Xk ) à valeurs dans T = {0, . . . , n}. Pour simplifier, on suppose que F0 est trivial,
i.e. X0 = x0 est déterministe et donc connu à la date 0. Etant donné une fonction
mesurable f sur T × Rd , on considère le problème d’arrêt optimal à horizon fini n :
U0 = sup E[f (τ, Xτ )]
τ ∈Tn
QUANTIFICATION D’UNE CHAINE DE MARKOV 32

Ce problème est motivé en finance par le calcul d’options américaines (en fait ici
bermudéennes car les dates d’exercice de l’options sont discrètes). Dans ce cas, (Xk ), k
= 0, . . . , n, représente le processus de prix d’une action aux dates tk = kδ, où δ > 0 est
le délai entre deux dates possibles d’exercice d’une option de flux g(Xk ), r est le taux
d’intérêt et f (k, x) = e−rtk g(x). Dans le cas d’un modèle à volatilité stochastique, (Xk )
peut représenter aussi le couple prix-volatilité. Par exemple, (Xk ) est la discrétisation
par schéma d’Euler de pas δ d’un modèle de diffusion pour le couple prix-volatilité
(voir exemple 2.1.2).
On va adopter la méthode de la programmation dynamique pour calculer U0 . On
introduit l’enveloppe de Snell de (f (k, Xk )) :

Uk = ess sup E[f (τ, Xτ )|Fk ], k = 0, . . . , n,

τ ∈Tk,n

où Tk,n désigne l’ensemble des temps d’arrêts à valeurs dans {k, . . . , n}. Uk est donc en
finance le prix de l’option bermudéenne à la date k. Le principe de la programmation
dynamique stipule que Uk s’exprime sous forme récursive par :

Un = f (n, Xn )
Uk = max (f (k, Xk ) , E[Uk+1 |Fk ]) , k = 0, . . . , n − 1.

Ceci signifie qu’à chaque date k, on a le choix entre arréter le processus et recevoir
comme gain f (k, Xk ) ou continuer et recevoir comme gain espéré E[Uk+1 |Fk ]. De plus,
par la propriété de Markov de (Xk ), pour toute date k, il existe une fonction mesurable
vk sur Rd telle que

Uk = vk (Xk ).

On doit donc calculer la suite de fonctions (vk ) qui s’exprime par le principe de la
programmation dynamique sous forme récursive comme :

vn (x) = f (n, x), ∀x ∈ Rd

vk (x) = max (f (k, x) , E[vk+1 (Xk+1 )|Xk = x]) , ∀x ∈ Rd , k = 0, . . . , n − 1.

On est donc ramené à un calcul successif d’espérances conditionnelles faisant intervenir

les probabilités de transitions des Xk .
Nous allons approximer les Uk par une quantification marginale de (Xk ) telle que
décrite au paragraphe précédent. Pour chaque k = 0, . . . , n, on note par X̂k le quan-
tifieur de Voronoi de Xk sur une grille xk = (x1k , . . . , xN k
k ) associée à une partition de
Voronoi Ci (xk ), i = 1, . . . , Nk . Notons qu’à la date k = 0, puisque X0 est supposé
déterministe égal à x0 , on choisit évidemment N0 = 1 et X̂0 = x0 . On approxime alors
QUANTIFICATION D’UNE CHAINE DE MARKOV 33

la suite de fonctions (vk ) par la suite de fonctions (v̂k ) où v̂k défini sur la grille xk se
calcule explicitement de façon récursive par :

v̂n (x) = f (n, x) ∀x ∈ xn

v̂k (x) = max f (k, x) , E[v̂k+1 (X̂k+1 )|X̂k = x] , ∀x ∈ xk , k = 0, . . . , n − 1,

Ceci s’écrit encore algorithmiquement comme :

v̂n (xin ) = f (n, xin ) i = 1, . . . , Nn

 
Nk+1
X ij
v̂k (xik ) = max f (k, xik ) , pk+1 v̂k+1 (xjk+1 ) , i = 1, . . . , Nk , k = 0, . . . , n − 1,
j=1

où P̂k = (pij

k ) est la matrice de probabilité de transition de X̂k−1 à X̂k . Ceci conduit à
une approximation des Uk par

Ûk = v̂k (X̂k ), k = 0, . . . , n.

On obtient alors l’estimation d’erreur suivante. On fait l’hypothèse que pour tout
k, les fonctions fk := f (k, .) sont Lipschiztiennes et on pose

[f ]lip = max [fk ]lip .

k=0,...,n

On suppose aussi que les probabilités de transition Pk de la chaine de Markov sont

Lipschitziennes.

Théorème 2.2.2 Pour tout k = 0, . . . , n, on a

n
X [P ]n−j+1
lip
−1
Uk − Ûk ≤ [f ]lip Xj − X̂j
2 [P ]lip − 1 2
j=k

Preuve. Le schéma de la preuve est similaire à celui du théorème 2.1.1.

Etape 1. D’après l’expression récursive de vk , on a :

[vk ]lip ≤ [fk ]lip + [Pk+1 vk+1 ]lip

≤ [f ]lip + [P ]lip [vk+1 ]lip .

Puisque [vn ]lip ≤ [f ]lip , on obtient par induction :

n n−k+1 − 1
X
n−l
[P ]lip
[vk ]lip ≤ [f ]lip [P ]lip = [f ]lip , k = 0, . . . , n. (2.7)
[P ]lip − 1
l=k
QUANTIFICATION D’UNE CHAINE DE MARKOV 34

Etape 2. D’après l’expression récursive de vk et en utilisant l’inégalité triviale | max(a, b)−

max(a0 , b0 )| ≤ max(|a − a0 |, |b − b0 |), on a

Uk − Ûk = vk (Xk ) − v̂k (X̂k )

2 2

≤ fk (Xk ) − fk (X̂k ) + Pk+1 vk+1 (Xk ) − P̂k+1 v̂k+1 (X̂k )

2 2

≤ [f ]lip Xk − X̂k + Pk+1 vk+1 (Xk ) − E[Pk+1 vk+1 (Xk )|X̂k ]

2 2

+ E[Pk+1 vk+1 (Xk )|X̂k ] − P̂k+1 v̂k+1 (X̂k )

≤ [f ]lip Xk − X̂k + Pk+1 vk+1 (Xk ) − Pk+1 vk+1 (X̂k )

2 2

+ vk+1 (Xk+1 ) − v̂k+1 (X̂k+1 ) ,

où on a utilisé dans la dernière inégalité la définition même de l’espérance conditionnelle

et la loi des espérances conditionnelles itérées avec le fait que X̂k est σ(Xk )-mesurable.
On obtient alors

Uk − Ûk ≤ [f ]lip + [P ]lip [vk+1 ]lip Xk − X̂k + Uk+1 − Ûk+1
2 2 2

Puisque Un − Ûn ≤ [f ]lip Xn − X̂n , une induction directe donne :

2 2

n
X
Uk − Ûk ≤ [f ]lip + [P ]lip [vj+1 ]lip Xj − X̂j
2 2
j=k

avec la convention que [vn+1 ]lip = 0. En substituant (2.7) dans cette inégalité, on a
l’estimation voulue. 2

Remarque 2.2.1 D’après le théorème de Zador, pour une quantification optimale

de chaque marginale Xk , et avec un nombre total de points N à répartir entre les
n + 1 dates k = 0, . . . , n, on obtient dans le cas typique de l’exemple 2.1.2 un taux de
convergence de l’ordre :

n1+1/d
.
N 1/d

Projet 6. Calculer dans un modèle à volatilité stochastique le prix du Put américain.

Chapitre 3

Filtrage et quantification

Le filtrage consiste à estimer l’état d’un système dynamique (évoluant au cours du

temps) à partir d’observations bruitées. Formellement, on a un signal (Xk ), k ≥ 0, qui
représente un système qu’on cherche à estimer ou à prédire : typiquement, X peut être
l’évolution de la température, d’un véhicule (avion, sous-marin ...) ou encore en finance
la volatilité d’un actif risqué, et l’aléa du signal est dû aux incertitudes du modèle. On
dispose alors d’une suite d’observations (Yk ), k ≥ 0, obtenues à partir d’informations
partielles et bruitées du signal. Ce sont typiquement les capteurs sensoriels de détection
du véhicule ou encore en finance le prix de l’actif risqué. Le bruit des observations
représente les incertitudes du modèle comme les erreurs d’observation. L’objectif est
de calculer :
- la loi de Xn sachant Y0 , . . . , Yn : c’est le filtrage
- la loi de Xn sachant Y0 , . . . , Yn−1 : c’est la prédiction.
Nous étudions d’abord le cas dit du filtre linéaire, i.e. lorsque le couple signal/ob-
servation forme un suite de variables gaussiennes, et pour lequel la résolution du filtre
est explicite, et nous servira de test pour les illustrations numériques. Nous considérons
ensuite le cas général, dit du filtre non linéaire qui conduit à des équations d’état en
dimension infinie. On utilisera alors les méthodes de quantification pour approximer
numériquement le filtre.

3.1 Filtrage linéaire

3.1.1 Rappel sur les variables gaussiennes
Les variables aléatoires gaussiennes et les systèmes linéaires gaussiens jouent un
rôle important dans la modélisation et le traitement du signal. Par exemple, d’après le
théorème central limite, la distribution gaussienne est universelle en ce sens que tout
phénomène résultant de l’accumulation d’un grand nombre de petits aléas indépendants

35
FILTRAGE ET QUANTIFICATION 36

suit approximativement une loi gaussienne. Ceci explique en partie que les variables
aléatoires gaussiennes sont l’un des modèles stochastiques fondamentaux. Ces distri-
butions offrent aussi l’avantage d’être caractérisées uniquement par deux paramètres :
la moyenne et la matrice de covariance.
Un vecteur aléatoire Z = (Z 1 , . . . , Z d ) de dimension d sur (Ω, F, P) est dit gaussien
si toute combinaison linéaire des composantes du vecteur X est une variable aléatoire
réelle gaussienne (normale), i.e. pour tout u ∈ Rd , u.Z est gaussien. On note Z ∼
N (µ, Σ) où m = E(Z) est la moyenne de Z et Σ sa matrice (symétrique-positive) de
covariance :

Σij = E[(Z i − E(Z i )(Z j − E(Z j ))].

Sa fonction caractéristique est

iu.Z 1
ΦZ (u) := E[e ] = exp iu.m − u.Σu .
2
Si la matrice Σ est inversible, la loi de Z admet une densité :

1 1 −1
pZ (z) = dp exp − (z − m).Σ (z − m) .
(2π) 2 det(Σ) 2

Soit Z = (X, Y ) un vecteur gaussien de dimension p + q de matrice de covariance :

!
ΣX ΣXY
Σ = , ( avec ΣXY = Σ0Y X ).
ΣY X ΣY

X et Y sont indépendants ssi ΣXY = 0. On a aussi la propriété fondamentale qui nous

servira plus tard sur la loi conditionnelle.

Proposition 3.1.1 Si la matrice ΣY est inversible, alors la loi de X sachant Y est

gaussienne de moyenne (linéaire en Y )

E[X|Y ] = E[X] + ΣXY Σ−1

Y
(Y − E[Y ]),

et de matrice de covariance (indépendante de Y )

ΣX|Y := E (X − E[X|Y ])(X − E[X|Y ])0 = ΣX − ΣXY Σ−1

Y
ΣY X .

Preuve. On note mX = E[X], mY = E[Y ], X̂(y) le candidat pour E[X|Y = y] :

X̂(y) = mX + ΣXY Σ−1

Y
(y − mY ),

et R celui pour ΣX|Y :

R = ΣX − ΣXY Σ−1
Y
ΣY X .
FILTRAGE ET QUANTIFICATION 37

On va montrer que la fonction caractéristique ΦX|Y =y de la loi conditionnelle de X

sachant Y = y est égale à

1
exp iu.X̂(y) − [Link] ,
2

i.e. c’est la loi gaussienne de moyenne X̂(y) et de matrice de covariance R. Pour cela,
on note que ΦX|Y =y est caractérisée par :

ΦX,Y (u, v) = E eiu.X+iv.Y = E eiv.Y E eiu.X Y

Z
= eiv.y ΦX|Y =y (u)pY (y)dy.

D’autre part, on vérifie aisément en substituant les expressions de X̂(y) et R, et les

expressions de la fonction caractéristique de Y et (X, Y ) que
Z
iv.y 1
e exp iu.X̂(y) − [Link] pY (y)dy
2

1 1
= exp [Link] + [Link] − u.ΣX u − u.ΣXY v − v.ΣY v
2 2
= ΦX,Y (u, v).

Par injectivité de la transformée de Fourier, ceci prouve que

1
ΦX|Y =y (u) = exp iu.X̂(y) − [Link] .
2
2

3.1.2 Filtre de Kalman-Bucy

Le modèle linéaire gaussien pour le couple signal-observation est défini par :

Xn = AXn−1 + Bεn
Yn = CXn + ηn ,

où A, B et C sont des matrices constantes de dimensions appropriées.

On suppose que (X0 , ε, η) sont des variables indépendantes gaussiennes. Les bruits
gaussiens εn , ηn , n ≥ 0 sont centrées, et on note Σεn et Σηn leurs matrices de covariance,
supposées inversibles. La moyenne et la variance de la variable gaussienne X0 est notée
m0 et ΣX0 .
On note par Πn la loi du filtre et Π− n celle de la prédiction :

Πn (dx) = P(Xn ∈ dx|Y0 , . . . , Yn )

Π−
n (dx) = P(Xn ∈ dx|Y0 , . . . , Yn−1 ).
FILTRAGE ET QUANTIFICATION 38

Notons que l’espace vectoriel engendré par (X0 , . . . , Xn , Y0 , . . . , Yn ) est égal à celui
engendré par (X0 , ε0 , . . . , εn , η0 , ηn ) qui est gaussien par hypothèse. On en déduit que
Πn et Π−
n sont des lois gaussiennes :

Πn (dx) = N (X̄n , Σ̄n )

Π− − −
n (dx) = N (X̄n , Σ̄n )

de moyennes et variances conditionnelles notées :

X̄n = E[Xn |Y0 , . . . , Yn ], Σ̄n = E[(Xn − X̄n )(Xn − X̄n )0 ]

X̄n− = E[Xn |Y0 , . . . , Yn−1 ], Σ̄− − − 0
n = E[(Xn − X̄n )(Xn − X̄n ) ].

Nous allons montrer que le calcul de ces moyennes et variances conditionnelles peut
être mené explicitement de manière inductive selon deux étapes :
• Une étape de correction/mise à jour
! !
X̄n− X̄n
−→ ,
Σ̄−
n Σ̄n

qui utilise la nouvelle observation Yn de la date n,

• Une étape de prédiction
! !
−
X̄n X̄n+1
−→ ,
Σ̄n Σ̄−
n+1

qui utilise la transition du signal de la date n à n + 1.

Partant d’une condition initiale donnée par X̄0− = m0 , Σ̄− X
0 = Σ0 , on a donc un
calcul explicite du filtre (et de la prédiction), appelé filtre de Kalman-Bucy.
Etape de correction/mise à jour :
Notons que puisque les vecteurs (Xn , Y0 , . . . , Yn−1 ) et (Y0 , . . . , Yn ) sont gaussiens, il en
est de même de X̄n− et de la variable

Ȳn− = E[Yn |Y0 , . . . , Yn−1 ].

On en déduit aussi que le couple de vecteurs

(X̃n , Ỹn ) = (Xn − X̄n− , Yn − Ȳn− )

est gaussien centré, avec une loi gaussienne conditionnelle caractérisée d’après la pro-
position 3.1.1 par :

E[X̃n |Ỹn ] = ΣX̃n Ỹn Σ−1 Ỹn (3.1)

Ỹn
h i
0
E (X̃n − E[X̃n |Ỹn ])(X̃n − E[X̃n |Ỹn ]) = ΣX̃n − ΣX̃n Ỹn Σ−1 ΣỸn X̃n . (3.2)
Ỹn
FILTRAGE ET QUANTIFICATION 39

Par définition, on a

ΣX̃n = Σ̄−
n. (3.3)

De plus, notons que Ȳn− = E(CXn + ηn |Y0 , . . . , Yn−1 ) = C X̄n− , et Ỹn = C X̃n + ηn . On
a donc

ΣX̃n Ỹn = E(X̃n Ỹn0 ) = Σ̄−

nC
0
(3.4)
ΣỸn = C Σ̄− 0 η
n C + Σn . (3.5)

D’autre part, puisque pour toute fonction mesurable ϕ :

h i
E X̃n ϕ(Y0 , . . . , Yn−1 ) = E [(Xn − E[Xn |Y0 , . . . , Yn−1 ]) ϕ(Y0 , . . . , Yn−1 )] = 0,

alors X̃n et (Y0 , . . . , Yn−1 ) sont des variables gaussiennes noncorrelés, et donc indépendantes.
On en déduit
h i h i
E X̃n |Y0 , . . . , Yn−1 , Yn = E X̃n |Y0 , . . . , Yn−1 , Ỹn = E[X̃n |Ỹn ].

On a alors

X̄n = X̄n− + E Xn − X̄n− |Y0 , . . . , Yn = X̄n− + E[X̃n |Ỹn ]

= X̄n− + Σ̄− 0 − 0 η −1 −
n C (C Σ̄n C + Σn ) (Yn − C X̄n ),

avec (3.1) et en notant que Ỹn = C X̃n + εn = Yn − C X̄n− . En écrivant

Xn − X̄n = Xn − X̄n− − (X̄n − X̄n− ) = X̃n − E[X̃n |Ỹn ],

et en utilisant (3.2)-(3.3)-(3.4)-(3.5), on obtient

Σ̄n = Σ̄− − 0 − 0 η −1 −
n − Σ̄n C (C Σ̄n C + Σn ) C Σ̄n .

On résume les résultats ci-dessus en écrivant les relations de correction/mise à jour :

X̄n = X̄n− + Kn (Yn − C X̄n− ) (3.6)

Σ̄n = [I − Kn C]Σ̄−
n, (3.7)

où Kn est la matrice dite de gain :

Kn = Σ̄− 0 − 0 η −1
n C (C Σ̄n C + Σn ) . (3.8)

Etape de prédiction :
Cette étape est plus simple que la précédente car elle ne dépend plus des observations.
On écrit
−
X̄n+1 = E [Xn+1 |Y0 , . . . , Yn ] = AE [Xn |Y0 , . . . , Yn ] = AX̄n .
FILTRAGE ET QUANTIFICATION 40

On a alors aussi

Σ̄− − − 0

n+1 = E (Xn+1 − X̄n+1 )(Xn+1 − X̄n+1 )
= E (A(Xn − X̄n ) + Bεn )(A(Xn − X̄n ) + Bεn )0

= AΣ̄n A0 + BΣεn B 0 .

Les relations de prédiction s’écrivent donc :

−
X̄n+1 = AX̄n (3.9)
Σ̄− 0 ε 0
n+1 = AΣ̄n A + BΣn B . (3.10)

Remarque 3.1.1 Les suites (Σ− n ) et (Σn ) ne dépendent pas des observations (Yn ). Ils
peuvent donc être pré-calculées.

Exemple
Considérons l’exemple d’un modèle unidimensionnel signal/observation :

Xn = aXn−1 + εn
Yn = cXn + ηn ,

avec X0 , εn , ηn i.i.d. ∼ N (0, 1) et a, c ∈ R.

cΣ̄−
On a X̄0− = 0, Σ̄−
0 = 1 et donc d’après (3.6)-(3.7) et (3.8) : K0 = c Σ̄−
2
0
= c
1+c2
et
0 +1

K0
X̄0 = X̄0− + K0 (Y0 − cX̄0− ) = K0 Y0 , Σ̄0 = (1 − cK0 )Σ̄−
0 = .
c
cΣ̄−
A la date n, on a par définition de la matrice de gain Kn = c2 Σ̄−
n
. D’après l’étape
n +1
de prédiction (3.10), on a Σ−n = a
2
Σ̄n−1 2+−1. D’autre part, avec l’étape de correction
c Σ̄n Σ̄−
(3.7), on a Σ̄n = (1 − cKn )Σ̄n = 1 − c2 Σ̄− +1 Σ̄n = c2 Σ̄− +1 = Kn /c. On a donc cΣ̄−
− − n
n
n n
= a2 Kn−1 + c, d’où la relation de récurrence sur la matrice de gain :

a2 Kn−1 + c c
Kn = , K0 = .
c(a2 Kn−1 + c) + 1 1 + c2

En combinant (3.6) et (3.9), on a finalement

X̄n = aX̄n−1 + Kn (Yn − caX̄n−1 ), X̄0 = K0 Y0 ,

Kn
Σ̄n = .
c
FILTRAGE ET QUANTIFICATION 41

3.2 Filtrage non linéaire

3.2.1 Description du modèle
Dans la suite, toutes les variables aléatoires sont définies sur un espace de proba-
bilité (Ω, F, P). On se place dans le cadre où le couple signal/observation (Xn , Yn )n≥0
défini sur l’espace mesurable produit (E × Rq ), avec (E, E) un espace mesurable, satis-
fait :
• (Xn )n est une chaine de Markov de probabilité de transition Pn de n − 1 à n, i.e. :

P[Xn ∈ dx0 |X0 , . . . , Xn−1 ] = P[Xn ∈ dx0 |Xn−1 ],

Pn (x, dx0 ) = P[Xn ∈ dx0 |Xn−1 = x],

et de loi initiale µ0
• la suite (Yn )n vérifie l’hypothèse de canal sans mémoire, i.e.
? conditionnellement aux états cachés X0 , . . . , Xn , les observations Y0 , . . . , Yn sont
mutuellement indépendantes
? la loi conditionnelle de Yn sachant X0 , . . . , Xn ne dépend que de Xn , avec une
probabilité d’émission à densité (par rapport à la mesure de Lebesgue sur Rq ) :

P[Yn ∈ dy 0 |Xn = x0 ] = gn (x0 , y 0 )dy 0 .

La fonction x 7→ gn (x, Yn ) est appelée fonction de vraisemblance.

Posons X[0,n] = (X0 , . . . , Xn ), Y[0,n] = (Y0 , . . . , Yn ). La loi jointe de X[0,n] est :

n
Y

P X[0,n] ∈ dx[0,n] = µ0 (dx0 ) Pk (xk−1 , dxk )
k=0

D’après la formule de Bayes et l’hypothèse de canal sans mémoire, la loi jointe du

couple (X[0,n] , Y[0,n] ) est

P X[0,n] ∈ dx[0,n] , Y[0,n] ∈ dy[0,n]

= P Y[0,n] ∈ dy[0,n] |X[0,n] = x[0,n] P X[0,n] ∈ dx[0,n]
n
Y
= P X[0,n] ∈ dx[0,n] gk (xk , yk )dyk . (3.11)
k=0

En intégrant par rapport aux variables x = (x0 , . . . , xn ), on obtient la loi jointe des
observations Y[0,n] :
Z Z n
Y
P Y[0,n] ∈ dy[0,n] = ... P X[0,n] ∈ dx[0,n] gk (xk , yk )dyk
E E k=0
n
" #
Y
= E gk (Xk , yk ) dy[0,n] (3.12)
k=0
FILTRAGE ET QUANTIFICATION 42

Autrement dit, (Y0 , . . . , Yn ) admet pour densité :

n
" #
Y
y = (y0 , . . . , yn ) 7−→ γn (y) = E gk (Xk , yk ) .
k=0

Remarque 3.2.2 Notons que (Xn , Yn ) est une chaine de Markov. En effet, on a par
la formule de Bayes et l’hypothèse de canal sans mémoire :

P Xn ∈ dxn , Yn ∈ dyn |X[0,n−1] = x[0,n−1] , Y[0,n−1] = y[0,n−1]

P X[0,n] ∈ dx[0,n] , Y[0,n] ∈ dy[0,n]
=
P X[0,n−1] ∈ dx[0,n−1] , Y[0,n−1] ∈ dy[0,n−1]

P Y[0,n] ∈ dy[0,n] |X[0,n] = x[0,n] P X[0,n] ∈ dx[0,n]
=
P Y[0,n−1] ∈ dy[0,n−1] |X[0,n−1] = x[0,n−1] P X[0,n−1] ∈ dx[0,n−1]
Qn Qn
k=0 gk (xk , yk )dyk µ0 (dx0 ) Pk (xk−1 , dxk )
= Qn−1 Qk=0
n−1
k=0 gk (xk , yk )dyk µ0 (dx0 ) k=0 Pk (xk−1 , dxk )
= gn (xn , yn )dyn Pn (xn−1 , dxn ).

La probabilité de transition de la chaine de Markov (Xn , Yn ) est donc donnée par :

Qn ((x, y), dx0 dy 0 ) = Pn (x, dx0 )gn (x0 , y 0 )dy 0

et sa loi initiale est ν0 (dxdy) = µ0 (dx)g0 (x, y).

Exemple. Le cadre typique d’un tel schéma signal/observation est donné par le
système :

Xn = Fn (Xn−1 , εn ), n ≥ 1, X0 ∼ µ0
Yn = Gn (Xn , ηn ), n ≥ 0,

où Fn , Gn sont des fonctions mesurables, et (εn )n≥1 , (ηn )n≥0 sont des bruits blancs,
indépendants entre eux et indépendants de X0 . Dans ce cas, (Xn )n≥0 est une chaine
de Markov de probabilité de transition Pn donnée par :

Pn f (x) = E[f (Fn (x, εn ))], pour toute fonction mesurable bornée f.

De plus, comme η0 , . . . , ηn sont mutuellement indépendants et indépendants de X0 , . . . , Xn ,

l’hypothèse de canal sans mémoire pour les observations est satisfaite. En supposant
que pour tout x, la variable aléatoire Gn (x, ηn ) admet une densité, notée gn (x, y), on
a

P[Yn ∈ dy|Xn = x] = P[Gn (x, ηn ) ∈ dy] = gn (x, y)dy.

FILTRAGE ET QUANTIFICATION 43

Par exemple, si Gn est de la forme :

Gn (x, η) = hn (x) + η,

et si ηn admet une densité notée kn , alors on a

gn (x, y) = kn (y − hn (x)).

Un autre exemple est le cas en finance où (Xn ) représente le rendement et/ou la
volatilité non observable d’un actif risqué S observable. La dynamique du prix est
donnée par :
√

1 2
Sn+1 = Sn exp b(Xn ) − σ (Xn ) δ + σ(Xn ) δηn ,
2

obtenue par exemple par discrétisation selon un schéma d’Euler de pas δ d’un modèle à
volatilité stochastique. En posant Yn+1 = ln(Sn /Sn−1 ), on a le modèle d’observation :
√
Yn = b̂(Xn )δ + σ(Xn ) δηn ,

où on a posé b̂ = b − σ 2 /2. Si ηn est un bruit blanc gaussien centré réduit, alors la loi
de Yn sachant Xn = x admet pour densité :
!
1 (y − b̂(x)δ)2
gn (x, y) = p exp − .
2πσ 2 (x)δ 2σ 2 (x)δ

3.2.2 Equation du filtre

Dans la suite, on fixera les observations à (Y0 , . . . , Yn ) = (y0 , . . . , yn ) et pour sim-
plifier les notations, on supprimera les indices y. On notera ḡn (x) = gn (x, yn ).
On note par Πn la loi du filtre et Π−n celle de la prédiction :

Πn (dx) = P(Xn ∈ dx|Y0 = y0 , . . . , Yn = yn )

Π−
n (dx) = P(Xn ∈ dx|Y0 = y0 , . . . , Yn−1 = yn−1 ).

D’après l’expression (3.11) de la loi jointe (X[0,n] , Y[0,n] ) et celle (3.12) de la loi de Y[0,n] ,
on obtient par la formule de Bayes :
Qn
k=0 ḡk (xk ) P X[0,n] ∈ dx[0,n]
P X[0,n] ∈ dx[0,n] Y0 = y0 , . . . , Yn = yn | = .
E [ nk=0 ḡk (Xk )]
Q

Autrement dit, pour toute fonction test ϕ bornée mesurable sur E n , on a :

E [ϕ(X0 , . . . , Xn ) nk=0 ḡk (Xk )]

Q
E [ϕ(X0 , . . . , Xn )|Y0 = y0 , . . . , Yn = yn )] = .
E [ nk=0 ḡk (Xk )]
Q
FILTRAGE ET QUANTIFICATION 44

En particulier, pour une fonction test ϕ ne dépendant que de xn , on a :

Πn ϕ = E [ϕ(Xn )|Y0 = y0 , . . . , Yn = yn ]
E [ϕ(Xn ) nk=0 ḡk (Xk )]
Q
πn ϕ
= Q n = ,
E [ k=0 ḡk (Xk )] πn 1
où πn est la mesure positive, appelée filtre non normalisé, définie par :
n
" #
Y
πn ϕ = E ϕ(Xn ) ḡk (Xk ) .
k=0

De manière similaire, on a

Π−
n ϕ = E [ϕ(Xn )|Y0 = y0 , . . . , Yn−1 = yn−1 )]
h Qn−1 i
E ϕ(Xn ) k=0 ḡk (Xk ) π−ϕ
= hQ i = n− ,
n−1 πn 1
E k=0 ḡk (Xk )

où πn− est la mesure positive, appelée filtre prédictif non normalisé, définie par :
n−1
" #
Y
πn− ϕ = E ϕ(Xn ) ḡk (Xk ) .
k=0

Nous allons montrer qu’on peut obtenir une équation récurrente exprimant Πn en
fonction de Πn−1 . Pour cela, il suffit d’une équation récurrente sur πn en fonction de
πn−1 , puis de normaliser. On note P(E) l’ensemble des mesures de probabilités sur E
et M(E) l’ensemble des mesures positives sur E.

Théorème 3.2.1 La suite (Πn ) dans P(E) vérifie l’équation de récurrence en deux
étapes, partant de l’initialisation Π0 = µ0 :
• Etape de prédiction :

Πn−1 −→ Π− n = Πn−1 Pn ,

où par définition Πn−1 Pn (dx0 ) = E Πn−1 (dx)Pn (x, dx0 ) est l’action du noyau de pro-
R

babilité de transition Pn de Xn sur Πn−1 ,

• Etape de correction/mise à jour :
ḡn Π− ḡn Π−
Π−
n −→ Πn = R 0
n
− 0
= n
− ,
E ḡn (x )Πn (dx ) (ḡn Πn )1

qui pondère la mesure Π− − 0 0 − 0

n par la fonction de vraisemblance ḡn : (ḡn Πn )(dx ) = ḡn (x )Πn (dx ).
De manière équivalente, (Πn ) est solution du système dynamique dans P(E) :
Πn−1 Hn Πn−1 Hn
Πn = R
0
=
E Πn−1 Hn (dx ) (Πn−1 Hn )1
FILTRAGE ET QUANTIFICATION 45

où Hn est le noyau de prédiction-correction :

Hn (x, dx0 ) = ḡn (x0 )Pn (x, dx0 )

agissant sur la mesure Πn−1 par : Πn−1 Hn (dx0 ) = E Πn−1 (dx)Hn (x, dx0 ).
R

Preuve. Etape correction : Πn en fonction de Π−n.

On a pour toute fonction test ϕ :
n n−1
" # " #
Y Y
πn ϕ = E ϕ(Xn ) ḡk (Xk ) = E ϕ(Xn )ḡn (Xn ) ḡk (Xk )
k=0 k=0
= πn− ϕḡn = ḡn πn− ϕ,

où la dernière égalité exprime simplement le fait que

Z Z
− 0 − 0
πn ϕḡn = (ϕḡn )(x )πn (dx ) = ϕ(x0 )(ḡn .πn− )(dx0 ) = ḡn πn− ϕ.
E E

On a donc

πn = ḡn πn− .

Par normalisation, on obtient

πn ḡn π − ḡn Π−
Πn = = −n = −n
πn 1 πn ḡn Πn ḡn

Etape prédiction : Π−n en fonction de Πn−1 .

Par la propriété de Markov de (Xn ), on a
n−1 n−1
" # " " ##
Y Y
πn− ϕ = E ϕ(Xn ) ḡk (Xk ) = E E ϕ(Xn ) ḡk (Xk ) X[0,n−1 ]
k=0 k=0
n−1 n−1
" # " #
Y Y
= E E ϕ(Xn )| X[0,n−1 ] ḡk (Xk ) = E E [ ϕ(Xn )| Xn−1 ]] ḡk (Xk )
k=0 k=0
n−1
" #
Y
= E Pn ϕ(Xn−1 ) ḡk (Xk ) = πn−1 (Pn ϕ) = (πn−1 Pn )ϕ,
k=0

où la dernière égalité exprime simplement, comme conséquence de Fubini, le fait que :
Z Z Z
πn−1 (Pn ϕ) = (Pn ϕ)(x)πn−1 (dx) = ϕ(x0 )Pn (x, dx0 ) πn−1 (dx)
ZE Z E
E Z
0 0
= πn−1 (dx)Pn (x, dx ) ϕ(x ) = πn−1 Pn (dx0 )ϕ(x0 )
E E E
= (πn−1 Pn )ϕ.
FILTRAGE ET QUANTIFICATION 46

On a donc :

πn− = πn−1 Pn .

Finalement, pour la normalisation, en remarquant que

"n−1 #
Y
πn− 1 = E ḡk (Xk ) = πn−1 1,
k=0
on a
πn− πn−1 Pn
Π−
n = − = = Πn−1 Pn .
πn 1 πn−1 1
2
L’équation du filtre a été obtenue simplement par utilisation de la propriété de
Markov et de la formule de Bayes. C’est une équation non linéaire (à cause de l’étape
de normalisation) à valeurs dans P(E) et il est en général impossible de la résoudre
explicitement, sauf dans des cas particuliers de modèles linéaires gaussiens, où elle se
ramène à un système en dimension finie 2 : les équations du filtre de Kalman-Bucy.
Il faut donc avoir recours à des méthodes numériques et on présente ci-dessous une
approximation par quantification.
Exercice. Montrer que dans le cas de modèles linéaires gaussiens décrits au paragraphe
3.1.2, l’équation de prédiction/correction du théorème 3.2.1 permet de retrouver les
équations explicites du filtre de Kalman-Bucy.

3.2.3 Approximation par quantification

On se place dans le cas où l’espace d’états du signal E = Rd est continu. L’idée
basique est d’approximer l’équation d’évolution du filtre en dimension infinie dans
P(Rd ), par une équation d’évolution en dimension finie grâce à une quantification de
la chaine de Markov du signal. On procède selon les étapes suivantes :
Etape de quantification marginale de (Xk )
C’est la méthode décrite au chapitre précédent. A chaque date k = 0, . . . , n, on se
donne une grille xk = (x1k , . . . , xkNk ) de Nk points dans Rd à laquelle est associée une
partition de Voronoi Ci (xk ), i = 1, . . . , Nk . On considère alors pour tout k le quantifieur
de Voronoi de Xk sur la grille xk :
Nk
X
X̂k = Projxk (Xk ) := xik 1Ci (xk ) (Xk ).
i=1

On définit la loi de probabilité discrète µ̂0 (de poids µ̂i0 , i = 1, . . . , N0 ) de X̂0 :

µ̂i0 = pi0 = P[X̂0 = xi0 ] = P[X0 ∈ Ci (x0 )], i = 1, . . . , N0 .

FILTRAGE ET QUANTIFICATION 47

et les matrices de probabilité de transition P̂k = (pij

k ), k = 1, . . . , n :

pij
k := P[X̂k = xjk |X̂k−1 = xik−1 ] i = 1, . . . , Nk−1 , j = 1, . . . , Nk .

Ces poids µi0 , pij

k sont estimés par simulation de Monte-Carlo Xk , k = 0, . . . , n, ou bien
simultanément dans l’algorithme de Kohonen.
Etape d’approximation du filtre
On rappelle que les observations sont fixées à (Y0 , . . . , Yn ) = (y0 , . . . , yn ). Le filtre Πk
et le prédicteur Π−k sont approximés par les mesures de probabilité discrète Π̂k et Π̂k
−

de support xk , et définis par les équations d’évolution en dimension finie :

• Initialisation

Π̂0 = µ̂0

• Prédiction

Π̂−
k = Π̂k−1 P̂k , k ≥ 1,

• Correction

ḡk Π̂−
k
Π̂k = , k ≥ 1,
(ḡk Π̂−
k )1

Les étapes de prédiction-correction s’écrivent aussi sous forme :

Π̂k−1 Ĥk
Π̂k = , k ≥ 1,
(Π̂k−1 Ĥk )1

où Ĥk = (Ĥkij ) est la matrice de transition :

Ĥkij = ḡk (xjk )p̂ij

k, i = 1, . . . , Nk−1 , j = 1, . . . , Nk .

Autrement dit, les poids (Π̂ik ), i = 1, . . . , Nk , de Π̂k se calculent explicitement de

manière inductive, pour k = 1, . . . , n, selon :

Π̂i0 = µ̂i0 , i = 1, . . . , N0
PNk−1 i ij
i=1 Π̂k−1 Ĥk
Π̂jk = PNk PNk−1 i ij
, k = 1, . . . , n, , j = 1, . . . , Nk .
j=1 i=1 Π̂k−1 Ĥk

D’un point de vue pratique, la procédure d’implémentation algorithmique ci-dessus

se décompose comme suit :
Phase de calculs off-line : Quantification optimale du signal. Notons que cette
phase ne dépend pas des observations et requiert de :
FILTRAGE ET QUANTIFICATION 48

- spécifier la taille Nk des grilles xk pour k = 0, . . . , n, étant donné un nombre total de

points N = N0 + . . . + Nn .
- implémenter les grilles optimales (par l’algorithme de Kohonen) et les poids de tran-
sition associés (p̂ij
k ).
Un cas spécial : signal stationnaire. Dans ce cadre usuel de modèle de filtrage où la
distribution de Xk est la même à toute date k, on a seulement besoin de calculer la grille
optimale x∗ = {x1 , . . . , xN̄ } de la loi stationnaire µ0 de X0 , de taille N̄ = N/(n + 1).
Alors, xk = x∗ , k = 0, . . . , n, sont les grilles optimales pour chaque Xk . On estime la
probabilité µ̂0 de X̂0 = Projx∗ (X0 ), et on estime une seule matrice de probabilité de
transition :
(k) (k−1)
p̂ij ij
k = p̂0 = P[X̂0 = xj |X̂0 = xi ], 0 ≤ i, j ≤ N̄ ,
(k)
où X̂0 suit la loi de X̂0 . D’un point de vue numérique, la taille des paramètres à
stocker est divisée par un facteur n, ou de manière équivalente, la taille de la grille de
quantification optimale pour X0 peut être multipliée par n.
Phase de calculs on-line : étant donné un jeu d’observations y = (y0 , . . . , yn ), on
calcule les matrices quantifiées de prédiction-correction (Ĥk ), k = 1, . . . , n, puis les
filtres quantifiées (Π̂k ), k = 0, . . . , n. Pour toute fonction test ϕ, on calcule alors :
Nn
X
Π̂n ϕ = ϕ(xin )Π̂in .
i=1

Cette phase de calcul est instantanée.

Nous analysons à présent l’erreur et la convergence du filtre approximé par quan-

tification.
Nous imposons essentiellement deux types de conditions sur le modèle de signal-
observation. Nous supposons une condition de Lipschitz sur les probabilités de transi-
tion du signal :
(A1) Les probabilités de transition Pk , k = 1, . . . , n, sont Lipschitz de ratio [Pk ]Lip ,
i.e. pour toute fonction Lipschitzienne ϕ sur Rd , de ratio [ϕ]Lip , on a :

b ∈ Rd ,
|Pk ϕ(x) − Pk ϕ(x̂)| ≤ [Pk ]Lip [φ]Lip |x − x̂|, ∀x, x

et on pose [P ]Lip := maxk=1,...,n [Pk ]Lip .

On suppose aussi une condition de Lipschitz sur les fonctions de vraisemblance :
FILTRAGE ET QUANTIFICATION 49



 (i) Les fonctions gk , k = 1, . . . , n, sont bornées


et on pose kgk∞ := maxk=1,...,n kgk k∞






(A2) (ii) Il existe [gk ]Lip , k = 1, . . . , n, tels que ∀x, x̂ ∈ Rd , y ∈ Rq



|gk (x, y) − gk (x̂, y)| ≤ [gk ]Lip |x − x̂|,







et on pose [g]Lip := maxk=1,...,n [gk ]Lip .

On obtient alors la borne d’erreur suivante pour l’approximation du filtre par quan-
tification.

Théorème 3.2.2 Sous (A1) and (A2), étant donnée une observation (Y0 , . . . , Yn ) =
(y0 , . . . , yn ), on a :
n
kgkn∞ X
sup Πn φ − Π̂n φ ≤ An,k kXk − X̂k k2 , (3.13)
φ∈BL1 (Rd ) γn (y)
k=0

où γn (y) est la densité de (Y0 , . . . , Yn ) en y = (y0 , . . . , yn ) :

" n #
Y
γn (y) = E gk (Xk , yk )
k=0

et
!
n−k [g] [P ]n−k+1 −1
An,k = 2 [P ]Lip + Lip Lip
.
kgk∞ [P ]Lip − 1

Preuve. Etape 1 : représentation backward du filtre. On considère le filtre non norma-

lisé (πk ) dont l’équation d’évolution forward est :

π0 = µ0 , πk = πk−1 Hk , k = 1, . . . , n,

d’où
πn
Πn = et πn = µ0 H1 . . . Hn
πn 1
De cette expression symétrique, on introduit les noyaux de transition donnés par les
équations backward :

Rn = Id, Rk = Hk+1 Rk+1 , k = 0, . . . , n − 1,

de telle sorte que

πn = µ0 R0 .
FILTRAGE ET QUANTIFICATION 50

De manière similaire, le filtre quantifié s’exprime sous forme backward par :

π̂n
Π̂n = , avec π̂n = µ̂0 R̂0
π̂n 1
et

R̂n = Id, R̂k = Ĥk+1 R̂k+1 , k = 0, . . . , n − 1.

Etape 2 : approximation d’erreur du filtre non normalisé. On écrit pour toute fonction
test ϕ ∈ BL1 (Rd ),
h i
|πn ϕ − π̂n ϕ| = µ0 R0 ϕ − µ̂0 R̂0 ϕ = E [R0 ϕ(X0 )] − E R̂0 ϕ(X̂0 )

≤ R0 ϕ(X0 ) − R̂0 ϕ(X̂0 ) .

Comme pour l’analyse d’erreur des options américaines, l’idée est alors, à partir de la
formule backward de Rk et R̂k , d’obtenir une estimation de Rk ϕ(Xk ) − R̂k ϕ(X̂k )
2

en fonction des erreurs de quantification Xk − X̂k . Précisément, en posant uk =

2
Rk ϕ, ûk = R̂k ϕ, et en notant par définition de Rk et Hk que

uk = Hk+1 uk+1 = Pk+1 (ḡk+1 uk+1 ), (3.14)

ûk = Ĥk+1 ûk+1 = P̂k+1 (ḡk+1 ûk+1 ),

on a :

uk (Xk ) − ûk (X̂k )

= Pk+1 (ḡk+1 uk+1 )(Xk ) − P̂k+1 (ḡk+1 ûk+1 )(X̂k )

2
h i
≤ Pk+1 (ḡk+1 uk+1 )(Xk ) − E Pk+1 (ḡk+1 uk+1 )(Xk )| X̂k
2
h i
+ E Pk+1 (ḡk+1 uk+1 )(Xk )| X̂k − P̂k+1 (ḡk+1 ûk+1 )(X̂k )
2

≤ Pk+1 (ḡk+1 uk+1 )(Xk ) − Pk+1 (ḡk+1 uk+1 )(X̂k )

+ (ḡk+1 uk+1 )(Xk+1 ) − (ḡk+1 ûk+1 )(X̂k+1 ) ,

≤ [P ]Lip [ḡk+1 uk+1 ]Lip Xk − X̂k + [g]Lip kuk+1 k∞ Xk+1 − X̂k+1

2 2

+ kgk∞ uk+1 (Xk+1 ) − ûk+1 (X̂k+1 ) .

On a utilisé pour l’avant dernière inégalité, la définition même de l’espérance condition-

nelle dans L2 pour le premier terme, et le fait que X̂k est σ(Xk )-mesurable, combinée
FILTRAGE ET QUANTIFICATION 51

avec la loi des espérances conditionnelles itérées pour le deuxième terme. On a uti-
lisé les conditions (A1) et (A2) pour la dernière inégalité. On a donc l’inégalité de
récurrence

uk (Xk ) − ûk (X̂k )

≤ αk Xk − X̂k + βk+1 Xk+1 − X̂k+1

2 2

+ kgk∞ uk+1 (Xk+1 ) − ûk+1 (X̂k+1 ) ,

avec αk = [P ]Lip [ḡk+1 uk+1 ]Lip , βk+1 = [g]Lip kuk+1 k∞ , et la relation terminale kun (Xn )−
ûn (X̂n )k2 ≤ Xn − X̂n . Par induction, on en déduit
2

n
X
|πn ϕ − π̂n ϕ| ≤ u0 (X0 ) − û0 (X̂0 ) ≤ Ck (ϕ) Xk − X̂k , (3.15)
2 2
k=0

avec Ck (ϕ) = kgkk−1

∞
(αk kgk∞ + βk ), k = 0, . . . , n, et la convention αn = 1 et β0 = 0.
D’autre part, puisque un = ϕ, avec kϕk∞ ≤ 1, et kuk k∞ ≤ kgk∞ kuk+1 k∞ d’après
(3.14), on en déduit

kuk k∞ ≤ kgkn−k
∞
.

De même, d’après (3.14), on a

[uk ]Lip ≤ [P ]Lip [ḡk+1 uk+1 ]Lip ≤ [P ]Lip kgk∞ [uk+1 ]Lip + kuk+1 k∞ [g]Lip
n−k−1
≤ [P ]Lip kgk∞ [uk+1 ]Lip + [P ]Lip [g]Lip kgk∞ .

Par induction, puisque [un ]Lip ≤ 1, on en déduit :

n−k
n−k n−k−1
X
[uk ]Lip ≤ [P ]Lip kgk∞ + [g]Lip kgk∞ [P ]lLip .
l=1

On a donc βk ≤ [g]Lip kgkn−k

∞
et

αk = [P ]Lip [ḡk+1 uk+1 ]Lip ≤ [P ]Lip kgk∞ [uk+1 ]Lip + kuk+1 k∞ [g]Lip
n−k
n−k X
≤ [P ]Lip kgk∞ + [g]Lip kgkn−k−1
∞
[P ]lLip .
l=1

En substituant αk et βk dans Ck (ϕ), on obtient pour tout ϕ ∈ BL1 (Rd ) :

n−k
X
Ck (ϕ) ≤ kgkn∞ [P ]Lip
n−k n−1
+ [g]Lip kgk∞ [P ]lLip
l=0
n−k+1
!
n n−k [g] [P ] −1
= kgk∞ [P ]Lip + Lip Lip
. (3.16)
kgk∞ [P ]Lip − 1
FILTRAGE ET QUANTIFICATION 52

d’après (3.15). On conclut en se rappelant que πn 1 = γn (y) est la densité de (Y0 , . . . , Yn )

et en utilisant la majoration (3.16) de Ck (ϕ). 2

Remarque 3.2.3 Convergence du filtre quantifié. Si les grilles sont choisies optimale-
ment à chaque date k = 0, . . . , n, alors d’après le théorème de Zador, on a le taux de
convergence pour le filtre quantifié :
n
kgkn∞ X 1
sup Πn ϕ − Π̂n , ϕ ≤ An,k C(PXk , d) 1 . (3.17)
φ∈BL1 (Rd ) γn (y) Nd
k=0 k

En conséquence :
- Etant donné un nombre total de points N , on peut répartir optimalement le
nombre de points Nk pour chaque date k, i.e. déterminer (N0 , . . . , Nk ) vérifiant N0 +
. . . + Nn = N et minimisant le terme de droite de (3.17).
- Pour un horizon fixé n, on a la convergence du filtre quantifié, i.e. Π̂n converge
vers Πn lorsque min0≤k≤n Nk tend vers l’infini.
- Lorsque n tend vers l’infini, la convergence du filtre quantifié est aussi satisfaite
typiquement dans le cas d’un schéma d’Euler issue d’une diffusion discrétisée sur [0, T ]
de pas T /n :
r
T T
Xk+1 = Xk + b(Xk ) + σ(Xk ) εk+1 .
n n
En effet, sous des conditions de Lipschitz sur les coefficients b et σ, on a vu que :
c
[P ]Lip ≤ 1+
n
pour une constante c indépendante de n. Dans ce cas, en répartissant simplement Nk
= N̄ = N/(n+1) points sur chaque grille de temps, la relation (3.17) donne une vitesse
de convergence de l’ordre :
kgkn∞ n + 1
.
γn (y) N̄ 1/d
FILTRAGE ET QUANTIFICATION 53

3.3 Applications et exemples

3.3.1 Application : Valorisation d’options européennes en informa-
tion partielle
Soit (Xk ), k = 0, . . . , n, le processus de rendement et/ou de volatilité d’un actif
risqué. (Yk ), k = 0, . . . , n, est le (Logarithme) du processus de prix. On note Fk =
σ(Xj , Yj , 0 ≤ j ≤ k), k = 0, . . . , n, la filtration d’information totale et FkY = σ(Yj , 0 ≤
j ≤ k), k = 0, . . . , n la filtration d’information partielle, i.e. lorsqu’on n’observe pas
le rendement et/ou volatilité mais seulement le prix des actions. Dans ce modèle, on
se donne une option européenne de payoff h(Yn ) et plus généralement h(Xn , Yn ). Son
prix en information totale est donné à la date k par :

Uk = E [h(Xn , Yn )|Fk ] = vk (Xk , Yk ),

pour une fonction Borélienne vk , d’après la propriété de Markov du couple (X, Y ).

(Nous avons supposé ici que P est déjà une probabilité risque-neutre). La fonction vk
peut être aisément calculée par diverses méthodes : quantification ou Monte-Carlo.
D’autre part, le prix de l’option européenne en information partielle est :

UkY = E h(Xn , Yn )|FkY .

D’après la loi des espérances conditionnelles itérées, on a :

UkY = E h(Xn , Yn )|FkY = E vk (Xk , Yk )|FkY

Z
= vk (x, Yk )Πk (dx) =: Πk vk (., Yk )

Ainsi, étant donnée une observation (Y0 , . . . , Yk ) = (y0 , . . . , yk ), son prix est approximé
par la formule explicite :
Nk
X
Π̂k vk (., yk ) := vk (xik , yk )Π̂ik ,
i=1

où Π̂k est le filtre quantifié.

3.3.2 Exemples
Modèle linéaire gaussien. C’est le modèle étudié au paragraphe 3.1.2 :

Xn = AXn−1 + Bεn , X0 ∼ N (µ0 , ΣX

0 ),
Yn = CXn + ηn ,

pour lequel le filtre Πn est explicite : Πn ∼ N (X̄n , Σ̄n ) avec X̄n et Σ̄n se calculant
explicitement de manière inductive.
FILTRAGE ET QUANTIFICATION 54

Projet 7. Choisir les paramètres du modèle en dimension 1 pour que le signal Xk soit
stationnaire, Xk ∼ N (0, ΣX 0 ) pour tout k, et impémenter le filtre quantifié. Comparer
avec le filtre théorique explicite.
Modèle à volatilité stochastique. On considère le modèle ARCH :

Xk+1 = ρXk + εk , X0 ; N (0, Σ0 )

Yk = σ(Xk )ηk ,

où (εk ) et (ηk ) sont deux bruits blancs indépendants gaussiens. Ce modèle est populaire
en finance où X est le facteur de la volatilité de l’actif risqué de prix logarithmique Y
= ln S.
Projet 8. Choisir les paramètres du modèle en dimension 1 pour que le signal Xk soit
stationnaire, Xk ∼ N (0, ΣX
0 ) pour tout k, et impémenter le filtre quantifié. Calculer le
prix d’un put européen en information totale et partielle.
Bibliographie

[1] Bally V., Pagès G. (2003) : A quantization algorithm for solving discrete time
multi-dimensional optimal stopping problems, Bernoulli, 9, 1003-1049.
[2] Bally V., Pagès G., Printems J. (2001) : A stochastic quantization method for
nonlinear problems, Monte Carlo Methods and Applications, 7, n0 1-2, pp.21-34.
[3] Bartoli N. et P. Del Moral (2005) : Simulation et algorithmes stochastiques,
Cépadues-Éditions.
[4] Bucklew J., Wise G. (1982) : Multidimensional Asymptotic Quantization Theory
with rth Power distortion Measures, IEEE Transactions on Information Theory,
Special issue on Quantization, 28, n0 2, pp. 239-247.
[5] Duflo, M. (1996) : Algorithmes stochastiques, Mathématiques et Applications, 23,
Springer-Verlag.
[6] Duflo, M. (1997) : Random Iterative Models, Coll. Applications of Mathematics,
34, Springer-Verlag, Berlin, 1997, 385p.
[7] Elliott R., Aggoun L. and J. Moore (1995) : Hidden Markov Models, Estimation
and Control, Springer Verlag, 361 pp.
[8] Fort J.C., Pagès G. (2002) : Asymptotics of optimal quantizers for some scalar
distributions, Journal of Computational and Applied Mathematics, 146, pp.253-
275.
[9] Gersho A., Gray R. (eds.) (1982) : IEEE Transactions on Information Theory,
Special issue on Quantization, 28.
[10] Graf S., Luschgy H. (2000) : Foundations of Quantization for Probability Distri-
butions, Lecture Notes in Mathematics n0 1730, Springer, Berlin, 230 pp.
[11] Kieffer J. (1982) : Exponential rate of convergence for the Lloyd’s method I, IEEE
Transactions on Information Theory, Special issue on Quantization, 28, 205-210.
[12] Kohonen T. (1982) : Analysis of simple self-organizing process, Biological Cyber-
netics, 44, pp. 135–140.
[13] Kushner H.J., Yin G.G. (1997) : Stochastic Approximation Algorithms and Appli-
cations, Springer, New York.

55
Bibliographie 56

[14] Le Gland F. (2004) : Introduction au filtrage en temps discret, Polycopié de cours,

Master STI, Université de Rennes 1.
[15] Pagès G. (1997) : A space vector quantization method for numerical integration,
Journal of Computational and Applied Mathematics, 89, pp.1-38.
[16] Pagès G., H. Pham and J. Printems, “An optimal markovian quantization algo-
rithm for multidimensional stochastic control problems”, 2004, Stochastics and
Dynamics, 4, 501-545.
[17] Pagès G., H. Pham et J. Printems, “Optimal quantization methods and applica-
tions to numerical problems in finance”, 2004, Handbook of Numerical and Com-
putational Methods in Finance, ed. Z. Rachev, Birkhauser.
[18] Pagès G., Pham H. (2005) : Optimal quantization methods for nonlinear filtering
with discrete-time observations, Bernoulli, 11, 5, 893-932.
[19] Pagès G., Printems J. (2003) : Optimal quadratic quantization for numerics : the
Gaussian case, Monte Carlo Methods and Applications, 9, 135-165.
[20] Sellami A. (2005) : Méthodes de quantification optimale en filtrage et applications
en finance, Thèse Université Paris Dauphine.
[21] Zador P. (1982) : Asymptotic quantization error of continuous signals and the
quantization dimension, IEEE Transactions on Information Theory, Special issue
on Quantization, 28, n0 2, pp. 139-148. .

Vous aimerez peut-être aussi

Maths Éco : Optimisation et Algèbre
Pas encore d'évaluation
Maths Éco : Optimisation et Algèbre
80 pages
Controle 17
Pas encore d'évaluation
Controle 17
6 pages
Cours Optim M1SAF
Pas encore d'évaluation
Cours Optim M1SAF
65 pages
Cours Optim M1SAF
Pas encore d'évaluation
Cours Optim M1SAF
65 pages
Param
Pas encore d'évaluation
Param
145 pages
Algorithmes Stochastiques et Convergence
Pas encore d'évaluation
Algorithmes Stochastiques et Convergence
88 pages
Correction TD ENAC OPTIM PDF
Pas encore d'évaluation
Correction TD ENAC OPTIM PDF
31 pages
Cours
Pas encore d'évaluation
Cours
65 pages
Controle 2016 FR
Pas encore d'évaluation
Controle 2016 FR
4 pages
Poly Modélisation
Pas encore d'évaluation
Poly Modélisation
41 pages
Optimisation Mathématique Avancée
Pas encore d'évaluation
Optimisation Mathématique Avancée
55 pages
Support - cours-PM-Licence (1) Optimisation Casa
Pas encore d'évaluation
Support - cours-PM-Licence (1) Optimisation Casa
36 pages
Méthodes de Monte Carlo Pour La Finance
Pas encore d'évaluation
Méthodes de Monte Carlo Pour La Finance
72 pages
Monte Carlo en Finance: Méthodes et Applications
Pas encore d'évaluation
Monte Carlo en Finance: Méthodes et Applications
72 pages
c1 PDF
Pas encore d'évaluation
c1 PDF
43 pages
Optimisation et Calcul Différentiel ECP
Pas encore d'évaluation
Optimisation et Calcul Différentiel ECP
104 pages
CoursOptim PDF
Pas encore d'évaluation
CoursOptim PDF
104 pages
X-Cachan 2023 PSI Mathématiques Ea
Pas encore d'évaluation
X-Cachan 2023 PSI Mathématiques Ea
5 pages
Poly 2022
Pas encore d'évaluation
Poly 2022
69 pages
Polycopie Optimisation Licence SSD Et MID
Pas encore d'évaluation
Polycopie Optimisation Licence SSD Et MID
44 pages
Cours Optimisation Lafitte
Pas encore d'évaluation
Cours Optimisation Lafitte
129 pages
Méthode de gradient optimal
Pas encore d'évaluation
Méthode de gradient optimal
4 pages
Opti l3
Pas encore d'évaluation
Opti l3
49 pages
Introduction à l'optimisation
Pas encore d'évaluation
Introduction à l'optimisation
39 pages
Exercices corrigés en optimisation convexe
100% (3)
Exercices corrigés en optimisation convexe
346 pages
Poly Copie Partie 2
Pas encore d'évaluation
Poly Copie Partie 2
78 pages
Cours d'Analyse Numérique L3
Pas encore d'évaluation
Cours d'Analyse Numérique L3
248 pages
1.livre Controle Sto
Pas encore d'évaluation
1.livre Controle Sto
156 pages
Cours Optimisation
100% (1)
Cours Optimisation
43 pages
Chap2 coursmagUVS Optimisation
Pas encore d'évaluation
Chap2 coursmagUVS Optimisation
81 pages
Exercices d'Optimisation Mathématique
Pas encore d'évaluation
Exercices d'Optimisation Mathématique
22 pages
Optimisation Non-Linéaire L3
Pas encore d'évaluation
Optimisation Non-Linéaire L3
53 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
46 pages
Cours Optimisation
100% (2)
Cours Optimisation
39 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
45 pages
Cours Galerne
Pas encore d'évaluation
Cours Galerne
38 pages
CoursCnam CSC104 Intro
Pas encore d'évaluation
CoursCnam CSC104 Intro
7 pages
219 - Extremums. Existence, Caracterisation, Recherche. Exemples Et Applications.
Pas encore d'évaluation
219 - Extremums. Existence, Caracterisation, Recherche. Exemples Et Applications.
2 pages
Cours d'Analyse Numérique - Aix Marseille
Pas encore d'évaluation
Cours d'Analyse Numérique - Aix Marseille
271 pages
Controle 18
Pas encore d'évaluation
Controle 18
7 pages
Analyse Matricielle en Mathématiques
100% (1)
Analyse Matricielle en Mathématiques
291 pages
Optimisation Mathématique FST Tanger
Pas encore d'évaluation
Optimisation Mathématique FST Tanger
12 pages
Cours Optim NL
Pas encore d'évaluation
Cours Optim NL
69 pages
Analyse Numérique pour Étudiants L3
Pas encore d'évaluation
Analyse Numérique pour Étudiants L3
301 pages
Methode Du Gradient Conjugue-1
Pas encore d'évaluation
Methode Du Gradient Conjugue-1
3 pages
Cours d'Analyse Numérique L3
Pas encore d'évaluation
Cours d'Analyse Numérique L3
243 pages
4M011 Poly Duquesne
Pas encore d'évaluation
4M011 Poly Duquesne
173 pages
Exercices Examens + Correction Modélisation
100% (1)
Exercices Examens + Correction Modélisation
36 pages
Analyse Numérisue Et Opt
100% (2)
Analyse Numérisue Et Opt
150 pages
Optimisation Numerique
Pas encore d'évaluation
Optimisation Numerique
29 pages
Anum tg5
Pas encore d'évaluation
Anum tg5
15 pages
Examen de Modélisation Mathématique
100% (1)
Examen de Modélisation Mathématique
6 pages
Cours Opt NL
Pas encore d'évaluation
Cours Opt NL
40 pages
Stabilité des pieux à Bellara, Jijel
100% (2)
Stabilité des pieux à Bellara, Jijel
118 pages
Commentaire Geo
100% (2)
Commentaire Geo
20 pages
Depannage Perkins
Pas encore d'évaluation
Depannage Perkins
160 pages
Chapitre 5 2021
Pas encore d'évaluation
Chapitre 5 2021
26 pages
Titrage du Fer II par Permanganate de Potassium
Pas encore d'évaluation
Titrage du Fer II par Permanganate de Potassium
4 pages
Le Maillon Faible - ECG Pour Les Nuls
Pas encore d'évaluation
Le Maillon Faible - ECG Pour Les Nuls
45 pages
Pyrométallurgie des Batteries Li-Ion
Pas encore d'évaluation
Pyrométallurgie des Batteries Li-Ion
11 pages
DM3 Correction
Pas encore d'évaluation
DM3 Correction
5 pages
Introduction au Système Triphasé
Pas encore d'évaluation
Introduction au Système Triphasé
26 pages
Marchés Financiers et Gestion de Portefeuille
100% (3)
Marchés Financiers et Gestion de Portefeuille
54 pages
Bilan: Propriétés Rhéologiques Des Matériaux Biologiques
Pas encore d'évaluation
Bilan: Propriétés Rhéologiques Des Matériaux Biologiques
22 pages
Bluetooth & Java pour Développeurs
Pas encore d'évaluation
Bluetooth & Java pour Développeurs
120 pages
ME Série N°1
Pas encore d'évaluation
ME Série N°1
1 page
2eme Seance 18 Sept2017 Diagrammes Unaires Suite Introduction Diagrammes Binaires
Pas encore d'évaluation
2eme Seance 18 Sept2017 Diagrammes Unaires Suite Introduction Diagrammes Binaires
32 pages
Presentation - Mémoire 27 - 10 - 2018 Kra Franck
100% (1)
Presentation - Mémoire 27 - 10 - 2018 Kra Franck
12 pages
Pdfslide - Tips Maths Au Ce2 p1 Maths Au Ce2 Calculs 81 278569 Je Sais Poser Et Calculer Des
Pas encore d'évaluation
Pdfslide - Tips Maths Au Ce2 p1 Maths Au Ce2 Calculs 81 278569 Je Sais Poser Et Calculer Des
16 pages
COURS de Dessin 2
Pas encore d'évaluation
COURS de Dessin 2
13 pages
Cours Ingenierie Systeme
100% (3)
Cours Ingenierie Systeme
67 pages
Syllabus Politique de Financement L3 STCF 2021
Pas encore d'évaluation
Syllabus Politique de Financement L3 STCF 2021
4 pages
Analyse Granulométrique des Sols
50% (2)
Analyse Granulométrique des Sols
12 pages
Resume Du Cours Mef
Pas encore d'évaluation
Resume Du Cours Mef
20 pages
Liquéfaction Du Chlore
Pas encore d'évaluation
Liquéfaction Du Chlore
13 pages
Examen Pratique de Ouattara Fousseni Mathematiques 1.1.1
Pas encore d'évaluation
Examen Pratique de Ouattara Fousseni Mathematiques 1.1.1
10 pages
Dist Chap1
0% (1)
Dist Chap1
15 pages
Lase9 Stat + Exos Et Exam Corriges
Pas encore d'évaluation
Lase9 Stat + Exos Et Exam Corriges
21 pages
Cours D'infographie 2025
Pas encore d'évaluation
Cours D'infographie 2025
23 pages
Controle N1S1 2024.25 - CORRECTION
Pas encore d'évaluation
Controle N1S1 2024.25 - CORRECTION
3 pages
Phrases Atypiques
50% (2)
Phrases Atypiques
3 pages
Note de Calcul Locaux
Pas encore d'évaluation
Note de Calcul Locaux
20 pages
Normal 2023 CORR
100% (1)
Normal 2023 CORR
10 pages