improving rolls of a die

[radosr]

Two players alternately roll an n-sided fair die. The player who fails to improve upon the previous roll loses. What is the probability that the first player wins?

 

[TATW]

50%, she either wins or not.

 

[amanda.jayne]

(\frac{\sum_{i=1}^n i}{n^2})

 

[Brad Warren]

(\frac{\sum_{i=1}^n i}{n^2})

That formula works for n=2. But the game can go on more than 2 rolls. This one works for n <= 6:

(\frac{79n^4+10n^3+5n^2+50n-24}{120n^4})

but I don't see a pattern for the general solution.

 

[Byron]

We need to find Pn. If the first player rolls k on the first die, the second player's probability of winning becomes Pn-k.....

Pn = (1/n) { (1 - Pn-1) + (1 - Pn-2) + (1 - Pn-3)..... }

That formula works for n=2. But the game can go on more than 2 rolls. This one works for n <= 6:

(\frac{79n^4+10n^3+5n^2+50n-24}{120n^4})

but I don't see a pattern for the general solution.

 

[amanda.jayne]

The player who fails to improve upon the previous roll loses.

The way I read this, there can only be one round - a tie by the second player results in a loss as does every roll that is lower. The only alternative is when player 2 outright wins - binary event. Unless I'm misinterpreting?

 

[ferdowsi]

I'm not sure it can be reduced, but I think it is:
sum of p(i)-p(i+1), where i is an odd number <= to n, and p(i) = nCi / n^i.

p(i) represents the probability that there have been i successful rolls.

 

[aaronhotchner]

The way I read this, there can only be one round - a tie by the second player results in a loss as does every roll that is lower. The only alternative is when player 2 outright wins - binary event. Unless I'm misinterpreting?

I think you are reading it wrong. My manual solution for n = 3 matches Brad Warren's formula (19/27), and it has 6 possible scenarios:

Player 1 rolls a 3. Player 2 cannot beat a 3, so player 1 wins.
Player 1 rolls a 2. Player 2 can roll a 1 or 2 and lose, or roll a 3 to win, since player 1 cannot beat a 3.
Player 1 rolls a 1. Player 2 loses if he rolls a 1, and wins if he rolls a 3. If player 2 rolls a 2, player 1 rolls again. Player 1 will lose on 1 or 2, and will win on 3.

The same reasoning can obviously be expanded for any n, but I haven't modeled it with any generality. Theoretically there can be n "rounds" to a game, which would only occur if player 1 rolls 1, followed by player 2 rolling 2, then player 1 rolling 3, and so on.

 

[pruse]

The number of increasing sequences of elements of (\{1, ..., n\}) of length (k) and ending in (m) is (\binom{m-1}{k-1}) (pick the (k-1) elements less than (m) from (\{1, ..., m-1\}) and there's a unique way to order them). There are (m) ways in which the following roll won't improve on the last one. The probability of this scenario is then (\frac{1}{n^{k+1}}\binom{m-1}{k-1}m=\frac{k}{n^{k+1}}\binom{m}{k}).

The desired probability is then (\sum_{m=1}^n m\sum_{k \text{ odd}} \frac{1}{n^{k+1}}\binom{m-1}{k-1}).

To compute the inner sum, we write it as (\frac{1}{n^2}\sum_{k \text{ odd}} \frac{1}{n^{k-1}}\binom{m-1}{k-1}=\frac{1}{2n^2}\left[\large(1+\frac{1}{n}\right)^{m-1}+\large(1-\frac{1}{n}\right)^{m-1}\right]).

The probability then becomes

(\frac{1}{2n^2}\sum_{m=1}^n\left[m\large(1+\frac{1}{n}\right)^{m-1}+m\large(1-\frac{1}{n}\right)^{m-1}\right]).

To compute the latter two sums, note that they are both of the form (\sum_{m=1}^n mx^{m-1}), which is the derivative of (\sum_{m=1}^n x^m = \frac{x^{n+1}-x}{x-1}).

Edit: Changed the sign and included the 2, as per Brad's correction.

 

[Brad Warren]

The number of increasing sequences of elements of (\{1, ..., n\}) of length (k) and ending in (m) is (\binom{m-1}{k-1}) (pick the (k-1) elements less than (m) from (\{1, ..., m-1\}) and there's a unique way to order them). There are (m) ways in which the following roll won't improve on the last one. The probability of this scenario is then (\frac{1}{n^{k+1}}\binom{m-1}{k-1}m=\frac{k}{n^{k+1}}\binom{m}{k}).

The desired probability is then (\sum_{m=1}^n m\sum_{k \text{ odd}} \frac{1}{n^{k+1}}\binom{m-1}{k-1}).

To compute the inner sum, we write it as (\frac{1}{n^2}\sum_{k \text{ odd}} \frac{1}{n^{k-1}}\binom{m-1}{k-1}=\frac{1}{n^2}\left[\large(1+\frac{1}{n}\right)^{m-1}-\large(1-\frac{1}{n}\right)^{m-1}\right]).

The probability then becomes

(\frac{1}{n^2}\sum_{m=1}^n\left[m\large(1+\frac{1}{n}\right)^{m-1}-m\large(1-\frac{1}{n}\right)^{m-1}\right]).

To compute the latter two sums, note that they are both of the form (\sum_{m=1}^n mx^{m-1}), which is the derivative of (\sum_{m=1}^n x^m = \frac{x^{n+1}-x}{x-1}).

I like your solution. But to get the odd k terms (for Player 1 winning), you should actually add the binomial powers, and then we need to divide by a factor of 2. The probability should be,

(\frac{1}{2n^2}\sum_{m=1}^{n}{\left[m\large(1+\frac{1}{n}\right)^{m-1}+m\large(1-\frac{1}{n}\right)^{m-1}\right]}=1-\large(1-\frac{1}{n}\right)^n)

 

[pruse]

You're right, of course. Thanks.

Now, given how simple the final formula is, there has got to be a prettier solution...