Multilevel Monte Carlo path simulation. (English) Zbl 1167.65316
Summary: We show that multigrid ideas can be used to reduce the computational complexity of estimating an expected value arising from a stochastic differential equation using Monte Carlo path simulations. In the simplest case of a Lipschitz payoff and a Euler discretisation, the computational cost to achieve an accuracy of \(O(\varepsilon)\) is reduced from \(O(\varepsilon)^{-3})\) to \(O(\varepsilon)^{-2} (\log \varepsilon)^{2})\). The analysis is supported by numerical results showing significant computational savings.
MSC:
65C05 | Monte Carlo methods |
68Q25 | Analysis of algorithms and problem complexity |
91G60 | Numerical methods (including Monte Carlo methods) |