Fast orthogonal transforms and generation of Brownian paths

We present a number of fast constructions of discrete Brownian paths that can be used as alternatives to principal component analysis and Brownian bridge for stratified Monte Carlo and quasi-Monte Carlo. By fast we mean that a path of length n can be generated in O(nlog(n)) floating point operations. We highlight some of the connections between the different constructions and we provide some numerical examples.

► Linear constructions of Brownian paths correspond to orthogonal transforms. ► Some orthogonal transforms enhance quasi-Monte Carlo. ► Principal component construction can be approximated by fast cosine transform. ► Orthogonal transforms can also enhance simulation of Levy paths.