I found what is called the "alias method" in http://fedc.wiwi.hu-berlin.de/xplore/ebooks/html/csa/node22.html. It sounds like it may be what you are wanting. The web page gives the following references:
Walker, A. J. (1974). New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronic Letters, 10:127-128. Walker, A. J. (1977). An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software, 3:253-256. Hope this helps. Dave Dodson On Jan 15, 9:21 pm, me13013 <[email protected]> wrote: > There is a clever algorithm stuck in my memory, for which I have > forgotten the reference (and the author to credit). I have had no > success searching for a reference online either. I am hoping someone > here can point me to a reference. I know a reference exists, because > I remember discovering the algorithm in some journal paper, probably > written in the 60s or 70s. I didn't stumble upon it until about > 2000. > > The algorithm solves the problem of picking a random variable from a > finite number of classes, with the probability of each class being > arbitrary (but given, and constant over time. It is able to do a > lookup in constant time, after some pre-computation to create a > lookup > table. > > How it works is best described by an example. Suppose I have ten > classes and the probabilities are these: > p(A) = .077 > p(B) = .093 > p(C) = .044 > p(D) = .091 > p(E) = .126 > p(F) = .147 > p(G) = .016 > p(H) = .168 > p(I) = .169 > p(J) = .069 > > It builds a table with 10 entries (shown below). Conceptually each > entry is a unit bar, divided into two pieces (the dividing points are > generally different for each bar). The left piece is assigned to one > class, the right to another (some bars may have both pieces assigned > to the same class). To convert a unit random value r to a random > selection, we multiply r by the number of classes, lookup the > corresponding table entry (using as index the floor of the scaled r). > Then we compare the scaled r to the entry's split value to decide > which side of the bar we're on, and which symbol to emit. > > For example, r=.503 scales to 5.03; entry [5] is "D 5.91 H", and > since 5.03 is less than 5.91, we select D. > [0] G 0.16 I > [1] C 1.44 H > [2] J 2.69 F > [3] A 3.77 E > [4] I 4.85 F > [5] D 5.91 H > [6] B 6.93 H > [7] H 7.96 E > [8] E 8.99 F > [9] F 9.50 F > > Table construction is not difficult but I'll leave that unexplained > unless anyone wants to see it. > > Does this algorithm ring a bell? > > Thanks for any help, > Bob H -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
