3
$\begingroup$

Game called death row: 1st person rolls 1 to 100, second person rolls 1 to (1st person's roll), etc... the first person to roll a 1 loses.

$\underline{Example:}$

Player 1 rolls 1 to 100 and gets 27.

Player 2 rolls 1 to 27 and gets 2.

Player 1 rolls 1 to 2 and gets 1.

Player 1 loses.

Assuming that we do a coin throw to decide who rolls first, is this game fair? (i.e. are the chances of winning 50/50 for both players?)

$\underline{Context:}$

Players in World of Wacraft like to play this game to kill time. Although it is much more fun than the traditional roll 1 to 100 and whoever gets a bigger number wins, I was thinking if there was another reason people choose to play this game (maybe it's not fair but seems fair to the outsider).

$\endgroup$
3
$\begingroup$

Interesting game. Of course, if you start with a coin throw to see who rolls first, the game is completely fair. This is true for any game, no matter how biased -- if the game is "whoever goes first always wins", the coin throw turns it into a fair game. Hence I will analyze the game without the coin throw to see whom it favors.

Let's work backwards from small numbers to large ones, and set $x(n)$ to be the probability of the first player losing when rolling an $n$-sided die.

For $n=2$, we have $x(2)=\frac{1}{2}+\frac{1}{2}(1-x(2))$; half of the time the first player simply loses, while half of the time the game repeats with the roles reversed. We solve this to get $x(2)=\frac{2}{3}$.

For $n=3$, we have $x(3)=\frac{1}{3}+\frac{1}{3}(1-x(3))+\frac{1}{3}(1-x(2))$. One third of the time, the first player loses. One third of the time, the players reverse roles. And one third of the time, the players reverse roles but we go down to $n=2$. Fortunately, we solved for $x(2)$ already, so we can now solve for $x(3)=\frac{7}{12}$.

For $n=4$, we have $x(4)=\frac{1}{4}+\frac{1}{4}(1-x(2))+\frac{1}{4}(1-x(3))+\frac{1}{4}(1-x(4))$. The pattern is clear: we can set $x(1)=0$ for consistency, and we have $$x(n)=1-\frac{1}{n}\sum_{i=1}^nx(i)$$ We can add $\frac{1}{n}x(n)$ to both sides, then $$x(n)=\frac{n}{n+1}\left(1-\frac{1}{n}\sum_{i=1}^{n-1}x(i)\right)=\frac{1}{n+1}\left(n-\sum_{i=1}^{n-1}x(i)\right)$$

I don't have a closed form for the answer, but it does approach $\frac{1}{2}$ pretty quickly, though is always greater than $\frac{1}{2}$. For $n=100$ we have $x(100)\approx 0.50009901$ (computed in a spreadsheet). Hence, the game is almost fair, but it's still better to go second.

$\endgroup$
  • 1
    $\begingroup$ $x(n)$ converges to $\frac 12$ reasonably quickly, but the first player is always at a disadvantage. It falls below $0.501$ at $n=32$ and at $n=100$ has just fallen below $0.5001$ $\endgroup$ – Ross Millikan Oct 11 '16 at 2:50
  • 1
    $\begingroup$ I spoke too soon! OEIS was thrown off by the initial zero and I was too reliant on computation to not recognize, after some inspection, $$x(n) = \frac{1}{2} + \frac{1}{n(n+1)}, \quad n \ge 1.$$ I believe that we should have $x(1) = 1$ since the first player necessarily loses on the first throw of a $1$-sided die. $\endgroup$ – heropup Oct 11 '16 at 3:09
  • $\begingroup$ @heropup, you should perhaps write up the closed form as a separate answer. $\endgroup$ – vadim123 Oct 11 '16 at 16:58
1
$\begingroup$

It's quite clear that player 2 gets the crappier end of the percentages. However, it's also important to note that the total number of rolls by player 1 is always greater than or equal to that of player 2.

As the number of total trials increase, a difference in 1 between the two should become minimal so I would expect player 1 to have a slight advantage.

Hey but luckily we don't have to rely on my poor intuition. I just ran a million trials in Matlab. According to my program, player 1 has a 50.001% chance of winning. Seems pretty fair to me.

$\endgroup$
  • $\begingroup$ Does 'number of total trials' refer to 'n' in 'Player 1 rolls from 1 to n' ? $\endgroup$ – BCLC Oct 11 '16 at 3:24
  • 1
    $\begingroup$ No, the number of trials is the total number of times the dice has been rolled $\endgroup$ – Trevor Squires Oct 11 '16 at 3:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.