有效的方法，用于计算概率的一个组成果？

StackOverflow https://stackoverflow.com/questions/3848285

题

我们说我打10个不同的游戏。每个游戏，我知道奖的概率，概率的搭售，以及该概率的丧失(每场比赛都有不同的概率).

从这些价值观，我可以计算出获胜的概率X游戏的概率就会失去X游戏，以及该概率的绑X游戏(X=0到10)。

我只是在试图找出获胜的概率 W 游戏，绑 T 游戏，并失去 我 游戏后播放的所有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 联系， 我 损失？可能的结果(W-L-T)将是：

  • 2-0-0
  • 1-1-0
  • 1-0-1
  • 0-1-1
  • 0-2-0
  • 0-0-2
有帮助吗？

解决方案

这可以通过动态规划，我不知道，如果有一个更好的方法作为这游戏是独立的。

有4-D阵列，胜，损失，关系和游戏。你可以限制赢得/损失/联系到你想要的数字(让这些可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]

编辑)

我们可以做到这一点(W*L*T*克/max(W,L,T))，即O(G3)。请注意，如果我们有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))，然后加上/减去他们聪明，但是我还没有找到一种方法来做到这一点。

其他提示

我的领域，统计！

你需要计算的可能性之一的置换，这是可以做到这样：

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

在numWin,numLose和numTie7、2和1,作为每您的例子。

现在乘以排列奖，这是：

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

然后失去:

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

然后绑:

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

现在是性，你赢得numWin游戏，失去numLose游戏和绑numTie游戏中的10场。

对你的例子，需要考虑的可能的方法，结果可能发生。

为赢得7，失去了2、绑1.还有 10! / (2!*7!) 或360可能的方式。所以繁衍所有后果，因为你，然后乘以通过许多排列的结果。

对于所有的胜利，你可以乘因为有一个置换十个胜利。一个混合，则需要考虑的置换。

一般对于这个问题的排列会 10!/(w!*l!*t!) 在w数的胜利，我是数量的损失，和t号码的联系。

编辑1 请注意，上述仅表明如何计算的排列。总的概率是多少排列次(pw^w*pl^l*pt^t)在pw概率赢了，pl损失，pt一条领带。w,l,和t，是计算每个。

编辑2 OK，鉴于新的信息，我不知道一般的方式做到这一点。你必须单独计算机的各个结果，通过手工和增加他们在一起。用你的两个游戏上面的例子。如果你想要找的概率为1赢得和1扎，你就必须找到各种可能的方式得到完全1赢了和一个打领带(只有两个)，并把它们加起来。

十游戏与最初的实例，只有360成果，满足您的标准。你必须做的每个排列，并加起来的概率。(wwwwwwwllt,wwwwwwwltl，等等)不幸的是，我不知道一个更好的方式来做到这一点。

此外，在你的两个游戏如，对于一个赢得和一个打领带，必须将赢得第一场比赛和绑第二概率绑第一，然后胜利。

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

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

如果你不想要运行着3^n选择的，你可以 近似的 答案通过使用 取样:决定N的次数你想要的样本。跑N样品，并计算有多少，结果每个类型你得(0获胜，赢得1,等)。大致的概率的每个成果是number_of_samples_resulting_this_outcome。

注意到

应以下是唯一有效的当赢得/损失的概率是 固定 通过一系列的游戏。我误解的条件。我离开这无论如何作为一种解决方案更简单的情况。

我得到了这个公式，用于W赢了，我失去了和N-W-L的关系：

alt text

复杂的计算

每一个的权力和阶乘具有至多一个令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;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top