1

我偶然发现了一个基本的离散数学/概率问题，我想获得一些改进我的解决方案的想法。

假设给你一个集合（字母、自然数等）。您如何确保X以给定的概率从该集合中提取某个值P？

我将用一个例子来解释我的幼稚解决方案：

Collection = {A, B}
X = A, P = 1/4

我们构建一个数组v = [A, B, B, B]并使用一个rand函数对数组的索引进行统一采样，即{0, 1, 2, 3}

这种方法有效，但效率不高： 越小P，存储的内存越大v。因此，我想知道 stackoverflow 社区在改进这方面可能有什么想法。

谢谢！

4

2 回答 2

5

将区间 [0,1] 划分为不相交的区间，其并集为 [0,1]。创建每个分区的大小以对应于选择每个事件的概率。然后简单地从 [0,1] 中随机抽样，评估结果所在的分区，然后查找对应于该区间的选择。在您的示例中，这将导致以下 2 个间隔 [0,1/4) 和 [1/4,1] - 从 [0,1] 生成随机统一值。如果您的样本位于第一个区间，那么您的选择X = A，如果在另一个区间，那么X = B。

于 2012-10-13T10:55:29.563 回答
1

您提出的解决方案确实不是很好，解决它的最通用和最有效的方法是 mathematician1975 状态（这被称为逆 CDF 方法）。对于您的具体问题，即多项抽样，您还可以使用从二项分布中抽取的一系列数据从您的集合中进行抽样。如果您不熟悉采样方法，这通常更直观。

如果集合中第一项的概率为 p_1，则在区间 [0-1] 内均匀采样。如果样本小于 p_1，则返回第 1 项。否则，将剩余结果重新归一化 1-p_1，并使用下一个可能的结果重复该过程。在每次不成功的抽样后，将剩余结果按被拒绝结果的总概率重新归一化，使剩余结果的总和为 1。如果得到最后一个结果，则以概率 1 返回它。该过程的结果将是随机样本分布根据您的原始向量。

该方法使用多项式的各个分量是二项式分布的事实，并且多项式的任何子向量也是多项式，其参数由我上面描述的重整化给出。

于 2012-10-16T10:30:57.953 回答