统计：优化 python 内的概率计算
Statistics: Optimizing probability calculations within python
设置：
问题是经典概率问题的复数形式：
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 是 urn 中 70 个球的列表）。
我可以将迭代器解压缩到我的计算机无法处理的 combinations(urn, 8) 长度。
注意：我知道这不会给我答案，这只是我脚本中的路障，换句话说，如果这可行，我的脚本就可以运行。
问题：如果没有世界上最快的超级计算机，我如何准确地找到预期的颜色？我的方法在计算上是否可行？
- 用每种颜色 10 个制作一个骨灰盒。
- 决定你想要的试验次数。
- 制作一个容器来保存每次试验的结果
- 对于每次试验，从骨灰盒中随机抽取 20 件物品，将这些物品制成一组，并将该组的长度添加到结果中。
- 求结果的平均值
不就是重复组合吗？
http://www.mathsisfun.com/combinatorics/combinations-permutations.html
既然有几个人要看数学解，那我就给吧。这是 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个，其他颜色的none颜色。
可能的索引集合包含在总和为 20 的非负整数 7 元组的集合中。其中一些是不可能的，例如 (11,9,0,0,0,0,0) by问题假设每种颜色只有 10 个球，但我们可以处理它。非负数加起来为 20 的 7 元组的大小为（26 选择 6）=230230，它有一个 natural correspondence with the ways of choosing 6 dividers among 26 spaces for dividers or objects. So, if you have 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 个案例并计算索引向量的非零坐标数的加权平均值，由以下项的乘积加权小二项式项。
设置：
问题是经典概率问题的复数形式：
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 是 urn 中 70 个球的列表）。
我可以将迭代器解压缩到我的计算机无法处理的 combinations(urn, 8) 长度。
注意：我知道这不会给我答案，这只是我脚本中的路障，换句话说，如果这可行，我的脚本就可以运行。
问题：如果没有世界上最快的超级计算机，我如何准确地找到预期的颜色？我的方法在计算上是否可行？
- 用每种颜色 10 个制作一个骨灰盒。
- 决定你想要的试验次数。
- 制作一个容器来保存每次试验的结果
- 对于每次试验，从骨灰盒中随机抽取 20 件物品，将这些物品制成一组，并将该组的长度添加到结果中。
- 求结果的平均值
不就是重复组合吗？
http://www.mathsisfun.com/combinatorics/combinations-permutations.html
既然有几个人要看数学解，那我就给吧。这是 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个，其他颜色的none颜色。
可能的索引集合包含在总和为 20 的非负整数 7 元组的集合中。其中一些是不可能的，例如 (11,9,0,0,0,0,0) by问题假设每种颜色只有 10 个球，但我们可以处理它。非负数加起来为 20 的 7 元组的大小为（26 选择 6）=230230，它有一个 natural correspondence with the ways of choosing 6 dividers among 26 spaces for dividers or objects. So, if you have 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 个案例并计算索引向量的非零坐标数的加权平均值，由以下项的乘积加权小二项式项。