improving rolls of a die

radosr

Baruch MFE Faculty
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?
 
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.
 
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?
 
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.
 
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.
 
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.
 
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)
 
You're right, of course. Thanks. :)

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