Error analysis of the optimal quantization algorithm for obstacle problems

In the paper Bally and Pagès (2000) an algorithm based on an optimal discrete quantization tree is designed to compute the solution of multi-dimensional obstacle problems for homogeneous -valued Markov chains (Xk)0[less-than-or-equals, slant]k[less-than-or-equals, slant]n. This tree is made up with the (optimal) quantization grids of every Xk. Then a dynamic programming formula is naturally designed on it. The pricing of multi-asset American style vanilla options is a typical example of such problems. The first part of this paper is devoted to the analysis of the Lp-error induced by the quantization procedure. A second part deals with the analysis of the statistical error induced by the Monte Carlo estimation of the transition weights of the quantization tree.