3 ms·
All this method does is break the continuous [0,1) range into enough discrete buckets that each bucket contains at most two choices. Because the buckets are the
by loeg 15y ago
All this method does is break the continuous [0,1) range into enough discrete buckets that each bucket contains at most two choices. Because the buckets are the same "probability-size" you can pick a bucket with O(1) and then do an O(1) comparison.
Everything between "Loaded Die with a Fair Die" and "Vose's Alias Method" seems superfluous.
- Someone 15y agoI agree with you that some parts distract more from the main line than that they add, but not about what those parts are. I would probably remove everything from the header "Simulating a Fair Die" up to the header "Throwing Darts". I would keep the "Throwing Darts" parts because it provides a smoother ride towards the main result. I guess many readers will need that to understand the algorithm (If the intended audience is hard-core, it could just have been a reference to TAOCP and an URL to Vose‘s paper. For me, that probably would have been enough, as I knew the algorithm from reading TAOCP, and have already implemented the O(nlogn) initialization method variant) Finally, I have one minor nitpick: the header "Simulating a Loaded Die with a Biased Coin" is incorrect. It should read "Simulating a Loaded Die with Biased Coins".