Serving the Quantitative Finance Community

 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 19th, 2015, 12:40 pm

QuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnQuoteI have carried out the A,B exerciseThat's fast. What are your findings?Maybe you think this is some form of Socratic dialogue, but it would be easier if you just explained what you meant (esp. about 2_A). I think the people replying have all used MC and PDE methods before.Isn't it? You play your cards close to your chest. LOL It's like pulling teeth. Never mind.BTW my question was to you, not 'people' :-)Anyhoo, it would see the issues are 1) Computability of a numerical approximation 2) How to define and measure accuracy, 3) the difficulty of partitioning functions spaces over random processes as is done with deterministic FEM. If yes, here's my take 2 cents...The original problem is defined in an infinite (uncountable) space U which is not very computable. If we can find a dense separable subspace V of U then we can expand the random process as an infinite Fourier-Hermite expansion in V which we truncate to N terms which we can compute in finite dimensional space V(N). Ghanem and Spanos discuss the details of this approach.Looking at Euler for SDE, the ensemble of all realisations is uncountable it would seem, so heuristically this by definition a shaky process.Quote2_A. It is missing the concept of a function as in real analysis.In spaces V and V(N) you do have functions of mathematical physics, e.g. orthogonal polynomials.U not.
Last edited by Cuchulainn on April 18th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 20th, 2015, 8:16 am

QuoteOriginally posted by: CuchulainnAnyhoo, it would see the issues are 1) Computability of a numerical approximation 2) How to define and measure accuracy, 3) the difficulty of partitioning functions spaces over random processes as is done with deterministic FEM. 1) This is not a problem for most MC schemes -- they are usually easy to implement.2) Usual measures are, for example, in L^2 norm in expectation (MSE)3) I don't see why this is an issue for MC -- just because it is for FEM does not mean it is for MC too.QuoteOriginally posted by: CuchulainnLooking at Euler for SDE, the ensemble of all realisations is uncountable it would seem, so heuristically this by definition a shaky process. If we are dealing with normal SDE with Brownian noise, your U is the set of continuous paths on [0,T], starting from 0. We want to integrate a functional over this space, i.e.[$]E [f(X_T)] = \int_U f(X_T(\omega)) P (d \omega)[$]where P is the Wiener measure.Typically, we do not have access to [$]X_T(\omega)[$] unless the SDE is exactly solvable. Instead, we replace by an approximation (e.g. the Euler-Maruyama scheme), call it [$]X^h_T(\omega)[$], with [$]h[$] being some discretisation parameter e.g. step size.We also cannot perform integration over U with respect to the Wiener measure, instead, we replace [$]P[$] with a measure which is equally weighted on all the MC paths. Call the paths [$]\omega^1, ... \omega^N[$] and the new MC measure [$]P^N:= \frac{1}{N} \sum_{i=1}^N \delta_{\omega^i}[$]Then, we can write the MC approximation as [$] \int_U f(X^h_T(\omega)) P^N (d \omega)[$].We have replaced integration over U w.r.t the measure P by integration with respect to a sum of Dirac masses (i.e. Summation!). You can then split the error into the part due to approximating [$]X_T(\omega)[$] by [$]X^h_T(\omega)[$] (the bias) and the part due to approximating P by [$]P^N[$] (the variance).There is nothing shaky going on. There is no concept of 'function' missing.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 20th, 2015, 10:23 am

QuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnAnyhoo, it would see the issues are 1) Computability of a numerical approximation 2) How to define and measure accuracy, 3) the difficulty of partitioning functions spaces over random processes as is done with deterministic FEM. 1) This is not a problem for most MC schemes -- they are usually easy to implement.2) Usual measures are, for example, in L^2 norm in expectation (MSE)3) I don't see why this is an issue for MC -- just because it is for FEM does not mean it is for MC too.QuoteOriginally posted by: CuchulainnLooking at Euler for SDE, the ensemble of all realisations is uncountable it would seem, so heuristically this by definition a shaky process. If we are dealing with normal SDE with Brownian noise, your U is the set of continuous paths on [0,T], starting from 0. We want to integrate a functional over this space, i.e.[$]E [f(X_T)] = \int_U f(X_T(\omega)) P (d \omega)[$]where P is the Wiener measure.Typically, we do not have access to [$]X_T(\omega)[$] unless the SDE is exactly solvable. Instead, we replace by an approximation (e.g. the Euler-Maruyama scheme), call it [$]X^h_T(\omega)[$], with [$]h[$] being some discretisation parameter e.g. step size.We also cannot perform integration over U with respect to the Wiener measure, instead, we replace [$]P[$] with a measure which is equally weighted on all the MC paths. Call the paths [$]\omega^1, ... \omega^N[$] and the new MC measure [$]P^N:= \frac{1}{N} \sum_{i=1}^N \delta_{\omega^i}[$]Then, we can write the MC approximation as [$] \int_U f(X^h_T(\omega)) P^N (d \omega)[$].We have replaced integration over U w.r.t the measure P by integration with respect to a sum of Dirac masses (i.e. Summation!). You can then split the error into the part due to approximating [$]X_T(\omega)[$] by [$]X^h_T(\omega)[$] (the bias) and the part due to approximating P by [$]P^N[$] (the variance).There is nothing shaky going on. There is no concept of 'function' missing.The part in bold is the part I precisely don't want to use; it doesn't work; instead I want to express the process as a truncated Fourier-Hermite expansion. It is very much like FEM but I have not seen it done for SDE, but it is used for SPDE (it's called the stochastic Galerkin method). This article is probably what I am looking for..
Last edited by Cuchulainn on April 19th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 20th, 2015, 10:36 am

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnAnyhoo, it would see the issues are 1) Computability of a numerical approximation 2) How to define and measure accuracy, 3) the difficulty of partitioning functions spaces over random processes as is done with deterministic FEM. 1) This is not a problem for most MC schemes -- they are usually easy to implement.2) Usual measures are, for example, in L^2 norm in expectation (MSE)3) I don't see why this is an issue for MC -- just because it is for FEM does not mean it is for MC too.QuoteOriginally posted by: CuchulainnLooking at Euler for SDE, the ensemble of all realisations is uncountable it would seem, so heuristically this by definition a shaky process. If we are dealing with normal SDE with Brownian noise, your U is the set of continuous paths on [0,T], starting from 0. We want to integrate a functional over this space, i.e.[$]E [f(X_T)] = \int_U f(X_T(\omega)) P (d \omega)[$]where P is the Wiener measure.Typically, we do not have access to [$]X_T(\omega)[$] unless the SDE is exactly solvable. Instead, we replace by an approximation (e.g. the Euler-Maruyama scheme), call it [$]X^h_T(\omega)[$], with [$]h[$] being some discretisation parameter e.g. step size.We also cannot perform integration over U with respect to the Wiener measure, instead, we replace [$]P[$] with a measure which is equally weighted on all the MC paths. Call the paths [$]\omega^1, ... \omega^N[$] and the new MC measure [$]P^N:= \frac{1}{N} \sum_{i=1}^N \delta_{\omega^i}[$]Then, we can write the MC approximation as [$] \int_U f(X^h_T(\omega)) P^N (d \omega)[$].We have replaced integration over U w.r.t the measure P by integration with respect to a sum of Dirac masses (i.e. Summation!). You can then split the error into the part due to approximating [$]X_T(\omega)[$] by [$]X^h_T(\omega)[$] (the bias) and the part due to approximating P by [$]P^N[$] (the variance).There is nothing shaky going on. There is no concept of 'function' missing.The part in bold is the part I precisely don't want to use; it doesn't work; instead I want to express the process as a truncated Fourier-Hermite expansion. It is very much like FEM but I have not seen it done for SDE, but it is used for SPDE (it's called the stochastic Galerkin method). This article is probably what I am looking for..But what do you mean by "it doesn't work"?It does work!!!! In theory and in practice P.S. -- the bit in bold is discretisation of an SDE. It is separate from generic MC methodology.
Last edited by emac on April 19th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 20th, 2015, 10:45 am

QuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnAnyhoo, it would see the issues are 1) Computability of a numerical approximation 2) How to define and measure accuracy, 3) the difficulty of partitioning functions spaces over random processes as is done with deterministic FEM. 1) This is not a problem for most MC schemes -- they are usually easy to implement.2) Usual measures are, for example, in L^2 norm in expectation (MSE)3) I don't see why this is an issue for MC -- just because it is for FEM does not mean it is for MC too.QuoteOriginally posted by: CuchulainnLooking at Euler for SDE, the ensemble of all realisations is uncountable it would seem, so heuristically this by definition a shaky process. If we are dealing with normal SDE with Brownian noise, your U is the set of continuous paths on [0,T], starting from 0. We want to integrate a functional over this space, i.e.[$]E [f(X_T)] = \int_U f(X_T(\omega)) P (d \omega)[$]where P is the Wiener measure.Typically, we do not have access to [$]X_T(\omega)[$] unless the SDE is exactly solvable. Instead, we replace by an approximation (e.g. the Euler-Maruyama scheme), call it [$]X^h_T(\omega)[$], with [$]h[$] being some discretisation parameter e.g. step size.We also cannot perform integration over U with respect to the Wiener measure, instead, we replace [$]P[$] with a measure which is equally weighted on all the MC paths. Call the paths [$]\omega^1, ... \omega^N[$] and the new MC measure [$]P^N:= \frac{1}{N} \sum_{i=1}^N \delta_{\omega^i}[$]Then, we can write the MC approximation as [$] \int_U f(X^h_T(\omega)) P^N (d \omega)[$].We have replaced integration over U w.r.t the measure P by integration with respect to a sum of Dirac masses (i.e. Summation!). You can then split the error into the part due to approximating [$]X_T(\omega)[$] by [$]X^h_T(\omega)[$] (the bias) and the part due to approximating P by [$]P^N[$] (the variance).There is nothing shaky going on. There is no concept of 'function' missing.The part in bold is the part I precisely don't want to use; it doesn't work; instead I want to express the process as a truncated Fourier-Hermite expansion. It is very much like FEM but I have not seen it done for SDE, but it is used for SPDE (it's called the stochastic Galerkin method). This article is probably what I am looking for..But what do you mean by "it doesn't work"?It does work!!!! In theory and in practice I take it back: Euler is not even wrong. Some claim that there are better methods, so I am interested in knowing what they might be.QuoteP.S. -- the bit in bold is discretisation of an SDE. It is separate from generic MC methodology.Indeed. We use Euler FDM to compute S at expiration and then we plug the value into the payoff.My question is: instead of Euler to compute S can we use Stochastic Galerkin?
Last edited by Cuchulainn on April 19th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 20th, 2015, 6:43 pm

QuoteOriginally posted by: CuchulainnI take it back: Euler is not even wrong. Some claim that there are better methods, so I am interested in knowing what they might be.There is a huge literature on MC methods for SDEs. See weak and strong Taylor schemes in Kloeden and Platen, and Richardson-Romberg extrapolation, and Multilevel MC, Ninomiya-Victoir, cubature on wiener space, Kusuoka scheme, exact simulation..............I still don't understand any of your original points though. You made 4 points, none of which hold any weight as far as I can see. Then, when asked to explain, you change tack and start asking about something else (stochastic Galerkin).I think I understand MC methods for SDE quite well, so it doesn't bother me, but it's confusing for other less-experienced people if you make vague comments about deficiencies of MC and then don't explain what they are.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 6:26 am

QuoteI still don't understand any of your original points though. You made 4 points, none of which hold any weight as far as I can see. Then, when asked to explain, you change tack and start asking about something else (stochastic Galerkin).This is beginning to sound like an inquisition :D If you don't understand it, let's call it a draw and move on. My remarks on stochastic Galerkin were very relevant because they are based on the FEM idea using polynomial approximations. QuoteI think I understand MC methods for SDE quite well, so it doesn't bother me, but it's confusing for other less-experienced people if you make vague comments about deficiencies of MC and then don't explain what they are.You probably are missing the nitty gritty of FDM for PDE/SDE. FDM for PDE is well-developed while less so for SDE.Nick Webber has the same kinds of conclusions in his book on VBA (chapter 25). In short, many methods are just average in performance and accuracy. For example, NW says "Higher-order Ito-Taylor schemes are complex; they can work well when they work at all but with some common processes, such as CIR, that do not satisfy their conditions, they may even blow up. Correcting for this is awkward, and unsatisfactory."This is a mathematical nightmare; it is not even wrong.Since you know SDE you may wish to explain this anomaly. Maybe you can appreciate why other methods might be useful to investigate.
Last edited by Cuchulainn on April 20th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 7:16 am

QuoteEuler usually works for processes met in finance but converges only slowly with possibly high error. It is usually possible to find a better scheme, even with the same rate of convergence, that better matches the distribution of the underlying state variable. Milstein is not always an improvement. NWEuler is not even wrong. QuoteRichardson-Romberg extrapolationExtrapolated Euler is also just OK. Do you have better experiences with this method? It's also twice as slow, at least. dv = d(lnV) = (- ½ s^2) dt + s dz
Last edited by Cuchulainn on April 20th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 9:52 am

QuoteOriginally posted by: CuchulainnQuoteEuler usually works for processes met in finance but converges only slowly with possibly high error. It is usually possible to find a better scheme, even with the same rate of convergence, that better matches the distribution of the underlying state variable. Milstein is not always an improvement. NWEuler is not even wrong. QuoteRichardson-Romberg extrapolationExtrapolated Euler is also just OK. Do you have better experiences with this method? It's also twice as slow, at least. dv = d(lnV) = (- ½ s^2) dt + s dz Okay -- the quote from NW does not make sense. A scheme cannot converge and have possibly high error. If it converges it means the error goes to zero. It might converge slowly, but then you need to take more MC samples or use smaller steps or both if you want a smaller error.Second, I don't know why you are saying Euler is "not even wrong" -- usually people say this when someone makes a logical fallacy in an argument. Euler works. You can prove that it works (UNDER CERTAIN CONDITIONS!). You can watch it work in practice.Third, if the CIR process does not satisfy the conditions needed for convergence, why would you expect it to converge?! There has been a lot of work done on MC methods for SDEs with non-Lipschitz coefficients, e.g. tamed Euler schemes. There is a very nice paper by Hutzenthaler & Jentzen on this. Complaining that Euler does not work for an SDE which does not satisfy the hypotheses for convergence is bizarre. I could equally take a very irregular PDE and show a standard method FDM doesn't work and then claim that all FDMs are rubbish.I also don't know see how R-R can be twice as slow. It is a higher order method, so the whole point is that it should be faster to converge.Finally, if you had just said "MC methods are not always that great, sometimes it's better to use a PDE method", I would agree with you. But you didn't. You made some vague comments about the MC framework not having a notion of function, there not being appropriate error estimates etc. None of which is true.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 10:09 am

QuoteI could equally take a very irregular PDE and show a standard method FDM doesn't work and then claim that all FDMs are rubbish.Not true. PDE and FDM are predictable. They have a history going back 100s of years. You can get all PDEs to work but SDEs are unpredictable when it comes to approximation.Quotethe quote from NW does not make senseLOL. It makes sense to NW and to me. QuoteNone of which is true. When I read this, this image came into my head for some strange reason.
Last edited by Cuchulainn on April 20th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 10:33 am

QuoteOriginally posted by: CuchulainnQuoteI could equally take a very irregular PDE and show a standard method FDM doesn't work and then claim that all FDMs are rubbish.Not true. PDE and FDM are predictable. They have a history going back 100s of years. You can get all PDEs to work but SDEs are unpredictable when it comes to approximation.This is bizarre. How can you claim that finite differences works for EVERY PDE?! See here: Section 5What do you mean "unpredictable"?! You look at the SDE, if it's coefficients satisfy certain hypotheses there is a proof that the method works. What is unpredictable?QuoteOriginally posted by: CuchulainnQuotethe quote from NW does not make senseLOL. It makes sense to NW and to me. [\q]Please explain how a numerical method can converge and have large error.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 1:13 pm

You don't give up easy, do you? A better place to look for PDE is Wilmott CFD threadThere are zillions of PDE/FDM threads here. //OK, can you price an option using the SDEdv = d(lnV) = (- ½ s^2) dt + s dz How many time steps do you need for Euler to work?
Last edited by Cuchulainn on April 20th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 1:27 pm

QuoteOriginally posted by: CuchulainnYou don't give up easy, do you? A better place to look for PDE is Wilmott CFD threadThere are zillions of PDE/FDM threads here. //OK, can you price an option using the SDEdv = d(lnV) = (- ½ s^2) dt + s dz How many time steps do you need for Euler to work?What is s in the above SDE?
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 1:36 pm

QuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnYou don't give up easy, do you? A better place to look for PDE is Wilmott CFD threadThere are zillions of PDE/FDM threads here. //OK, can you price an option using the SDEdv = d(lnV) = (- ½ s^2) dt + s dz How many time steps do you need for Euler to work?What is s in the above SDE?Let me quote OP from the bespoke link (aka RT*M)Quotes is the volatility. When we deal with large volatility, in a simulation, the first term quickly dominates. Am I doing something wrong? Now, how many draws are needed?
 
User avatar
emac
Posts: 1
Joined: July 7th, 2009, 7:15 pm

What does ?convergence? in Monte Carlo simulation mean?

April 21st, 2015, 1:38 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: emacQuoteOriginally posted by: CuchulainnYou don't give up easy, do you? A better place to look for PDE is Wilmott CFD threadThere are zillions of PDE/FDM threads here. //OK, can you price an option using the SDEdv = d(lnV) = (- ½ s^2) dt + s dz How many time steps do you need for Euler to work?What is s in the above SDE?Let me quote OP from the bespoke link (aka RT*M)Quotes is the volatility. When we deal with large volatility, in a simulation, the first term quickly dominates. Am I doing something wrong? Now, how many draws are needed?Is s a constant or a process or what?
Last edited by emac on April 20th, 2015, 10:00 pm, edited 1 time in total.