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?