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

CNRS U.M.R. 7599
| ||

``Probabilités et Modèles Aléatoires''
| ||

**Auteur(s): **

**Code(s) de Classification MSC:**

- 60G40 Stopping times; optimal stopping problems; gambling theory, See also {62L15, 90D60}
- 65C05 Monte Carlo methods
- 65C20 Models, numerical methods
- 65N50 Mesh generation and refinement
- 90A09 Finance, portfolios, investment

**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