schematics-development

 Re: [Schematics-development] discrete random variables From: - 2003-05-05 07:54:42 Attachments: Message as HTML ```Hi, The algorithm in its most simple form selects a minimum and a maximum repeatedly---in fact once for every alias constructed. You may want to consult Section 3.2.6 [4] M.C. Fu: Simulation of Discrete-Event 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 6-55) 5656 AA Eindhoven The Netherlands tel: +31 40 27-42069 *** new telephone number fax: +31 40 27-42566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard 04-05-2003 15:00 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: schematics-development@... Subject: Re: [Schematics-development] 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[n-1] summing to one, > construct a pseudo-random process for values x in {0..n-1} > 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 pseudo-random 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 ```
 Re: [Schematics-development] discrete random variables From: - 2003-05-05 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 cut-offs 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 6-55) 5656 AA Eindhoven The Netherlands tel: +31 40 27-42069 *** new telephone number fax: +31 40 27-42566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard 05-05-2003 10:18 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: schematics-development@... Subject: Re: [Schematics-development] discrete random variab= les Classification:=20 sebastian.egner@... wrote: > The algorithm in its most simple form selects a minimum and a maximum > repeatedly---in fact once for every alias constructed. You may want to > consult Section 3.2.6 > > [4] M.C. Fu: Simulation of Discrete-Event 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 delete-min 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 ```
 Re: [Schematics-development] discrete random variables From: - 2003-05-09 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 cut-offs 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 ```
 Re: [Schematics-development] discrete random variables From: - 2003-05-09 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 6-55) 5656 AA Eindhoven The Netherlands tel: +31 40 27-42069 *** new telephone number fax: +31 40 27-42566 *** new fax number email: sebastian.egner@... Jens Axel S=F8gaard 09-05-2003 00:01 =20 To: Sebastian Egner/EHV/RESEARCH/PHILIPS@... cc: Subject: Re: [Schematics-development] 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 cut-offs 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 ```
 Re: [Schematics-development] discrete random variables From: - 2003-05-05 08:22:30 ```sebastian.egner@... wrote: > The algorithm in its most simple form selects a minimum and a maximum > repeatedly---in fact once for every alias constructed. You may want to > consult Section 3.2.6 > > [4] M.C. Fu: Simulation of Discrete-Event 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 delete-min 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 ```