Université Paris 6
Pierre et Marie Curie
Université Paris 7
Denis Diderot

CNRS U.M.R. 7599
``Probabilités et Modèles Aléatoires''

A quantization algorithm for solving multi-dimensional optimal stopping problems


Code(s) de Classification MSC:

Résumé: A new grid method for computing the Snell envelop of a function of a $\RR^d$-valued Markov chain $(X_k)_{0\le k\le n}$ is proposed. (This problem is typically non linear and cannot be solved by the standard Monte Carlo method.) Every $X_k$ is replaced by a ``quantized approximation" $\widehat{X}_k$ taking its values in a grid $\Gamma_k$ of size $N_k$. The $n$ grids and their transition probability matrices make up a discrete tree on which a pseudo-Snell envelop is devised by mimicking the regular dynamic programming formula. We show, using Quantization Theory of probability distributions the existence of a set of optimal grids, given the total number $N$ of elementary $\RR^d$-valued vector quantizers. A recursive stochastic algorithm, based on some simulations of $(X_k)_{0\le k\le n}$, yields the optimal grids and their transition probability matrices. Some $a$ $priori$ error estimates based on the quantization errors are established. These results are applied to the computation of the Snell envelop of a diffusion (assuming that it is simulatable or using its Euler scheme). We show how this approach yields a discretization method for Reflected Backward Stochastic Differential Equation. Finally, some first numerical tests are carried out on a $2$-dimensional American option pricing problem.

Mots Clés: Numerical Probability ; Markov chains ; Snell envelop ; Quantization of random variables ; Reflected Backward Stochastic Differential Equation ; American option pricing

Date: 2000-12-12

Prépublication numéro: PMA-628

Gzipped postscript file : PMA-628.ps.gz