6

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
4

5 に答える 5

4

これは動的計画法で行うことができます。ゲームは独立しているため、より良い方法があるかどうかはわかりません。

勝ち、負け、引き分け、ゲームの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））、それらをインテリジェントに加算/減算することで、これを大幅に高速化できるかもしれませんが、これを行う方法は見つかりませんでした。

于 2010-10-03T06:50:07.037 に答える
1

3 ^ nオプションを実行したくない場合は、サンプリングを使用して答えを概算できます。サンプリングする回数であるNを決定します。N個のサンプルを実行し、各タイプの結果の数を数えます（0勝、1勝など）。各結果のおおよその確率は、number_of_samples_resulting_this_outcome/Nです。

于 2010-10-03T06:50:50.683 に答える
1

私の地域、統計！

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

あなたの例では、結果が発生する可能性のある方法を考慮する必要があります。

7勝、2敗、1引き分け10! / (2!*7!)。360通りの方法があります。だから、あなたがしたようにすべての結果を掛けてから、結果のその多くの順列を掛けます。

10 勝の順列は 1 つしかないため、すべての勝利で乗算することができます。ミックスの場合、順列を考慮する必要があります。

一般に、この問題の順列は次のよう10!/(w!*l!*t!)になります。w は勝った回数、l は負けた回数、t は引き分けの回数です。

編集1 上記は、順列の数え方のみを示していることに注意してください。合計確率は、順列の回数 (pw^w*pl^l*pt^t) です。ここで、pw は勝つ確率、pl は負ける確率、pt は引き分けの確率です。w、l、および t は、それぞれのカウントです。

編集 2 OK、新しい情報に照らして、これを行う一般的な方法がわかりません。各結果を手作業で個別に計算し、それらを合計する必要があります。上記の 2 ゲームの例で。1 勝 1 引き分けの確率を求めたい場合は、ちょうど 1 勝と 1 引き分け (2 つしかありません) を得る可能性のあるすべての方法を見つけて、それらを合計する必要があります。

最初の例の 10 ゲームでは、基準を満たす 360 の結果が得られます。各順列を実行し、確率を合計する必要があります。(wwwllt、wwwltl など) 残念ながら、これを行うためのより良い方法を知りません。

さらに、2 つのゲームの例では、1 勝 1 引き分けの場合、最初のゲームに勝ち、2 番目に同点になる確率を、最初に同点になり、次に勝つ確率に加算する必要があります。

したがって、9 つの独立した結果があります。

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

ノート

以下の応答は、一連のゲームを通じて勝敗の確率が固定されている場合にのみ有効です。条件を間違えました。とにかく単純なケースの解決策として残します。

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 に答える