This post is based on the paper An Analysis of Sobol and the Brownian Bridge.

The traditional story (how we understand it)

We can read or hear it quite often: the Sobol numbers get worse at high dimensions, they show patterns of poor quality (see this great book by Peter Jaeckel), but the Brownian Bridge (BB) removes the problem by making sure that the first few dimensions are attributed to “the most important points”.

But what is the problem in Sobol? How bad can it get? From what dimension? Are its numbers really worse at higher dimensions, and in what sense? What do we mean by “most important points”? These questions are what pushed us to write the paper above.

Our analysis led us to a slightly different conclusion.

What we can confirm

First of all, the common results

• We can confirm the poor convergence of Sobol sequence in the Incremental Brownian motion (BM) construction and for high-dimensional paths, in the sense of a single very long path (we did not investigate the case of many short paths)
• We can confirm the patterns observed by P. Jaeckel in the charts he shows in his book. These are a very nice way of looking at the sequence and they can give us hints about what the problem is
• We can confirm that the BB brings a big improvement (and we can see that it doesn’t really improve the performance of Mersenne-Twister for instance).

Problems with the traditional story

And what we disagree with.

• Yes we see some patterns at dimensions like 60, but is that “high”? The convergence is not too bad at dim 60. Does it get worse beyond it? Continuously worse and worse? Or statistically? How bad?
• We created a small spreadsheet that draws the Jaeckel charts and we think it’s not so clear. Yes we do see some horrible patterns at high dimensions, but we also see nasty ones at dimension 20. Remember that these patterns are 2-dimensional charts therefore representing the combination of 2 dimensions, so there is a huge number of them. We saw bad patterns at combinations of the type 20×45. And 20 is not high.
• Also we do see horrible patterns at dim 500 for instance, but before it and after it we see tons of very good charts, just as good as in the small dimensions. How representative are the bad ones? Do they happen more and more often as we go high in dimensions? It seems to us that these are the points to prove in order to conclude that things indeed do get worse for Sobol at high dimensions. But we are not aware of the existence of such proofs (please contact us if you know where to find them).
• We are a bit perplex with the concept of “most important time” of a trade. What does that mean? Probably the maturity. But typically Sobol is relevant for the Monte-Carlo method which will be used for exotic products. Exotic products will often have intermediate important times such as barrier monitorings or call dates. We have no idea in advance that the early Sobol points will fall on these when using the Brownian Bridge.
• We could imagine a complex pre-processing algorithm that would be clever enough to determine at what times the trade has its largest sensitivity and attribute the early Sobol numbers to it. But that sounds very cumbersome.
• And anyway, the BB does improve things in a spectacular manner, that we can confirm. But we can also confirm this by pricing an exotic and making sure that a very important time falls not at all where the Brownian bridge picks early Sobol points. So the BB does not help because of the most important times, but then why does it help?

Our Results

Cut and Paste

If the Sobol sequence gets worse at high dimensions, we’d expect it to get worse and worse. Say you are pricing something with a BM of 500 dimensions. You can price it normally by using the first 500 dimensions. But you could also price it with using the next 500 dimensions. In principle you’d expect things to get worse. We find that they don’t.

Non-Black Processes

Even if we had written a clever pricing algorithm that is able to identify what the most important time is for every trade and brought the best Sobol number to it, what we mean by this is that the BM for this time is built from 1 Gaussian number coming from the best Sobol. How useful is that in real life situations? Very often when we use Monte-Carlo we’ll do so with a model that suffers from time discretization, such as local volatility models, stochastic volatilities, jumps, etc… In such a model we are not allowed to calculate the underlying spot price simply by knowing the value of the BM at that point: we need to discretize the interval into many small pieces and use the BM increments on each piece, that we multiply by all kinds of things (deterministic or not). So we are not using the total BM at that important point.

We may think that it should still help to have a good total BM, even though we’re not going to use it. But this does not sound like a strongly grounded reason.

Problem in the auto-correlations

In any case, the traditional story does not address the issue of what exactly goes wrong with the Sobol sequence.

So we looked at the distributions of many dimensions of the sequence. We were thinking that if something goes wrong at high dimensions, we should see the distributions of the corresponding numbers going farther and farther away from normal (after being transformed into Gaussians by the inverse CDF). We do not observe such a phenomenon, at least in the first 4 moments. The distributions at high dimensions seem just as good as those at low dimensions.

But Jaeckel’s charts give us a clue. Their patterns mean that there seem to be unwanted correlations between dimensions. And indeed we see this. We calculated the correlations between dimensions and drew their distribution (through many dimension pairs). While we do find that the distribution of the auto-correlation has a small mean and variance, at least much smaller than in Mersenne-Twister, we find that it is biased while Mersenne-Twister’s equivalent distribution of auto-correlations is centred on 0.

Auto-correlations and Incremental Brownian motion

Take the simple case of a vanilla option. In the incremental Brownian motion construction, and assuming a simple model with constant volatility and equal time steps, the value of underlying spot is essentially determined by the sum of the Gaussians and how well it approximates a normal distribution. The variance of this sum depends on the many auto-correlations. If these are not so small but well distributed around 0 as in Mersenne-Twister, the total variance does not suffer from the auto-correlations. But in Sobol sequence there is a bias in these auto-correlations (in our experiments it was a negative bias). So when we sum all the Gaussians, we accumulate the bias. And the more Gaussians we sum, the more bias we get. We showed that this accumulation can grow quite big and significantly alter the variance.

Why the Brownian Bridge helps

Now we can explain why the BB helps, without any relation to “important times”. The BB construction works by halving intervals. A quick inspection of its algorithm shows that for a path of dimension 2^n, no point on the path is reached by a sum of more than n-1 Gaussians. While for the incremental construction, the Gaussians sum little by little and the last one is obtained as a sum of 2^n.

Or in other words, the Brownian Bridge construction never accumulates a large number of Gaussians, no matter what point in time we are looking at.

Other remedies and parallel implementations

The BB is not the only remedy. Happily there are other solutions that are easier to implement in parallel. The first other such remedy we investigated is the scrambling (or “randomization”) of Sobol sequence, where a fixed number is added to the draws and the draws are rescaled by a modulo operation. We found this to be very efficient, about as efficient as the BB. Another remedy is more heuristic, and consists in warming-up the Sequence by rejecting a few 1000’s of the first draws (the first Monte-Carlo draws). We thank Marcos Da Silva for letting us know about this nice trick.

Conclusions

Let us summarize our conclusions:

1. Jaeckel charts do show bad patterns at high dimensions, but they also show bad ones at dimensions we’d consider as low, and most charts at high dimensions look good. There are some terrible ones but it’s hard to say how representative that is and if it even gets worse.
2. The distributions of individual Sobol numbers are not worse at high dimensions, at least in the first 4 moments
3. There is at least one problem in Sobol sequence, but it’s not particular to high dimensions. It is that the auto-correlations across dimensions have a bias (negative in our experiments)
4. In the incremental construction, this bias accumulates and it is because of its accumulation that pricing gets worse at high dimensions: not because the numbers get worse at high dimension, but because there is simply more accumulation of bad auto-correlations.
5. In the Brownian Bridge construction, all points on the path are reached only by a much smaller accumulation of Gaussians, thereby accumulating far less auto-correlation bias. And this makes the Brownian Bridge very helpful in remedying Sobol sequence’s deficiency.

Further Discussion

We welcome the readers’ feedback on the results above. In particular, if they disagree with the arguments or conclusions, we’d be interested to know the test results or arguments they have obtained that convinced them differently. Moreover, we think that a few points remain open to investigation, such as

1. Why is there a bias in the auto-correlations? Is it always negative?
2. Why is the Sobol sequence randomization helping in removing the bias?
3. Same question for the warm-up.