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.