Databases
StackOverflow2013
Postsdbo
POprobability puzzle, expected payoff for game
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POprobability puzzle, expected payoff for game
    text
    copied!<p>This was a question at a programming contest that finished yesterday at interviewstreet:</p> <p>Alice and Bob play a game. The operations at round i (i >= 1) is as follows:</p> <ul> <li>Alice pays Bob 2 * i - 1 dollars,<br></li> <li>Alice tosses a biased coin,<br></li> <li>If the result of the coin was heads for k consecutive rounds, the game stops, otherwise the game continues.<br></li> </ul> <p>Given k and the probablity that the outcome of a toss is heads (p), your program should find the expected number of dollars Alice pays Bob, and also the expected number of rounds played.</p> <p>Input</p> <blockquote> <p>First line of input contains number of test-cases (T &lt;= 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 &lt;= p &lt;= 1. k is a positive integer such that 0 &lt; k &lt;= 20.</p> </blockquote> <p>Output</p> <blockquote> <p>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.</p> </blockquote> <p>Sample Input</p> <pre><code>3 0.6 1 1 20 0.80 8 </code></pre> <p>Sample Output</p> <pre><code>1 3 20 400 24 976 </code></pre> <p>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</p> <pre><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) #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) </code></pre> <p>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?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload