统计学：优化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), print sum([1 for x in combos]) （其中urn是一个包含70个球的列表）。

我可以展开迭代器，直到combinations(urn, 8)的长度，超过这个长度我的电脑无法处理。

注意：我知道这不会给我答案，这只是我的脚本中的障碍，换句话说，如果这个方法可行，我的脚本就能工作。

问题：如何精确地找到预期的颜色，而不需要世界上最快的超级计算机？我的方法是否可行？

- PVNRT

---

你是否已经尝试解决 https://projecteuler.net/problem=493 ？如果是的话，我们可以添加“[project-euler]”标签。（暴力破解通常无法解决更高级别的PE问题 - 您需要一种数学/组合解决方案）。 - Alex Riley

我没有使用这个标签的唯一原因是标签描述中写着：“请勿使用此标签，Project Euler 是一个包含各种难度的数学编程问题集合。” - PVNRT

啊 - 我上次检查的时候那里没有...我猜你不使用它是正确的。 - Alex Riley

不要解包，迭代。 - wwii

基于将计数重写为求和的一行数学解决方案，并利用期望的线性性质，可以得到一个简单的解决方案。 - Douglas Zare

Answer 1

由于有几个人要求看数学解法，我将给出解法。这是 Project Euler 问题之一，可以用纸笔在合理的时间内完成。答案是

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

要得到这个结果，将颜色的数量X表示为X0+X1+X2+...+X6的总和，其中Xi表示第i种颜色是否存在，如果存在则为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))

期望值总是线性的。因此，当您被要求找到某个随机量的平均值时，通常有助于尝试将该量重写为更简单的部分之和，例如指示器（0-1）随机变量。

---

这并没有说明如何使原作者的方法起作用。虽然有一个直接的数学解决方案，但了解如何有条理、可行地遍历各种情况是很好的。如果您想要更复杂的颜色集合函数而不仅仅是计数，则这可能会有所帮助。Duffymo的答案提出了一些建议，我将其更加明确：

您可以将从70个中抽取20个的方式分成按颜色计数的类别。例如，索引(5,5,10,0,0,0,0)表示我们抽取了第一种颜色的5个，第二种颜色的5个，第三种颜色的10个，而其他颜色则没有抽取到。

可能的索引集包含非负整数7元组和为20的集合。有些是不可能的，比如(11,9,0,0,0,0,0)，因为问题假设每种颜色只有10个球，但我们可以解决这个问题。非负数加起来为20的7元组的数量是(26 choose 6) = 230230，并且它与在26个空间中选择6个分隔符或对象的方式有 自然对应。因此，如果你有一种方法可以迭代通过26个元素集的6个元素子集, 那么你可以将它们转换为迭代所有索引。

你仍然需要按照从70个球中抽取20个球的方式计算每种情况的数量来加权。 (a0,a1,a2,...,a6) 的权重为(10 choose a0)(10 choose a1)...*(10 choose a6)。这样可以优雅地处理不可能的指数情况，因为10 choose 11是0，所以乘积也是0。

因此，如果您不知道通过期望的线性数学解决方案，则可以遍历230230种情况，并计算由小二项式项的乘积加权的指数向量的非零坐标的加权平均值。

- Douglas Zare

---

谢谢您提供这个清晰的解决方案，Douglas。您最初的评论促使我使用电子表格来解决问题，所以我不会因为阅读您的解决方案而感到难过。 - PVNRT

非常高质量的答案 Douglas - vasia

Answer 2

“不就是有重复的组合吗？”

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

- duffymo

---

我不知道星条旗方法是什么。该链接提供了我所想的公式。 - duffymo

星号和条形码方法是您提供的链接中所称为“重复组合”的标准名称。我不知道您是如何从那个链接得出这个问题所要求的概率的。您链接中的哪个公式是指的？将20个对象分配给7个类别的方式计数与此问题无关。 - Douglas Zare

也许不是完美的答案，但它应该适用于一个限制条件。我知道每种颜色只有10个，所以用户在没有替换的情况下从袋子里抽取。我认为先做一些简单的事情然后再进行改进是有价值的。 - duffymo

如果这是一个数学问题，我可以回答它，但那并不能回答编程问题，而且我已经好多年没有使用Python了。 - Douglas Zare

有一个基于将计数重写为总和，然后利用期望线性性的一行数学解决方案。 - duffymo

Answer 3

• 用每种颜色的10个物品制作一个坛子。
• 决定您想要的试验次数。
• 制作一个容器来保存每次试验的结果
• 对于每次试验，从坛子中随机抽取20个物品，制作一个该组物品的集合，并将该集合的长度添加到结果中。
• 找出结果的平均值

- wwii

---

你会建议进行多少次随机试验才能达到所需的10^-9精度？在我看来，大约需要进行10^18次试验，因此我认为应该使用另一种方法。 - Douglas Zare

@DouglasZare 我没有在问题中看到精度要求 - 那有点过头了。 - wwii

@DouglasZare 只是出于好奇，您是如何计算达到所需精度所需的试验次数的？ - rubik

@rubik: 你预计为了获得1/n的精度，需要进行大约cn^2次尝试，其中c是一些常数。我通过简化指标变量（用于表示每种颜色的存在）独立的假设来估算c的值（大约为1）。独立随机变量之和的方差等于各个方差的总和，因此这种独立性假设使得计算数量的方差变得简单，即7p(1-p)，其中p为0.974，即每种颜色被包括的概率。标准差是7p(1-p)的平方根，即0.42，足够接近1/2或1。 - Douglas Zare

您可以通过将独立假设与尽可能反相关的指标之和进行比较，来限定错误的重要性。这并不会有太大的影响。我们假设相关性为0，实际相关性是一个小的负数，使其尽可能负数会产生另一个易于分析的随机变量，其标准差为0.43。 - Douglas Zare

@DouglasZare 哇，谢谢！这真的很有启发性。 - rubik