Return random value from array with probability proportional to its value

Question

I have an array like

$keywords = array('apple'=>10,'orange'=>2,'grape'=>12); 

I want to randomly select one of the "keys" from the array. However, the probability distribution must be such that the probability of choosing an element is proportional to its value.

Answer 1

Add all values ​​(10 + 2 + 12 - 24); get a random number in the range [0, 24) and select the corresponding element depending on whether it is in [0, 10), [10, 12] or [12, 24].

Answer 2

I would do it like this:

  $probabilities = array('apple'=>50, 'orange'=>20, 'banana'=>10); function random_probability($probabilities) { $rand = rand(0, array_sum($probabilities)); do { $sum = array_sum($probabilities); if($rand <= $sum && $rand >= $sum - end($probabilities)) { return key($probabilities); } } while(array_pop($probabilities)); } 

Answer 3

O (log (n)) approach (this is torn directly from the answer to a very similar question ):

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 cumulative array to find the index in 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, 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.