python – 概率难题,游戏的预期收益

这是昨天在面试中完成的编程竞赛中的一个问题：

爱丽丝和鲍勃玩游戏.第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)

但问题的第二部分仍然令我感到困惑,即爱丽丝支付预期的美元数量.如何计算预期收益？

解决方法:

您需要对所有可能的支出进行平均而不是它们发生的概率,即使您知道预期的轮次数.这意味着它比在预期的停止时间计算支出更复杂.以下是细节：

回想一下,期望的技术定义说如果X是随机变量,那么X的期望值是X(w)* Pr(w)的所有可能结果w的总和.如果X取正整数值,我们可以将其改为,因为X的期望值是i = 1到i * Pr(X = i)的无穷大之和.在你的情况下,我们正在处理的随机变量是T =游戏停止的时间,P =支付.

预期的轮数是T的期望,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,我们就可以停止求和.

来源：https://www./content-1-282751.html