CODEWITHSUNDEEP
algorithmmontecarlo
Ian
Ian

Reputation: 5725

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

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?

Upvotes: 3

Views: 2621

Answers (5)

atzz
atzz

Reputation: 18010

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.

Upvotes: 1

Martin DeMello
Martin DeMello

Reputation: 12346

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

Upvotes: 1

jk.
jk.

Reputation: 14004

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

Upvotes: 0

mariozski
mariozski

Reputation: 1134

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.

Upvotes: 0

rsp
rsp

Reputation: 23373

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.

Upvotes: 4

Related Questions