## Brownian bridge path construction

When Sobol sequences are used, their variance reduction effect is enhanced when the paths are constructed via the Brownian Bridge technique. This which makes use of Brownian motion's conditional distribution when the end points are fixed to build a path by initially defining its main "skeleton" and then gradually filling in the detail. The numbers corresponding to the first dimensions of a Sobol N-dimensional vector have better equidistribution properties than the latter ones and are thus used to define the main structure of each path, leaving the less effective larger dimensions to just fill in the detail.

When Sobol sequences are used, their variance reduction effect is enhanced when the paths are constructed via the Brownian Bridge technique. This which makes use of Brownian motion's conditional distribution when the end points are fixed to build a path by initially defining its main "skeleton" and then gradually filling in the detail. The numbers corresponding to the first dimensions of a Sobol N-dimensional vector have better equidistribution properties than the latter ones and are thus used to define the main structure of each path, leaving the less effective larger dimensions to just fill in the detail.

It is obvious that using the Brownian bridge (BB) path construction significantly accelerates the convergence of the simulation (or integration if you prefer). The reason why is that, as hinted at above, some of the dimensions of the pricing problems are naturally more important than others. For example for a European option contract, the last value in the simulated path is clearly very important. The BB technique acts much like Principal Component Analysis would on the discretized Brownian motion, in that it orders the dimensions involved in near-optimal order of importance (see Jaeckel 2002). In that sense it can also be described as resulting in a reduction of the effective dimensionality of the problem. This reduction combined with the fact that Sobol numbers perform better in the lower dimensions, enables the gains seen in the above presentation by matching those better low dimensions of the Sobol sequences to the most important dimensions of the problem at hand.

Perhaps agreeing with intuition, the effect is more dramatic with the Asian option, still significant with the barrier option and less so with the Bermudan vanilla. In the latter case the variance reduction benefit is less obvious (but generally still there as more tests show). It can also be seen that using the original Sobol sequence without BB doesn't quite work very well (the simulation starts biased high and then falls), but this behavior can be eliminated by discarding the first half of the total number of Sobol vectors we generate. This is sometimes known as "warming up" the sequence. At this point I am not sure if this behaviour is related to the particular initialization numbers used here, or is more general of Sobol sequences.

It can also be seen that the use of BB may also be helping us in a different way with the Bermudan calculation (other than reducing variance). First let us note that both simulations seem to undervalue the option. This is to be expected and is because the Longstaff-Schwartz algorithm involves an approximation of the continuation value of the option at each exercise date via least-squares regression. Because this is only an approximation, the exercise strategy based on it will be sub-optimal and thus the valuation will in general be low-biased. For this particular example 2^17 paths were used for the regression phase, with the first 5 weighted Laguerre polynomials as basis functions. This is not a bad specification but still not enough to eliminate all the low bias. That said it seems that this bias is smaller when BB is used (and this is usually the case), presumably because BB helps produce a more accurate fit during the regression phase.

Overall then we can say that Sobol numbers are pretty good for low dimensions but less so for high dimensions and that is why BB works so well for most problems. For high dimensions it is (was?) believed that they lose most, if not all their advantage over pseudo-random numbers and may even become worse. But that's OK because using the Brownian bridge we can always use their strong core (low dimensions) to "support" the main skeleton structure of a problem and come out winning. But how much less useful (or even bad) are the Sobol numbers generated by the pricer (via initialization parameters courtesy of Joe & Kuo, 2010) for those high dimensions? Not as bad as I expected as can be seen here.

You can reproduce the above graphs, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).

Perhaps agreeing with intuition, the effect is more dramatic with the Asian option, still significant with the barrier option and less so with the Bermudan vanilla. In the latter case the variance reduction benefit is less obvious (but generally still there as more tests show). It can also be seen that using the original Sobol sequence without BB doesn't quite work very well (the simulation starts biased high and then falls), but this behavior can be eliminated by discarding the first half of the total number of Sobol vectors we generate. This is sometimes known as "warming up" the sequence. At this point I am not sure if this behaviour is related to the particular initialization numbers used here, or is more general of Sobol sequences.

It can also be seen that the use of BB may also be helping us in a different way with the Bermudan calculation (other than reducing variance). First let us note that both simulations seem to undervalue the option. This is to be expected and is because the Longstaff-Schwartz algorithm involves an approximation of the continuation value of the option at each exercise date via least-squares regression. Because this is only an approximation, the exercise strategy based on it will be sub-optimal and thus the valuation will in general be low-biased. For this particular example 2^17 paths were used for the regression phase, with the first 5 weighted Laguerre polynomials as basis functions. This is not a bad specification but still not enough to eliminate all the low bias. That said it seems that this bias is smaller when BB is used (and this is usually the case), presumably because BB helps produce a more accurate fit during the regression phase.

Overall then we can say that Sobol numbers are pretty good for low dimensions but less so for high dimensions and that is why BB works so well for most problems. For high dimensions it is (was?) believed that they lose most, if not all their advantage over pseudo-random numbers and may even become worse. But that's OK because using the Brownian bridge we can always use their strong core (low dimensions) to "support" the main skeleton structure of a problem and come out winning. But how much less useful (or even bad) are the Sobol numbers generated by the pricer (via initialization parameters courtesy of Joe & Kuo, 2010) for those high dimensions? Not as bad as I expected as can be seen here.

You can reproduce the above graphs, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).

## References

[1] Jäckel, P. (2002). Monte Carlo Methods in Finance. John Wiley & Sons Ltd.