python - 弄清楚非均匀随机算法的工作原理

Question

我想弄清楚生成非均匀分布的伪随机数的算法是如何工作的。我正在看的书给出了伪代码实现如下

// Pick an item from a array with given probabilities.

Item: PickItemWithProbabilities(Item: items[],
Float: probabilities[])
Float: value = <PRNG value where 0 <= value < 1>
For i = 0 To items.Length - 1
value = value – probabilities[i]
If (value <= 0) Then Return items[i]
Next i
End PickItemWithProbabilities

我已经在 python 中实现了伪代码并且它按预期工作，如果我运行该函数足够多的轮次，分布将按照输入的概率值进行。问题是我并不完全理解它的原因和如何。

这是我根据伪代码实现的代码。

from random import random

colors = ["pink", "green", "yellow"]
probabilities = [0.7, 0.2, 0.1]
trials = 1000000

def non_uniform_random_picker(array, probabilities):
    rand_value = random()
    for i in range(len(array)):
        rand_value -= probabilities[i]
        if rand_value <= 0:
            return array[i]

results = dict()

for i in range(trials):
    value = non_uniform_random_picker(colors, probabilities)

    if results.get(value) == None:
        results[value] = 1
    else:
        results[value] += 1


for key in results:    
    percentage = round(((results[key]/trials) * 100), 2)
    print(f"{key}:{percentage}% ")

我需要帮助来弄清楚算法是如何工作的。

Answer 1

您可以使用累积函数从均匀分布创建非均匀分布(参见 https://en.wikipedia.org/wiki/Inverse_transform_sampling#The_method)

分布 P(x) 的累积函数是概率之和 <= x。

In this case, we have distribution [0.7, 0.2, 0.1]
The cumulative is: [.7, .9, 1.0]

If we select a uniformly random variable between 0 and 1 (i.e. random.uniform(0, 1)), and compare and output (rand_value) to the cumulative distribution we would expect:

• 70% of the time, rand_value would be < .7
• 20% of the time, rand_value would be between .7 and .9
• 10% of the time, rand_value to be between .9 and 1

The code:

rand_value = random()
for i in range(len(array)):
    rand_value -= probabilities[i]
    if rand_value <= 0:

停止时: 概率[0] + 概率[1] + ...概率[i] >= rand_value

这与索引 i 的累积分布相同。

通过根据此停止条件选择索引 i，我们创建了所需的列表非均匀采样。