2

Say I have input that looks something like this:

[
  {index: 0, probability: 0.20},
  {index: 1, probability: 0.10},
  {index: 2, probability: 0.40},
  {index: 3, probability: 0.25},
  {index: 4, probability: 0.05},
]

Given that I generate a random number [0,1), is there an O(1) algorithm that I can use to find which index of this array "matches" that probability?

The way I would do it in O(N) is to do something like:

let cumulative = 0;
const r = Math.random();
for(const v of list){
    cumulative += v.probability;
    if(r < cumulative){
      return v.index;
    }
}

I believe the O(N) algorithm is doing what I want, but not sure if there is a faster way?

Alexander Mills
  • 90,741
  • 139
  • 482
  • 817
  • 2
    I'm guessing the probability is not unique for all. So, you probably need to create a hashmap of the probability with its key and array of indexes as its value if you want to run it in O(1) but that would take O(n) of space I guess – innocent Nov 30 '22 at 05:55
  • 1
    Is preprocessing the list an option? Or is the list an input that is used only once? – user3386109 Nov 30 '22 at 06:08
  • Yeah preprocessing is definitely an option – Alexander Mills Nov 30 '22 at 06:10
  • If you replace the probabilities with the cumulative totals, then a binary search for the index is possible. I will point out that for small lists like the example, the linear search is probably going to be the fastest option, simply due to the very small constant factor. – user3386109 Nov 30 '22 at 06:16
  • O(log(n)) with binary search – MBo Nov 30 '22 at 06:17
  • 1
    Another option for preprocessing is an array with 100 entries. Fill the array with twenty 0's, ten 1's, etc. Then multiply `r` by 100, and look up the answer in the table. – user3386109 Nov 30 '22 at 06:20

1 Answers1

4

Replace the list with cumulative probability:

[
  {index: 0, probability: 0.20},
  {index: 1, probability: 0.30},
  {index: 2, probability: 0.70},
  {index: 3, probability: 0.95},
  {index: 4, probability: 1.00},
]

Then do a binary search on probability to find the index. The complexity would be O(log N)

TYeung
  • 2,579
  • 2
  • 15
  • 30