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.

  • $\begingroup$ What you ignored is that player 2 doesn't always start at 100. $\endgroup$ – Don Thousand May 22 at 3:43
  • $\begingroup$ @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. $\endgroup$ – Andrew Li May 22 at 3:45
  • $\begingroup$ @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. $\endgroup$ – Andrew Li May 22 at 3:52
  • 3
    $\begingroup$ 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\%$. $\endgroup$ – Don Thousand May 22 at 3:53
  • $\begingroup$ @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$. $\endgroup$ – Andrew Li May 22 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.