Fast constructions from the Brownian motion and Brownian bridge are required in many applications such as Quasi-Monte Carlo simulations and statistical inferences on stochastic processes. A simple method for construction of discrete Brownian motion is a step-by-step method of computing the cumulative sum of i.i.d. normal variables.
The construction of N dimensional discrete Brownian motion (or a N-1 dimensional discrete Brownian bridge) that requires at most O(NlogN) floating point operations (flops) is called fast construction. Discrete Brownian motion can also be constructed using decompositions of its covariance matrix, and the method based on eigenvalue decomposition not only shows superior performances in many simulations over the step-by-step method but also becomes a fast construction. Usually the discrete Brownian bridge can be constructed from the discrete Brownian motion using the linear relationship between them. The inserting method using a decomposition of covariance matrix of discrete Brownian bridge gives another decomposition of covariance matrix for high dimensional discrete Brownian motion and it is very significant in Quasi-Monte Carlo simulations for financial derivatives.
Ri Sung Hyon, a section head at the Faculty of Applied Mathematics, has obtained eigenvalue decomposition of covariance matrix for discrete Brownian bridge and LDU (Lower-Diagonal-Upper) decompositions for covariance matrices of discrete Brownian motion and bridge newly and then proposed new fast construction methods on the basis of them. He has also proposed an inserting method for construction of discrete Brownian motion using eigenvalue decompositions which requires O(Nlog(logN)) flops.
The proposed new construction methods might be used effectively in simulations using Brownian motion and Brownian bridge. In addition, the construction algorithms would be used in analytical study for Brownian motion and Brownian bridge.
You can find more information about this in his paper “Decompositions of the Covariance Matrix of the Discrete Brownian Bridge: New Fast Constructions of Discrete Brownian Motions and Brownian Bridges” published in “American Journal of Applied Mathematics”.
© 2021 KumChaek University of Technology