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

Question

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

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

我只是想计算出赢得 W 场比赛、打平 T 场比赛和输掉 L 场比赛的概率10 场比赛……希望比 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 失败的概率？可能的结果 (W-L-T) 将是:

• 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))，然后智能地添加/减去它们来更快地执行此操作，但我还没有找到一种方法来执行此操作.