Home

Functional quantization of the Brownian motion and the Brownian bridge

If $ X $ is a bi-measurable $ L^2 $ stochastic process on $ [0,T] $, it can be considered as a random variable valued in the Hilbert space $ H = L^2([0,T]) $.

In [1], it is shown that in the Gaussian case, if the covariance function $ \Gamma^X $ is continuous, linear subspaces $ U $ of $ H $ spanned by $ N $-stationary codebooks correspond to principal components of $ X $, in other words, are spanned by eigenvectors of the covariance operator of $ X $.

Thus, the quantization consists first in exploiting the Karhunen-Loève decomposition. The discretization consists in truncating the decomposition at a fixed order $ d(N) $ and to quantize the $ \mathbb{R}^d(N) $-value Gaussian vector constituted of the $ d(N) $ first coordinates of the process on its Karhunen-Loève decomposition.

To reach optimal quantization, one has both to determine the optimal rank of truncation $ d(N) $ (the quantization dimension) and to determine the optimal $ d(N) $-dimensional Gaussian quantizer corresponding to the first coordinates.

Formally, if $ X $ is a bi-measurable $ L^2([0,T]) $ Gaussian process, with a continuous covariance function, its Karhunen-Loève expansion $ (e_n^X,\lambda^X_N) $ writes:

$\displaystyle X = \sum\limits_{k=1}^\infty \xi_n^X e_n^X \ \in L^2(\Omega \times [0,T]), $
where $ (\xi_n)_{n \geq 1} \sim \mathcal{N}(0,\lambda^X_N) $ is a sequence of independent Gaussian random variables.

The terms of the Karhunen-Loève decomposition are explicit for classical Gaussian processes (the standard Brownian motion, the Brownian bridge and the Ornstein-Uhlenbeck process).

  • The Karhunen-Loève decomposition of the standard Brownian motion $ W $ on $ [0,T] $ is:
    $$ e_n^W(t) = \sqrt \frac 2T \sin \left ( \frac{\pi t}{T} \left ( n - \frac 12\right )\right ), \ n \geq 1, $$
    $$ \lambda^W_n = \left (\frac {T}{\pi \left (n - \frac 12 \right )} \right )^2, \ n \geq 1. $$
  • The Karhunen-Loève decomposition of the standard Brownian bridge $ B $ on $ [0,T] $ is:
    $$ e_n^B(t) = \sqrt \frac 2T \sin \left ( \pi n \frac{t}{T}\right ), \ n \geq 1, $$
    $$ \lambda^B_n = \left (\frac {T}{n\pi} \right )^2, \ n \geq 1. $$

In this case, the $ d(N) $-dimensional random vector to be quantized is a Gaussian vector with diagonal variance-covariance matrix $ \xi^N = \{\xi^X_1, \dots, \xi^X_{d(N)} \} \sim {\cal N}(0, \Gamma_{d(N)}) $ with $ \Gamma_{d(N)} = \mathrm{diag}(\lambda^X_1, \dots,\lambda^X_{d(N)}). $

Optimal quantization of the Brownian motion

Download brownian_optimal_grids.zip

The compressed folder brownian_optimal_grids.zip contains optimal quantization grids of the standard Brownian motion.

To get optimal quantization, the point now is to quantize the finite-dimensional Gaussian vector $ {\cal N}(0, \mathrm{diag}(\lambda^W_1, \dots,\lambda^W_{ d(N)})) $ optimally.

Hence, the method is the same as for the standard distribution except that the simulated Gaussian vector is not standard. For a given size $ N $, all possible dimensions are tested, and the one that yields the smaller quadratic distortion ($ d(N) $) is kept.

For a given size $ N $, the text files are organized as follows. It presents in the form of a matrix $ G = (G_{i,j}) $ with $ N+1 $ rows and $ d+2 $ columns.

  • On row $ i, i=1,\cdots,N $: Element $ i $ of the grid and its companion parameters. Consider $ \Gamma_{d(N)}=\mathrm{diag}(\lambda^W_1, \dots,\lambda^W_{d(N)}) $
    $$ G_{i,1} = \left(\textrm{weight of the Voronoi cell of element } i \right)= \mathbb{P}[ \mathcal{N}(0,\Gamma_{d(N)}) \in C_i(G) ]. $$
    $$ \{G_{i,j}, j=2 \cdots d+2 \}= \left(\textrm{coordinates of element } i \right). $$
    $$ G_{i,d+2} =\left( \textrm{conditional local } L^2-\textrm{distortion of the cell of element } i\right) = \frac{\int_{C_i(G)} |z-G_{i,d}|^2 \mathcal{N}(0,\Gamma_{d(N)})(dz)}{G_{i,1}}. $$
  • On last row $ (i = N+1) $:
    $$ G_{N+1,j} = 0 \quad \textrm{ for }j=1 \cdots d+1. $$
    $$ G_{N+1,d+2} = \left(\textrm{quadratic distortion of the quantization grid}\right). $$
    $$ G_{N+1,d+2} = \left(L^1-\textrm{distortion of the quantization grid}\right). $$

In particular we can verify that

$$ \sum\limits_{i=1}^N G_{i,1} = 1, $$
and
$$ G_{N+1,d+2} = \frac{1}{\textrm{tr}(\Gamma_{d(N)})} + \sum\limits_{i=1}^N G_{i,1} G_{i,d+2}. $$

For further details and further reading, let us refer to [1].

Product quantization of the Brownian motion and the Brownian bridge

An other way to get a good quantizer of a Gaussian process is Product Quantization. In practice, $ N $ being settled, one determines the truncation threshold $ d(N) $ of the decomposition and then, $ X $ is approximated by $ X(t) = \sum\limits_{n=1}^{d(N)} x_n e_n^X(t), \quad 1\leq i \leq N $ where $ \left(x_1,\cdots,x_{d(N)}\right) $ is a quantizer of the $ \mathbb{R}^{d(N)} $-valued random vector $ (\xi_1,\cdots,\xi_{d(N)}) $.

The product quantization consists in choosing the quantizer $ \left(x_1,\cdots,x_{d(N)}\right) $ of $ \left(\xi_1,\cdots,\xi_{d(N)}\right) $ as a Cartesian product of one dimensional quantization grids.

Thus, one replaces $ x^i = \left(x_1^i, \dots, x_{d(N)}^i\right) \in \mathbb{R}^{d(N)} $ by $ x^{i_1,\dots,i_{d(N)}} = \left(x_1^{i_1}, x_2^{i_2}, \dots, x_{d(N)}^{i_{d(N)}}\right) \in \mathbb{R}^{d(N)} $ where $ \left(x^i_k\right)_{1\leq i \leq N_k} $, $ \quad 1\leq k \leq d(N) $ are optimized quantizers of the $ 1 $-dimensional Gaussian distribution, of size $ N(k) $, and where the values $ N(k) $ are such that $ N_1 \times N_2\times \cdots \times N_{d(N)} \leq N $. A database of optimal quadratic quantizers of the standard Gaussian distribution is available here.

After all, one has for a settled integer $ N $ to determine among all its possible product decomposition the one that minimizes the distortion error.

In article [2], the optimal product decompositions are used to compute Asian option prices in a stochastic volatility model.

Data to download:

Download RECORD_QF.TXT Download RECORD_QF_BB.TXT

The text file RECORD_QF.TXT contains optimal product decompositions for the standard Brownian motion of size $ N=1 $ to $ N=11519 $.

The text file RECORD_QF_BB.TXT contains optimal product decompositions for the standard Brownian bridge of size $ N=1 $ to $ N=11519 $.

The both cases two first columns give, for a number $ N \leq 11519 $, the value of the distortion of the optimal product quantization.

The following columns give the size $ N_{rec} $ of the best product quantizer for a maximum number of points of $ N $, and the corresponding distortion. At least, the corresponding optimal product decomposition is given.

References

  1. Harald Luschgy, and Gilles Pagès, "Functional quantization of Gaussian processes", Journal of Functional Analysis, vol. 196, no. 2: Academic Press, pp. 486–531, December, 2002.
  2. Gilles Pagès, and Jacques Printems, "Functional quantization for numerics with an application to option pricing", Monte Carlo Methods and Appl., vol. 11, no. 11, pp. 407-446, 2005.