Itertools, чтобы создать список и определить вероятность

Question

Я пытаюсь определить вероятность победы «Сьюзи».

Вероятность «Сьюзи» победу в игре = 0,837
Вероятность «Bob» выиграть игру = 0,163

Если первый человек, чтобы выиграть п игры выигрывает матч, то, что является наименьшим значением п такой что у Сьюзи лучше шанса на победу в 0,9?

До сих пор у меня есть этот код:

import itertools 

W = 0.837 
L = 0.163 
for product in itertools.product(['W','L'], repeat=3): #3=number of games 
    print product 

который печатает:

('W', 'W', 'W') 
('W', 'W', 'L') 
('W', 'L', 'W') 
('W', 'L', 'L') 
('L', 'W', 'W') 
('L', 'W', 'L') 
('L', 'L', 'W') 
('L', 'L', 'L') 

Затем я хочу использовать эти результаты, чтобы выработать вероятность «Сьюзи» победу в матче в целом.

Я разработал эту проблему на бумаге, чем больше сыгранных игр, тем больше шансов на победу «Сьюзи».

Answer 1

Вы можете использовать словарь для вероятностей:

import itertools 
import operator 

probabilities = {'W':0.837, 'L':0.163} 

for product in itertools.product(['W','L'], repeat=3): #3=number of games 
    p = reduce(operator.mul, 
       [probabilities[p] for p in product]) 
    print product, ":", p 

reduce функция аккумулирует все элементы списка с помощью функции, заданной в первом аргументе - здесь мы накапливаем их умножение.

Это дает вам вероятность каждой последовательности событий. Из этого вы можете легко выбрать, какой из них «Сьюзи выигрывает матч», и суммировать вероятности. Одна из возможностей сделать это:

import itertools 
import operator 

probabilities = {'W':0.837, 'L':0.163} 

winProbability = 0 
for product in itertools.product(['W','L'], repeat=3): #3=number of games 
    p = reduce(operator.mul, 
       [probabilities[p] for p in product]) 

    if product.count('W') > 1: #works only for 3 games 
     winProbability += p 
     print "Susie wins:", product, "with probability:", p 
    else: 
     print "Susie looses:", product, "with probability:", p 

print "Total probability of Susie winning:", winProbability 

условие работает только для 3 игр, но я на самом деле оставить это одно к вам - это легко обобщить это для n игр :)

Answer 2

Кроме того, необходимо для циклических значений n. Также обратите внимание, что «от первого до n» совпадает с «лучшим из 2n-1». Итак, мы можем сказать m = 2 * n - 1 и посмотреть, кто победит в большинстве игр этого набора. max(set(product), key=product.count) - короткий, но непрозрачный способ разработки, который выиграл большинство игр. Кроме того, зачем беспокоиться о представлении вероятностей со строками, а затем использовать словарь для их чтения, когда вы можете напрямую хранить значения в своих кортежах.

import itertools 

pWin = 0 #the probability susie wins the match 
n = 0 
while pWin<0.9: 
    n += 1 
    m = 2 * n - 1 
    pWin = 0 
    for prod in itertools.product([0.837,0.163], repeat=m): 
     #test who wins the match 
     if max(set(prod), key=prod.count) == 0.837: 
      pWin += reduce(lambda total,current: total * current, prod) 
print '{} probability that Susie wins the match, with {} games'.format(pWin, n) 

Answer 3

Я был заинтригован @ desired_login указывают, но думал, что я хотел бы попробовать вычисления перестановок вместо итерацию через них:

import sys 
if sys.hexversion >= 0x3000000: 
    rng = range  # Python 3.x 
else: 
    rng = xrange # Python 2.x 

def P(n, k): 
    """ 
    Calculate permutations of (n choose k) items 
    """ 
    if 2*k > n: 
     k = n - k 
    res = 1 
    for i in rng(k): 
     res = res * (n-i) // (i+1) 
    return res 

Ps = 0.837 # Probability of Susie winning one match 
Px = 0.980 # Target probability 

# Probability of Susie winning exactly k of n matches 
win_k   = lambda n,k: P(n, k) * Ps**k * (1.0-Ps)**(n-k) 
# Probability of Susie winning k or more of n matches 
win_k_or_more = lambda n,k: sum(win_k(n, i) for i in rng(k, n+1)) 

def main(): 
    # Find lowest k such that the probability of Susie winning k or more of 2*k - 1 matches is at least Px 
    k = 0 
    while True: 
     k += 1 
     n = 2*k - 1 
     prob = win_k_or_more(n, k) 
     print('Susie wins {} or more of {} matches: {}'.format(k, n, prob)) 
     if prob >= Px: 
      print('At first to {} wins, Susie has >= {} chance of winning the match.'.format(k, Px)) 
      break 

if __name__=="__main__": 
    main() 

Для Рх = 0,98, это приводит к

Susie wins 1 or more of 1 matches: 0.837 
Susie wins 2 or more of 3 matches: 0.9289544940000001 
Susie wins 3 or more of 5 matches: 0.9665908247127419 
Susie wins 4 or more of 7 matches: 0.9837066988309756 
At first to 4 wins, Susie has >= 0.98 chance of winning the match. 

Runtime - это что-то вроде O (n^3) для этого алгоритма, в отличие от O (2^n) для остальных.