数理解析研究所講究録 1462 巻 2006 年 79-99

79

Quantization Methods in Filtering and Applications toPartially Observed Stochastic Volatility Models
Huyen PHAM
Laboratoire de Probabilites etModeles Al\’eatoires
CNRS, UMR 7599
Universite Paris 7

e-mail: pham@math.jussieu.fr
and CREST

October 12, 2005
Abstract

We present some recent developments on optimal quantization methods for discretetime nonlinear filtering, We analyse first the quantization algorithm for the filter given
a fixed observation, and then the quantization of the filter process. This last study
is motivated by dynamic optimization problems under partial information arising forexample in finance in the pricing of American options under partially observed stochastic volatility models. Several numerical illustrations are carried out, emphasizing theconvergence and the stability of the approximate filter.

Key words :Nonlinear filtering, Markov chain, quantization, stochastic gradient descent,optimal stopping.

MSC ClassiEcation (2000) :$60\mathrm{G}35,65\mathrm{C}20$,$65\mathrm{N}50,60\mathrm{G}40$

.

80
1

Introduction

Optimal quantization of random vectors consists in finding the best approximation innorm of a random vector by a discrete random vector taking at most $N$ values. Thiswas originally developed in the 50’s in the context of information theory where the basic
motivation was to transmit efficiently a continuous stationary signal by means of a finite
number of codes (or quantizers) . More recently, the quantization approach was applied tovarious fields, and notably to numerical probability, where it appears as an efficient spatial
discretization method for solving multi-dimensional problems arising typically in finance.
In this article, we present recent developments of optimal quantization methods applied
to the nonlinear filtering problem. This is form ally the situation where we face a stochastic
system whose evolution is governed by a hidden process that we observe only throughsome noise. Filtering is a traditional problem in probability and statistics, and occurs inparticular in a financial context where we can observe stock price but not its volatility.
Mathematically, the problem is to recover the optimal filter, i.e. the conditional law of thehidden process (the signal) given the past observations. For instance, standard filtering
problems in finance are the estimation of the law of the volatility given the past priceobservations, and then the pricing of derivatives and portfolio optimization in a partiallyobserved stochastic volatility model. Except some very specific cases like the Kalman-Bucy
model, there is no explicit solution for the filter and one has to resort on numerical methods.
The various approaches proposed in the literature (particle methods, grid methods) rely
basically on the principle of finding a finite-dimensinal representation of the filter. We
present here the quantization approach for filtering introduced in [7], which is a grid method,
and where one searchs for grids that fit optimally according to -norm to the distributionof the sign al. In these numerical methods, the filter is approximated for a given fixed
set of observations. However, in many applications arising in dynamic optimization underpartial observation, one need to approxim ate the filter process where randomness is due
to past observation process. We then present a quantization approach of the filter processintroduced in [9] and give a numerical application to the problem of optimal stopping underpartial observation.
The paper is organized as follows. Section 2 formulates and recalls some preliminaries
on the filtering problem. In Section 3, we present the quantization method for approximating the filter given a fixedx observation. Section 4 illustrates the results with numericalexperim ents. In Section 5, we introduce the quantization approach for the approximationof the filter process, and we deal in the last Section 6 with a numerical application to the
optimal stopping problem in a partially observed stochastic volatility model.
$L^{p}-$$L^{2}$

2

Filtering problem for discrete observations

2.1

General framework

We consider a discrete time, partially observable process $(X, Y)$ where $X$ represents thestate or signal process that may not be observable, while is the observation, The signal
process
is valued in a measurable space
and is a Markov chain with$Y$$\{X_{k}, k\in \mathrm{N}\}$$(E, \mathcal{E})$81

probability transition (Pk) (i.e. the transition from time $k-1$ to time ), and initial law, such that the pair $(Xk, Yk)$ is a Markov. The observation sequence (Yk) is valued inandchain on the probability space$k$$\mathbb{R}^{q}$$\mu$$(\Omega \mathrm{P})\}$

denoted (Xk-U,
The law of conditional on (Xk-U $Yk-1,$ $Xk$ ),admits a bounded density (called sometimes local likelihood function) :(H)$k\geq 1_{7}$$Y_{k}$

$y’$

$qk$

),

.

$g_{k}(X_{k-1}, Y_{k-1}, X_{k}, y’)$$\mapsto$$Y_{k-1},$ $Xk,$ $dy’$is a known deterministic constant equal to yo- NoFor simplicity, we assume thatis then given bytice that the probability transition of the Markov chain.
, $dx’)gk(x, y_{2}x’, y’)dy’$ with initial law
and bythe filtration generated by the observation process
We denote bygiven:
the filter conditional law of$Y_{0}$$(Xk, Yk)_{k\in \mathrm{N}}$$\mu(dx)\delta_{y0}(dy)$$Pk$$(Y_{k})$$(F_{k}^{Y})$$X_{k}$$\Pi_{k}$$\mathcal{F}_{k}^{Y}$$\Pi_{k}(dx)$$=$$\mathrm{P}$$[Xk\in dx| F_{k}^{Y}]$,$k\in \mathrm{N}$.

A typical case of signal-observation model is given by the following scheme :,$X_{k}$$=$$F_{k}(X_{k-1\mathrm{t}}\epsilon_{k})$$Y_{k}$$=$$G_{k}(X_{k-1}, Y_{k-1},X_{k}, \eta_{k})$,are two white noises. For, and where (ek) andfor some measurable functions F&,
volatilityof stock price while
returnis the unobservable
example in finance,$Y_{k}=$ In
is the logarithm of the observed price process$(\eta k)$$G_{k}$$(X_{k})_{k}$$S$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$$S_{k}$$Y_{k}$$Y_{k-1}+b(X_{k-1})+\sigma(X_{k-1})\eta_{k}$$=$and gk is explicit once the density of the white noise

2.2$\eta k$,is specified.

Filter evolution

theand bythe set of finite nonnegative measures on
We denote byequipped
space
Polish
is
a
.
known
that
It
is
subset of probability measures onwith the weak topology, hence a measurable space endowed with the Borel -field. Fromsatisfies thevalued inMarkov property and Bayes formula, the filter processfiltering forward equation :$\mathcal{P}(E)$$(E, \mathcal{E})$$\mathrm{A}l(E)$$\lambda 4(E)$$(E, \mathcal{E})$$\mathrm{c}\mathrm{r}$$\mathcal{P}(E)$$\mathrm{I}\mathrm{I}k$

where$H_{k}$$\Pi_{0}$$=$$\Pi_{k}(dx’)$

$=$

$\mu$

,

$\frac{\Pi_{k-1}H_{k}(dx’)}{\Pi_{k-}{}_{1}H_{k}(E)}$$.= \frac{\int_{B}\Pi_{k-1}(dx)H_{k}(X_{\}}dx’)}{\int_{B}\Pi_{k-1}H_{k}(dx’)}$(2.1)

is the prediction-updating transition kernel given by :$H_{k}(x, dx’)$

$=$

$gk$

( , Xk$x$, $x’,$$Y_{k}$) $P_{k}(x, dx’)$ .

tois done in two steps: a first step of prediction, which
Hence, the calculation fromuses the a priori information from the signal transition probability , and a second step of$\Pi_{k-1}$$\Pi_{k}$$P_{k}$

82

correction and updating, which uses the a posteriori inform ation given by the observation attime via the local likelihood function g%. We denote the relation (2.1) (which is nonlinear
toby :due the norm alization) from$k$$\Pi_{k-1}$$\Pi_{k}$$=$$\Pi_{k}$$\overline{G}_{k}(\Pi_{k-1}, Y_{k-1}, Y_{k})$.

Given a fixed set of observations, the filtering problem consists in solving or simulating
by approximation this filtering equation valued in the infinite di mensional space(when the state space $E$ is continuous). We distinguish essentially three types of methods :Analytical methods where one tries to solve analytically the forward equation. This is
explicitly possible when $X$ and $Y$ are Gaussian processes leading to the well-known Kalmanfilter, which is a finite-dimensional filter completely characterized by its mean and variance.
Some extensions are derived with the so-called extended Kalm an filter. We also cite recent
work in [3], which derives an explicit filter of infinite dimension.
by a-Monte-Carlo methods :this approach consists basically in approximatinginteracting particles at each time andsequence of empirical measures associated tomechanism given by the transition kernel
simulate according to the.
by a transition
Grid methods . this consists in approxirnating the transition kernel
equationanvaluedin a finite
,
leads
in
turn
to
approximate
matrixwhich
forward$\mathcal{P}(E)$-$\mathrm{I}\mathrm{I}k$$k$$\overline{N}$$\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}/\mathrm{u}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$$H_{k}$$H_{k}$-$\sim$$\hat{H}_{k}$dimensional space
We develop in the two next sections optimal quantization methods that belong to grid
methods. It is also of interest to approximate not only the filter for a given set of observations, but more generally the filter process viewed as a random measure function of theuncertainty of the observation process. This will be developed in the two last sections wherea quantization approach is introduced for approximating the filter process with applications
to partial observation problems.

3

Approximate filter by optimal quantization (Fixed observation)

3.1

Short background on optimal vector quantization

The basic idea of (quadratic) quantization is to replace an -valued random vector $X\in$, with probability law, by a random vector taking at most $N$ values in orderto minimize the induced -error. For this, consider a grid $x=\{x^{1}, . , . , x^{N}\}$ of $N$ points in(we shall often identify such a grid with a $N$-tuple in), and its Voronoi tesselations,$C_{1}(x)$$C_{N}(x)$,, . .,
that is Borel partitionsofsatisfying :$\mathbb{R}^{d}$$L^{2}(\mathrm{P}, \mathbb{R}^{d})$$\mathrm{p}_{X}$$L^{2}$$\mathbb{R}^{d}$$\mathbb{R}^{d}$$\mathbb{R}^{d}$$C_{i}(x)$$\subset$$\{u\in \mathbb{R}^{d}$: $|u-x^{\iota}|= \min j=1,$$,N|u-x^{j}|\}$ ,.

$\mathrm{i}=1$,$\ldots$, $N$ .

Then, one defines the -Voronoi quantization of $X$ as the closest neighbour projection of$X$ on the grid
:
$x$

$x$

$\hat{X}^{x}$$=$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}_{x}(X):=\sum_{\mathrm{i}=1}^{N}x^{i}1_{C_{i}(x)}(X)$,83

whose discrete probability law$\mathrm{P}_{\hat{X}}$is characterized by :$\hat{p}i|.=\mathrm{P}_{\hat{X}}(x^{i})=\mathrm{P}x$(Ci (x)),$\mathrm{i}=1$, .. . ’ $N$ .

when there is no ambiguity, and we say
In the sequel, we often drop the exponent in$X$that is a quantizer of . The -error induced by this projection, called -quantization, theerror, is. As a function of the $N$-tuple (grid)square of the -quantization error, called distorsion, is written as :$\hat{X}^{x}$$x$$L^{2}$$L^{2}$$\hat{X}$$x=(x^{1}, \ldots x^{N})\}\in(\mathbb{R}^{d})^{N}$$||X-\hat{X}||_{2}$$L^{2}$$D_{N}^{X}(x)=||X-\hat{X}||_{2}^{2}$$=$$\int\iota=1\mathrm{m},\acute{.}1..\mathrm{n},N|u-x^{\mathrm{i}}|^{2}\mathrm{P}_{X}$

(du).

(3.2)

First, notice by definition of the closest neighbour projection that the -quantization error
error $||X-Y||_{2}$ among all random variables taking values in theis the minimum of
which
grid . Then, two questions arise naturally: for fixed $N$ , is there an optimal grid-quantization error (or equivalently the distorsion), and how does thisminimizes theminim um behave when $N$ goes to infinity7 The latter question is answered by the so-called
Zador theorem :$L^{2}$$Y$$L^{2}$$x^{*}$$x$$L^{2}$

Theorem 3.1 (see [4])Assume thatfor some $>0$ and set the Radon-Nykodim density ofon . Then,in its decomposition with respect to the Lebesgue measure$X\in L^{2+\epsilon}(\mathrm{P}, \mathbb{R}^{d})$$f$$\epsilon$$\mathrm{P}_{X}$$\mathbb{R}^{d}$$\lambda_{d}$$\lim_{N}N^{\frac{2}{d}}\min_{x}$$||X-\hat{X}^{x}||_{2}^{2}$

where $||f||_{r}=$for $r>0$ , andto the uniform distribution on $[0, 1]^{d}$ .
$(f |f|^{r}d\lambda d)^{1/r}$

Remark 3.1 In dimensions d $=1$ and 2,
d goes to infinity.

$J_{d}$$=$$J_{d}||f||_{\phi+}$,

is a constant depending on$J_{1}= \frac{1}{12}$aaand$\mathrm{J}_{2}=\frac{5}{18\sqrt{3}}$. forr d$d_{f}$

corresponding$\geq 3$,

$J_{d} \sim\frac{d}{2\pi e}$as

The optimal $N$ -quantization problem that consists in determ ining a grid , which minimizes the -quantization error, relies on the property that the distorsion is continuously
diflerentiable at any $N$-tuple having pairwise distinct components, with a gradient obtainedby formal differentiation in (3.2) :$x^{*}$$L^{2}$$\nabla D_{N}^{X}(x)$A quantizer$\hat{X}=\hat{X}^{x}$$=$

2 $( \int_{C,(x)}(x^{i}-u)Px(du))1\leq i\leq N$(3.3)

is said stationary if the associated $N$-tuple $ satisfies$\nabla D_{N}^{X}(x)$

$=$

0.

An optimal quantizer is a stationary quantizer. From (3.3), we have the useful property ofstationary quantizers :$\mathrm{E}[X|\hat{X}]$$=$$\hat{X}$.

84suggests, as soon as independent copies of $X$
The integral representation (3.3) of
can be simulated, to implement a stochastic gradient algorithm (descent), in order to getnumerically a stationary quantizer. In our context, this leads to the Kohonen algorithm
or competitive learning vector quantization (CLVQ) algorithm, which also provides as a
byproduct an estimation of the weights $pi$ of the Voronoi tesselations associated to thestationary quantizer. We refer to [8] for a description and discussion of the algorithm.
Optimal grids and their companion parameters, i.e. weights of the Voronoi tesselation anddistorsion, for the normal distribution are available and downloadable on the webpages of$\nabla D_{N}^{X}$

Gilles Pages or Jacques Printems.

3.2

Filter quantization approximation for a fixed observation

We are in the framework where the signal state space is continuous, say . We show how
one can apply quantization methods for providing a numerical approximation of the filter,
given a fixed set of observations. This is achieved in three steps.
$\mathbb{R}^{d}$is square integrable andStep 1. We assume that for each time the random vectorof the random
quantization
optimalvector
apply
an
,
we
for
each
Then,
simulatable.
. We denote
vector
$X_{k}$$k_{2}$$k$$X_{k}$$\hat{X}_{k}$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}_{x_{h}}(X_{k}):=\sum_{i=l}^{N\mu}x_{k}^{i}1_{C_{i}(\mathrm{a}_{\mathrm{k}})}(X_{k})$$=$,points in.
of size
the associated quantizer on the optimal grid $xk=$ . , . . . ,Step 2. : Marginal quantization of the Markov chain (Xk).
This consists in approximating the distribution law of the Markov chain $(Xk)0\leq k\leq n$ as
follows :$x_{k}^{N_{k}}$$(x_{k}^{1}$approximate law of $X0$
of $X_{k}|X_{k-1}$
approximate law
$\mu$

by

law

by

law

$P_{k}$

In other words,$\hat{\mu}$is the weight vector$\hat{p}_{0}^{i}$and for $k=1$ ,$\ldots$

)

$n$

,

$P\wedge k=(\hat{p}_{k}^{ij})$$\hat{p}_{k}^{ij}$for$\mathrm{i}=1$,$\ldots$$=$, Nk-i, $j=1$ ,$\ldots$$\hat{\mathrm{p}}_{0}^{i}$$\mathrm{P}$$(\hat{p}_{0}^{i})$$\hat{\mu}$of$\hat{X}_{0}$of$\hat{P}_{k}$k-12$\hat{X}_{k}|\hat{X}$A $=1$ ,$\ldots$

}

$n$

.

given by:$[\hat{X}_{0}=x_{0}^{i}]$,$\mathrm{i}=1$,$\ldots$,$N_{0}$.

is the probability transition matrix :$=$$\mathbb{P}[\hat{X}_{k}=x_{k}^{J}|\hat{X}_{k-1}=x_{k-1}^{i}]$,, $Nk$ . These transition weights$=$$\mathrm{P}_{X_{0}}[C_{i}(x_{0})]$$\mathrm{P}x_{k-1},x_{\mathrm{k}}[C_{l}(x_{k-1}), C_{j}(x_{k})]$$\hat{p}_{k}^{ij}$$\mathbb{R}^{d}$$N_{k}$$)$$=$$\overline{\mathrm{P}_{X_{k-1}}[C_{l}(x_{k-1})]}$

are estimated by Monte Carlo simulations of
as a byproduct of the Kohonen algorithm.

$X_{k}$,, $k=0$ , . . . ’ . They can also be obtaine$n$85
Step 3. : Filter approximation for a fixed observation.
. For each $k=1$ , . . , , we,...,
fixed toWe are given a set of observations
by the transition
consider the approximation of the prediction-updating transition kernel
defined as :matrix$(y\mathit{0}, \ldots, y_{n})$$Y_{n})$$(Y\mathit{0}$$n$$H_{k}$$\overline{H}_{k}=(\hat{H}_{k}^{i\gamma})$$\hat{H}_{k}^{\mathrm{o}j}$$g_{k}(x_{k-1}^{l}, y_{k-1}, x_{k}^{f}, y_{k})\hat{p}_{k}^{ij}$$=$,$\mathrm{i}=1$,$\ldots$, $N_{k-1}$ , $j=1$ ,$\ldots$,$N_{k}$.

on the grid $xk$ :by the discrete probability measure
We then approxim ate the filter, that is defined by the approximate forward equation :$\hat{\Pi}_{k}$$\Pi_{k}$$\hat{\mathrm{I}}\mathrm{I}_{k}=\sum_{i=1}^{N_{k\Pi_{k}^{l}\delta_{x_{k}^{i}}}^{\wedge}}$$\hat{\Pi}_{0}$$\hat{\Pi}_{k}$The weights$(\hat{\Pi}_{k}^{l})$$\Pi_{0}^{i}\wedge$$\Pi_{k}^{j}\wedge$, $k=0$ ,$=$$\hat{p}_{0}^{\iota}$$=$$\ldots$,, , $l=1$ ,$n$$\mathrm{i}=1$

,...

$=$

$\hat{\mu}$$=$$\frac{\hat{\Pi}_{k-}{}_{1}\hat{H}_{k}}{(\Pi_{k-1}\hat{H}_{k})(x_{k})\wedge}$$\ldots$$iN_{0}$,.

, are then computed as :$N_{k}$,$\frac{\sum_{i=1}^{N_{k-1}}\hat{H}_{kk-1}^{ij_{\Pi}^{\wedge}i}}{\sum_{j=1}^{N_{k}}\sum_{i=1}^{N_{k-1}}\hat{H}_{kk-1}^{xj_{\Pi}^{\wedge}i}}$$k=1$ ,,$\ldots$, ,$n$$j=1$ ,$\ldots$,$N_{k}$.

Prom a practical viewpoint, the above procedure is implem ented as follows :Phase 1. Off-line computations (the most demanding): Optimal quantization of the signal.
Notice that this phase does not depend on the observations. We need to :, given a total number of points $N=$of the grids for $k=1$ ,Specify the size
$N_{0}+$ . $..+N_{n}$ .
.
-Process optimal grids (by Kohonen algorithm) and the associated transition weights
A special case of interest :a stationary signal. In this usual case in filtering model,of the stationary distribution
we only need to compute the optimal grid
, , are the optimal grids for, with size $\overline{N}=N/(n+1)$ . Then, $xk=x’$ , $k=0$ ,of,and
we only have to estimateofprobabilitythe. We estimate
each
one single transition matrix :$N_{k}$-$\ldots$$n$$(\hat{p}_{k}^{ij})$$x^{*}=\{x^{1}, \ldots, x^{\overline{N}}\}$$\mu$$X_{0}$$\ldots$$X_{k}$$\hat{p}_{k}^{ij}=\hat{p}_{0}^{ij}$

$=$

$n$

$\hat{X}0=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}_{x}*(X_{0})$$\hat{\mu}$$\mathrm{P}[\hat{X}_{0}=x^{j}|\hat{X}_{0}=x^{i}]$,$0\leq \mathrm{i},j$$\leq\overline{N}$, $k=1\}\ldots$ , .
$n$From a computational viewpoint, the size of the parameters to be stored is divided by aand the transition(or the available quantization size for the distribution offactormatrix is multiplied by ).
$(y0, \ldots, y_{n})$ , we comPhase 2. On-line computations :given an observation vector, $k=1$ , , . Finally, wepute the quantized prediction-updating transition matrix, , by the approximate forward equation, and, $k=1$ ,compute the quantized filter
for every (needed) test function :$X_{0}$

$n$

$n$

$y$

$(\hat{H}k)$$(\hat{\Pi}k)$$\ldots$$n$$\phi$$\hat{\Pi}_{n}\varphi$

This phase is almost instantaneous$=$$\sum_{i=1}^{N_{n}}\varphi(x_{n}^{i})\Pi_{n}^{i}\wedge$$=$$\ldots$$n$

gg

Error and convergence analysis

3.3

We denote$BL_{1}(\mathbb{R}^{d})$$=$$\{\phi$:andFor any$\Pi\in \mathcal{P}(\mathbb{R}^{d})$,$\mathbb{R}^{d}arrow \mathbb{R}$bounded by 1$\phi$$\phi$

Lipschitz with,$\frac{|\phi(x)-\phi(x’)|}{|x-x|},\leq 1\}$$[ \phi]_{Lip}:=\sup_{x\neq x}$.

, we denote$\int\phi(x)\Pi(dx)$$=$$\Pi\phi$,$\forall\phi\in BL_{1}(\mathbb{R}^{d})$We make essentially two conditions on the signal-observation model. We assum a
Lipschitz condition on the probability transitions of the signal :i.e.
, are Lipschitz with ratio(A1) The probability transitions $Pkj$ $k=1$ ,, with ratio, we have:for any Lipschitz function on$\mathrm{e}$$\ldots$$[Pk]_{Lx\mathrm{p}7}$$n_{7}$$\mathbb{R}^{d}$$\phi$$[\phi]_{Lip}$$|P_{k}\phi(x)-Pk\phi(\hat{x})|$$[Pk]_{Lip}[\Phi]_{L\mathrm{z}p}|x-\hat{x}|$$\leq$,$\forall x,\hat{x}\in \mathbb{R}^{d}$.

We then set $[P]_{Lip}:= \max_{k=1,\ldots,n}[Pk]_{Li\mathrm{p}}$ .
We also assume a Lipschitz condition on the updating observation functions :The functions $gk$ ) $k=1$ ,$-(i)$$\ldots$, , are bounded.
$n$$||g||_{\infty}:= \max_{k=1,\ldots,n}||g_{k}||_{\infty}$

(A2)

(ii)

There exists$[g_{k}]_{Lip}$, $k=1$ ,$\ldots$, ,$n$$\mathrm{s}.\mathrm{t}$.

$\forall x$,$x’,\hat{x},$$x\wedge;\in \mathbb{R}_{1}^{d}y$,$y’\in \mathbb{R}^{q}$$|gk(x, y, x’, y’)-gk(\hat{x}, y,\hat{x}’, y’)|\leq[g_{k}]_{L\mathrm{i}p}(|x-\hat{x}|+|x’-\hat{x}’|)$$[g]_{L\mathrm{p}}:= \max_{k=1},$$\backslash$.

$n[g_{k}]_{Lip}$’.

.

We then have the following error bound for the approximation of the filter by quantization.

Theorem 3.2 Under (A1) and (A2), given a fixed observation $(Y_{0}, \ldots , Y_{n})=(y_{0}, . . " y_{n})$ ,we have :$\emptyset(\mathbb{R}^{d})\sup_{\in BL_{1}}|\Pi_{n}\phi-\hat{\Pi}_{n}\emptyset|$There$\gamma_{n}(y)$is the density of$(Y_{1}, \ldots, Y_{n})$$\gamma_{n}(y)$$=$$\mathrm{E}$$\leq$$\frac{||g||_{\infty}^{n}}{\gamma_{n}(y)}\sum_{k=0}^{n}A_{n,k}||X_{k}-\hat{X}_{k}||_{2}$

,

(3.4)

at $y=(y_{1}, \ldots, y_{n})$ :$\ovalbox{\tt\small REJECT}\prod_{k=1}^{n}g_{k}(X_{k-1,yk-1}, X_{k}, y_{k})]$and$A_{n,k}$$=$$[P]_{L\dot{\tau}p}^{n-k+1}+ \frac{2[g]_{L\mathrm{s}\mathrm{p}}}{||g||_{\infty}}(\frac{[P]_{Lip}+1}{[P]_{Lip}-1}([P]_{Lip}^{n-k+1}-1)+2)$.

87

Elements of proof. We give a sketch of the proof of this theorem.
Step 1. Backward representation of the filter : We consider the unnormalized filter
given by the unnormalized forward linear equation :$\pi_{0}=\mu$,$\pi_{k-1}H_{k}$$=$$\pi_{k}$,$k=1$ ,$\ldots$$(\pi k)$, ,$n$so thatand$\Pi_{n}=\frac{\pi_{n}}{\pi_{n}(E)}$$\pi_{n}=\mu H_{1}$ ,..

$H_{n}$

Rom this symmetric expression, we introduce the transition kernels given by the backward
equation :$K_{n}=Id$ ,$K_{k}$$k=0$ ,

$H_{k+1}K_{k+1\prime}$$=$$\ldots$, $n-1$ ,so that$\pi_{n}$$=$$\mu K_{0}$Similarly, the quantized filter is expressed in a backward induction :$\hat{[}\mathrm{h}=\frac{\hat{\pi}_{n}}{\hat{\pi}_{n}(E)}$

,

where
$\hat{\pi}_{n}$$\hat{\mu}\hat{K}_{0}$

$=$

and
$\hat{K}_{n}=Id$,$\hat{K}_{k}$$=$$\hat{H}_{k+1}\hat{K}_{k+1}$,$k=0$ ,$\ldots$, $n-1$ .

Step 2. Error approximation of the unnormalized filter : We write$|_{J}\tau_{n}\phi-\hat{\pi}_{n}\phi|=|\mu K_{0}\phi-\hat{\mu}\hat{K}_{0}\phi|$$=$$\leq$

From the backward formula on$K_{k}$

and$\hat{K}_{k}$$|\mathrm{E}$$[K_{0}\phi(X_{0})]-\mathrm{E}$$[\hat{K}_{0}\phi(\hat{X}_{0})]|$$||K_{0}\phi(X_{0})-\hat{K}_{0}\phi(\hat{X}_{0})||_{2}$, we derive an estimation of$||K_{k}\phi(X_{k})-\hat{K}_{k}\phi(\hat{X}_{k})||_{2}$in terms of the quantization error $||Xk-\hat{X}_{k}.||_{2}$ by a backward induction :this uses
Lipschitz condition (A1), (A2)
is $\sigma(Xk)-$-contraction property of conditional expectation and the fact that$arrow$$\hat{X}_{h}$-$L^{2}$

measurable
Gronwall’s lemma.
-

88
Step 3. Error approximation of the (normalized) filter : We write$=$$\phi(\mathrm{R}^{d})\sup_{\in BL_{1}}|\Pi_{n}\phi-\hat{\Pi}_{n}\phi|$$\emptyset(\mathbb{R}^{d})\sup_{\in BL_{1}}|\frac{\pi_{n}\phi}{\pi_{n}(E)}-\frac{\hat{\pi}_{n}\phi}{\hat{\pi}_{\mathcal{T}l}(E)}|$$\frac{2\sup_{\phi\in BL_{1}(\mathrm{R}^{d})}|\pi_{n}\phi-\hat{\pi}_{n}\phi|}{\pi_{n}(E)\vee\hat{\pi}_{n}(E)}$$\leq$

and we notice that $\pi_{n}(E)=\gamma_{n}(y)$ is the density of$(Y_{1}, \ldots, Y_{n})$,.

$\square$Remark 3.2 Convergence of the quantized filter. If the grids are chosen optimally at, then in view of Zador’s theorem, we get a bound for the rate ofeach time $k=0$ ,convergence of the quantized filter :$\ldots$)$n$$\emptyset(\mathbb{R}^{d})\sup_{\in BL_{1}}|<\Pi_{n2}\phi>-<\hat{\Pi}_{n}$,$\phi>|$$\leq$$\frac{||g||_{\infty}^{n}}{\gamma_{n}(y)}\sum_{k=0}^{n}A_{n},{}_{k}C(\mathrm{P}_{X_{k}}, d)\frac{1}{N^{\frac{1}{k^{d}}}}$

.

(3.5)

Consequently :Given a total number of points $N$ , we may optimally dispatch the number of points
for each time grid, i.e. find (No, . . . ’ ) . $N0+\cdots+N_{n}=N$ and minimizing the r.h.s.
of (3.5).
converges
For a fixed horizon , we have the convergence of the quantized filter,goes to infinity.
astoinfinity,
the convergence of the filter is satisfied typically in the case
When goes toof discretized diffusion on [Os ] with Euler scheme of step $T/n$ :-$N_{k}$$\mathrm{s}.\mathrm{t}$$\mathrm{i}.\mathrm{e}.\hat{\Pi}_{\eta}$$n$-$\Pi_{n}$$\mathrm{m}\mathrm{i}\mathrm{n}0\leq k\leq nkN$

$n$

-

$T$

$X_{k+1}$

Under Lipschitz condition on

$=$

$b$

$X_{k}+b(X_{k}) \frac{T}{n}+\sigma(X_{k})\sqrt{\frac{T}{n}}\epsilon_{k+1}$

and$\sigma$.

, we have :$[P]_{Lip}$$=$$1+ \frac{c}{n}$for some constant . Then if we simply assign $N_{k}=\overline{N}=N/(n+1)$ points at each grid,(3.5) provides a rate of convergence of order$c$$\frac{||g||_{\infty}^{n}}{\gamma_{n}(y)}\frac{n+1}{\overline{N}^{1/d}}$This is to be compared with the rate of convergence obtained by Monte-Carlo methods
interacting particles :using$\overline{N}$$( \frac{||g||_{\infty}^{n}}{\gamma_{n}(y)})^{n}\frac{1}{\overline{N}^{1/2}}$

Remark 3.3 Extensions :first-order schemes. In the method described in paragraph 3.2,
as follows:for any Borel function
we approximated the probability transition$P_{k}$$P_{k}\phi(Xk)=\mathrm{E}$$[\phi(Xk+1)|Xk]$$\simeq$$\phi$$\hat{P}_{k}\phi(\hat{X}k)$$:=\mathrm{E}[\phi(\hat{X}k+1)|\hat{X}k]$BE)This is a piecewise constant approximation of the conditional expectation at the centers, and is called zero-order scheme. Thisandof the tesselations ofandsuggests to consider linear interpolation based on Taylor expansion around the centers of
the tesselations, which leads to correction terms in the transition weights , and to socalled first order scheme for quantization. The main interest is that thanks to stationary, we expect to get an estimation error with terms
property of optimal grids :$x_{k+1}^{j}$$\hat{X}_{k+1}$$x_{k}^{i}$$\hat{X}_{k}$$\hat{P}_{k}$$\mathrm{E}[Xk|\hat{X}k]=\hat{X}k$$||X_{k}-\hat{X}_{k}||_{2}^{2}$for zero order scheme as in (3.4). Consequently, we should get an
improved rate of convergence. These first-order schemes are developed in [11].

instead of

3.4$||X_{k}-\hat{X}_{k}||_{2}$Application :Pricing of European options under partial inform option

We give a direct application of the above quantization procedure for the calculation of, ,European options under partial observation. Namely, let us consider $(Xk)_{2}k=0$ ,(Logarithm)
$k=0$
is
the
,
,
,
(Yk),
price.
stock
volatility process of thethe return, $Yj$ , $0\leq j\leq k$ ), $k=0$ , . . ., , the completeof the stock price process. We denote, ,$F_{k-}^{Y}=\sigma(Yj,
0\leq
j\leq
k)$
$k=0$
.
the partial information, , when one,.
,
information andbut only price process. In this model, we are given an
does not observe
European option of payoff $h(Y_{n})$ and more generally $h(X_{n}, Y_{n})$ . Its price under complete
information is given at time by :$\ldots$$\ldots$$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$

$n$

$n$

$n$

$F_{k}=\sigma\langle Xj$$\mathrm{i}.\mathrm{e}$$n$$\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}/\mathrm{v}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}$$k$$U_{k}$$=$$\mathrm{E}$$[h(X_{n}, Y_{n})|F_{k}]=vkj(X_{k}, Y_{k})$,by the Markov property of $(X, Y)$ . (Here, we supposed thatfor some Borel functionis already a risk-neutral probability measure). The function may be easily computed bydifferent methods, e.g. quantization or Monte-Carlo. On the other hand, the price of theEuropean option under partial information at time is given by :$\mathrm{P}$

$vk$

$v$

$k$

$=$

$U_{k}^{Y}$$\mathrm{E}[h(X_{n}, Y_{n})|F_{k}^{Y}]$.

By the law of iterated condition expectation, it is written as :$U_{k}^{Y}=\mathrm{E}$$[h(X_{n}, Y_{n})|F_{k}^{Y}]$

$=$

$=$

$[v_{k}(\mathrm{x}_{k_{\rangle}}Y_{k})|F_{k}^{Y}]$$\mathrm{E}$$\int$$v_{k}(x, Y_{k})\Pi_{k}$(Jr) $=:\Pi_{k}v_{k}($ .,$Y_{k})$

Given an observation $(Y_{0}, \ldots, Y_{k})=(y0, \ldots, yk)$ , this is approximated by the explicit formula :$\hat{\Omega}_{k}v_{k}($where$\hat{\mathrm{n}}_{k}$is the quantized filter.,$y_{k})$$:=$$\sum_{i=1}^{N_{k}}v_{k}(x_{k}^{i},y_{k})\hat{\Pi}_{k}^{\mathrm{t}}.$

,

so
4

Numerical experiments (Fixed observation)

4.1

Kalman-Bucy model

We first illustrate the filtering quantization method in paragraph 3.2 with the Kalman Bucy
model. This linear Gaussian model for the signal-observation process is described by$X_{k+1}$$=$$pX_{k}+\theta\epsilon_{k}$$Y_{k}$$=$$X_{k}+\gamma\eta_{k}$,$X_{0}\sim’\Lambda’(0, \Sigma_{0})$,are indepenwhere and are constant matrices of appropriate dimensions, and
$N(0,
Id)$
case,
.
is
explicit :In
thisfilterthedent Gaussian noises :$(\epsilon_{k})_{\mathrm{J}}(\eta_{k})$$\theta$$\rho$$\epsilon_{k}\sim \mathrm{N}(\mathrm{Q}, Id)_{2}\eta k\sim$$\Pi_{n}$$\wedge A$$N(m_{n}, \Sigma_{n})$,are computed by forward induction, see e.g. [2].
and
where
is stationary,
We perform numerical tests with param eters chosen so that the signal. $X_{k}\sim N$ (0, So) for all . In that case, we can work with a single grid at each time .
Actually, we start with the optimal (prestored) grid for $N(0, I_{d})$ and make an homothetyof points at each time grid.
of . We put the same number$m_{n}$$\Sigma_{n}$$X_{k}$$k$$k$$\mathrm{i}\mathrm{e}$$\overline{N}$$\Sigma_{0}$4.1.1

Test 1 : convergence of the filter at a fixed instant n when the numberof each grid goes to infinityof points$\overline{N}$The approximate filter$\hat{\Pi}_{n}$is computed on the test functions,$\phi_{1}(x)$$=$$x_{d}$$\phi_{2}(x)$$=$$|x|^{2}$$\phi_{i}$, i.e.

$\Pi_{n}\phi:$, for$x=(x_{1}, \ldots, x_{d})$,$\phi_{3}$

($)

$=$

$\exp(-|x_{d}|)$,in signal dimension $d=1$ and 3. The following figures show the convergence and the rate
goes to infinity. The
of convergence of the approxim ated filter by quantization, when(see Remark 3.2) is then in In-scale 1 in dimension 1 andtheoretical convergence rate
1/3 in dimension 3, and is consistent to what we found by numerical experiments. Actually,
we even get better rate of convergence with the numerical tests.
$\overline{N}$$\overline{N}^{\frac{1}{d}}$Figure la: diml -:Convergence and Convergence Rate (in afor $=15$ and $\phi_{1}(x)=x$ .
$n$-scale) of$\ln$$\hat{\Pi}_{n}\phi_{1}$as$\mathrm{N}$grows,

91

Figure lb : diml -: Convergence and Convergence Rate (in afor $n=15$ and $\phi_{2}(x)=x^{2}$ .

-scale) of$\ln$

Figure lc : diml -: Convergence and Convergence Rate (in a -scale) of$=\exp(-|x|)$ .
for $n=15$ and$\ln$$\hat{\Pi}_{n}\phi_{2}$$\dot{\Pi}_{n}\phi_{3}$$\mathrm{f}\mathrm{f}\mathrm{i}$as$\mathrm{N}$grows,$\mathrm{N}$grows,$\phi_{3}(x)$$-\sim-\mathrm{o}u’\acute{\mathrm{v}}\cdot \mathrm{t}\mathrm{u}\mathrm{v}\cdot\oe\cdot$

.

07
$00$

$-\mathrm{r}-\mathrm{i}$.
’$―…dotarrow–$
02$0\mathrm{Q}$$\mathfrak{N}$Figure$2\mathrm{a}$

$m$

$m$

$m$

{

$\tau \mathrm{m}$$\mathfrak{M}\mathrm{N}$

$m

1n

leeo

rcoo

: dim3 : Convergence and Convergence Rate (in afor $n=15$ and $\phi_{1}(x)=x_{3}$ .
--scale) of$\ln$$\hat{\Pi}_{7l}\phi_{1}$as$\mathrm{N}$grows,

92$-\cdot*’ \mathrm{w}^{\mathrm{R}}\dot{\omega}0*|$$*$$\mathrm{t}\infty$.

.
$\wedge$$\mathrm{s}$

$A$

.

1

.

$\cdot$———-$\mathrm{m}_{0}$Figure$xo$$2\mathrm{b}$$\mathrm{r}\mathrm{o}$$\mathrm{g}w$$\mathrm{m}$$\prime 0_{\mathrm{N}}oe\mathrm{t}\mathrm{I}\prime 4\infty 76\infty\backslash e\omega$: dim3 -: Convergence and Convergence Rate (in a In-scale) of$=|x|^{2}$ .
for $n=15$ and$\hat{\Pi}_{n}\phi_{2}$as$\mathrm{N}$grows,$\hat{\Pi}_{n}\phi_{3}$as$\mathrm{N}$grows,$\phi_{2}(x)$$\cdot$$\mathrm{R}\cdot 1\mathrm{V}*\mathrm{I}*0\cdot \mathrm{w}$-06$–=–.-$
.

$–$ .

05

——

$*$

$\mathrm{o}\mathrm{a}$0’$0_{\mathfrak{g}}$$2\Phi$$\prime \mathrm{m}’\infty \mathrm{Q}\{\mathrm{o}\mathrm{m}2\mathrm{R}$$4\infty$$\epsilon\infty\iota\infty\tau_{\aleph}\mathrm{m}\prime \mathrm{T}\mathfrak{d}$Figure4.1.2$2\mathrm{c}$: dim3 -: Convergence and Convergence Rate (in a In-scale) of
for $n=15$ and $\phi_{3}(x)=\exp(-|x_{3}|)$ .

Test 2 : Stability of the filter for a fixed grid size$\overline{N}$as n goes to infinity.

We perform numerical tests for a signal in dimension 2. The following figures show thestability of the quantized filter when the horizon goes to infinity.
$n$Figure 3. $\dim 2-$ : Error dependence ofas, $\phi(x)=x_{1}$ and $\phi(x)=x_{2}$ .
for$\hat{\Pi}_{n}\emptyset$$\overline{N}=600$$n$grows,

93

A stochastic volatility model

4.2

We now consider the ARCH model :$X_{k+1}$$=$$pX_{k}+\epsilon_{k}$$Y_{k}$$=$$\sigma(X_{k})\eta_{k}$,,$X_{0}\sim\nu N(0, \Sigma_{0})$$\sigma(x)=\gamma+|x|$,

independent Gaussian noises. This model is popular in finance, as
arethe pricea discretization of stochastic volatility model, where $X$ is the volatility andtheforfilter.
formulareference
explicitnoismodel,
there
Kalman-Bucy
process. Unlike
infinity.
goes toThe following figures show the convergence of the quantized filter when

where$(\eta_{k})$$(\epsilon k)$$Y$$\overline{N}$$0\theta 735$$\mathrm{o}\mathrm{s}73$$\mathrm{o}sr_{-}5$$0972$$0\mathrm{B}745$$0\mathrm{B}7\mathrm{t}$osm$0\mathrm{B}7$oma$\mathrm{o}s\mathrm{a}\mathrm{e}_{0}$50$’\infty$$2\mathfrak{B}$$\infty$$3\infty$$\mathrm{g}$$\mathrm{m}$$2\infty\aleph$at fixed n as
Figure 4:SV model:filter values of, and $\exp(-|x|)$ .
for $\phi(x)=x$ ,$\hat{\Pi}_{n}\emptyset$$\overline{N}$grows,$|x|^{2}$More numerical illustrations are investigated in Sellami’s thesis [12] with in particularcomparison to Monte-Carlo particle methods.

5Approximation of the filter process by quantization
In the quantization algorithm described in the previous section, we need for each new
via the loca
set of observations, to compute again the quantized transition matrices$(\hat{H}_{k})$84likelihood observation function . This on-line phase may be rem oved by an off-line preprocessing of the observations, as suggested in [6] , One can then store in addition to the signal$gk$

quantizers, the local likelihood functions precomputed on the signal-observation grids. Thisobservation quantization approach is developed in [11], where error estimation are provided
and numerically illustrated. If we stress the dependence of the filter on the observation :, where,...,is a quantizer of Yk.
, then it is approximated by
However, we notice that the size of the look-up tables for the filter may be very large. For
would takeinstance, if
takes $M$ values, then at time , the random filter, which may explode for a long horizon . This makes computations
values inuntractable when solving dynamic optimization problems under partial information, even
if $E$ is already a finite state space
In order to overcome this numerical difficulty, we present a quantization approach introduced in [9] and based on the Markov property of the pair filter-observation
the filtration. Indeed, by denotingwith respect to the observation filtration, and using the law of iterated conditional expectations, we have forgenerated by:any an bounded Borelian function on$\Pi_{n}(Y_{0}, \ldots , Y_{n})$$\Pi\wedge n(\hat{Y}0$$\hat{Y}_{k}$$M^{n}$$\hat{Y}_{k}$$\hat{Y}_{n})$$\hat{\Pi}_{n}(\hat{Y}_{0}, .

$n$.

, ,\hat{Y},)$$n$$\mathcal{P}(E)$$(\Pi k, Y_{k})$$(F_{k}^{Y})$$(\mathcal{F}_{k})$$(X_{k}, Y_{k})$$k$$\mathcal{P}(E)\mathrm{x}$$\mathrm{n}\mathrm{d}$$\varphi$$\mathbb{R}^{q}$$\mathrm{E}[\varphi(\Pi_{k+1}, Y_{k+1})|F_{k}^{Y}]$

$=$

$=$

$=$

$\mathrm{E}[\mathrm{E}[\varphi(\overline{G}_{k+1}(\Pi k, Yk_{t}.Yk+1), Yk+1)|\mathcal{F}k]|F_{k}^{Y}]$$\mathrm{E}$$[ \int\varphi(\overline{G}_{k+1}(\Pi_{k}, Y_{k},y’), y’)P_{k+1}(X_{k}, dx’)qk+1(X_{k}, Y_{k}, x’, dy’)|F_{k}^{Y}]$$\oint\varphi(\overline{G}_{k+1}(\Pi_{k}, Y_{k}, y’), y’)P_{k+1}(x, dx’)qk+1(x, Y_{k}, x’, dy’)\Pi_{k}(dx)$This shows the Markov property of (Zk) with probability transitionto ) given by :$R_{k}$.

(5.6)(from time $k-1$$k$$R_{k}\varphi(\pi, y)$where $Qk(\pi, y, dy’)$ is the law of$y’$$arrow$$=$$Yk$$\int\varphi(\overline{G}_{k}(\pi, y, y^{\mathit{1}}), y’)Q_{k}(\pi,y, dy’)$

,

(5.7)

conditional on $(\Pi k-1_{7}Yk-1)=(\pi, y)$ with density :$\int gk(x, y, x’, y’)Pk(x, dx’)\pi(dx)$.

We consider a framework with finite state space : $E=\{x^{1}, \ldots, x^{m}\}$ , so that the filter
is a random discrete probability measure identified with a random vector
in the simplexof:$\Pi_{k}$$\Pi_{k}=(\Pi_{k}^{\tau})_{1\leq\not\in\leq m}$$K_{m}$$\mathbb{R}^{m}$$K_{m}$$=$$\{\Pi\in \mathbb{R}_{+}^{m}$:$\sum_{i=1}^{m}\Pi^{i}=1\}\simeq \mathcal{P}(E)$.

The idea is to apply a marginal quantization of the Markov chain $(z_{k})=(\Pi k, Yk)$ valuedin. Hence, for each $k=0$ ,, , we denote$K_{m}\mathrm{x}$$\mathbb{R}^{q}$$\ldots$$\hat{Z}_{k}$

$=$

$n$

,

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}_{z_{k}}(Z_{k}):=\sum_{i=1}^{N_{k}}z_{k}^{i}1_{C_{i}(z_{k})}(Z_{k})$S5points in,...,.
of size
the associated quantizer on the optimal grid $zk=$of the Markov chain (Zk) is approximated by the transition
The probability transition:
matrix$(z_{k-}^{1}$$z_{k}^{N_{k}})$$N_{k}$$K_{m}\mathrm{x}\mathbb{R}^{q}$$R_{k}$$\hat{R}_{k}=(\hat{r}_{k}^{\mathrm{z}j})$$=$$\hat{r}_{k}^{ij}$$\mathrm{P}$$[\hat{Z}_{k}=z_{k}^{j}|\hat{Z}_{k-1}=z_{k-1}^{i}]$.

are processed and estimated
The optimal grids $zk$ and the associated transition weights, which relyby the Kohonen algorithm. This is based on the Monte-Carlo simulations ofthemselves, from (5.7), on the following simulation procedure of the probability transition$\hat{r}_{k}^{ij}$$(Z_{k})$$R_{k}$.
..
:

according to the probability, and thensimulate $X_{k-1}$ with probability law
transition
according to the probability transition $\mathit{9}k(Xk-l, Yk-1, Xk)dy’$simulateby the forward filtering (finite-dim ensional) equation
compute$\Pi_{k-1}$$X_{k}$$P_{k}$$Y_{k}$$\Pi_{k}$$\Pi_{k}$.

$=$$\overline{G}_{k}(\mathrm{I}\mathrm{I}_{k-1}Y_{k-1}, Y_{k})=\frac{\Pi_{k-}{}_{1}H_{k}}{\Pi_{k-}{}_{1}H_{k}(E)}$

6

Application :pricing of American options under partial
observation

6.1

Optimal stopping problem under partial observation, and a horizon , we denote for any
Given a bounded measurable function on-stopping times valued in $\{k, \ldots, n\}$ , and we consider the$=0$ ,, ,as the set offollowing optimal stopping problem under partial observation :$h$$\ldots$$n$$E\mathrm{x}$

$k$

$n$

$\mathbb{R}^{q}$$(F_{k}^{Y})$$T_{k,n}^{Y}$$U_{k}$$=$$\mathrm{e}\mathrm{s}\mathrm{s}\sup_{\tau\in T_{\mathrm{t}^{Y}n}}.,\mathrm{E}[h(X_{\tau}, Y_{\tau})|F_{k}^{Y}]$

.

(6.8)

By using the law of iterated conditional expectation and the definition of the filter, we noticethat problem (6.8) may be reduced to a complete observation model with state variable the-adapted process (Zk) :$(F_{k}^{Y})$$U_{k}$$=$$\ovalbox{\tt\small REJECT}\sum_{j=k}^{n}1_{\tau=j}\mathrm{E}[h(X_{j_{2}j}Y)|F_{j}^{Y}]|\mathcal{F}_{k}^{Y}\ovalbox{\tt\small REJECT}$$\mathrm{e}\mathrm{s}\mathrm{s}\sup_{\tau\in \mathcal{T}_{k,n}^{Y}}\mathrm{E}$$=$$\mathrm{e}\mathrm{s}\mathrm{s}\sup_{\tau\in \mathcal{T}_{k,n}^{Y}}\mathrm{E}\ovalbox{\tt\small REJECT}\sum_{\mathrm{i}=k}^{n}1_{\tau=j}\Pi_{\mathrm{J}}h(., Yj)|F_{k}^{Y}\ovalbox{\tt\small REJECT}$$=$$[ \Pi_{\tau}h(., Y_{j})|F_{k}^{Y}]=\mathrm{e}\mathrm{s}\mathrm{s}\sup_{\tau\in \mathcal{T}_{k_{J}n}^{Y}}\mathrm{E}[\tilde{h}(Z_{\tau})|F_{k}^{Y}]$,$\mathrm{e}\mathrm{s}\mathrm{s}\sup_{\tau\in T_{k,n}^{Y}}\mathrm{E}$with the notation :$\tilde{h}(z)$$=$$\pi h(., y)=\sum_{i=1}^{m}h(x^{i}, y)\pi^{\mathrm{i}}$,$\forall z=(\pi, y)$, $\pi=(\pi^{i})_{i}\in K_{m}$ ,$y\in \mathbb{R}^{q}$.

se
By the$(F_{k}^{Y})$$U_{k}=u_{k}(Zk)$-Markov property of (Zk) and the dynamic progra mming principle, we havewhere functions $uk$ are calculated in backward induction by :$u_{n}(z)$$=$$\tilde{h}(z)$$u_{k}(z)$$=$$\max\{\tilde{h}(z)$, $\mathrm{E}[u_{k+1}(Z_{k+1})|Z_{k}=z]\}$ .

=\^u,Following [1], we provide a quantization approximation of $U_{k}=uk(Zk)$ by
on grid , as described in the previous
whereis a marginal quantization ofsection, and functions
are explicitly computed in recursive form by :$\hat{U}_{k}$$(\hat{Z}k)$$(Z_{k})$$k(\hat{Z}k)$$zk$$\text{\^{u}}_{k}$$\hat{u}_{n}(z)$$=$$\overline{h}(z)$$\hat{u}_{k}(z)$$=$$\max\{\overline{h}(z))\mathrm{E}[\hat{u}_{k+1}(\hat{Z}k+1)|\hat{Z}_{k}=z]\}$.

Prom an algorithmic viewpoint, this reads as :$L^{1}$,$\mathrm{i}=1$$\hat{u}_{n}(z_{n}^{i})$$=$$\overline{h}(z_{n}^{i})$$\text{\^{u}}_{k}(z_{k}^{i})$$=$$\max\{\overline{h}(z_{k}^{i}),$-error estimation ||Uk--\^U$k||_{1}$,...,$N_{n}$$N \sum_{j=1}^{k+1}\hat{r}_{k+1}^{i\gamma}\hat{u}_{k+1}(z_{k+1}^{j})\}$,

in terms of quantization error$\mathrm{i}=1$,$\ldots$,$||Z_{k}-\hat{Z}\iota.||_{2}$$N_{k}$.

is stated in [9],Numerical illustration : Bermudean options in a partially observed
stochastic volatility model

6.2

We consider an observable stock (logarithm) price $Y_{k}=$ in$Y_{k+1}$$=$$Y_{k}+(r- \frac{1}{2}X_{k}^{2})\delta$$s_{k}$, with dynamics given by :$+X_{k}\sqrt{\delta}\epsilon_{k+1}$

is a sequence of Gaussian white noise, and (Xk) is the unobservable volatility
where
process.
is the time step from an Euler scheme. We assume thatis a Markov
chain approximation a la Kushner [5] with spatial step A and with $m=3$ states of amean-reverting process :$(\epsilon_{k})$$(X_{k})$$\delta=\frac{T}{n}$$dX_{t}$$=$$\lambda(x_{0}-X_{t})dt+\eta dW_{t}$.

In this context of a partially observed stochastic volatility model, we consider a Bermudean
put option with payoff $h(y)=(\kappa-e^{y})_{+}$ , and with price :$u_{0}$$=$$\sup \mathrm{E}[e^{-r\tau \mathit{5}}h(Y_{\tau})]$

.

(6.9)

$\tau\in \mathcal{T}_{0,n}^{Y}$

We perform numerical tests with :-Price and put option parameters : $r=0.05$ , $S_{0}=110$ , ts $=100$ ,-Volatility param eters : A $=1$ , y7 $=0,1_{7}X_{0}=0.15$ ,Spatial step : $\Delta=0,05$ .
Quantization :Grids are of same size
fixed for each time Period with step--$\overline{N}$$\delta=\frac{1}{n}$.

87Monte Carlo
Quant. with
Quant. with $\overline{N}=600$
Quant. with
Quant. with $\check{N}=1200$
Quant. with $\overline{N}=1500$$\overline{N}=300$$\overline{N}=900$$E[\Pi_{n}^{1}]$$E^{\lceil}.\Pi_{n}^{2}]$0.287608
0.301651
0.301604
0.301598
0.301618
0.301605

0.422833
0.421725

0.421458
0.421316
0.421220.421205$E[\Pi_{n}^{3}]$Relative error (%)

0.289558
0.276624
0.276938$0.89\mathrm{S}$0.277086
0.277162
0.27719

0.886
0.881
0.879
0.878

Table 1: Comparison of quantized filter value to its Monte Carlo estimation

We first compare in Table 1 the filter expectation at the final date computed with atime step size $=1/5$ and by using the optim al quantization method with increasing grid
, and with 10 Monte Carlo iterations,size$\delta$$\overline{N}$We observe that besides the very low error level, the absolute error (plotted in Figure5) and the relative error are decreasing as the grid size grows.

Figure 5: Filter error convergence as$\mathrm{N}$grows

Secondly, in order to illustrate the effect of the time step, we compute the Anerican
option price under partial observation when the time step decreases to zero (i.e.
increases) and compare it with the American option price with complete observation of$\delta$$n$

98). Indeed, in the limit for
we fully observe the volatility, and so the partial
complete observation price.
theconverge
shouldtopriceobservation
Moreover, when we have more and more observations, the difference between the two
prices should decrease and converge to zero. This is shown in figure 6, where we performed(Xk,$\deltaarrow 0$$Y_{k}$

option pricing over grids of size $\overline{N}_{\Pi,Y}=1500$ in case of partial observation. The total
pointsobservation price is given by the same pricing algorithm carried out on
$(Xk,
Yk)$
approximation
convergence
for
the
,
rate
the
of
of
.
For
fixed
grid
product
theforis thewhereof the value function under partial observation is of order. Promnumber of points used at each time for the grid of $(\Pi k, Yk)$ valued inresults of [1], we also know that the rate of convergence for the approximation of the value
is the number of
wherefunction under full observation is of order
$(Xk,
Yk)$
explains why, in
,
in
.
This
grid
of
points at each time used for thevaluedorder to have comparable results, and with $m=3$ and $d=1$ , we have chosen$\overline{N}_{X_{\rangle}Y}=45$$n$$\tilde{N}_{\Pi,Y}^{1/(m-1+d)}$$\overline{N}_{\Pi_{\mathrm{z}}Y}$$K^{m}\mathrm{x}\mathbb{R}^{d}$$k$$\overline{N}_{X,Y}=m\mathrm{x}\overline{N}_{Y}$$m\mathrm{x}\overline{N}_{Y}$$E\mathrm{x}\mathbb{R}^{d}$$k$$\overline{N}_{Y}\sim\overline{N}_{\Pi_{\mathrm{z}}Y}^{1/3}$

Figure 6: Partial and total observation option prices as $3arrow 0$

In addition, it is possible to observe the effect of information enrichment as the time
step decreases. In fact, if we consider multiples of as the time step parameter, we noticethat the American option price increases for both total and partial observation models (seetables 2 and 3)
$n$

S9
$n$

Tot. Obs.
Part. Obs.

$(\overline{N}_{X}‘ Y=30)$$(\overline{N}_{\mathrm{I}\mathrm{I},Y}=1000)$

Variation

4
1.458630.921729
0.53

81.7568916
1.776421.470890.30

1.13898
0.61

Table 2: Am erican option price for embedded filtrations First Example-

Table 3: American option price for embedded filtrations Second Example-

References[1] Bally V. and G. Pages (2003) . “A quantization algorithm for solving discrete time multidimensional optimal stopping problems”, Bernoulli, 9, 1003-1049.
[2] Elliott R., Aggoun L. and J. Moore (1995) : Hidden Markov models, estimation and control,
Springer Verlag[3] Genon Catalot V. (2003) : “A non linear explicit filter”, Stat Prob. Lett, 61, 145-154.
[4] Stat S and H Luschgy (2000) : :Foundations of quantization for random $uectors_{)}$ Lecture Notes, Springer, Berlin, 230 pp.
in Mathem atics$\mathrm{n}^{0}1730$[5] Kushner H.J. and P. Dupuis (1992) . Numerical Methods for Stochastic Control Problems $m$Continuous Time, Springer, New York
[6] Newton N. (2001) : “Approximations for nonlinear filters based on quantization”, Monte Carlo
Methods and Appl, 7, 311-320.
[7] Pag\‘es G. and H. Pharn (2005) : “Optimal quantization methods for nonlinear filtering with, Bernoulli, 11.
discrete-time$\mathrm{o}\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{v}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}^{y}’$[8] Pages G,, Pham H. and J. Printems (2004) : “Optimal quantization methods and applications
to numerical problem s irr finance” , Handbook of computational and nu merical methods in finance,
ed S. Rachev, Birkhauser.

. Runggaldier W. and A. Sellami (2005) : “Approximation by quantization of the filter
process and applications to optimal stopping problems under partial observation”, Monte Carlo
Methods and Applications, 11, 57-82.

[9] Pham$\mathrm{H}_{2}$[10] Sellami A. (2004) : “Nonlinear filtering with observation quantization”, Preprint, Laboratoire
Paris 6 & 7 (France).
de Probabilit\’es et mod\‘eles aleatoires,$\mathrm{U}\mathrm{n}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{e}^{J}\mathrm{s}$[11] Sellami A. (2005) : “Quantization based filtering method using first order approximation”,
Preprint PM A-1009.
[12] Sellami A. (2005) : Methodes de quantification optimale en filtrage et appl cations en finance,
Phd Thesis, University Paris Dauphine