CODEWITHSUNDEEP
arraysnumpyselectrandomweighted
user2341412
user2341412

Reputation: 401

Select element from array with probability proportional to its value

I have an array of doubles and I want to select a value from it with the probability of each value being selected being inversely proportional to its value. For example:

arr[0] = 100
arr[1] = 200

In this example, element 0 would have a 66% of being selected and element 1 a 33% chance. I am having difficulty coding this. What I have done so far is to calculate the total value of the array (the example would be 300), then I've played around with inversing the numbers before calculating them as a percentage of the total. I can't get anything to work. In the end I desire:

new randomNumber
for(int y=0; y < probabilities.length; y++){
     if(randomNumber < probabilities[y]){
          Select probabilities[y]
     }
}

Or something to that affect. Any help? Coding is in Java but I can adapt any pseudocode.

Upvotes: 11

Views: 10999

Answers (4)

Artem
Artem

Reputation: 9

I faced with the same problem and come up with some simple solution. Not the perfect, but suitable for some cases.

You have array with some numbers [1,2,3,...] and you need to select a value with some probability [10,5,20,...] just make new array and repeat each value as much times as much probability it has, eg 

arr[] = [1,1,1,1,...(10 times),2,2,2,..(5 times),3,3,3,3,...(20 times)];

And them just get random number from 0 to new array length and get your value with number with desirable probability.

int r = Random(0,arr.count);
int value = arr[r];

As I mention it's not perfect and also it's not memory efficient algorithm, but it works.

Upvotes: 0

user3107673
user3107673

Reputation: 443

Php code: 

/**
 * Returns a random item from an array based on a weighted value.
 * @param array $array ['foo' => 70, 'bar' => 30] Foo has a 70 percent chance of being returned
 * @return int|string
 */
public function randomize(array $array)
{
    $sumOfWeights = array_sum($array);

    $random = rand(1, $sumOfWeights);
    foreach ($array as $name => $weight) {
        $random -= $weight;

        if ($random <= 0) {
            return $name;
        }
    }

}

Find the sum of all the element in array. Then generate a random number in this range. The final selection will be the element in the index returned by the above function.

Upvotes: 0

Raymond Hettinger
Raymond Hettinger

Reputation: 226754

The usual technique is to transform the array into an array of cumulative sums:

 [10 60 5 25]  --> [10 70 75 100]

Pick a random number in the range from zero up to the cumulative total (in the example: 0 <= x < 100). Then, use bisection on the cumulative array to locate the index into the original array:

Random variable x      Index in the Cumulative Array      Value in Original Array
-----------------      -----------------------------      ----------------------
 0 <= x < 10                      0                            10
10 <= x < 70                      1                            60
70 <= x < 75                      2                             5
75 <= x < 100                     3                            25

For example, if the random variable x is 4, bisecting the cumulative array gives a position index of 0 which corresponds to 10 in the original array.

And, if the random variable x is 72, bisecting the cumulative array gives a position index of 2 which corresponds to 5 in the original array.

For an inverse proportion, the technique is exactly the same except you perform an initial transformation of the array into its reciprocals and then build the cumulative sum array:

[10 60 5 25]  -->  [1/10  1/60  1/5  1/25]  -->  [1/10  7/60  19/60  107/300]

Upvotes: 20

Shawn Balestracci
Shawn Balestracci

Reputation: 7550

For Inverse proportionality:

  1. sum the array
  2. Pick a random number between 0 and (n-1)*sum -1
  3. Accumulate sum-value starting from the beginning until you are >= to the random value.

This is for proportional

Note: All values must be positive for this to work.

  1. sum the array
  2. Pick a random number between 0 and the sum-1
  3. Accumulate the values starting from the beginning of the array until you are >= to the random value.

Upvotes: 1

Related Questions