如何从具有概率分布的数组中选择一个元素？

Question

我有一个 mathematical/programming 关于我正在尝试解决的问题的问题。给定这个简单的整数数组：

int[] goals = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

你知道我如何实现一个函数来从数组中选择一个元素，就像这个例子中的概率分布一样吗？:

选择目标[0]的概率为 50%
选择目标[1]的概率为 30%
选择目标[2]的概率为 12%
选择目标[3]的概率为 2.5%
选择进球[4]的概率为0.85%
等等

概率分布是我选择的，为了简单起见进行了硬编码。

非常感谢您的意见！

Answer 1

假设您在数组中指定概率：

double[] probs = {50, 30, 12, 2.5, 0.85 /*, ...*/};

您可以计算概率的总和：

double totalProbs = DoubleStream.of(probs).sum();

并声明一个随机对象：

Random random = new Random();

然后您可以编写一个方法，returns一个随机目标：

public int randomGoal() {
    double x = random.nextDouble()*totalProbs;
    for (int i = 0; i < probs.length; ++i) {
        x -= probs[i];
        if (x <= 0) {
            return goals[i];
        }
    }
    return goals[goals.length-1];
}

Answer 2

您可以创建一个包含 100 个元素的数组，然后对于数组 goals 中的每个数字 i，将 i 放入新数组 n 次，其中 n 等于 i 乘以数组大小 (100) 的概率。然后从新数组中随机选择一个元素。

您可以增加数组大小 (100) 以获得更精确的结果。最精确的结果将是当您选择使每个 n 成为整数的数组大小时。

示例：

https://jsfiddle.net/o5hmjxd2/28/

const x = [0,1,2,3,4,5,6,7,8,9];
const p = [0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
const l = 100;

let y = [];


for (const i = 0; i < x.length; i++) {
  y = y.concat(new Array(l*p[i]).fill(x[i]));
}

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

// result
console.log(y);
console.log(y[getRandomInt(y.length - 1)])

Answer 3

试试这个。

public class DistributedProbability {

    final NavigableMap<Double, Integer> distribution = new TreeMap<>();
    final Random random = new Random();
    public final int size;
    public final double max;

    public DistributedProbability(double... rates) {
        double sum = 0;
        int index = 0;
        for (double rate : rates) {
            sum += rate;
            this.distribution.put(sum, index++);
        }
        size = index;
        max = sum;
    }

    int next() {
        double d = random.nextDouble(max);
        Entry<Double, Integer> entry = distribution.higherEntry(d);
        return entry.getValue();
    }
}

和

public static void main(String[] args) {
    DistributedProbability d = new DistributedProbability(
        50, 30, 12, 2.5, 0.85, 4.65);

    int[] counts = new int[d.size];
    for (int i = 0; i < 100000; ++i)
        ++counts[d.next()];

    System.out.println(Arrays.toString(counts));
}

输出：

[49844, 30101, 12023, 2512, 845, 4675]

如何从具有概率分布的数组中选择一个元素？

How to pick an element from an array with a probability distribution?

java

arrays

random

probability-distribution