计算一组结果的概率的有效方法？

Question

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

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

我只是想计算出在玩完所有 10 场比赛后赢得 W 场比赛、平局 T 场比赛以及输掉 L 场比赛的概率。 ..希望比 O(3^n) 做得更好。例如，赢 7、输 2、平 1 的概率是多少？

有什么想法吗？谢谢！

---

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

比赛 1：

• 获胜：23.3%
• 平局：1.1%
• 输掉：75.6%

比赛 2：

• 获胜：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

Answer 1

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

有一个 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))，然后智能地添加/减去它们来更快地完成此操作，但我还没有找到一种方法来做到这一点。

Answer 2

我的地区，统计！

您需要计算一种排列的几率，可以这样完成：

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 场比赛的赔率。

Answer 3

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

赢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 场平局（只有两种）并将它们相加。

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

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

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

W W
W T
W L
T W
T T
T L
L W
L T
L L

Answer 4

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

Answer 5

注意

只有当一系列游戏的赢/输概率固定时，以下响应才有效。我误解了条件。无论如何，我将其保留为更简单情况的解决方案。

我得到了 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;
}