Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: <sebastian.egner@ph...>  20030505 07:54:42
Attachments:
Message as HTML

Hi, The algorithm in its most simple form selects a minimum and a maximum repeatedlyin fact once for every alias constructed. You may want to consult Section 3.2.6 [4] M.C. Fu: Simulation of DiscreteEvent Systems. Course notes for course BMGT 835 (Chapter 3) Spring 2003, Robert H. Smith School of Business, University of Maryland.=20 http://www.rhsmith.umd.edu/MSS/mfu/bmgt835/notesCh3.pdf for a modern and well written explanation (beware: a typo in 2.(a)). (The original article of A. J. Walker is terrible.) In fact, since there may be up to n aliases, the worst case run time=20 is O(n^2). With a priority queue, this could be brought back to O(n) with sophisticated things, and O(n log n) with small constants without much of effort. Good luck with you exams! Sebastian.  Dr. Sebastian Egner Senior Scientist Philips Research Laboratories Prof. Holstlaan 4 (postbox WY63, kamer WY 655) 5656 AA Eindhoven The Netherlands tel: +31 40 2742069 *** new telephone number fax: +31 40 2742566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard <jensaxel@...> 04052003 15:00 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: schematicsdevelopment@... Subject: Re: [Schematicsdevelopment] discrete random variab= les Classification:=20 sebastian.egner@... wrote: > Mike Sperber forwarded me a short discussion related to using > pseudo random values with given probability distribution. > In other words, given probabilities p[0], .., p[n1] summing to one, > construct a pseudorandom process for values x in {0..n1} > such that Pr{x =3D k} =3D p[k]. > > I would like to bring to your attention that there is a method to > draw the next pseudorandom value in O(1), after having > prepared a datastructure of size O(n). This method is known > as the "method of aliases" by A. J. Walker (Electronic Letters 1974). > It will be much faster than the code currently used in Schemathics > which uses time O(n) for drawing the next random value. For those that have Knuth, I have found the algorithm in volume 2, section 3.4.1 (page 120). He writes: However, there is actually a faster way to select x1,...,xk with arbitrarily given probabilities, based on an ingenious approach introduced by A. J. Walker [Electronics Letters 10, 8 (1974)]. Note the "ingenious". > For convenience, I just wrote some code for this :) > If there would be a good implementation for priority queues > around, the preparation phase could be improved... Is there special requirements for the priority queue? At first glance at the exercise in Knuth, it seems that one must be able to find both the minimum and the maximum element of the priority queue. Is the priority queue used after the initial preparation of the table? =20 Jens Axel S=F8gaard 
From: <sebastian.egner@ph...>  20030505 09:34:57
Attachments:
Message as HTML

By the way, if you really intend to do serious work on this... Recently, there has been a renewed interest in the topic of drawing at unimodally at random, but with dynamically changing weights (think of data compression applications). Walker's method requires constructing a new set of aliases and cutoffs when any of the weights change, but this can be avoided. There is an article by Mtias, Vitter, and Ni http://citeseer.nj.nec.com/correct/507561 who have devised a method for fast drawing at random while the weights (or probabilities) are changing. It would be interesting to know if the algorithms are practical. Cheers, Sebastian.  Dr. Sebastian Egner Senior Scientist Philips Research Laboratories Prof. Holstlaan 4 (postbox WY63, kamer WY 655) 5656 AA Eindhoven The Netherlands tel: +31 40 2742069 *** new telephone number fax: +31 40 2742566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard <jensaxel@...> 05052003 10:18 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: schematicsdevelopment@... Subject: Re: [Schematicsdevelopment] discrete random variab= les Classification:=20 sebastian.egner@... wrote: > The algorithm in its most simple form selects a minimum and a maximum > repeatedlyin fact once for every alias constructed. You may want to > consult Section 3.2.6 > > [4] M.C. Fu: Simulation of DiscreteEvent Systems. > Course notes for course BMGT 835 (Chapter 3) Spring 2003, > Robert H. Smith School of Business, University of Maryland. > http://www.rhsmith.umd.edu/MSS/mfu/bmgt835/notesCh3.pdf I'll do that. Thanks for the reference. > for a modern and well written explanation (beware: a typo in 2.(a)). > (The original article of A. J. Walker is terrible.) :) > In fact, since there may be up to n aliases, the worst case run time > is O(n^2). With a priority queue, this could be brought back to O(n) > with sophisticated things, and O(n log n) with small constants without > much of effort. Ok  I have Okasaki's book on functional datastructures and that contains quite a few heap algorithms. (so far I have implemented 7). Amongst them are heaps where insert takes O(1) and deletemin O(log n), but I better read the article first to figure out which heap to choose. > Good luck with you exams! Thanks  but it's not exactly my exams (I'm a teacher). The trick is that in the exam period, I don't (always) have to prepare for the next day, which mean that I have for time for Scheming. =20 Jens Axel 
From: <jensaxel@so...>  20030509 00:59:47

sebastian.egner@... wrote: > By the way, if you really intend to do serious work on this... I'm not. This is strictly for fun. > Recently, there has been a renewed interest in the topic > of drawing at unimodally at random, but with dynamically > changing weights (think of data compression applications). > Walker's method requires constructing a new set of aliases > and cutoffs when any of the weights change, but this can > be avoided. There is an article by Mtias, Vitter, and Ni > > http://citeseer.nj.nec.com/correct/507561 > > who have devised a method for fast drawing at random > while the weights (or probabilities) are changing. It would > be interesting to know if the algorithms are practical. But I might read the article  the other you recommended was enjoyable. Yours,  Jens Axel Søgaard 
From: <sebastian.egner@ph...>  20030509 07:28:26
Attachments:
Message as HTML

Sebastian wrote: > > By the way, if you really intend to do serious work on this... Jens Axel wrote: > I'm not. This is strictly for fun. All the better! Same with me. If you have any question relating to my implementation of Walker's method (in particular you will need to have two SRFIs available) let me know. Cheers, Sebastian.  Dr. Sebastian Egner Senior Scientist Philips Research Laboratories Prof. Holstlaan 4 (postbox WY63, kamer WY 655) 5656 AA Eindhoven The Netherlands tel: +31 40 2742069 *** new telephone number fax: +31 40 2742566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard <jensaxel@...> 09052003 00:01 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: <schematicsdevelopment@...> Subject: Re: [Schematicsdevelopment] discrete random variab= les Classification:=20 sebastian.egner@... wrote: > By the way, if you really intend to do serious work on this... I'm not. This is strictly for fun. > Recently, there has been a renewed interest in the topic > of drawing at unimodally at random, but with dynamically > changing weights (think of data compression applications). > Walker's method requires constructing a new set of aliases > and cutoffs when any of the weights change, but this can > be avoided. There is an article by Mtias, Vitter, and Ni > > http://citeseer.nj.nec.com/correct/507561 > > who have devised a method for fast drawing at random > while the weights (or probabilities) are changing. It would > be interesting to know if the algorithms are practical. But I might read the article  the other you recommended was enjoyable. Yours,  Jens Axel S=F8gaard 
From: <jensaxel@so...>  20030505 08:22:30

sebastian.egner@... wrote: > The algorithm in its most simple form selects a minimum and a maximum > repeatedlyin fact once for every alias constructed. You may want to > consult Section 3.2.6 > > [4] M.C. Fu: Simulation of DiscreteEvent Systems. > Course notes for course BMGT 835 (Chapter 3) Spring 2003, > Robert H. Smith School of Business, University of Maryland. > http://www.rhsmith.umd.edu/MSS/mfu/bmgt835/notesCh3.pdf I'll do that. Thanks for the reference. > for a modern and well written explanation (beware: a typo in 2.(a)). > (The original article of A. J. Walker is terrible.) :) > In fact, since there may be up to n aliases, the worst case run time > is O(n^2). With a priority queue, this could be brought back to O(n) > with sophisticated things, and O(n log n) with small constants without > much of effort. Ok  I have Okasaki's book on functional datastructures and that contains quite a few heap algorithms. (so far I have implemented 7). Amongst them are heaps where insert takes O(1) and deletemin O(log n), but I better read the article first to figure out which heap to choose. > Good luck with you exams! Thanks  but it's not exactly my exams (I'm a teacher). The trick is that in the exam period, I don't (always) have to prepare for the next day, which mean that I have for time for Scheming.  Jens Axel 