组合数学计算题:掷20个8面骰子,得到至少5个相同值的骰子的概率是多少?

重复计数可以通过使用 Inclusion/Exclusion Principle

我怀疑结果是:

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

等等。这并不能直接解决“多于5个相同”的问题,就好像你简单地把这个结果加在5,6,7..20上一样;你会把你有10个1和5个8的案例数过多。

你可能会再次应用包含排除来得出第二个答案;所以,p(至少是5的)=p(20的一组)+…+(P(15-7*P一套(5个骰子5套))+(P(14-7*P一套(6-7*P一套(6-6-7*P一套))。为这个问题提出源代码证明自己更困难。

我建议你花点时间写一个蒙特卡洛模拟,让它在你手工计算数学的时候运行。希望蒙特卡洛模拟能在你完成数学运算之前收敛,并且你能检查你的解决方案。

一个稍微快一点的选项可能涉及到为数学问题创建一个这样的克隆。

一个i s边骰子和的确切概率分布fs,i可以计算为单个骰子概率分布与其自身的重复卷积。

哪里 为了所有 否则为0。

http://en.wikipedia.org/wiki/Dice

如果你必须把这个问题推广(得到确切的公式),这个问题真的很难。

但无论如何,让我解释一下算法。 如果你想知道

获得精确5的方法的数目 相同价值的骰子

你必须重新表述你以前的问题,因为

计算获得 正好5个骰子的值3和否 其他值可以精确重复5 时代

为了简单起见,让我们调用函数f(20,8,5)(5个骰子,所有值)作为第一个答案,而f(20,8,5,3)(5个骰子,值3)作为第二个答案。 我们得到f(20,8,5)=f(20,8,5,3)*8+ (多个值重复5次时的事件)

所以如果我们能得到f(20,8,5,3),应该很简单,不是吗? 嗯……没那么多……

首先,让我们定义一些变量: X1,X2,X3…,Xi,其中X=我们得到骰子i的次数

然后:

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

,p(语句)是编写概率的标准方法。

我们继续:

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

递归地:

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

那么……f(5,5,5,4)是5卷中获得5个值为4的骰子的方法数,例如没有其他骰子重复5次。只有一条路,总共5^5条。概率是1/5^5。

f(5,5,5)是在5卷中获得任意值(5个值中的5个)的5个骰子的方法数。显然是5点。概率是5/5^5=1/5^4。

f(10,6,5,2)是10卷中获得5个值为2的骰子的方法数,例如没有其他骰子重复5次。 f(10,6,5,2)=(1-f(5,5,5)/5^5)*6^10=(1-1/5^4)*6^10

好。。。我认为这在某些方面可能是不正确的,但无论如何,你明白了。我希望我能理解算法。

编辑: 我做了一些检查,我意识到当你得到一个以上的值重复5次时,你必须添加一些案例。你没有时间去解决那部分…

这就是我的想法…

如果你只有5个骰子,你只有8种方法得到你想要的。

对于这八种方法中的每一种,其他15个骰子的所有可能组合都起作用。

所以-我想答案是:(8*8) 15)/ 8 二十

(至少5个相同的答案。)

我相信你可以使用n个事件中x次出现的公式:

p=概率^n*(n!/((N-X)!X!)

所以最后的结果是从0到n的结果之和。

我真的看不出有什么简单的方法可以把它合并成一个不那么混乱的步骤。通过这种方式,您也可以在代码中阐明公式。不过,您可能需要编写自己的阶乘方法。

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

递归解决方案:

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))