python - 统计:优化python中的概率计算

Question

设置:

问题是经典概率问题的复杂形式:

70 colored balls are placed in an urn, 10 for each of the seven rainbow colors.

What is the expected number of distinct colors in 20 randomly picked balls?

我的解决方案 是 python 的 itertools 库:combos = itertools.combinations(urn, 20),打印总和([1 for x in combos])(其中 urn 是 urn 中 70 个球的列表)。

我可以将迭代器解压缩到我的计算机无法处理的 combinations(urn, 8) 长度。

注意:我知道这不会给我答案，这只是我脚本中的路障，换句话说，如果这有效，我的脚本就会有效。

问题:如果没有世界上最快的 super 计算机，我如何准确地找到预期的颜色？我的方法在计算上是否可行？

Answer 1

既然有几个人要求看数学解，那我就给吧。这是 Project Euler 问题之一，可以在合理的时间内用铅笔和纸完成。答案是

7(1 - (60 choose 20)/(70 choose 20))

要获得此值，请将 X(存在的颜色数)写为总和 X0+X1+X2+...+X6，其中如果存在第 i 种颜色，则 Xi 为 1，如果不存在，则为 0。

E(X) 
= E(X0+X1+...+X6) 
= E(X0) + E(X1) + ... + E(X6)        by linearity of expectation
= 7E(X0)                             by symmetry
= 7 * probability that a particular color is present
= 7 * (1- probability that a particular color is absent)
= 7 * (1 - (# ways to pick 20 avoiding a color)/(# ways to pick 20))
= 7 * (1 - (60 choose 20)/(70 choose 20))

Expectation is always linear.因此，当您被要求找到某个随机量的平均值时，尝试将数量重写为更简单的部分(例如指示符 (0-1) 随机变量)的总和通常会有所帮助。

---

这并没有说明如何使 OP 的方法起作用。虽然有一个直接的数学解决方案，但最好知道如何以有组织和可行的方式迭代案例。如果您接下来想要比计数更复杂的颜色集功能，这可能会有所帮助。 Duffymo 的回答提出了一些我会更明确的建议:

您可以将 70 个调用中的 20 个调用分解为按颜色计数索引的类别。例如，索引 (5,5,10,0,0,0,0) 表示我们绘制了第一种颜色的 5 种，第二种颜色的 5 种，第三种颜色的 10 种，并且没有其他颜色。

可能的索引集合包含在和为 20 的非负整数的 7 元组集合中。其中一些是不可能的，例如 (11,9,0,0,0,0,0) 由问题的假设每种颜色只有 10 个球，但我们可以处理这个问题。非负数加起来为 20 的 7 元组的大小为(26 选 6)=230230，它有一个 natural correspondence。具有在 26 个空间中选择 6 个分隔线作为分隔线或对象的方式。所以，如果你有 a way to iterate through the 6 element subsets of a 26 element set ，您可以将它们转换为遍历所有索引。

您仍然需要根据从 70 个球中抽取 20 个球的方法数来对案例进行加权，以获得该案例。 (a0,a1,a2,...,a6) 的权重是 (10 选择 a0)(10 选择 a1)...*(10 选择 a6)。这很好地处理了不可能索引的情况，因为 10 选择 11 是 0，所以乘积是 0。

因此，如果您不知道线性期望的数学解决方案，您可以迭代 230230 个案例并计算索引向量的非零坐标数的加权平均值，由小二项式的乘积加权条款。