5
$\begingroup$

The Monte Carlo method for numerical integration is usually presented as a method invented to efficiently compute high dimensional integrals numerically. However, I haven't found any source which has a believable real world example of when it may be applied. All the sources I have provide "toy problems" which are simple integrals like say the 3D integral exp( -x^2 - y^2 - z^2 ) over a box, without any motivation. I would like a real world example, that is hopefully also accessible. For instance, for what specific problem did Ulam and Neumann originally invent the method?

$\endgroup$
  • 2
    $\begingroup$ This may be useful to you- permalink.lanl.gov/object/tr?what=info:lanl-repo/lareport/… In particular, I believe the first couple of paragraphs on p 133 (second full page), suitably interpreted, describe the Monte Carlo estimate of an integral of a region in a phase space. $\endgroup$ – Neal Oct 20 '16 at 20:17
  • $\begingroup$ what would you consider realistic? is other academic research (perhaps in Computer Science, Engineering, Physics) considered realistic? Are you looking for financial applications? $\endgroup$ – john mangual Oct 20 '16 at 20:28
  • 2
    $\begingroup$ Please consult a book on molecular dynamics or data science where high-dimensional integrals of this sort are routinely computed. For example, store.elsevier.com/Understanding-Molecular-Simulation/… or springer.com/us/book/9780387763699 $\endgroup$ – Nawaf Bou-Rabee Oct 20 '16 at 20:39
  • 3
    $\begingroup$ I would be amiss if I didn't mention the 1953 paper of Metropolis et al. en.wikipedia.org/wiki/… In that paper, the authors also relate their work to that of Mayer and Ulam. $\endgroup$ – Nawaf Bou-Rabee Oct 20 '16 at 21:22
  • 1
    $\begingroup$ Bollobas, Balister, Sarkar and Walters have some (recent!) results of the form: Suppose that (integral) is at least (threshold). Then (random geometric model) exhibits percolation.Here (integral) is a high-dimensional, complicated integral which seems hopeless to bound rigorously (they tried, quite hard); but by use of these Monte Carlo methods one becomes confident that it indeed exceeds (threshold) and hence the geometric percolation statement is true. $\endgroup$ – user36212 Oct 20 '16 at 21:29
5
$\begingroup$

Some buzzwords that should lead to some non-textbook examples: In the fields of uncertainty quantification, statistical inverse problems or Bayesian inference one wants, for example, compute conditional expectations for posterior distributions. The domain of integration has as many dimensions as the the quantity of interest has degrees of freedom, and this can be a distributed parameter which, after discretization, may well be in the ten thousands up to millions. Before Monte Carlo methods can be applied one needs to think carefully, how to generate samples from the distribution and one often uses Markov chains to do so (leading to Markov chain Monte Carlo methods).

To be a bit more concrete: Consider an inference problem where the quantity of interest $u$ is observed through an operator $A$. Moreover, take into account that the measurement $Au$ is not exact, i.e. we observe $v^\delta = Au + \eta$ with some noise $\eta$ and also consider the case where $A$ has no continuous inverse (or, discretized, a large condition number). Assuming that the distribution of the noise is known, we can write down the probability $$ p(v^\delta\mid u) = p(\eta). $$ If we further assume prior knowledge about the real $u$, formulated in a prior distribution $p(u)$ (could be Gaussian or something else - whatever makes sense in the application), then the distribution that is really of interest is the posterior $$ p(u\mid v^\delta) \propto p(v^\delta\mid u)p(u) $$ i.e. the one that answers the question "What is a probable $u$, now that we have seen the data $v^\delta$?".

It's not easy to deal with the posterior, since it is a distribution on the space where $u$ comes from, so if the problem is a discretized problem and you want $u$ with $n$ degrees of freedom, then, it is a distribution over $\mathbb{R}^n$ - $n$ in millions.

One quantity of interest for the posterior is the conditional mean, i.e. something like "the expected solution $u_{CM}$, given the current data $v^\delta$" and this is the integral $$ u_{CM} = \int u \, p(u\mid v^\delta) du $$ and this is an integral over $\mathbb{R}^n$. Here people (and especially companies) indeed use Monte Carlo integration. Even more concrete: $u$ is oil distribution under ground, $A$ takes this distribution and gives back the surface measurements under seismic stimulation and $v^\delta$ is the measurement you take. Oil companies invest a lot of time and money to infer as much as possible about the oil reservoirs and indeed use techniques as described above. They want a good resolution of the oil distribution and hence, $n$ as large as possible (but to have at least a crude picture of how it looks like under ground, you need at least some ten or hundred thousand…) This is probably not what Ulam and von Neumann had in mind but I think you can't get more real world than that.

A starting point for the general idea is

Kaipio, Jari, and Erkki Somersalo. Statistical and computational inverse problems. Vol. 160. Springer Science & Business Media, 2006.

and there are also some work on the concrete application of oil reservoirs like

Iske, Armin, and Trygve Randen. Methods and Modelling in Hydrocarbon Exploration and Production. Springer, 2005.

(but I have to admit that I do not know the latter book well).

$\endgroup$
  • $\begingroup$ Thanks! Do you know of a paper or book that has a worked example along these lines? $\endgroup$ – David Oct 27 '16 at 17:08
  • $\begingroup$ Added two books - can really recommend the first one. $\endgroup$ – Dirk Oct 27 '16 at 17:36
2
$\begingroup$

Here are a few papers that discuss high-dimensional Monte Carlo integrals, together with quotes from Math Reviews.

MR2719643 (2011i:65038) Griebel, Michael; Holtz, Markus; Dimension-wise integration of high-dimensional functions with applications to finance, J. Complexity 26 (2010), no. 5, 455–489.

"In addition to error bounds, the authors also produce numerical results. In particular they study several financial problems, with up to 512 dimensions."

MR2657124 (2011f:65319), Sloan, Ian H, How high is high-dimensional? Essays on the complexity of continuous problems, 73–87, Eur. Math. Soc., Zürich, 2009.

"For example, evaluating a parcel of mortgage-backed securities involves the calculation of 360-dimensional integrals! In 1995, Goldman Sachs approached J. F. Traub and S. Paskov of Columbia University, who investigated quasi-Monte Carlo ({qmc}) methods.... Traub and Paskov provided computations which showed that {qmc} methods using low-discrepancy sequences work very well."

[The Paskov and Traub results are reported in Faster evaluation of financial derivatives, Journal of Portfolio Management 22, 1995, 113-120. See http://www.cs.columbia.edu/~traub/cucs-030-96.pdf ]

MR2183869 (2006j:65061), Kuo, Frances Y.; Sloan, Ian H.; Lifting the curse of dimensionality,
Notices Amer. Math. Soc. 52 (2005), no. 11, 1320–1329.

"360-dimensional integrals appear in mathematical finance"

$\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.