Select an element from the array with a probability proportional to its value

Question

I have an array of doubles, and I want to select a value from it with the probability that each selected value will be inversely proportional to its value. For instance:

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

In this example, item 0 will have 66% of the selected, and item 1 will have 33%. I find it hard to code this. What I have done so far is to calculate the total value of the array (the example will be 300), then I played with the inverse of the numbers before calculating them as a percentage of the total. I can’t make it work. In the end, I wish:

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

Or something in this is affected. Any help? The coding is done in Java, but I can adapt any pseudocode.

Answer 1

The usual method is to convert the array to an array of sums:

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

Select a random number in the range from zero to the total (in the example: 0 <= x < 100 ). Then use bisection in the aggregate array to find the index in the source 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, then halving 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, halving the cumulative array gives an index of position 2, which corresponds to 5 in the original array.

For the inverse proportion, the method is exactly the same, except that you perform the initial conversion of the array to its inverse, and then create an aggregate array of sums:

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

Answer 2

For inverse proportionality:

• sum the array
• Choose a random number between 0 and (n-1) * sum -1
• Accumulate the value of the sum, starting from the beginning, until you = = = to a random value.

---

This is for proportional

Note. For this, all values ​​must be positive.

• sum the array
• Choose a random number between 0 and sum-1
• Accumulate values, starting at the beginning of the array, until you = = = to a random value.

Answer 3

I ran into the same problem and came up with some simple solution. Not perfect, but suitable for some occasions.

You have an array with some numbers [1,2,3, ...], and you need to select a value with some probability [10,5,20, ...], just create a new array and repeat each value as much times more likely for example

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

And they just get a random number from 0 to the new array length and get your value with the number with the desired probability.

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

As I mentioned, it is not perfect, nor is it an efficient memory algorithm, but it works.

Answer 4

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 the whole element in the array. Then create a random number in this range. The final choice will be the element in the index returned by the specified function.