どのようにNゲームからatleast kを獲得する確率

Question

問題は簡単で、KとNを与えれば、勝ち負けの確率が等しい場合/ 2。

Nは10^6ほどの大きさです。

私は効率的に正確にKの確率Nのゲームのうち、勝利を計算することができますが、それは、少なくともK.

が親切に効率的なアプローチを提供するための効率的なようではありません素因数分解を使用。

Answer 1

は、この再帰を使用する場合は、素因数分解を行う必要はありません

P(k,n) = P(k,n| nth chance was win)*P(nth win) + P(k,n| nth chance was lost)*P(nth lost) 
     = 1/2*P(k-1,n-1) + 1/2*P(k,n-1) 

、今

P(k,n)= Probability of winning atleast k out of n games 

を表すことができます。

Answer 2

あなたはCDFを探しています（累積分布関数 - 分布関数はx以下の値を取る確率 。）お使いの場合には

https://en.wikipedia.org/wiki/Cumulative_distribution_function

からBinomial distributionをCDFはRegularized Incomplete Beta function：

CDF(p, N, K) = I(1 - p, N - K, 1 + K) 

あなたの場合は

（p = 1/2）

P(N, K) = 1 - I(0.5, N - K + 1, K) 

多くの数学エンジンは、例えば、そのようベータ機能を提供します無料Octaveはbetaincを使用しています。

N = 10; # 10 games 
    K = 2; # win at least 2 
    1 - betainc(0.5, N - K + 1, K) 

アウトカム

0.98926