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. The 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 a N dimensional discrete Brownian motion (or a N-1 dimensional discrete Brownian bridge) that require at most O(NlogN) floating point operations(flops) is called fast one. Discrete Brownian motion can be also constructed using decompositions of its covariance matrix and the method based on eigenvalue decomposition not only shows superior performances in many simulations to 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. In this paper, the inverse of the covariance matrix for the discrete Brownian bridge is computed. The explicit expression of eigenvalue decomposition for the covariance matrix is given. Using it, a fast construction of the discrete Brownian Bridge is derived. The LDU (Lower-Diagonal-Upper) decompositions of the covariance matrices for the discrete Brownian motion and Brownian Bridge are obtained, respectively. The constructions of the discrete Brownian motion and Brownian bridge derived from these decompositions are fast ones and have step-by-step types. It is interesting that the discrete Brownian bridge is constructed as the cumulative sum of normal variables. Performances of the step-by-step method and methods using LDU and eigenvalue decompositions are compared through simulation results on the maximum distributions of the Brownian motion and Brownian bridge. Finally, an inserting method for construction of discrete Brownian motion using eigenvalue decompositions which requires O(Nlog(logN)) flops is proposed. The new fast constructions could be significant in Quasi-Monte Carlo simulations require high accuracy.
| Published in | American Journal of Applied Mathematics (Volume 10, Issue 4) |
| DOI | 10.11648/j.ajam.20221004.13 |
| Page(s) | 134-140 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2022. Published by Science Publishing Group |
Brownian Motion, Brownian Bridge, LDU Decomposition, Eigenvalue Decomposition, Quasi-Monte Carlo
| [1] | Åkesson, F., Lehoczky, J. P. (1998). Discrete eigenfunction expansion of the multi-dimensional Brownian motion and the OrnsteinUhlenbeck process, Technical report, Carnegie-Mellon University. |
| [2] | Asmusssen, S., Glynn, P. W. (2007). Stochastic Simulation. Algorithms and Analysis, Springer-Verlag. |
| [3] | Billingsley, P. (1999). Convergence of Probability Measures, Second Edition, John Wiley and Sons, Inc, 1-120. |
| [4] | Ferger, D. (2018). On the supremum of a Brownian bridge standardized by its maximizing point with applications to statistics, Statistics and Probability Letters, 134, 63-69. |
| [5] | Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering, Springer-Verlag. |
| [6] | Imai, J., Tan, K. S. (2007). A general dimension reduction technique for derivative pricing, J. Comput. Finance, 10, 129–155. |
| [7] | Larcher, G., Leobacher, G., Scheicher, K. (2003). On the tractability of the Brownian Bridge algorithm, Journal of Complexity, 19, 511-528. |
| [8] | Leobacher, G. (2012). Fast orthogonal transforms and generation of Brownian motions, Journal of Complexity, 28, 278-302. |
| [9] | Kolkiewicz, A. W. (2014). Efficient Monte Carlo simulation for integral functionals of Brownian motion, Journal of Complexity, 30, 255–278. |
| [10] | Lin, J., Wang, X. (2008). New Brownian bridge construction in Quasi-Monte Carlo methods for computational finance, Journal of Complexity, 24, 109-133. |
| [11] | Moskowitz, B., Caflisch, R. E. (1996). Smoothness and dimension reduction in Quasi-Monte Carlo methods, Math. Comput. Modeling, 23, 37-54. |
| [12] | Papageorgiou, A. (2002). The Brownian bridge does not offer a consistent advantage in Quasi-Monte Carlo integration, Journal of Complexity, 18 (1), 171-186. |
| [13] | Quarteroni, A., Riccardo, S. (2007). Numerical Mathematics, Springer Berlin Heidelberg, 32-40. |
| [14] | Scheicher, K. (2007). Complexity and effective dimension of discrete Levy areas, Journal of Complexity, 23, 152-168. |
| [15] | Wang, X., Sloan, I. H. (2008). Quasi-Monte Carlo Methods in Financial Engineering: An Equivalence Principle and Dimension Reduction, Operations Research, 59 (1), 80-95. |
APA Style
Sung-hyon Ri, Ye-rim Ki, Kwang Ri. (2022). Decompositions of the Covariance Matrix of the Discrete Brownian Bridge: New Fast Constructions of Discrete Brownian Motions and Brownian Bridges. American Journal of Applied Mathematics, 10(4), 134-140. https://doi.org/10.11648/j.ajam.20221004.13
ACS Style
Sung-hyon Ri; Ye-rim Ki; Kwang Ri. Decompositions of the Covariance Matrix of the Discrete Brownian Bridge: New Fast Constructions of Discrete Brownian Motions and Brownian Bridges. Am. J. Appl. Math. 2022, 10(4), 134-140. doi: 10.11648/j.ajam.20221004.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajam.20221004.13,
author = {Sung-hyon Ri and Ye-rim Ki and Kwang Ri},
title = {Decompositions of the Covariance Matrix of the Discrete Brownian Bridge: New Fast Constructions of Discrete Brownian Motions and Brownian Bridges},
journal = {American Journal of Applied Mathematics},
volume = {10},
number = {4},
pages = {134-140},
doi = {10.11648/j.ajam.20221004.13},
url = {https://doi.org/10.11648/j.ajam.20221004.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20221004.13},
abstract = {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. The 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 a N dimensional discrete Brownian motion (or a N-1 dimensional discrete Brownian bridge) that require at most O(NlogN) floating point operations(flops) is called fast one. Discrete Brownian motion can be also constructed using decompositions of its covariance matrix and the method based on eigenvalue decomposition not only shows superior performances in many simulations to 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. In this paper, the inverse of the covariance matrix for the discrete Brownian bridge is computed. The explicit expression of eigenvalue decomposition for the covariance matrix is given. Using it, a fast construction of the discrete Brownian Bridge is derived. The LDU (Lower-Diagonal-Upper) decompositions of the covariance matrices for the discrete Brownian motion and Brownian Bridge are obtained, respectively. The constructions of the discrete Brownian motion and Brownian bridge derived from these decompositions are fast ones and have step-by-step types. It is interesting that the discrete Brownian bridge is constructed as the cumulative sum of normal variables. Performances of the step-by-step method and methods using LDU and eigenvalue decompositions are compared through simulation results on the maximum distributions of the Brownian motion and Brownian bridge. Finally, an inserting method for construction of discrete Brownian motion using eigenvalue decompositions which requires O(Nlog(logN)) flops is proposed. The new fast constructions could be significant in Quasi-Monte Carlo simulations require high accuracy.},
year = {2022}
}
TY - JOUR T1 - Decompositions of the Covariance Matrix of the Discrete Brownian Bridge: New Fast Constructions of Discrete Brownian Motions and Brownian Bridges AU - Sung-hyon Ri AU - Ye-rim Ki AU - Kwang Ri Y1 - 2022/08/17 PY - 2022 N1 - https://doi.org/10.11648/j.ajam.20221004.13 DO - 10.11648/j.ajam.20221004.13 T2 - American Journal of Applied Mathematics JF - American Journal of Applied Mathematics JO - American Journal of Applied Mathematics SP - 134 EP - 140 PB - Science Publishing Group SN - 2330-006X UR - https://doi.org/10.11648/j.ajam.20221004.13 AB - 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. The 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 a N dimensional discrete Brownian motion (or a N-1 dimensional discrete Brownian bridge) that require at most O(NlogN) floating point operations(flops) is called fast one. Discrete Brownian motion can be also constructed using decompositions of its covariance matrix and the method based on eigenvalue decomposition not only shows superior performances in many simulations to 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. In this paper, the inverse of the covariance matrix for the discrete Brownian bridge is computed. The explicit expression of eigenvalue decomposition for the covariance matrix is given. Using it, a fast construction of the discrete Brownian Bridge is derived. The LDU (Lower-Diagonal-Upper) decompositions of the covariance matrices for the discrete Brownian motion and Brownian Bridge are obtained, respectively. The constructions of the discrete Brownian motion and Brownian bridge derived from these decompositions are fast ones and have step-by-step types. It is interesting that the discrete Brownian bridge is constructed as the cumulative sum of normal variables. Performances of the step-by-step method and methods using LDU and eigenvalue decompositions are compared through simulation results on the maximum distributions of the Brownian motion and Brownian bridge. Finally, an inserting method for construction of discrete Brownian motion using eigenvalue decompositions which requires O(Nlog(logN)) flops is proposed. The new fast constructions could be significant in Quasi-Monte Carlo simulations require high accuracy. VL - 10 IS - 4 ER -
Email: