从数组中选择元素，其概率与其值成正比 [英] 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

在此示例中，元素0将有66％的被选择，元素1将有33％的机会.我很难对此进行编码.到目前为止，我所做的是计算数组的总值(示例将为300)，然后在将它们计算为总值的百分比之前先进行了反演.我什么都不能工作.最后，我希望:

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]
     }
}

或其他有影响的东西.有什么帮助吗?编码是用Java编写的，但是我可以修改任何伪代码.

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

推荐答案

通常的技术是将数组转换为累积和数组:

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

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

选择一个从零到累积总数的随机数(在示例中为0 <= x < 100).然后，在累积数组上使用 bisection 将索引定位到原始数组中:

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 

例如，如果随机变量 x 为4，则将累积数组二等分会得出位置索引0，该索引对应于原始数组中的10.

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.

并且，如果随机变量 x 为72，则将累积数组二等分会得到位置索引2，该位置索引对应于原始数组中的5.

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]

这篇关于从数组中选择元素，其概率与其值成正比的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！