假设我正在玩10种不同的游戏。对于每个游戏，我都知道获胜的概率，平局的概率和失败的概率(每个游戏都有不同的概率)。
从这些值，我可以计算出赢得X场比赛的几率，输掉X场比赛的几率以及并入X场比赛的几率(对于X = 0到10)。
我只是想算出赢得10场比赛之后赢得W场比赛，并列T场比赛和输掉L场比赛的可能性……希望能比O(3 ^ n)做得更好。例如，赢7，输2和并1的概率是多少？
有任何想法吗？谢谢!
编辑-如果只有2个游戏，这是一些示例数据:
比赛1:
游戏2:
基于此，我们可以计算出玩了以下两个游戏之后的概率:
根据这些数字，是否存在用于确定W胜，T胜和L败的概率的通用公式？可能的结果(W-L-T)为:
最佳答案
这可以通过动态编程来完成，我不确定是否有更好的方法，因为游戏是独立的。
拥有4D阵列，包括获胜，失败，平局和比赛。您可以将赢/输/平局限制为所需的数目(让它们为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))，然后智能地对其进行加/减，来显着提高这一速度，但是我还没有找到一种方法来做到这一点。
关于algorithm - 计算一组结果的概率的有效方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3848285/