베르누이 실험에게 다음과 같은 실험을 가정 할 시간

Question

많은 수의 실행의 자세한 결과 (확률 트리)를 얻는 방법 : 시간

I의 N 번호를 (성공 P의 확률로) 같은 베르누이 시험을 실행 다음 정보가 필요합니다 : 성공/실패 가능성이있는 모든 가능한 순서.

예 :

FFF 0.216

: 성공 P의 확률로 베르누이 실험 = 40 %는 다음과 같은 결과를 얻을 것이다 3 배 (S 성공이고, F는 실패이다) 실행될 SFF 0.144

FSF 0.144

SSF 0.096

FFS 0.144

SFS 0.096

FSS 0.096

SSS 0.064

나는 결과를 얻을를 bruteforce하려고하지만 급속 초크 만 N = 25 , OutOfMemoryException이 발생합니다 ...

using System; 
using System.Linq; 
using System.Collections.Generic; 
using System.Text.RegularExpressions; 

namespace ConsoleApplication 
{ 
    class Program 
    { 
     static Dictionary<string, double> finalResultProbabilities = new Dictionary<string, double>(); 

     static void Main(string[] args) 
     { 
      // OutOfMemoryException if I set it to 25 :(
      //var nbGames = 25; 
      var nbGames = 3; 
      var probabilityToWin = 0.4d; 

      CalculateAverageWinningStreak(string.Empty, 1d, nbGames, probabilityToWin); 

      // Do something with the finalResultProbabilities data... 
     } 

     static void CalculateAverageWinningStreak(string currentResult, double currentProbability, int nbGamesRemaining, double probabilityToWin) 
     { 
      if (nbGamesRemaining == 0) 
      { 
       finalResultProbabilities.Add(currentResult, currentProbability); 
       return; 
      } 

      CalculateAverageWinningStreak(currentResult + "S", currentProbability * probabilityToWin, nbGamesRemaining - 1, probabilityToWin); 
      CalculateAverageWinningStreak(currentResult + "F", currentProbability * (1 - probabilityToWin), nbGamesRemaining - 1, probabilityToWin); 
     } 
    } 
} 

나는 최적이 할 수있는 수학적 방법이 있나요 (모든 P에 대한 3 초 미만에 결과를 얻을 수) 적시

에 = 3000 N을 지원할 수 있어야합니다?

Answer 1

여기 하는 다른 접근 방식의 정확하고 충분한 만 차있는 빠른. 가장 긴 우승의 예상 값은

n 
sum Pr(there exists a win streak of length at least k). 
k=1 

과 같은 확률입니다. 레코드가 길이가 k 인 상태 (확률은 pwin**k)로 열리거나, j in 0..k-1에 대해 j의이긴 후 (확률은 pwin**j * (1 - pwin)) 손실이 발생하여 확률이 길이 확률과 같습니다. k 이길 수 있습니다 n - (j + 1)의 행진이 시도됩니다. 이 논리가 암시하는 재발을 평가하기 위해 메모를 사용합니다. pwinstreak; fastpwinstreak의 더 빠른 버전은 반복되는 합계를 피하기 위해 대수를 사용합니다. 수

def avglongwinstreak(n, pwin): 
    return sum(fastpwinstreak(n, pwin, k) for k in range(1, n + 1)) 


def pwinstreak(n, pwin, k): 
    memo = [0] * (n + 1) 
    for m in range(k, n + 1): 
     memo[m] = pwin**k + sum(pwin**j * (1 - pwin) * memo[m - (j + 1)] 
           for j in range(k)) 
    return memo[n] 


def fastpwinstreak(n, pwin, k): 
    pwink = pwin**k 
    memo = [0] * (n + 1) 
    windowsum = 0 
    for m in range(k, n + 1): 
     memo[m] = pwink + windowsum 
     windowsum = pwin * windowsum + (1 - pwin) * (memo[m] - pwink * 
                memo[m - k]) 
    return memo[n] 


print(avglongwinstreak(3000, 0.4)) 

버전 오류 :

def avglongwinstreak(n, pwin, abserr=0): 
    avg = 0 
    for k in range(1, n + 1): 
     p = fastpwinstreak(n, pwin, k) 
     avg += p 
     if (n - k) * p < abserr: 
      break 
    return avg 


def fastpwinstreak(n, pwin, k): 
    pwink = pwin**k 
    memo = [0] * (n + 1) 
    windowsum = 0 
    for m in range(k, n + 1): 
     memo[m] = pwink + windowsum 
     windowsum = pwin * windowsum + (1 - pwin) * (memo[m] - pwink * 
                memo[m - k]) 
    return memo[n] 


print(avglongwinstreak(3000, 0.4, 1e-6)) 

Answer 2

가장 긴 연승의 길이에 관심이 있으니 시련의 어느 시점에서든 역사에 관한 두 가지 관련 사실 만 있습니다. (1) 최장 연승이 얼마나 오래 (m)이고 (2) 현재 연승이 얼마나 오래 (k)인지. 초기 상태는 (0, 0)입니다. 전이는 승리시 (m, k) -> (max (m, k + 1), k + 1)이고 손실시 (m, k) -> (m, 0)입니다. 모든 최종 상태의 확률을 알면 평균을 구할 수 있습니다.

편집 :이 코드의 수정 된 버전은 매우 드문 경우의 이벤트에 필요한 계산을 줄이기위한 최적화 기능을 제공합니다. 특히, 길이가 약 cutoff 이상인 모든 상태를 무시합니다. 절대 오차 예산 abserr이 주어지면 가능한 가장 긴 줄무늬가 n이므로 최종 예상 값 계산에서 abserr/n까지 확률 질량을 제외 할 수 있다고 결정합니다. 줄무늬가 시작하는 곳이 n 개 미만이고 각 위치에서 길이가 cutoff 인 줄무늬의 확률은 pwin**cutoff입니다. 마지막 불평등 log(pwin) < 0 때문에 방향을 뒤집 곳 바인딩 원유 조합을 사용하여, 우리는

n * pwin**cutoff <= abserr/n 
pwin**cutoff <= abserr/n**2 
log(pwin) * cutoff <= log(abserr/n**2) 
cutoff >= log(abserr/n**2, pwin), 

이 필요합니다.

이 수정 된 코드는 품질이 좋지 않은 평가 도구 (예 : 2014 년 하드웨어의 Python 3 인터프리터)에도 불구하고 3 초 이내에 실행됩니다.

import math 


def avglongwinstreak(n, pwin, abserr=0): 
    if n > 0 and pwin < 1 and abserr > 0: 
     cutoff = math.log(abserr/n**2, pwin) 
    else: 
     cutoff = n + 1 
    dist = {(0, 0): 1} 
    for i in range(n): 
     nextdist = {} 
     for (m, k), pmk in dist.items(): 
      winkey = (max(m, k + 1), k + 1) 
      if winkey[0] < cutoff: 
       nextdist[winkey] = nextdist.get(winkey, 0) + pmk * pwin 
      losskey = (m, 0) 
      nextdist[losskey] = nextdist.get(losskey, 0) + pmk * (1 - pwin) 
     dist = nextdist 
    return sum(m * pmk for ((m, k), pmk) in dist.items()) 


print(avglongwinstreak(3000, 0.4, 1e-6))