Simulating "Wheel of fortune" (Monte Carlo Simulation Hit or Miss Method)

Question

Hello,

I'm trying to make a randomizer that will use the Monte Carlo Hit or Miss Simulation.

I have a Key-Value pair that represents the ID and the probability value:

ID - Value
2  - 0.37
1 - 0.35
4 - 0.14
3 - 0.12

When you add all of those values, you will get a total of 1.0.

You can imagine those values as the total area of a "slice" on the "wheel" (EG: ID 2 occupies 37% of the wheel, while ID 3 only occupies 12% of the wheel). When converted to "range" it will look like this:

ID - Value - Range
2  - 0.37 - 0 to 37
1 - 0.35 - 37 to 72
4 - 0.14 - 72 to 86
3 - 0.12- 86 to 100

Now, I am using Random.NextDouble() to generate a random value that is between 0.0 and 1.0. That random value will be considered as the "spin" on the wheel. Say, the randomizer returns 0.35, then ID 2 will be selected.

What is the best way to implement this given that I have an array of doubles?

Answer 1

a sorted map/dictionary with the 'Value' as the key and the 'ID' as the value would allow you to quickly find the upper bound of the range you are in and then look up the ID for that range

assuming your dictionary allows it, a binary search would be better to find the upper bound than interating throught the entire dictionary

Answer 2

The simplest solutions are often the best, if your range is 0 - 100 by design (or another manageebly small number), you can allocate an int[] and use the table of ranges you created to fill in the ID at the corresponding index, your "throw" will then look like:

int randomID = rangesToIDs[random.nextInt(rangesToIDs.length)];

Btw, it is not necessary to sort the ID's on range size, as the randoms are assumed to be distributed uniformly it does not matter where in the lookup table a range is placed. It only matters that the number of entries is proportional to the chance to throw an ID.

Answer 3

As jk wrote sorted dictionary of should be fine.

let's say you got dictionary like this:

0.37 2
0.72 1
0.86 4
1.00 3

You roll xx = 0.66.. Iterate through dictionary starting from lowest number (that's 0.37) if xx < dict[i].key return dict[i].value

Or another solution which comes to my mind is List of custom objects containing lower and upper bound and value. You iterate then through list and check if rolled number is in range of up and low bounds.

Answer 4

Let's assume your initial data is represented as array D[n], where D[i] = (id, p) and sum(D[i].p for i=0..n-1) == 1.

Build a second array P[n] such that P[i] = (q, id): P[i] = (sum(D[j].p for j in 0..i), D[j].id) -- i.e., convert individual probablity of each slice i into cumulative probability of all slices preceding i (inclusive). Note that, by definition, this array P is ordered by field q (i.e. by cumulative probability).

Now you can use binary search to find the slice chosen by the random number r (0 <= r <= 1):

find highest i such that P[i].q <= r; then P[i].id is your slice.

It is possible to speed up the lookup further by hashing the probability range with a fixed grid. I can write more details on this if anybody is interested.

Answer 5

boundaries = [37, 72, 86, 100]
num = 100 * random
for i in boundaries:
  if num < i then return i