# How to calculate the exact probability that the second player wins?

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.

• Why cannot I highlight the code – Jessepinkman56 May 11 at 11:00
• What happens if you play with $2$ rather than $100$ (for the total and the range of choice)? You can analyze that (and probably $3$ ) by listing all the cases. – Ethan Bolker May 11 at 11:07
• I cannot find any regular pattern @EthanBolker – Jessepinkman56 May 11 at 11:24
• Very interesting question. Intuitively I don't even see any reason the second player should win more. This seems to be homework / quiz? If so, when you get the official solution for the extra credit, can you post it here? – antkam May 12 at 2:26
• I think it is because of the conditional probability that leads to a better situation for the second player. And I do not take the course, so I can't get the official solution.@antkam – Jessepinkman56 May 12 at 4:08

A way to calculate the exact probability in such scenarios is to make a program play all the possible games for you. In this case you should be aware of the probability of each possible game and either play each game more than once depending on it's probability or count the result of a more probable scenario more times than that of an improbable one. Here is what I tried in this program:

combs = []
for n in range(0,100):
combs.append(2**n)
winsA = winsB = stalemates = 0
for i in range(201,301):
for j in range(i-100,201):
plB = i - j
for k in range(101,j+1):
for g in range(k-100,101):
plA = k - g
if plB == plA:
stalemates = stalemates + combs[j-k-1] * combs[g-1]
elif plB > plA:
winsB = winsB + combs[j-k-1] * combs[g-1]
else:
winsA = winsA + combs[j-k-1] * combs[g-1]
print("Probability of each scenario")
print("Stalemates:\t",stalemates/(stalemates+winsA+winsB))
print("Winner A:\t",winsA/(stalemates+winsA+winsB))
print("Winner B:\t",winsB/(stalemates+winsA+winsB))


This is it's output:

Probability of each scenario
Stalemates:  0.009947994216784273
Winner A:    0.4765110809002827
Winner B:    0.513540924882933


I am not entirely sure if it is correct though since the difference between $$0.513540924882933$$ and $$0.524$$ seems to big. Feel free to ask for any part of the code that seems to confuse you, and please let me know if you find the reason(s) why there is this difference between my result and your simulation result. Also I don't think you can highlight code here as in stackoverflow

• what's the meaning of 2^n – Jessepinkman56 May 12 at 4:00
• There are 2^n ways to reach the number n+1 with random integers smaller or equal to n+1. You can reach 2 with these 2 ways: 1,1 or 2. You can reach 3 with these 4 ways: 1,1,1 2,1 1,2 3. And so on. You can prove it with induction – michail vazaios May 12 at 14:13

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$$.