Peek at a value from an array with a probabilistic quantity

Question

I have an array of 10 elements.

|1|2|3|4|5|6|7|8|9|10|

The idea is to randomly peek at a value from this array, but with some probabilistic quantity.

The probabilistic selection of the element is as follows:

|5%|10%|15%|30%|20%|4%|6%|1%|3%|6%|

This means that selecting the first element has a 5% chance, the second element has a 10% chance and so on.

My Solution:

import java.util.*;

public class Example {
     public static void main( String[] args ) {

         int [] values = {1,2,3,4,5,6,7,8,9,10};
         double [] probabilities = {0.05,0.1,0.15,0.3,0.2,0.04,0.06,0.01,0.03,0.06};


         double cumulativeSum = 0;
         double r = new Random().nextDouble();//random number between 0 and 1
         int index=0;// index of the chosen value
         for (double prob:probabilities) {
             cumulativeSum += prob;
             if (cumulativeSum >= r) {
                 break;
             }
             index++;
         }
         System.out.println(index);
         System.out.println("the value picked "+values[index]);

     }
}

I'm looking for a faster solution than mine. The array i made is only a tiny example, normally I can have arrays with 10000 cells.

https://stackoverflow.com/questions/1761626/weighted-random-numbers There is a good answer. So if you will have array with a lot of numbers you can use binary search tree with cumulative weights — Ulad, Dec 10 '18 at 21:07
@vlad324 The answer you linked is almost the same as the OP's solution. — Soutzikevich, Dec 10 '18 at 21:15
@P.Soutzikevich yes, but OP have mentioned that he has big input array, and I recommend him to use binary search tree with cumulative weights instead of array, because it will be faster, and this is expected result to make his code faster. The idea of binary search tree is not my, so I attached link, because it has more details about it — Ulad, Dec 10 '18 at 21:20

score 2 · Answer 1 · answered Dec 10 '18 at 20:53

It looks like you are implementing a type of Roulette Wheel Selection algorithm.

You can check this stack-overflow question for a detailed explanation of RWS.

As for the faster solution you're asking for, I don't think there would be a big increase in execution speed with some other algorithm. Your solution seems to be pretty fast and I can't see a reason why you would need something "faster". Code can always be optimized, but it depends on what you want to optimize and why you need something to be as fast as can be. If computational speed is critical in your situation, maybe consider implementing your code in Assembly, instead of Java.

There are other selection algorithms similar to RWS, like Stochastic Universal Selection (SUS), which would be more suited if you wanted to peek at more than one elements for example.

the chosen awnser in the provided link is almost the same as my solution. the problem in this solution in my case is that when we should peek the last element of the array we should iterate over the full array. using another language dosen't fit my need as my project is written using Java. — xmen-5, Dec 10 '18 at 21:03
You could order your list, so that the item with the highest probability is at the head of it (at the start). Otherwise, I can't think of an algorithm to optimize what you want — Soutzikevich, Dec 10 '18 at 21:16

score 1 · Accepted Answer · answered Dec 11 '18 at 00:39

1

The alias method is an algorithm for the general problem of taking a set of probabilities for a number of possible values and precomputing some tables to be able to select an element with the specified probability distribution in O(1), instead of O(n). This is almost certainly the optimal algorithm for your use case.

answered Dec 11 '18 at 00:39

Louis Wasserman

191,574
25
345
413

yes it is what i was lookig for. an implementation http://www.keithschwarz.com/interesting/code/?dir=alias-method – xmen-5 Dec 11 '18 at 13:28
the problem is that in my project i peek one value -> i change the probabilistics value-->peek another value-> i change...... an so one. would this solution give a better performance? – xmen-5 Dec 11 '18 at 13:30
2

@zakzak If you change probabilities all the time, then alias method would be very expensive - you have to rebuild table all the time – Severin Pappadeux Dec 11 '18 at 15:54

score 0 · Answer 3 · answered Dec 10 '18 at 20:47

If your program uses those exact values (1-10), then it is rather trivial - just create an array where each entry appears multiple times according to its probability.

public static void main(String[] args) {
    int[] values = {
            1, 1, 1, 1, 1,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            6, 6, 6, 6,
            7, 7, 7, 7, 7, 7, 8, 9, 9, 9,
            10, 10, 10, 10, 10, 10, 10
    };

    int value = values[new Random().nextInt(values.length)];
    int index = value - 1; // values 1-10 are in indices 0-9

    System.out.println(index);
    System.out.println("the value picked " + value);
}

Like I said, this works for static values. If you have dynamic values, you'll need a different method.

Peek at a value from an array with a probabilistic quantity

3 Answers3