9772

The Method of Common Random Numbers: An Example

Variance reduction is of great interest to the creators of Monte Carlo experiments. For example, investment banks use very complicated Monte Carlo simulations to price esoteric mortgage-backed securities. These simulations often run overnight because many Monte Carlo trials are necessary to obtain (by the central limit theorem) a point estimate of some true population parameter, bounded by a relatively small confidence interval. One way to reduce the number of required Monte Carlo trials is to use a variance reduction technique.
The method of common random numbers is one such technique. It is useful in Monte Carlo experiments generally, including Monte Carlo integration. We illustrate its use with a simple example.
Let and , and and . Mathematica's numerical integration techniques tell us that , but this fact is not necessarily clear from the graphs of these two functions over the unit interval.
We propose two different techniques for estimating .
1. Suppose that we estimate and by and , where and are sequences of independent random numbers from the unit interval. Then .
2. Now consider the following alternative. Let and be positively correlated, but identically distributed uniform random variables. Estimate according to the rule .
The Demonstration output shows that is a modestly better way to estimate than . The histogram on the left features a simulated collection of the quantity . The histogram on the right features a simulated collection of the quantity .
Run the simulation repeatedly to see that in this example, the method of common random numbers always results in a reduction of variance.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

This method of common numbers produces good, but not overwhelming, variance reduction. The method of common random numbers (also known as the method of correlated sampling, the method of matched pairs, or the method of matched sampling) does not always work. It can backfire if the the engineer of the Monte Carlo simulation creates a negative, rather than positive, correlation between the two random variables and . Often, it is useful to choose , which we do in this example.
Why does this method work?
Recall that, for example, is a sequence of independent, identically distributed random variables. The variance of the first Monte Carlo method, when is independent of , is
.
Now consider the second Monte Carlo method, the method of common random numbers. The variance of this Monte Carlo method, when is positively correlated to , is
and therefore
.
If we make the additional assumption that and are either: (a) both monotonically nondecreasing; or (b) both monotonically nonincreasing, then
,
and we see that .
Notice that in both cases, and have the identical marginals—the method of common numbers only permits us to manipulate the joint distribution of and . Also, notice that in our example, both and are strictly monotonically increasing.
In this particular example, the variance reduction is always successful. However, notice that other measures of dispersion—like the range or the interquartile range—are not always reduced by the technique.
There are more powerful variance reduction techniques available, including antithetic variates, control variates, importance sampling, and stratified sampling. For more information on the method of common random numbers, see Sheldon Ross's textbook Stochastic Processes or Paul Glasserman's book on Monte Carlo methods.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+