문제는 간단합니다. K와 N이 주어지면 게임 한 개당 1 개를이기거나 잃을 확률이 1 인 경우 N 개의 게임 중에서 최소한 K 번째로 승리 할 확률은 얼마입니까?/2.계산 방법 N 게임에서 최소한 k를 얻는 확률
N은 10^6 크기뿐입니다.
내가 효율적으로 정확히 K의 확률 N 게임에서 승리를 계산할 수 있지만, 적어도 K.
이 친절 효율적인 접근 방법을 제공하기위한 효율적인하지 않는 것 소인수 분해를 사용하여.
는이 재귀를 사용하는 경우, 당신은 소인수 분해를 수행 할 필요가 없습니다
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
나타낸다 수 있습니다.
당신은 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