вероятностная головоломка, ожидаемый выигрыш за игру

Это был вопрос на конкурсе программистов, который завершился вчера на interviewstreet:

Элис и Боб играют в игру. Операции на круге i (i >= 1) выглядят следующим образом:

    Алиса платит Бобу 2 * i-1 доллар,
  • Алиса бросает пристрастную монету,
  • Если результат монеты был орел для k последовательных раундов, игра останавливается, в противном случае игра продолжается.

Учитывая k и вероятность того, что результат броска-Орел (p), ваша программа должна найти ожидаемое количество долларов, которое Алиса платит Бобу, а также ожидаемое количество сыгранных раундов.

Вход

Первая строка ввода содержит количество тестовых случаев (T

Вывод

Для каждого тест-кейс, выведите два целых числа. Первое число-это целая часть от ожидаемого количества раундов игры, а вторая число-это целая часть ожидаемого количества долларов. платит Боб.

Ввод Образца

3

0.6 1

1 20

0.80 8

Образец Вывода

1 3

20 400

24 976
Я получил первую часть задачи, то есть ожидаемое количество раундов игры. Я получил его со следующим кодом 
if __name__ == '__main__':
    t = int(raw_input())   
    while t :
        t -= 1
        temp = str(raw_input())
        p,k = temp.split(' ')
        p = float(p)
        k = int(k)

        #print p,k
        ans  = 0.0
        num = k * (p**k)
        den = 1
        q = 1.0 - p
        for N in range(1,k+1):
            den = den - ((p**(N-1))*q)
            num = num + (N*(p**(N-1))*q)
            #print (N*(q**N))

        print int(num/den)
Но вторая часть проблемы все еще озадачивает меня, т. е. ожидаемое количество долларов Алиса платит Бобу. Как можно рассчитать ожидаемый выигрыш?
1 4
python puzzle probability

1 ответ:

Вам нужно усреднить все возможные выплаты по вероятности их возникновения, даже если вы знаете ожидаемое количество раундов. Это означает, что это сложнее, чем просто вычислить выплату в ожидаемое время остановки. Вот мелкие детали:

Напомним, что техническое определение математического ожидания гласит, что если X-случайная величина, то ожидаемое значение X-это сумма всех возможных исходов w Из X(w)*Pr(w). Если X принимает значения в натуральных числах, мы можем перефразировать это как ожидаемое значение X есть сумма от i=1 до бесконечности i * Pr(X=i). В вашем случае случайными величинами, с которыми мы имеем дело, являются T = время остановки игры и P = выплата.

Ожидаемое число раундов-это ожидание T, которое является суммой от i=1 до бесконечности i * Pr (T=i). Поскольку они просят только целочисленную часть математического ожидания, мы можем прекратить суммирование, как только i * Pr (T=i) меньше 1/2^i. (идея остановки суммы, когда i*Pr (T=i)

Ожидание P несколько сложнее. Если бы игра длилась j раундов, то выигрыш был бы равен сумме от i=1 до j из 2i-1, которая оказывается j^2. При этом могут происходить только выплаты вида j^2, а Pr(P=j^2)=Pr(T=j). Таким образом, ожидаемое значение P-это сумма от i=1 до бесконечности i^2 * Pr(P=i^2), которая равна сумме от i=1 до бесконечности i^2*Pr(T=i). Опять же, мы можем прекратить суммирование, как только i^2 * Pr (T=i) меньше, чем 1/2^i.

3