2
$\begingroup$

I would like to show explicitly the rate of convergence of Monte Carlo method to be $O(\sqrt{n})$, where $n$ is the number of simulation paths. Assume I want to do that with a price of a European call option. That is, I pick an analytic solution for the price and start my simulation: fix the number of time steps, say 100 and choose a sequence of paths: $100, 400, 1600, 6400$, and I should see the error between the analytical solution and the one generate by MC decrease by $4$? Would that be the example how to generate it?

$\endgroup$
  • 1
    $\begingroup$ The rate of convergence is described by the central limit theorem. $\endgroup$ – user16651 Aug 1 '16 at 21:17
  • $\begingroup$ Indeed , as $n\to \infty$ then ${{\widehat{C}}_{n}}\to C$. in other words $$\frac{{{\widehat{C}}_{n}}-C}{{\sigma }/{\sqrt{n}}\;}\sim{\ }N(0\,,\,1)$$ $\endgroup$ – user16651 Aug 1 '16 at 21:28
  • $\begingroup$ I see that in books, my question is how to actually show it numerically, on the computer. $\endgroup$ – Medan Aug 1 '16 at 21:56
6
$\begingroup$

The estimation error is a random variable and not a simple scalar. As such, when performing one-shot assessments, you could always end up observing that using $6400$ paths provides a "better" price estimate than using $100$ of them. What matters is to investigate the variance of the estimator rather than looking at pointwise values it can take (*)

To get a graphical feel for the Monte Carlo rate of convergence, you'll need an exact price to compare your MC estimations to. For a European option and under the BS modelling framework, this price is given by the celebrated BS formula. Let's denote it by $C$. Similarly, let's assume you've picked a discretisation scheme for your SDE (although it's not needed for European contingent claims) and managed to simulate $N$ paths, hence $N$ values for the terminal asset price $S_T$: $$ S_T^{(n)},\ \forall n=1,\dots,N $$

  • Form a Monte Carlo estimator $\hat{C}_n$ of the true option price $C$ by using only $n$ paths out of the total $N$. $$ \hat{C}_n = \frac{1}{n} \sum_{i=1}^n e^{-rT} f(S_T^{(i)}) $$
  • Repeating this for all $n=1,\dots,N$ gets you a sequence of estimators $\{ \hat{C}_n \}_{n=1}^N$.
  • Plot the sequence $\{X_n\}_{n=1}^N$ where $X_n = \vert \hat{C}_n - C \vert$ in a log-log scale (x-axis = simulations used $n$, y-axis = $X_n$).

Due to CLT (as noted by @Behrouz Maleki), you should then observe that the "backbone" of your graph is a straight line of slope $-\frac{1}{2}$ as illustrated in the bottom subplot below (**)

enter image description here

(*) We can look only at variance because we know the mean is fine: MC estimators are unbiased (leaving aside discretisation-related bias as made explicit in @MJ73550's answer).

(**) You may want to skip the first simulations and start directly with $n=100$ to avoid polluting your graph.

$\endgroup$
  • $\begingroup$ Very Comprehensive +1 $\endgroup$ – user16651 Aug 2 '16 at 9:05
  • $\begingroup$ ok, but where is the discretization error then? Even if you have a very large $N$, having a fixed number of steps will give just a constant error which is not decreased, so I am not sure how you end up showing only the Monte Carlo error when compare the estimate with an actual price? $\endgroup$ – Medan Aug 2 '16 at 12:51
  • $\begingroup$ Also, in the first plot $C_n$ gets closer to $C$ with increasing $n$, but in the second plot there are larger differences between the two from left to right. Are the legends correct? $\endgroup$ – Medan Aug 2 '16 at 12:53
  • $\begingroup$ @Medan The legends are correct: it is the scale which changes between the 2 subplots. The first one is the classic one. The second illustrates the convergence in $\sqrt{N}$ (which in log-log terms means a negative slope of $-1/2$). In the second subplot, notice how the error $\vert C_n - C \vert$ starts around $10^0$ and finishes around $ 10^{-2.5}$ with peaks at $10^{-9}$. $\endgroup$ – Quantuple Aug 2 '16 at 13:01
  • $\begingroup$ @Medan Monte Carlo is a generic method for calculating the expectation of a random variable. The convergence is in $N^{-1/2}$ by the CLT. Now, it seems like you're looking at a particular case, where for some reason you cannot sample the random variable of which you wish to compute the expectation (here $S_T$ direclty) which produces an additional discretisation bias. It is not clear from your OP that it is the discretisation bias you're interested in. Note that (1) You can sample directly $S_T$ wirh no bias under the BS assumptions, (2) In case of bias MJ73550's answer tells it all. $\endgroup$ – Quantuple Aug 2 '16 at 15:25
3
$\begingroup$

Since you talk about time steps, I assume you use a discretization scheme (like Euler) to simulate your asset. In that case, you have two errors:

Let $X$ be the true asset, let $X^{M}$ be the discretized asset with $M$ time-steps and let $x^{M,i}$ for $i=1\dots n$ the $n$ paths.

I.e $(x^{M,i})_{i=1\dots n}$ is a $n$-sample of $X^{M}$

Then you have :

$$\mathbb{E}[f(X_T)]-\frac{1}{n}\sum_{i=1}^n f(x^{M,i}_T) = \underbrace{\mathbb{E}[f(X_T)]-\mathbb{E}[f(X^M_T)]}_{\text{discretization error}}+\underbrace{\mathbb{E}[f(X^M_T)]-\frac{1}{n}\sum_{i=1}^n f(x^{M,i}_T)}_{\text{Monte carlo error}}$$

Discretization error is governed by $\frac{1}{M}$ to the power of the order of the scheme.

MonteCarlo error is governed as you said.

$\endgroup$
  • $\begingroup$ thank you, I think this gets me closer. So assume I use Euler, that is it is first order in time. Then, If I were numerically to show an error estimate, i.e. $O(1/M)+O(1/\sqrt{n})$, I would need to double the number of time steps, keeping $n=M^2$, and see my error decrease by half? $\endgroup$ – Medan Aug 2 '16 at 12:20
  • 1
    $\begingroup$ In the case of Euler, for $f$ Lipschitz and with no particular assumptions on the eds, you have : $|E(f(X_T)-f(X^M_T)|\leq \frac{C_T}{\sqrt{M}}$, so you need to keep $ M~\sim~n$ $\endgroup$ – MJ73550 Aug 2 '16 at 16:15
2
$\begingroup$

If you are pricing a standard European-style option then there is no need to have any time-steps and any discretization error can be avoided. You can jump directly to the expiry time of the option in $T$ years using the formula

$S(T)=S(0) \exp \left( (r-\sigma^2/2)T + \sigma \sqrt{T} g \right)$

where $g$ is an independent Gaussian draw from $N(0,1)$. If you compare the results of this simulation to the output of the Black-Scholes European option pricing formula then you should see the inverse square root dependence of the error.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.