# Quasi Monte Carlo

I read several articles regarding quasi Monte Carlo algorithm with Sobol sequences but I still have questions.

I implemented MC simulations with an ordinary random generator in matlab. I'd like to improve the speed of convergence but I'm not sure it's the correct way.

Say I have to price a 2 year American barrier option with daily monitoring, from what I understood this is going to be a high dimensional problem (around 500 steps). I read that it doesn't work better than an ordinary MC.

Extrapolating, I will also price American basket options, therefore with even higher dimensions.

I would need help not to start implementing useless things.

Is QMC ok or should I stick to implementing other variance reduction techniques such as antithetic variable ?

General question: Are Sobol sequences any better than pseudo-random (PR) numbers (and thus still worth the effort) when the dimension is high? In most cases I'd say yes, if they are used with the Brownian Bridge (BB) path construction (or other effective dimensionality-reduction technique). Then again it depends on the type of option you are trying to price.

Have a look at these two pages that delve a little bit into this subject: https://www.acenumerics.com/option-pricer-sobol-sequences.html https://www.acenumerics.com/option-pricer-brownian-bridge.html

You can see there that for Asian options for example, Sobol numbers with BB give a huge advantage over PR numbers, even for high dimensions. For European barrier options the gain is smaller and for Bermudan/American options even less. But I still think that in all these cases you'll get better convergence wih Sobol & BB.

You can actually download the pricer from the site above and perform your particular test (American barrier with daily monitoring) so that you get the answer to your question, or at least a much better feel of what to expect. By the way, this will also point you to a different way of speeding up your MC pricing: Forgetting Matlab and going to C++ :) By the way, this pricer does the American exercise with the Longstaff-Schwartz algo. How are you planning to do it?

So I did a sample test for you, for an up and out Bermudan put with T=2Y and 500 monitoring points. First convergence graph is using PR numbers (what you call ordinary random numbers) with antithetics and the second is using Sobol sequences with BB path construction. For these I chose to use 10 basis functions (overkill, for accuracy) 65K paths for the L-S phase and 262K paths for the pricing.

A quick visual check gives the edge to Sobol & BB, though the gain is not dramatic. Unfortunately the pricer doesn't give you error estimates, so you have to go by the convergence graphs, which should give you an idea anyway. You can of course use the pricer yourself to do many more tests with different parameters and get a better idea of what to expect under different circumstances.

For Basket options I would expect the gains to be smaller. This is because the initial (better) dimensions of the Sobol variates will have to be allocated not only across the different time-points but also the different stocks in the basket. And if you use a stochastic volatility model then you'd also have the variance stochastic driver to take into account when deciding where to allocate your "best" Sobol dimensions.

• To be clear, I'm using Heston model to price options. To price American options I'm also using LS algo. The setup should be ok, the pricing accuracy is not yet. Since most of the pricing I'll be doing will be on basket options (US or EU options) I'm not sure the implementation of QMC is worth the time (set QMC with BB and a stoch vol model doesn't seem easy), if there's little improvement in the end. Anyway I'll play with pricer to get an idea – Cedric_W Aug 6 '18 at 7:32
• Basket, American, barrier and Heston, yes it sounds like the advantage you'd gain may not be significant. I would stick to the pseudorandom numbers to start with. Oh course there are "tricks" people do when pricing baskets (which I know little of). How many simulation paths are you using right now and what is your error? I've seen quite a few people here expecting miracles from 10000 paths... – Yian Pap Aug 6 '18 at 8:43
• My error is around 1%, or maybe a little less. 6 basis functions, 50000 paths for a 2Y US option. And it takes about 40s to run with LS algo. I'm going to implement antithetic and control variate and see what it gives in the first instance – Cedric_W Aug 6 '18 at 9:03
• That's not too bad. Is that for a US barrier with Heston? If so where do you get your benchmark from if I may ask, just curious. Yea do antithetics as it costs nothing. Not so sure the vanilla US control variate would help a lot for a barrier, but who knows. – Yian Pap Aug 6 '18 at 9:17
• Yes. I have access to several pricers from banks, that's how I compare. The point is that my computations are then not stable, whereas banks ones are... I also have little discrepancies on EU options so I hope control variate might help. I just don't know how this works exactly, just aware of the theory behind. – Cedric_W Aug 6 '18 at 9:48

Certainly, if the barrier is way out of the money and does not get hit often, quasi Monte Carlo is a good idea. It helps in achieving the right sampling frequency... This is not to say that you should not implement other variance reduction techniques as well. In my experience,

1) using a vanilla American option (no barrier) as a control variate helps; you should have prices of those readily available;

2) using the mirror image of each trajectory of random shocks as an antithetic variate helps;

3) applying importance sampling by putting a bigger weight around the barrier is likely to improve the accuracy.

• The barrier is usually -20 to - 50%. These are mainly down & in puts. 1/ how about basket options when you dont have theoretical prices ? 2/ To me, since you need to draw a second variable, it means that the number of simulations is doubled, is it correct ? Also, when in the simulation you draw uniform as well as Gaussian laws, you should mirror the draw for the 2 laws at the same time ? 3/ I haven't read IS method yet, but shouldn't the pricing be biaised it my paths tend to go to the barrier ? There's probably something I don't understand here – Cedric_W Aug 6 '18 at 7:38
• With importance sampling, pricing is not biased. You do tilt the sampling frequencies towards a particular kind of scenarios but, to compensate for that, your are evaluating a slightly different function on each scenario. Importance sampling is a very clever idea. I suggest you read about it in detail... The whole reason behind antithetic variates is that you do not sample the second trajectory. You just take shocks $\epsilon_i$ form the first trajectory (whatever they are: N(0,1) or U([-1,1])) and do: $\epsilon_i' = -\epsilon_i.$ – stans - Reinstate Monica Aug 6 '18 at 13:19
• A good reference on Monte Carlo methods, classic and modern, is Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). New York: Springer.. – stans - Reinstate Monica Aug 6 '18 at 13:20
• Ok i understand I'll have a look at the book. What about payoffs that depend on a wider range, such as autocalls with triggers at ATM strikes (100 i.e.) and with Option barrier at -40% ? The region is quit large in that case. – Cedric_W Aug 6 '18 at 13:47