从 N 个元素集合中选择不同概率的 K 个元素的概率
我有一组 N 个元素。我想从集合中选择一些元素。现在集合中的每个元素i都有被选择的概率P(i)。那么如何计算从集合中选择至少 K 个元素的概率呢？
I have a set of N elements. I want to select a few elements from the set. Now each element i of the set has a probability P(i) of getting selected. Then how can I figure out the probability of selecting at least K elements from the set?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为了准确起见，您需要包含/排除：
即对于 k 个元素的每个子集 (i_1...i_k)，添加 P(i_1)*P(i_2)...P(i_k)
然后对于 k+1 个元素的每个子集减去：
P(i_1)*P(i_2)...P(i_k+1)
然后对于 k+2 个元素的每个子集添加：
P(i_1)*P(i_2)...P(i_k+2)
依此类推，交替加减，直到达到 n 或各项可以忽略不计。
或者，如果 k 小于 N/2，您可以采用其他方法：
从 1 开始
对于 n-k+1 个元素的所有子集减去：
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+1))
然后对于 n-k+2 个元素的所有子集添加：
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+2))
然后对于 n-k+3 个元素的所有子集减去：
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+3))
依此类推，交替加减，直到达到 n 或各项可以忽略不计。
To get it exact, you need inclusion/exclusion:
ie for each subset of k elements (i_1...i_k), add P(i_1)*P(i_2)...P(i_k)
Then for each subset of k+1 elements subtract:
P(i_1)*P(i_2)...P(i_k+1)
Then for each subset of k+2 elements add:
P(i_1)*P(i_2)...P(i_k+2)
and so on so forth alternately adding and subtracting until you reach n or the terms become negligible.
Alternatively, if k is smaller than N/2 you can go the other way:
Start with 1
For all subsets of n-k+1 elements subtract:
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+1))
then for all subsets of n-k+2 elements add:
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+2))
then for all subsets of n-k+3 elements subtract:
(1-P(i_1))*(1-P(i_2))*(1-P(i_3))...(1-P(i_n-k+3))
and so on so forth alternately adding and subtracting until you reach n or the terms become negligible.