Generating the Brownian motion

To generate a Brownian motion (BM) path, it is clear that we can only sample its discretized approximation. Given a time discretization $\color[rgb]{1,1,.99} t_1 < \dots < t_d$, we know that the vector $\color[rgb]{1,1,.99} B_{t_1},\dots,B_{t_d}$ is a d-dimensional gaussian vector with mean $\color[rgb]{1,1,.99}\vec{0}$ and covariance matrix $\color[rgb]{1,1,.99}\Sigma_{ij}=\min(t_i,t_j)$.

In order to sample this gaussian vector, one can consider the decomposition $\color[rgb]{1,1,.99}\Sigma=AA^t$. There are 2 well kown ways to find $\color[rgb]{1,1,.99}A$: Cholesky decomposition (a covariance matrix is symmetric and positive definite), and PCA construction. Additionally, a BM path can also be generated by using the Brownian Bridge construction. Once $\color[rgb]{1,1,.99}A$ is known, the random variable $\color[rgb]{1,1,.99}A\vec{X}$ (where $\color[rgb]{1,1,.99}\vec{X}$ is a vector of d independent gaussians with mean 0 and variance 1), has covariance matrix $\color[rgb]{1,1,.99}\Sigma$ (one can easily see the proof using the characteristic function). To produce $\color[rgb]{1,1,.99}\vec{X}$, the easiest way is to take $\color[rgb]{1,1,.99}\vec{X}\sim N^{-1}(\vec{U})$, $\color[rgb]{1,1,.99}N^{-1}(y)$ the inverse cumulative distribution function for the gaussian and $\color[rgb]{1,1,.99}\vec{U}$ a vector of indpenent uniforms.

To generate the BM using qMC points, $\color[rgb]{1,1,.99}\vec{U}$ can be sampled according to a d-dimensional low-discrepancy sequence. Below, there is an example of 512 BM paths with 16 time steps, computed by each method using the same qMC sequence (first 512 points of a 16 dimensional scrambled Sobol' sequence):

cholesky Brownian Bridge
PCA

It is very important to remark that the PCA construction comes indeed from the SVD decomposition. From this decomposition, we can extract the singular values and understand which dimensions of the qMC sequence should we map to which singular values. As suggested in the Numerical integration section, the lower dimensions of the qMC sequence should be mapped to the higher singular values. This will provide full advantage of the stratification properties of the qMC sequences.

Another more advanced technique is to use the Karhunen-Loève expansion of the min Kernel (this Kernel corresponds indeed to the covariance of the Brownian motion). With this decomposition, one can write the Brownian motion as an infinite sum of independent normal gaussian random variables times the appropiate eigenfunctions/eigenvalues.