# What is the probability that the second player will win in this random game?

I'm working through Stanford's CS109 Problem Set 1 on Probability for Computer Scientists, and on #15 there's an extra credit question I can't explain:

1. 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 as $$x$$. The second player continues adding random numbers from the generator to $$S$$ until $$S > 200$$ and records her last random number as $$y$$. The player with the highest number wins, i.e. if $$y > x$$ the second player wins. Is this 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).

By creating a Python script to simulate 100,000 games, the probability of the second player winning hovers around $$0.532$$. Yet, I suspected it to be $$0.495$$ since each players' last number could be any number from $$1$$ to $$100$$ since $$S \leq 100$$ is met to allow them to keep generating numbers. The same goes for player two and $$S \leq 200$$. Since each number seems equally likely, I found:

$$P(y > x) = \frac{99 \cdot 100}{2} \cdot \frac{1}{100^2} = 0.495$$

But this is definitely not correct as the simulation shows. Where is the problem in my analysis? I made sure I used a uniform distribution for generating numbers in my simulation.

• What you ignored is that player 2 doesn't always start at 100. – Don Thousand May 22 at 3:43
• @DonThousand Yes, but doesn't player two still have the potential to generate any number. The worst case is if player one generates $100$ then $100$ again. Player two still has a chance to generate. – Andrew Li May 22 at 3:45
• @DonThousand I agree. But why does the starting condition for player two matter? They will always be able to generate a number no matter what. – Andrew Li May 22 at 3:52
• Lets consider the bound of 2, instead of 100. For player 1, the probability of the last number being 2 is 75% (if player 1 first picks 2, then that ends his turn, but if he picks 1, he has another chance to pick 2). For player 2, there is a 75% chance he starts at 2, and 25% at 3. For the case of player 2 starting at 2, the same calculations hold, but if he starts at 3, the probability of picking 2 last is 50%, not 75%. So, for player 2, the probability of the last number being 2 is $75\%\cdot75\%+25\%\cdot50\%=68.75\%$. – Don Thousand May 22 at 3:53
• @DonThousand Oh, that's right. I completely overlooked that. Also--the note about the last number being $2$--even if player 1 chooses a $2$ initially, they can still go again. Player 1 stops when $S > 2$ not $S \geq 2$. – Andrew Li May 22 at 3:56