NE582 Monte Carlo
Spring semester 1998
|
NE582 Monte Carlo
Spring semester 1998
|
Lesson 4 -Choosing random numbers from distributionsIn the previous lessons reading, we learned how computers generate pseudo-random numbers uniformly in the range (0,1). In practice, though we need make choices based on general distributions over other ranges.In this lesson, we will study several ways of making choices from other distributions and over other (sometimes not continuous) ranges. We will discuss these in order of increasing difficulty:
as the symbol for the uniform deviate (i.e., random number supplied by
computer in range (0,1)).
Choosing a random number uniformly over a range (a,b)If the distribution is uniform and the only problem is that the range is (a,b) instead of (0,1) use the intuitive:
Enough said. Making choices from a discrete distributionFor the case that we must choose between N items, each of which has a relative probability of ,
the basic idea is that we divide the range (0,1) into appropriately sized
sub-ranges, pick a ,
and then determine which range it falls into. A procedure to follow
for this is:
1. Normalize the probabilities by finding
2. Choose the item j as the integer that satisfies the relation:
Choosing random numbers from a continuous distribution (directly)For continuous distributions, we will show two methods. The first, in this section, is the preferred one for well-behaved functions that can be integrated and inverted easily.Mathematically, we proceed by assigning (as usual) the x-axis to the variable to be chosen from a normalized probability distribution function f(x) over a range (a,b) and the y-axis to the pseudo-random number supplied by the computer. Then we set up a mapping function y=y(x) that relates the two. Ultimately, though, we will have to invert this to get a mapping from y to x. Okay, so it basically looks like this:
Note that the mapping function must be unique both in the x->y mapping
and the y->x direction, so it must be a non-decreasing function.
To figure out the mapping function, we consider the mapping between two differential areas of the axes, dy and dx:
Since the two represent the same region of the curve, they must correspond to the same probability:
where f(x) is the probability distribution in x and the corresponding
(uniform) distribution in y is 1.
Solving for the function y(x):
we see that the mapping function must be the same as the Cumulative
Distribution Function, F(x).
A step-by-step procedure for choosing an x from an unnormalized function
,
x chosen from: will, therefore, be distributed according to
Choosing random numbers from a continuous distribution (rejection)A second way of picking a variable x from a continuous distribution is the rejection method. It is less efficient an less elegant than the direct method, but is needed in cases where the direct method cannot be used. This can occur, of course, for a computer program if:
by picking points inside an enclosing square. Basically, we do the
same thing: create a uniform distribution that contains (i.e., bounds)
the desired function  ,
pick an (x,y) point inside the rectangle "under" the bounding function,
then keep it only if it is also under .
It is not even necessary to normalize the function first.
A step-by-step procedure for using this method to choose an x from an
unnormalized function 1. Find the maximum value, 2. Pick an x uniformly in the range using
3. Choose a y uniformly between 0 and
4. If Probability mixing methodThe probability mixing method is a simple mathematical technique used for choosing random numbers from linear combinations of p.d.f.'s. It gets its name from the fact that it allows the user to "mix" different p.d.f.'s. The method shows up in many different forms, so in this lesson we will present the simple mathematics and then proceed to show several of the forms that it can show up in.Mathematical formThe basic idea of the probability mixing method is that if you have a p.d.f. (possibly unnormalized) that is the sum of other functions:
and all of the
Choosing from that individual distribution. The step-by-step procedure for doing this is: 1. For each of the i functions, find its integral over the range:
2. Normalize the
3. Choose one of the functions, j, from 1 to N, from
a discrete distribution using these 4. Choose a value of x using the (now normalized) continuous distribution:
Example #1 -- Sum of functions over entire rangeThe most straight-forward application is when each of the functions is defined over the entire range. As an example, let us use
This, of course, can be broken down into:
where:
Following the procedure, we get: Step1. Find the
Step 2. Normalize the
Step 3. Choose one of the functions, j, using the We would do this by: Step 4: Choose a number x using the normalized distribution for the j chosen If j=1, this comes down to If j=2, then it is The overall answer is that we choose from 
90.94% of the time
Example #2 -- Histogram functionAnother example is choosing a random number from a histogram function, which is a step function over contiguous regions:
For example:
Although this function is a single continuous function, we can force into the multi-function format using:
This formally re-formulates
Because these are well-behaved functions, we can derive that:
which can be normalized and used to choose j, which in this case is
a choice of the jth "step".
Once a step has been chosen, the choice of a point on the step is done using:
Example #3 -- Linear fits to continuous functionsThe same basic idea applies to linear continuous fits to continuous functions, which are like histograms except that a function is approximated with connected line segments:
Once again, we make this a sum of functions that are 0 except within
a single region. If we let
The choices that must be made are:
Choose an x within region j using the relation: 
|
|
Return to Course Outline © 2004 by Ronald E. Pevey. All rights reserved. |
.
using:
,
is:
in the range 
.
,
of the function in the range.
,
keep the x. Otherwise, repeat 1-3.
over
a range (a,b)
are
greater than zero in the range (a,b). Then you can choose a random
number between (a,b) according to 
with a two-step procedure of:
's
so that they sum to 1:
probabilities.
over the range (1,2).
values in a discrete distribution:
,
j=1.
be the values of the functions at the endpoints, the equations for the
function within region i is:
