Re: easy question about random numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg53429] Re: easy question about random numbers
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Tue, 11 Jan 2005 01:31:30 -0500 (EST)
- References: <crqb7f$cak$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Here's how the alias method works for "nice" rational probabilities.
Once this case is understood, the extension to real probabilities
should be straightforward.
Suppose we want to sample from the following
5-valued discrete distribution:
x p[x] histogram
1 1/30 1
2 4/30 2222
3 6/30 333333
4 9/30 444444444
5 10/30 5555555555
The setup routine, that creates the alias and comparand vectors,
"rectangularizes" the histogram by moving numbers from one row to
another until each row has the same length (in this case, 6), subject
to the condition that each row contains no more than two different
values. Each step moves as many numbers as possible from the longest
row to the shortest row, trying to make the "to" row the right length,
even if this makes the "from" row too short.
The first step moves five 5s from row 5 to row 1, giving
155555
2222
333333
444444444
55555
The second step moves two 4s from row 4 to row 2, giving
155555
222244
333333
4444444
55555
The third step moves a 4 from row 4 to row 5, giving
155555
222244
333333
444444
555554
The histogram is now rectangular.
To generate an observation from the original distribution,
choose a number at random from the rectangle:
first pick a row at random (equiprobably),
then pick a column at random (equiprobably).
The alias of a row is its second value.
In this case, the alias vector is a = {5,4,3,4,4}.
The comparand for a row is its proportion of original numbers.
In this case, the comparand vector is c = {1,4,6,6,5}/6.
To pick a column, compare a Uniform[0,1] variable, u,
to the comparand, c[[x]], for row x;
if u > c[[x]] then return a[[x]], otherwise return x.