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?
3
-
1$\begingroup$ The rate of convergence is described by the central limit theorem. $\endgroup$– user16651Aug 1, 2016 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$– user16651Aug 1, 2016 at 21:28
-
$\begingroup$ I see that in books, my question is how to actually show it numerically, on the computer. $\endgroup$– MedanAug 1, 2016 at 21:56
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
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 (**)
(*) 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.
-
$\begingroup$ Very Comprehensive +1 $\endgroup$– user16651Aug 2, 2016 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$– MedanAug 2, 2016 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$– MedanAug 2, 2016 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$ Aug 2, 2016 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$ Aug 2, 2016 at 15:25
$\begingroup$
$\endgroup$
2
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.
-
$\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$– MedanAug 2, 2016 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$ Aug 2, 2016 at 16:15
$\begingroup$
$\endgroup$
0
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.
