Fast orthogonal transforms and generation of Brownian paths

Area of Science:

• Computational Statistics
• Numerical Analysis
• Stochastic Processes

Background:

• Principal Component Analysis (PCA) and Brownian bridge are standard methods in Monte Carlo simulations.
• Existing methods for constructing discrete Brownian paths can be computationally intensive.
• Stratified and quasi-Monte Carlo methods require efficient path generation for variance reduction.

Purpose of the Study:

• To introduce novel, fast algorithms for constructing discrete Brownian paths.
• To provide computationally efficient alternatives to existing methods like PCA and Brownian bridge.
• To enhance the performance of stratified and quasi-Monte Carlo simulations.

Main Methods:

• Development of several distinct algorithms for fast discrete Brownian path generation.
• Analysis of computational complexity, achieving O(n) floating point operations for paths of length n.
• Exploration of interconnections between the proposed construction methods.

Main Results:

• Demonstrated fast constructions of discrete Brownian paths.
• Achieved generation of paths with length n in O(n) operations.
• Highlighted mathematical connections between different path construction techniques.

Conclusions:

• The presented fast constructions offer significant computational advantages for Monte Carlo methods.
• These new algorithms serve as viable and efficient alternatives to traditional approaches.
• Numerical examples validate the speed and applicability of the proposed discrete Brownian path constructions.