Combining Brownian Bridges with Randomized Quasi-Monte Carlo

# Quasi Monte Carlo and Brownian bridge (how to combine them)


# Quasi Monte Carlo and Brownian bridge (how to combine them)












I am trying to understand how quasi Monte Carlo (QMC) and the Brownian bridge (BB) can be combined to price an asset, but I am having a hard time understanding how. I am just considering a European option on a single asset modelled by a simple scalar SDE $S_t=a(S_t,t)\mathrm{d}t+b(S_t,t)\mathrm{d}W_t$. Here is what I understand so far.

- In the usual Euler-Maruyama approximation, we discretise using the $\hat{S}_{t+1}=a(\hat{S}_t,t)\Delta t+b(\hat{S}_t,t)\sqrt{\Delta t}\mathrm{d}Z_t$.

- In standard Monte Carlo (SMC), $\mathbb{E}f(S_t)\approx\frac1{L}\sum_{i=1}^Lf(S_t^{(L)})$, where $L$ is the simulation number.

- We can also use a single BB with $M=2^N$ uniform timesteps by generating the end point first, and using $W_t|W_T\sim\mathcal{N}\left(\frac{t}TW_T,\frac{t(T-t)}{T}\right)$ to generate midpoints recursively.

- In QMC, instead of pseudo-random numbers, we generate using low-discrepancy sequences, e.g. rank-1 lattice/Sobol points.

I therefore have the following questions:

- How do I combine the BB and QMC ideas? I haven't found a resource that really helps me understand how to use the two of them together.

- The variance of the BB is geometrically decreasing, isn't that a good thing? I read that the BB is only helpful for QMC estimation of the European option, but not for SMC. Where does this come from? The same resource mentions that they "have the same variance and thus convergence rate of $\mathcal{O}(L^{-1})$", which does not make sense to me.

- How does this extend to multiple assets? So far, I understand the Cholesky decomposition $LL^\mathrm{T}=\Sigma$, $L{\bf W}_t^\perp={\bf W}_t$ helps us capture the covariance, but I don't see how this works with QMC/BB.

Edit: the resource I was referring to in particular is this one on page 7, which says "Both schemes have the same variance, hence their MC convergence rates are the same, but QMC sampling shows different efficiencies for SD and BBD".

## Answer by oliversm (score 1)

https://quant.stackexchange.com/a/61542

#### Combining Brownian bridges with quasi-Monte Carlo

> How do I combine the BB and QMC ideas?

Brownian bridges is just a means of producing a Brownian path $W$, and Monte Carlo is a means by which we can evaluate expectations and integrals. Regular Monte Carlo would use a pseudo-random point set $U$ to estimate such things, whereas quasi-Monte Carlo would use a low-discrepancy point set $\tilde{U}$. So what needs to be changed in the Monte Carlo scheme? The uniforms which generate the Gaussian increments $Z$ (aka the Normal random variables) should be switched for low-discrepancy quasi-random uniforms. To preserve the low-discrepancy property of the sequence, it is best to use a mapping which doesn't reject any samples. Arguably best for this is the inverse transform method, for which we usually have for regular Monte Carlo $Z=\Phi^{-1}(U)$, where $\Phi^{-1}$ is the inverse cumulative distribution function of the standard Gaussian distribution. For quasi-Monte Carlo you instead use quasi-Gaussian random variables $\tilde{Z}=\Phi^{-1}(\tilde{U})$.

Aside from this, you can largely proceed as normal, although for good estimates you really want to be doing randomised quasi-Monte Carlo.

> I haven't found a resource that really helps me understand how to use the two of them together.

I think the best resource is Randomized Quasi-Monte Carlo: An Introduction for Practitioners by Pierre l’Ecuyer.

> How does this extend to multiple assets?

With this in mind, I think you just proceed as you usually would, but using the set of quasi-Gaussian random variables (and being mindful of randomising your uniform sequences).

Regarding your second question about SMC (Sequential Monte Carlo I presume), the variance of Brownian bridges, and your (unnamed) resource, I don't know enough to suggest an answer addressing this point.

## Answer by Matt (score 0)

https://quant.stackexchange.com/a/68848

Let me explain in laymans terms how to go about doing this. Really I see no need to use a Brownian Bridge if you don't have path-dependent options; if it's just a single date expiry (with no averaging), just simulate to the expiration date for every simulation.

Basically, you usually want to use RQMC instead of normal QMC (as mentioned in the first answer), as it works on more complex problems, and tends to produce more accurate results. There are various scrambling methods available (if you use Python, the latest SciPy 1.7.1 package has a Sobol generator (good up to 21,201 dimensions - Joe and Kuo) with a built in scrambler (Owen-Scrambling)) https://docs.scipy.org/doc/scipy/reference/reference/generated/scipy.stats.qmc.Sobol.html. These points are fed into the the inverse of the standard normal cumulative distribution to generate your GBM shocks. The same way a normal MC simulation uses pseudo random numbers in the range 0->1. The python function that's fastest for this is scipy.special.ndtri(number in the range 0->1). You have to be a bit careful (i.e. adjust your shocks to avoid 0 and 1 values, which the inverse would generate -Inf and Inf shocks, respectively). Otherwise, use just as you would in a normal MC simulation. You should notice the results converge much faster than the standard MC pseudo random number based approach.

On Brownian Bridges - the reference documents usually describe this at simulating to an endpoint T_expiry, then backwards solving splitting the paths you desire by 1/2, 1/4/, 1/8, etc. until all shocks are created. This would be common with an Asian style arithmetic option, a basket of Asian arithmetic options, a calendar spread with the same style again, etc. Now a standard Brownian Bridge will begin (and end) at that first simulated T_expiry. The bridge has a fixed start and end point, with movement in between the 2 points. It's always easier to see an example, note this is using pseudo random numbers instead of RQMC ones, and not correlating the paths either: https://gist.github.com/delta2323/6bb572d9473f3b523e6e - see the 1st comment for the fix to get the last shock back at 0. Anyhow, the graphs will show that the shocks always start at a 0 shock and end at a 0 shock (price is the same at the start and end, with randomness in between).

Basically merge the 2 ideas together and change how your paths are generated. 1) simulate to T_expiry for each leg from F0 (say for a basket Asian option). 2) create your Brownian Bridge shocks leading to this value for each underlying 3) apply the shocks from the Brownian Bridge to get all your fixing date shocks against the simulated T_expiry instead of the F0 price, plug them into your GBM equation. 4) then repeat for each simulation batch, and do your normal payoff function for the type of option you're pricing. This is an example for 1 simulation path. You can generate all your shocks ahead of time instead (which is the normal way).

That's how I understand combining the techniques together. I have used RQMC and created my own version of the BB technique, but not combined them together for exotic option pricing (yet). Anyone with more experience, or that can explain more clearly the proper steps, please feel free to jump in and correct anything I said that is incorrect. I'm really just putting this together from what's in my head currently, what I've read about each technique, etc.

Hope this helps. It's more of a pragmatic approach, rather than a mathematical one.