• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

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