Calculate the exact probability that the second player wins

algorithmsprobabilitypythonrandom

Consider a game that uses a generator which produces independent random integers between 1 and 100 inclusive. The game starts with a sum S = 0. The first player adds random numbers from the generator to S until S > 100 and records her last random number 'x'. The second player, continues adding random numbers from the generator to S until S > 200 and records her last random number 'y'. The player with the highest number wins, i.e. if y > x the second player wins. Is this game fair? Write a program to simulate 100,000 games. What is the probability estimate, based on your simulations, that the second player wins? Give your answer rounded to 3 places behind the decimal. For extra credit, calculate the exact probability (without sampling).

import random

CONST_TIMES = 100000
CONST_SMALL = 100
CONST_LARGE = 200

def playGame():
    s = 0
    while s <= CONST_SMALL: 
        x = random.randint(1, CONST_SMALL)
        s = s + x;
    while s <= CONST_LARGE:
        y = random.randint(1, CONST_SMALL)
        s = s + y
    if x < y:
        return 's'
    elif x == y:
        return 'm'
    else:
        return 'f'

fst = sec = 0
for i in range(CONST_TIMES):
    winner = playGame()
    if winner == 'f':
        fst = fst + 1
    elif winner == 's':
        sec = sec + 1
secWinPro = round(float(sec) / CONST_TIMES, 3)

print secWinPro

The simulation probability is about 0.524. I want to know how to calculate the exact probability.

Best Answer

An analytic calculation shows the probability that the second player wins is $0.521491$.

For a start, consider the probability that the sum $S$ is equal to $n$ at some point, where $n \le 100$; let's call that probability $p(n)$. On the previous step, the sum must have been $n-i$ for some $i$ with $0 \le i \le n-1$, and then the player must have drawn $i$, with probability $1/100$. So $$p(n) = \sum_{i=0}^{n-1} \frac{p(i)} {100}$$ where we define $p(0) = 1$. The solution to this recurrence is $$p(n) = \frac{(1+1/100)^{n-1}} {100}$$ for $0 \lt n \le 100$. (This formula does not hold for $n > 100$, but we will not need values of $p(n)$ in that range.)

Now that we know how to compute $p(n)$, let's consider how the player's scores can be $x$ and $y$ for the first and second players, respectively. We might as well consider a slightly more general problem and ask how the first player's score can be $x$ when the score is the first number drawn with $S \ge G$ for some $G \le 100$. Let's say the previous number drawn was $m$, where $m \le G$, and then the next number was $x$, where $m+x > G$. The probability of this sequence of events is $p(m) / 100$. For the first player's score, we are interested only in the case $G=100$.

Suppose we then continue drawing numbers until $S \ge 200$, with the last number drawn being $y$ and the previous number being $n$, so $n+y > 200$. Since we started at $m+x$, this is just like starting from zero as in the first case, but now with a goal of $200 - (m+x)$ instead of $100$. Then the associated probability is $p(n -(m+x)) / 100$. So the overall probability of the sequence of numbers $m, m+x$, (zero or more numbers omitted), $n, n+y$ is $$\frac{p(m) \cdot p(n-(m+x))}{100^2}$$

We are interested in the total probability of the cases where $x < y$. Taking into account the constraints on $m, x, n$ and $y$, this probability is $$\sum_{m=1}^{100} \sum_{x=101-m}^{100} \sum_{n=m+x}^{200} \sum_{y= \max(200-n,x)+1}^{100} \frac{p(m) \cdot p(n-(m+x))}{100^2} $$ Observing that the summand does not involve $y$, we can simplify this sum to $$ \sum_{m=1}^{100} \sum_{x=101-m}^{100} \sum_{n=m+x}^{200} \frac{[100-\max(200-n,x)] \cdot p(m) \cdot p(n-(m+x))}{100^2}$$ which evaluates to $0.521491$.

Related Question