6

假设我正在玩 10 种不同的游戏。对于每场比赛，我知道获胜的概率、平局的概率和失败的概率（每场比赛的概率不同）。

从这些值中，我可以计算出赢得 X 场比赛的概率、输掉 X 场比赛的概率以及平局 X 场比赛的概率（对于 X = 0 到 10）。

我只是想弄清楚在打完所有 10 场比赛后赢得W场比赛、平局T场比赛和输掉L场比赛的概率……希望比 O(3^n) 做得更好。例如，赢 7 输 2 平 1 的概率是多少？

有任何想法吗？谢谢！

编辑 - 如果只有 2 场比赛，这里有一些示例数据：

游戏一：

  • 胜率：23.3%
  • 领带：1.1%
  • 损失：75.6%

游戏二：

  • 胜率：29.5%
  • 领带：3.2%
  • 损失：67.3%

基于此，我们可以计算出玩了 2 场比赛后的概率：

  • 0胜：54.0%
  • 1胜：39.1%
  • 2胜：6.9%
  • 0 条关系：95.8%
  • 1 平：4.2%
  • 2 条： 0.0%
  • 0 损失：8.0%
  • 1 损失：41.1%
  • 2 次损失：50.9%

根据这些数字，是否有一个通用公式来计算W胜、T平和L负的概率？可能的结果（WLT）将是：

  • 2-0-0
  • 1-1-0
  • 1-0-1
  • 0-1-1
  • 0-2-0
  • 0-0-2
4

5 回答 5

4

这可以通过动态编程来完成，我不确定是否有更好的方法，因为游戏是独立的。

有一个包含胜利、失败、平局和比赛的 4 维数组。您可以将赢/输/平局限制为您想要的数字（让这些为 W、L、T、W+L+T=G），时间复杂度将为 O(W*L*T*G)，这是有界的由 O(G⁴)。

该算法基本上是：

A[][][][] = new double[G+1][W][T][L]
// A[g][w][t][l] is the probability of have w wins, t ties, l losses
// after g games. This can be computed from A[g-1].
// Let P[g][o] be the probability of outcome o for game g
//everything else is initially 0.
A[0][0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   for l=0..L
    A[g][w][t][l] = A[g-1][w-1][t][l]*P[g][win] // assume out of bounds
                   +A[g-1][w][t-1][l]*P[g][tie] // reference returns 0
                   +A[g-1][w][t][l-1]*P[g][lose]
return A[G][W][T][L]

编辑）

我们可以在 O(W*L*T*G/max(W,L,T)) 中做到这一点，即 O(G³)。请注意，如果我们在 G 场比赛之后有 W 胜和 T 平局，那么我们必须有 L 场失利。

// we should pick the conditions we loop to be the smallest two.
// here we just use wins and ties.
A[][][][] = new double[G+1][W][T]
A[0][0][0] = 1
for g=1..G
 for w=0..W
  for t=0..T
   A[g][w][t] = A[g-1][w-1][t]*P[g][win] // assume out of bounds
               +A[g-1][w][t-1]*P[g][tie] // reference returns 0
               +A[g-1][w][t]*P[g][lose]
return A[G][W][T]

通过分别计算 x 次获胜/平局/损失的概率 (O(G))，然后智能地添加/减去它们，也许可以显着更快地做到这一点，但我还没有找到一种方法来做到这一点。

于 2010-10-03T06:50:07.037 回答
1

对于您的示例，您需要考虑结果可能发生的方式。

赢7，输2，平1。有10! / (2!*7!)或360种可能的方法。所以像你一样乘以所有结果，然后乘以结果的许多排列。

对于所有胜利，您可以乘以，因为十次胜利只有一个排列。对于混合，您需要考虑排列。

一般来说，对于这个问题，排列将是10!/(w!*l!*t!)其中 w 是获胜次数，l 是失败次数，t 是平局数。

编辑 1 请注意，以上仅说明如何计算排列。总概率是排列次数 (pw^w*pl^l*pt^t)，其中 pw 是获胜的概率，pl 是失败的概率，pt 是平局的概率。w、l 和 t 是每个的计数。

编辑 2 好的，鉴于新信息，我不知道执行此操作的一般方法。您必须手动单独计算每个结果并将它们加在一起。上面有你的两场比赛的例子。如果你想找到 1 胜 1 平的概率，你必须找到每一种可能的方法来得到 1 胜和 1 平（只有两个），然后把它们加起来。

对于初始示例的十场比赛，您将获得 360 个符合您标准的结果。您必须进行每个排列并将概率相加。（wwwwwwwllt、wwwwwwwltl 等）不幸的是，我不知道有更好的方法来做到这一点。

此外，在您的两场比赛示例中，对于一场胜利和一场平局，您必须将赢得第一场比赛并打平第二场比赛的概率与先平局然后获胜的概率相加。

因此，有九个独立的结果：

W W
W T
W L
T W
T T
T L
L W
L T
L L
于 2010-10-03T02:20:38.620 回答
1

我的区域，统计！

您需要计算一个排列的几率，可以这样做：

O = chanceWin^numWin * chanceTie^numTie * chanceLose^numLose

根据您的示例，其中 numWin、numLose 和 numTie 分别为 7、2 和 1。

现在乘以获胜的排列，即：

O *= 10! / ((10-numWin)! * numWin!)

然后输了：

p = 10-numWin
O *= p! / ((p-numLose)! * numLose!)

然后绑：

p = 10-(numWin+numLose)
O *= p! / ((p-numTie)! * numTie!)

现在 O 是您在 10 场比赛中赢得 numWin 场比赛、输 numLose 场比赛和平局 numTie 场比赛的几率。

于 2010-10-03T02:33:21.557 回答
1

如果您不想超过 3^n 选项，您可以使用采样来近似答案：决定 N，您希望采样的次数。运行 N 个样本，并计算每种类型的结果数（0 胜、1 胜等）。每个结果的近似概率是 number_of_samples_resulting_this_outcome / N。

于 2010-10-03T06:50:50.683 回答
1

笔记

只有在通过系列游戏确定了输赢概率时，以下响应才有效。我误解了条件。无论如何，我把它作为更简单情况的解决方案。

我得到了 W 胜、L 负和 NWL 平局的公式：

替代文字

计算复杂度

幂和阶乘中的每一个最多具有 N 的阶数，因此可以在线性时间中计算该值，除非我缺少某些要求。

以下 Java 代码适用于我。我还验证了概率总和为 1：

public static double p(int w, int l, int t, double pw, double pl) {
    double r = factorial(w+l+t) * Math.pow(pw,w) * Math.pow(pl,l) * Math.pow(1-pw-pl, t);
    r /= factorial(w) * factorial(l) * factorial(t);
    return r;
}

private static long factorial(int n) {
    long res = 1;
    for(int i = 2; i <= n; i++)
        res *= i;

    return res;
}
于 2010-10-03T10:07:03.377 回答