statistics - 如何从多项分布中采样?
问题描述
假设我有一组概率 [0.1, 0.6, 0.2, 0.1]。我想从这组概率中采样位置。例如,当我采样时,我应该比其他位置更频繁地获得位置 1。我知道我可以在 Matlab(使用命令 mnrnd)或其他语言中实现这一点。但是,我想知道算法细节。我想知道一个非常简单的算法,可以用来从多项分布中采样。
解决方案
蛮力方法
在您的情况下,创建一个包含累积概率的数组cdf = [0.1, 0.7, 0.9, 1.0]
。生成U
,一个统一的(0,1)随机值。选择第一个索引,使得cdf[i] <= U
. 对于少数结果,这可以通过线性搜索 (O(n)) 来完成,如果结果数量很大,则可以使用二分搜索 (O(log n))。
别名法
别名表要求您使用条件概率来构造主要元素和别名值的表,以使每个主要/别名对的总概率相同。然后,您使用一个随机数选择表中的一列(概率相等),并使用第二个值在主要和别名之间进行二项式选择。构建表后,运行时间为 O(1),这需要 O(n) 的努力。有关详细信息,请参阅Wikipedia,或有关 Ruby 实现的 ruby gems 。请注意,这需要每个结果有两个制服,因此这不是倒置,并且您不能做有趣的技巧,例如生成对立变量。
推荐阅读
- java - 特定Java Swing算法中的ActionListener延迟?
- r - 在 R 中模拟具有代表性的数据集
- angular - 如何使用 [hidden] 属性正确地为 Angular 中的对象设置动画?
- elasticsearch - 创建动态 kibana 索引
- python - 数据狗跨度在 python 线程池中丢失
- swift - 为什么 SCNAudioSource 在应用关闭并重新打开后停止工作?
- javascript - 使用 Redux-thunk 调用操作不起作用
- swift - Firebase - 如何通过嵌入式结构阅读此地图?
- vue.js - 如何告诉 VScode 将文件类型 A 格式化为文件类型 B,同时保留语法高亮显示?
- javascript - 服务器端将信息发送到普通 HTML