如何从多项分布中采样的算法

Question

如果给定一个多项分布

p=[0.2,0.4,0.1,0.3]

，并且必须多次从该分布中采样并返回结果，我该如何编写算法呢？

例如 - 如果我有一个公平的骰子，我想滚动它 20 次并获得它落在哪一侧的总次数，

[4, 1, 7, 5, 2, 1]

这应该是结果（随机） ->它在 1 上降落了 4 次，在 2 上降落了一次，以此类推。 Numpy 中有一个函数可以做到这一点 在 numpy 中我们可以使用

numpy.random.multinomial()

>>> np.random.multinomial(20, [1/6.]*6, size=1)

array([[4, 1, 7, 5, 2, 1]]) # random

我想了解如何编写算法来执行此操作 我在 python 中尝试过这种方法 ->

import numpy as np
import random
probs = [0.2, 0.4, 0.1, 0.3]

def sample(count:int)->list:
    output = [0,0,0,0]
    for i in range(count):
        num = random.random()
        if(0 < num <= 0.15):
            output[2]+=1
        elif(0.15 < num <= 0.25):
            output[0]+=1
        elif(0.25 < num <= 0.35):
            output[3]+=1
        elif(0.35 < num <= 0.45):
            output[1]+=1
        
    return output

final_output = sample(10)
print(final_output)

np.random.multinomial(10, probs, size=1)

但我认为这不是最佳方法，也许我缺乏概率方面的一些概念？

CPython 中 Numpy 编写的实际代码： 链接到包含 numpy.random 代码的 Numpy 文件.multinomial() 从第 4176 行开始编写

可能重复： 如何从多项分布中采样？

https://numpy.org/doc/stable/参考/随机/生成/numpy.random.multinomial.html

使用 rmultinom() 从 R 中的多项分布生成随机数功能

Answer 1

如果您关心多次从此分布中采样，那么值得查看别名方法 - https://en.wikipedia.org/wiki/Alias_method#:~:text=In%20computing%2C%20the%20alias%20method,任意%20probability%20distribution%20pi。

在初始计算 $O(K\log K)$ 后，您可以在 $O(1)$ 时间内进行采样，其中 $K$ 是分布支持度的大小。