# Speeding up computations: when to use Quasi and standard Monte-Carlo in pricing

I am familiar with the theory of Monte-Carlo techniques in the numerical integration, and recently I have started my experiments with these methods applied to derivatives pricing. I am using Glasserman's book as my reference.

I've started by computing simply ATM vanilla call price. My setting is very basic: I have 100 time steps, I use Black-Scholes model (so that I can check the validity of the results) and Euler-Maryuama, Runge Kutta and Milstein numerical integration schemes. It appears that I need about $10^6$ samples to get stable results, and in Python that takes about 6 minutes. I have a rather fast machine, and I find this speed to be really low. Initially I thought the reason is in random sampler. However from what I've checked, sampling normal random variables does take some time, but $80\%$ of the computational time comes from the arithmetic operations (addition and multiplication) - even in case of basic Euler-Maryuama scheme. I do understand that in case of Geometric Brownian Motion there are much smarter simulation techniques available, but I'd like to keep it generic since I ultimately would like to work with more general diffusions.

Perhaps that's just an issue with Python, but that issue made me thought of speeding up my Monte-Carlo simulations. In Glasserman's book there are two types of speeding procedures:

1. Variance reduction, including control variates, antithetic sampling and importance sampling. I've used the latter before, and my best bet is on that.

2. Quasi Monte Carlo (low discrepancy sequences). I've never used it before, and it seems now to me that it can only be applied to compute integrals in the usual form, say when the densities are given explicitly just the analytic formula for the integral is unknown.

So far my goal is to be able to price exotic options with Monte-Carlo. Say, the model is 1-dimensional, and exotic payoff is extremely path-dependent. Perhaps later I'd need to price also an American version of such option. My questions are as follows:

1. Which of the variance reduction methods shall I pay special attention to?

2. Is QMC at all possible to apply in such problem, or do I really need to have an integral expression (over a finite-dimensional domain) for the option price?

To clarify my question regarding QMC. I see three ways (Q)MC can be applied in pricing.

• to sample increments of Brownian motion/jump components over the real line
• to sample whole paths from the path space
• if the value of the option have been found to have shape $$\tag{1} \int_D p(S_1,\dots,S_n)f(S_1,\dots,S_n)\;\mathrm dS_1\dots \mathrm dS_n$$ where $p$ is a payoff function, $S_1,\dots, S_n$ are payoff variable (multiple stocks or multiple time measurements of stock or whatever else), then (Q)MC can also be used to sample from $D$ to compute the integral in $(1)$ numerically.

As far as I understood from Glasserman's book, he only considers QMC as a good solution for the very last method, where he provides some evidence that it beats usual random MC. In contrast, for the first two methods he talks about usual MC and variance reduction techniques. So my question regarding QMC is: can it be successfully applied in the first two methods, or it is not well-designed for them and I shall not expect much benefits from using QMC in the first two methods?

• 6 minutes? That sounds like there might be something wrong with your code. I just quickly implemented the Euler-Maryuama scheme in MATLAB, with 100 time steps and $10^6$ sample paths. The vanilla call price took me less than 5 seconds to calculate. Granted, this is only one scheme, but still. – torbonde May 28 '15 at 12:09
• MC and QMC methods are essentially the same thing, except for the random variates generation. So, while using QMC isn't always all that useful, I'm not sure what you perceive as an issue. – ocstl May 28 '15 at 13:17
• @torbonde: straight away code for the simulation (with loop) in MATLAB runs 20 minutes for me (1.2 seconds for 1000 samples, hence extrapolation for 1000000 samples). Perhaps you coded it using matrix multiplication, but I am not sure how would you do that in case of higher-order scheme, that's why I'm talking about the loop implementation. – Ulysses May 29 '15 at 8:04
• @ocstl: see my update – Ulysses May 29 '15 at 8:17
• QMC can be applied anywhere MC methods can. For a m-dimensional problem with N d-dimensional samples, the upper bound for the approximation error for the QMC method is of $O (\frac{(log N)^m}{N})$ while the MC method's is $O (\frac{1}{\sqrt{N}})$. So, for low-dimensional problems, you can easily either reduce the number of random variates for the same error bound, or obtain a better estimate. – ocstl May 29 '15 at 16:22

By definition the fair value of an option is given by an expectation value of the payoff, $\mathbf{E}\left[\textrm{payoff}(\textit{paths})\right]$. The probability distribution of the paths is the risk neutral measure. This is just an integral expression of the form you wrote. This applies to all option prices. Many options are, of course, special in the sense that they only depend on the terminal value of each path.

Quasi Monte Carlo can therefore always be applied in these situations, and the sampling of paths is essentially the same thing as computing an integral (i.e. the expectation value of the option payoff). Glasserman's comment most likely refers to the fact that if you simply use QMC to generate paths, then it is possible that you are not receiving the full benefit of the low discrepancy of the random numbers generated by QMC. Put differently: the samples have a low discrepancy, but the generated paths might not. So the variance reduction might not be that big. This is all relative, in the sense that other variance reduction methods might produce better results (i.e. lower variance in the price estimate).

Now, your actual problem doesn't have anything to do with QMC. It's Python which is holding you back. Schemes such as Euler-Maryuama, Runge Kutta and Milstein are all schemes which cannot be vectorized. Therefore I suspect that you might have some code snippets of the form:

import numpy as np
... some definitions ...
for i in range(1, N_timesteps):
for j in range(N_paths):
S[i, j] = S[i - 1, j] * np.exp((r-0.5*sigma**2)*dt
+ sigma*np.sqrt(dt) * np.random.randn())


The problem is that this is usually very slow in Python. Things you can do to speed this up:

• Sample all your random numbers outside the loop.
• Pre-compute as many factors outside the loops as possible.
• Vectorize inner loops, if possible.
• Avoid functions calls inside the loop as much as possible.

So in general, we want to do as little as possible inside the for loops, since these calls are very expensive in Python.

For example, we could write the above as:

import numpy as np
... some definitions ...
Z = sigma*np.sqrt(dt) *np.random.randn(N_timesteps -1, N_paths)
drift = (r-0.5*sigma**2)*dt
for i in range(1, N_timesteps):
S[i] = S[i - 1] * np.exp(drift + Z[i-1])


So the inner loop has been "vectorized" away, the sampling is all done before the loops, etc.

If that is still not enough (which is very likely if you have many for loops), then you will need to perform some more "advanced" optimization. This usually comes down to taking the slowest piece of your code (almost always the for loop), put that in a function and write this function in e.g. Cython or Numba.

For example, with Numba we might define the for loop in a decorated function as:

from numba import autojit

@autojit
def my_loop(S, Z, drift):
for i in range(1, S.shape[0]):
for j in range(S.shape[1]):
S[i, j] = S[i - 1, j] * np.exp(drift + Z[i-1, j])

... some definitions ...
Z = sigma*np.sqrt(dt) *np.random.randn(N_timesteps -1, N_paths)
drift = (r-0.5*sigma**2)*dt
my_loop(S, Z, drift)


The first time my_loop is called Numba will compile the function (takes half a second). This results in a function that runs much, much faster. It's a great way to optimize certain routines in your code.

• In the first sentence you may have an error. Don't you mean that the arb price of an option is given by the expected value? – analystic May 30 '15 at 15:55
• Thanks, that's a nice answer. Actually, Glasserman does not comment anything on that matter AFAIK - in fact, his writing is good and such comment would help. Just he does not use QMC in the 'naive' way to generate the paths to compute the prince in a general way (through the expectation you wrote, integral over the path domain), only to compute (analytically derived) integrals over the payoff domain. I also had a guess, that a generated path sequence with Z being sampled using QMC may not have low discrepancy in the path space, so I wondered if there are other ways to get low-discrepancy... – Ulysses Jun 3 '15 at 6:54
• ...sequence of paths using QMC methods. Likely there is none, but would be good to know for sure. Wrt Python - thanks a lot for the tips! I am only building a prototype, so a real program is gonna be rewritten in C, so I don't even try to parallelize at this stage since other people would do that. Yet, I'd like to speed it up as much as possible from all other perspectives. Based on this answer and comments, I think I leave QMC aside and focus on variance reduction for classical Monte-Carlo. – Ulysses Jun 3 '15 at 6:58