6

我试图在java中实现一个概率分布函数，它以概率返回数组中的条目：ith

Fi = 6i(n-i) / (n3 - n)

数组长度在哪里，n即数组长度为 4：

P1 = 3/10, P2 = 4/10, P3 = 3/10, P4 = 0

请注意，此函数假定从 1 到n0 到n-1Java 中的编号。

目前我只是使用均匀分布，即

 int i = (int)(Math.random()*((arraySize)-1));

使用 -1 所以它不会选择最后一个元素（即 P n = 0，如上式）。

任何人对实现此有任何想法或提示？

4

4 回答 4

2

这本质上就是 thomson_matt 所说的，但更正式一点：您应该执行离散逆变换采样。您的示例的伪代码：

p = [0.3, 0.4, 0.3. 0.0]
c = [0.3, 0.7, 1.0, 1.0] // cumulative sum

generate x uniformly in continuous range [0,1]
find max i such that c[i] < x.
于 2011-07-02T13:44:04.097 回答
2 
double rand = Math.random(); // generate a random number in [0,1]
F=0;
// you test if rand is in [F(1)+..+F(i):F(1)+..+F(i)+F(i+1)] it is in this rnge with proba P(i) and therefore if it is in this range you return i
for (int i=1,i<array.size();i++ ){
   F+=F(i);
   if rand < F
       return i;
}
return array.size(); // you went through all the array then rand==1 (this probability is null) and you return n
于 2011-07-02T13:44:47.157 回答
1

为此，您希望将范围 [0, 1] 划分为具有所需大小的区域。所以在这种情况下：

0 -> 0.0 - 0.3
1 -> 0.3 - 0.7
2 -> 0.7 - 1.0
3 -> 1.0 - 1.0

然后用 生成一个随机数Math.random()，看看它属于哪个区间。

通常，您想要执行类似以下伪代码的操作：

double r = Math.random();
int i = -1;

while (r >= 0)
{
  i++;
  r -= F(i);
}

// i is now the value you want.

您在 [0, 1] 上生成一个值，然后减去每个间隔的大小，直到低于 0，此时您已经找到了随机值。

于 2011-07-02T13:39:55.827 回答
1

您可以尝试使用带有概率分布的可导航地图。与普通 Map 不同，NaviableMap 定义了对其键的绝对排序。如果映射中不存在键，它可以告诉您哪个是最接近的键，或者哪个是大于参数的最小键。我使用ceilingEntry它返回具有大于或等于给定键的最小键的映射条目。

如果您使用 TreeMap 作为 NavigableMap 的实现，那么查找具有许多类的分布会更快，因为它执行二进制搜索，而不是从第一个键开始，然后依次测试每个键。

NaviableMap 的另一个优点是您可以获得您直接感兴趣的数据类，而不是另一个数组或列表的索引，这可以使代码更清晰。

在我的示例中，我使用了 BigDecimals，因为我不是特别喜欢使用浮点数，因为您无法指定所需的精度。但是你可以使用浮点数或双精度数或其他任何东西。

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.NavigableMap;
import java.util.TreeMap;


public class Main {

    public static void main(String[] args) {

        String[] classes = {"A", "B", "C", "D"};
        BigDecimal[] probabilities = createProbabilities(classes.length);
        BigDecimal[] distribution = createDistribution(probabilities);

        System.out.println("probabilities: "+Arrays.toString(probabilities));
        System.out.println("distribution: "+Arrays.toString(distribution)+"\n");

        NavigableMap<BigDecimal, String> map = new TreeMap<BigDecimal, String>();

        for (int i = 0; i < distribution.length; i++) {
            map.put(distribution[i], classes[i]);
        }

        BigDecimal d = new BigDecimal(Math.random());

        System.out.println("probability: "+d);

        System.out.println("result: "+map.ceilingEntry(d).getValue());

    }

    private static BigDecimal[] createDistribution(BigDecimal[] probabilities) {
        BigDecimal[] distribution = new BigDecimal[probabilities.length];

        distribution[0] = probabilities[0];
        for (int i = 1; i < distribution.length; i++) {
            distribution[i] = distribution[i-1].add(probabilities[i]); 
        }
        return distribution;
    }

    private static BigDecimal[] createProbabilities(int n) {
        BigDecimal[] probabilities = new BigDecimal[n];

        for (int i = 0; i < probabilities.length; i++) {
            probabilities[i] = F(i+1, n);
        }
        return probabilities;
    }

    private static BigDecimal F(int i, int n) {
//      6i(n-i) / (n3 - n)
        BigDecimal j = new BigDecimal(i);
        BigDecimal m = new BigDecimal(n);
        BigDecimal six = new BigDecimal(6);

        BigDecimal dividend = m.subtract(j).multiply(j).multiply(six);
        BigDecimal divisor = m.pow(3).subtract(m);

        return dividend.divide(divisor, 64, RoundingMode.HALF_UP);
    }
}
于 2011-07-02T19:23:13.870 回答