如何根据列表中的概率进行随机选择（加权随机分布）？

Question

假设你有一个概率列表，像这样：

P = [0.10, 0.25, 0.60, 0.05]

（我可以确保这个列表中所有数字加起来总是等于1）

我该怎么写一个函数，让它根据列表中的值随机返回一个有效的索引呢？换句话说，对于这个特定的输入，我希望它返回 0 的概率是10%，返回 1 的概率是25%，返回 2 的概率是60%，而返回 3 的概率是剩下的5%。

Answer 1

嗯，有趣，那我们可以这样做...

1. 先生成一个0到1之间的数字。

2. 然后遍历这个列表，把每个项目的概率从你的数字中减去。

3. 最后选择那个减完后让你的数字变成0或更小的项目。

这个方法简单，效率是O(n)，应该能行 :)

Answer 2

基本上，你需要创建一个叫做累积分布函数（CDF）的数组。简单来说，CDF中某个位置的值，就是所有小于或等于这个位置的概率值的总和。接着，你可以生成一个0到1之间的随机数，然后进行二分查找（如果你愿意，也可以用线性查找）。下面是一些简单的代码示例。

from bisect import bisect
from random import random

P = [0.10,0.25,0.60,0.05]

cdf = [P[0]]
for i in xrange(1, len(P)):
    cdf.append(cdf[-1] + P[i])

random_ind = bisect(cdf,random())

当然，你可以用类似的方法生成一堆随机索引，比如

rs = [bisect(cdf, random()) for i in xrange(20)]

这样会得到

[2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2]

（结果会有所不同，这很正常）。当然，对于可能的索引数量很少的情况，使用二分查找其实没必要，但如果可能的索引数量多的话，使用二分查找就很推荐了。

Answer 3

你可以很简单地用numpy来做到这一点。它有一个叫做choice的函数，可以接受概率作为参数。

np.random.choice(
  ['pooh', 'rabbit', 'piglet', 'Christopher'], 
  5,
  p=[0.5, 0.1, 0.1, 0.3]
)