统计:优化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是urn中70个球的列表).

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

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

问题:如果没有世界上最快的超级计算机,我怎样才能准确找到预期的颜色？我的计算方式是否可行？

Answer 1

由于有几个人要求看数学解决方案,我会给它.这是项目欧拉问题之一,可以在合理的时间内用铅笔和纸张完成.答案是

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))

期望总是线性的.因此,当您被要求查找某个随机数量的平均值时,通常会尝试将数量重写为较简单的部分(如指标(0-1)随机变量).

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

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

这组可能的指数包含在7元非负整数的集合中,其中总和20.其中一些是不可能的,例如(11,9,0,0,0,0,0)问题假设那里每种颜色只有10个球,但我们可以解决这个问题.一组7个非负数的元组加起来有20个大小(26个选择6)= 230230,它与在26个空间中为分隔符或对象选择6个分隔符的方式自然对应.因此,如果您有办法遍历26个元素集的6个元素子集,则可以将这些子元素转换为迭代所有索引.

你仍然需要通过从70得到20个球来获得这种情况的方法来计算重量.(a0,a1,a2,...,a6)的权重是(10选a0)(10选a1) ......*(10选a6).这可以优雅地处理不可能的索引的情况,因为10选择11是0所以产品是0.

因此,如果您不了解期望线性的数学解,则可以迭代230230个案例并计算索引向量的非零坐标数的加权平均值,并用小二项式的乘积加权.