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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
