python - 概率谜题，游戏的预期 yield

Question

这是昨天在 interviewstreet 结束的编程竞赛中的一个问题:

爱丽丝和鲍勃玩游戏。第i轮(i >= 1)的操作如下:

• Alice 付给 Bob 2 * i - 1 美元，
  
• 爱丽丝抛出一枚有偏见的硬币，
  
• 如果硬币的结果连续k轮为正面，则游戏停止，否则游戏继续。
  

给定 k 和抛掷结果为正面朝上的概率 (p)，您的程序应该计算出 Alice 支付给 Bob 的预期美元数，以及预期的回合数。

输入

First line of input contains number of test-cases (T <= 50). Each of the next T lines contain p and k separated by a single space. p is a decimal number with at most two digits after the decimal point such that 0.6 <= p <= 1. k is a positive integer such that 0 < k <= 20.

输出

For each test-case, print two integer numbers. First number is the integer part of the expected number of rounds of game, and the second number is the integer part of the expected number of dollars Alice pays Bob.

示例输入

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)

但是问题的第二部分仍然让我感到困惑，即 Alice 支付给 bob 的预期美元数。如何计算预期 yield ？

Answer 1

即使您知道预期的回合数，您也需要对所有可能的支出取其发生概率的平均值。这意味着它比仅计算预期停止时间的支出要复杂得多。以下是具体细节:

回想一下期望的技术定义，如果 X 是随机变量，则 X 的期望值是 X(w)*Pr(w) 的所有可能结果 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)<1/2^i 时停止求和的想法是 1/2^i 总和为 1，但您可能需要对此进行调整以避免低估。)

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^2*Pr(T=i) 小于 1/2^i，我们就可以停止求和。