This was a question at a programming contest that finished recently at interviewstreet:
Alice and Bob play a game. The operations at round $i$ ($i ≥ 1$) is as follows:
- Alice pays Bob $2i - 1$ dollars,
- Alice tosses a biased coin,
- If the result of the coin was heads for $k$ consecutive rounds, the game stops, otherwise the game continues.
Given $k$ and the probablity $p$ that the outcome of a toss is heads, your program should find the expected number of dollars Alice pays Bob, and also the expected number of rounds played.
I had gotten the first part of the problem, i.e the expected number of rounds of the game. I got it with the following code
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)
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)
But the second part of the problem is still puzzling me, i.e the expected number of dollars Alice pays bob. How can expected payoff be calculated?