Databases
StackOverflow2013
Postsdbo
POData structure for loaded dice?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POData structure for loaded dice?
    text
    copied!<p>Suppose that I have an n-sided loaded die where each side k has some probability p<sub>k</sub> of coming up when I roll it. I'm curious if there is good algorithm for storing this information statically (i.e. for a fixed set of probabilities) so that I can efficiently simulate a random roll of the die.</p> <p>Currently, I have an O(lg n) solution for this problem. The idea is to store a table of the cumulative probability of the first k sides for all k, them to generate a random real number in the range [0, 1) and perform a binary search over the table to get the largest index whose cumulative value is no greater than the chosen value. I rather like this solution, but it seems odd that the runtime doesn't take the probabilities into account. In particular, in the extremal cases of one side always coming up or the values being uniformly distributed, it's possible to generate the result of the roll in O(1) using a naive approach, though my solution will still take logarithmicallh many steps.</p> <p>Does anyone have any suggestions for how to solve this problem in a way that is somehow "adaptive" in it's runtime?</p> <p><strong>EDIT</strong>: Based on the answers to this question, I have written up <strong><a href="http://www.keithschwarz.com/darts-dice-coins/" rel="noreferrer">an article describing many approaches to this problem</a></strong>, along with their analyses. It looks like Vose's implementation of the alias method gives &Theta;(n) preprocessing time and O(1) time per die roll, which is truly impressive. Hopefully this is a useful addition to the information contained in the answers!</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload