Hi,Does anyone know of a smart way to perform integrals of the form\int\int...\int p(x1,x2,...xN) g(x1,x2,...xN) dx1dx2...dxNwhere p() is a multivariate normal and g is a simple (in most caseslinear) the region of integration is an N dimensional cuboid?N is of the order of 100.Cheers for any pointers.

frankly i dont know/remember the smartest way. so i just invent the wheel here:try to rotate the integrand ( g()*p() ) such that covariance matrix is diagonalised and m-gauss becomes factorizable (=g(x1)*g(x2)*g(x3)*...g(xN)). as a result, p() will become a bit more complex... and dont forget jacobian when rotating.nik

QuoteOriginally posted by: nikolfrankly i dont know/remember the smartest way. so i just invent the wheel here:try to rotate the integrand ( g()*p() ) such that covariance matrix is diagonalised and m-gauss becomes factorizable (=g(x1)*g(x2)*g(x3)*...g(xN)). as a result, p() will become a bit more complex... and dont forget jacobian when rotating.nikThanks nik. Rotation definitely makes the multivariate part easier - the integration range then becomes some transformed solid (parallelepiped?? ) which I wasn't quite sure how to handle.

I don't think there's an easy way to solve this problem. As a specific example, give me the integral of two uncorrelated normals over the region [10,20]x[2,8]. If you want to be precise, it's not that easy. Qualitatively speaking, a big product of uncorrelated normals is a spherical thing, which you're intersecting with a parallelipiped (did I spell that right?). These two things don't mix well! My gut reaction is to break the normals into regions. When you're near the high point of the bell, you will do well to use a polynomial approximation - just take it out a lot of terms, and the integration should be a piece of cake. In the tails, the integration region is big and it may take a lot more terms. The salient point here is that you have rapid decay. So you might as well integrate by parts a bunch of times. This should distill out the important stuff in the boundary terms (i.e. mostly the 'near' side), and you can throw away the rest when it appears sufficiently small. How this approach works in high dimensions is a good question. There are some research papers lying around. I'm going to put it on my 'to do' list.

QuoteOriginally posted by: twHi,Does anyone know of a smart way to perform integrals of the formWell, I suspect that you really haven't solved your problem in a smart wayif the answer is a 100-D integral. So, for the best advice, I would post theoriginal problem and perhaps someone will see a much better solution.regards,alan

all techniques I've seen involve in some way Monte-Carlo

The problem has also been studied in the context of optimization subject to chance constraints. Such problems lead to calculation of multivariate integrals over regions specified by linear-affine constraints. Such problems are notoriously intractable. A couple of hungarian scientist have tried to look for efficient calculations/approximations/bounding when the underlying distribution function is multivariate. Unless the problem can be recast as a series of univariate problems by a suitable transformation (or problems of small dimension, say, less than 6) there is not much hope. Monte-carlo methods is the weapon of choice...

QuoteOriginally posted by: AlanWell, I suspect that you really haven't solved your problem in a smart wayif the answer is a 100-D integral. So, for the best advice, I would post theoriginal problem and perhaps someone will see a much better solution.regards,alanAlan (and others)Thanks for the input. I would never say I have "solved" the problem in questionin terms of this many dimensional integral. I was just experimenting with(im)possible methodsThe problem is a rather invovled option with manystrikes conditioned upon exogenous variables and I know these extra variableshad strong correlation properties but was rather ignorant of existing models forthem.My gut reaction was that any explicit expectation value calculation was toodifficult. However looking in Abramowitz at calculating integrals of bi-normal densites over polygonal regions, the methods seemed very geometrical, I wondered if someone hadcome up with a neat geometrical method in may dimensions.Obviously not.Anyhow, there are plenty more ideas to try out...

One idea I had was to work with the sphericality of the normal, and use that as an approximation to the polygonal region. I can see how this would work for 2 dimensions, but it could be a lot stickier for higher dimensions. Here's the idea:- imagine that you have a piece of spherically-ruled graph paper - i.e. for d=2 you have circles and spokes.- you draw the region on the graph paper, and then, using the ruling, approximate the region with the little stretched boxes of the graph paper rulings- we are assuming that you've already done the change of variable to make the gaussian variables uncorrelated- integral of each little region is just theta . (N(r2) - N(r1)), and you add these up- as d increases, the theta term will be replaced by product of theta1.theta2.theta3....- because of the rapid decay, you can afford to be more sloppy about the approximation as the radial parameter gets bigger. Thus, the graph paper will not have regular rulings... the delta-r will increase very rapidly for a given error size- so, the problem is reduced to finding an algorithm which will approximate the polygonal region by these squares to a given error- whether this is computationally convenient or not remains to be seen, but since it's pretty fast to compute sines, cosines, and arctangents, it might not be too bad- high-dimensional performance... who knows. Depends on the region, but don't lose sight of the fact that specifying a high-dim polygon is already a pain.

Maybe you should look at the sparse finite element schemes for high dimensions ... I don't remember the reference, but they converge at least as well as MC without all the randomness ...

Such integrals are often encountered in quantum mechanics (if you are looking for analytic approximations), eg. move your constraint to exponent using integration over lagrange multipler and then try semiclassical approximation. From numerical methods Monte Carlo is the best.

Try a search for "Smolyak's construction" for the sparse grid method. Thomas Gerstner has done some work in finance with this.To be quite honest I didn't really undrestand his, much less implement! So if you get anywhere, let me know! I'd be interested!Charlie