Numerical Integration Monte Carlo style

Mark Huber

Dept. of Mathematics and Inst. of Statistics and Decision Sciences

Duke University

mhuber@math.duke.edu

www.math.duke.edu/~mhuber

Integration is hard

Nature laughs at the difficulties of integration.

Pierre-Simon de Laplace

Darwin

Darwin visited the Galapagos in 1835

Finches

Darwin noted 14 species of finches

(these 11 photographed

by Dr. Robert Rothman)

Darwin's Finches

Not all finches on all islands!

14 types of finches, 17 islands

The Question

Is this data random?

Or is it evidence of evolution?

To answer deterministically, sum over all tables with same row and column sums

Is this data random?

Or is it evidence of evolution?

To answer deterministically, sum over all tables with same row and column sums

The Oldest Problem

What is the area of ?

Counting versus Integration

How many integer points in ?

Why is this hard?

These problems have very high dimension

Examples

Statistical problems

dimension is number of data points

Network (graph) problems

dimension is number of nodes

Physics problems

dim. is number of interacting entities

Curse of Dimensionality

Deterministic methods exist

Directly count the integer points

Running time grows exponential with dim.

Trapezoidal Rule, Simpson's Rule, etcetera

Effectively reduce dimension by 1

#P hard

Counting the proper colorings of a graph

Counting Hamiltonian cycles in a graph

Basic Monte Carlo

Acceptance/Rejection

1) Generate samples from bounding region

2) Find percentage lie in

3) Multiply by area of bounding region

Why rarely used

The Problem

Need “tight” bounding box

Otherwise need lots of samples for good estimate

Difficult to get in high dimensions

Research Area #1

Find good bounding boxes for actual high dimensional problems of interest.

Better Idea

Many times, problem reducible

Jerrum, Valiant, Vazirani, 1986

Example: convex regions

Estimating volume

28%

72%

Estimate

Suppose convex and fairly nice

large

(even with this help, can't come within factor of 2 efficiently with deterministic methods [Elekes 86])

Center box

Inside inner ball, box half edge length

Slicin' and Dicin'

Slice off region to right of box

Generate lots of random samples

Estimate percent of area in sliced region

Case I

If region with box at least 50%

use as reduced problem

If region with box at least 50%

use as reduced problem

62%

Case II

Else

find median, use that instead

50%

Approximating the median

1) grab samples from body

2) project onto one dimension

3) take median of projections

Either way...

Either

1) Match one facet of box or

2) Volume of body reduced by 1/2

50%

How many steps?

Note

For center box

Volume of body after many steps

So most steps that can be taken

How many samples?

To get median need [Cohen 97][Huber 98]

To get within of answer with probability

Overall, if steps taken need

Polynomial in the dimension!

To get samples

Most used method: Markov chains

Pick a direction uniformly at random

Move to a uniform point staying inside body

[Kannen, et. al. 94]

Some questions

Can bound for Markov chain be improved?

Can perfect sampling methods be used for this problem?

Research Area #2

Research Area #3

Currently working on

Some of my current research questions:

Data from unknown mixtures of distributions

(ex: responders versus nonresponders to drugs)

Perfect matchings in a graph

(ex: astronomical data is doubly truncated)

Multinormal distribution on positive orthant
Contingency tables with extra constraints

(ex: perhaps columns represent age)

The many worlds version of the Ising model

Self organizing lists

(because who has time to organize their own lists?)

The power of Monte Carlo

Monte Carlo methods are the only known way to handle high dimensional numerical integration

Many interesting questions remain:

Better envelopes for acceptance/rejection

Better Markov chains

Perfect sampling algorithms instead of MC

Mark Huber

2004-02-11T10:43:09