MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: easy question about random numbers

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


The second step moves two 4s from row 4 to row 2, giving


The third step moves a 4 from row 4 to row 5, giving


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.

  • Prev by Date: Re: easy question about random numbers
  • Next by Date: Re: Strange installation problem
  • Previous by thread: Re: Re: easy question about random numbers
  • Next by thread: Re: easy question about random numbers