Dice Problem #1000

Let’s say there’s a game where you roll a six-sided die as long as the values keep increasing. So if you roll 2, 5, 1 the game ends at 3 rolls. If your first roll is a 6 the game ends at 1 roll.

Now, imagine the same game played with a die that has an infinite number of sides. What is the expected number of rolls to end the game?

Closed-form solutions only please.

My assumptions for 6 sided die :-
1) If 2,5,5, game ends, total 3 rolls
2) If 4 ,4, game ends, total 2 rolls
3) If 2, 4 ,5, 6, game ends, total 4 rolls
4)If 2 ,3, 5, 2, game ends, total 4 rolls

For a six sided die game, average rolls = 2.1614 ?

For N sided die, average rolls = 1 + 1/N * ∑[(N+1)/N]^(N-n), n = 2 to N

Simplify further, average rolls =[(N+1)/N]^{(N – 1)}

I suspect average rolls = e = Euler's number, when N = infinity !

Quote: ssho88

...I suspect average rolls = e = Euler's number, when N = infinity !

I tend to agree using this logic.

Rather than assuming the dice is N sided assume we are picking random numbers between 0 and 1 (technically depending on the number of faces the choices would be 1/N 2/N 3/N etc, but as N tends to infinity it's just every possible number).

After n numbers have been rolled the chances they are in ascending order, and you can roll again, is 1/n! Thus to get the next roll the chances are 1/n! (I might be 1 out, but who cares, this is proof by induction).

You'll always have the first roll and last roll, so this corresponds to 1 + 1/1!.

The chances of having an extra/third roll is that the second number is bigger than the first number, the chances of that are 1/2!.

Hence the total IS 1 + 1/1! + 1/2! etc = e.

Quote: charliepatrick

I tend to agree using this logic.

Rather than assuming the dice is N sided assume we are picking random numbers between 0 and 1 (technically depending on the number of faces the choices would be 1/N 2/N 3/N etc, but as N tends to infinity it's just every possible number).

After n numbers have been rolled the chances they are in ascending order, and you can roll again, is 1/n! Thus to get the next roll the chances are 1/n! (I might be 1 out, but who cares, this is proof by induction).

You'll always have the first roll and last roll, so this corresponds to 1 + 1/1!.

The chances of having an extra/third roll is that the second number is bigger than the first number, the chances of that are 1/2!.

Hence the total IS 1 + 1/1! + 1/2! etc = e.

I am using Markov Chain to find the average rolls, from there, part of the formula can be simply with Geometric series formula, then finally it is Euler's number when N = infinity !

Quote: ssho88

My assumptions for 6 sided die :-
1) If 2,5,5, game ends, total 3 rolls
2) If 4 ,4, game ends, total 2 rolls
3) If 2, 4 ,5, 6, game ends, total 4 rolls
4)If 2 ,3, 5, 2, game ends, total 4 rolls

For a six sided die game, average rolls = 2.1614 ?

For N sided die, average rolls = 1 + 1/N * ∑[(N+1)/N]^(N-n), n = 2 to N

Simplify further, average rolls =[(N+1)/N]^{(N – 1)}

I suspect average rolls = e = Euler's number, when N = infinity !

Those are incorrect answers for a six-sided die and for an infinite-sided die

Quote: Ace2

Quote: ssho88

My assumptions for 6 sided die :-
1) If 2,5,5, game ends, total 3 rolls
2) If 4 ,4, game ends, total 2 rolls
3) If 2, 4 ,5, 6, game ends, total 4 rolls
4)If 2 ,3, 5, 2, game ends, total 4 rolls

For a six sided die game, average rolls = 2.1614 ?

For N sided die, average rolls = 1 + 1/N * ∑[(N+1)/N]^(N-n), n = 2 to N

Simplify further, average rolls =[(N+1)/N]^{(N – 1)}

I suspect average rolls = e = Euler's number, when N = infinity !

Those are incorrect answers for a six-sided die and for an infinite-sided die

My assumptions for 6 sided die correct ?

My both algebraic calculations and simulations give same answer.

Assumptions look good

Then I can't find any error in my calculations. My simulations give same answer as well.

six sided die, rolls = 2.1614

Please double check, Assumptions 3 correct ?

My apologies, I misstated the problem.

Only increasing rolls are counted. So 2455, 1342, and 236 are all counted as 3 rolls.

It’s not difficult to see what the expected value converges to as the number of sides goes up. But the proof of the answer is clever in my opinion.

ssho88, you are correct for the six-sided die EV for the originally stated problem (when all rolls are counted). Sorry about that

Quote: Ace2

My apologies, I misstated the problem.

Only increasing rolls are counted. So 2455, 1342, and 236 are all counted as 3 rolls.

It’s not difficult to see what the expected value converges to as the number of sides goes up. But the proof of the answer is clever in my opinion.

ssho88, you are correct for the six-sided die EV for the originally stated problem (when all rolls are counted). Sorry about that

Thanks for the clarification. I get 1.52163 for a 6-sided die. By varying the number of sides, I see that for an infinite-sided die, the answer would be near 1.718. (Like sscho88, I first thought the answer would have been infinity.)

Please show us your technique to get the exact answer.

Quote: ChesterDog

Thanks for the clarification. I get 1.52163 for a 6-sided die. By varying the number of sides, I see that for an infinite-sided die, the answer would be near 1.718. (Like sscho88, I first thought the answer would have been infinity.)

Please show us your technique to get the exact answer.

Both of your answers are correct, with the EV for the infinite-sided die being (e -1) = 1.718

I’ll post the proof tomorrow, just in case someone else wants to take a a stab at it.

Quote: Ace2

My apologies, I misstated the problem.

Only increasing rolls are counted. So 2455, 1342, and 236 are all counted as 3 rolls.

It’s not difficult to see what the expected value converges to as the number of sides goes up. But the proof of the answer is clever in my opinion.

ssho88, you are correct for the six-sided die EV for the originally stated problem (when all rolls are counted). Sorry about that

With new rules, I got 1.521626372 for 6 sided die(by markov chain method and confirmed with monte carlo simulation)

I am trying to find a formula for N sided die.

Quote: charliepatrick

I tend to agree using this logic.

Rather than assuming the dice is N sided assume we are picking random numbers between 0 and 1 (technically depending on the number of faces the choices would be 1/N 2/N 3/N etc, but as N tends to infinity it's just every possible number).

After n numbers have been rolled the chances they are in ascending order, and you can roll again, is 1/n! Thus to get the next roll the chances are 1/n! (I might be 1 out, but who cares, this is proof by induction).

You'll always have the first roll and last roll, so this corresponds to 1 + 1/1!.

The chances of having an extra/third roll is that the second number is bigger than the first number, the chances of that are 1/2!.

Hence the total IS 1 + 1/1! + 1/2! etc = e.

Obviously this would give e-1 if the "last roll" (see underlined parts) was excluded.

Here are the calculations :-

Let En is the rolls required if first roll is n, where n = 1 to 6.

Probability of each side = p = 1/6

E1 = p( 1 + E1) +p( 1 + E2) +p( 1 + E3) +p( 1 + E4) +p( 1 + E5) +p( 1 + E6)

Since Only increasing rolls are counted, E6 = 0 and all terms with equal or lower point will be ignored,

E1 = 0 +p( 1 + E2) +p( 1 + E3) +p( 1 + E4) +p( 1 + E5) +p( 1 + 0) = 5*p + p( E2 + E3 + E4 + E5) ........Eq1

With same logic,

E2 = 4*p + p( E3 + E4 + E5) ........Eq2

E3 = 3*p + p( E4 + E5) ........Eq3

E4 = 2*p + p(E5) ........Eq4

E5 = p ........Eq5

E6 = 0 ........Eq6

Therefore,

E5 = 1/6

E4 = 2/6 + 1/6*1/6 = 13/36

E3 = 3/6 + 1/6*1/6 + 1/6*13/36 = 127/216

E2 = 4/6 + 1/6*1/6 + 1/6*13/36 + 1/6*127/216 = 1105/1296

E1 = 5/6 + 1/6*1/6 + 1/6*13/36 + 1/6*127/216 + 1/6*1105/1296 = 9031/7776


So total average rolls = 1 + p( E1 + E2 + E3 + E4 +E5 + E6) = 1 + 1/6 * ( 9031/7776 + 1105/1296 + 127/216 + 13/36 + 1/6 + 0) = 1.521626

Question : Possible to form a general formula for N sided die ?

I think I have a general solution:
Let E(k) be the expected number of rolls needed before making a "bad" roll on an n-sided die where the most recent roll was k
Note that this includes the one "bad" roll that ends the run

Proof by induction that E(n-k) = (1 + 1/n)^k:
E(n-0) = 1 = (1 + 1/n)^0
Let E(n-k) = (1 + 1/n)^k
E(n-(k+1)) = 1 + 1/n (1 + (1 + 1/n) + (1 + 1/n)^2 + ... + (1 + 1/n)^k)
= 1 + 1/n ((1 + 1/n)^(k+1) - 1) / ((1 + 1/n) - 1)
= 1 + (1 + 1/n)^(k+1) - 1)
= (1 + 1/n)^(k+1)

Since the desired solution does not count the "bad" roll, for an N-sided die, E(0) = (1 + 1/N)^N - 1

Bonus Math: proof that, as N approaches infinity, E(N) approaches e - 1:
LIM(x->+INF) {(1 + 1/x)^x - 1}
= LIM(x->+INF) {e^(x ln (1 + 1/x))} - 1
= e^(LIM(x->+INF) {x ln (1 + 1/x)} - 1, since e^x is strictly increasing
= e^(LIM(x->+INF) {ln (1 + 1/x) / (1/x)} - 1
L'Hopital's rule:
d/dx (ln (1 + 1/x)) = 1 / (1 + 1/x) * (-1/x^2)
d/dx (1/x) = -1/x^2
LIM(x->+INF) {ln (1 + 1/x) / (1/x)} = LIM(x->+INF) (1 / (1 + 1/x)) = 1
Therefore LIM(x->+INF) {(1 + 1/x)^x - 1} = e^1 - 1 = e - 1

Quote: ThatDonGuy

Since the desired solution does not count the "bad" roll, for an N-sided die, E(0) = (1 + 1/N)^N - 1

Nice proof and closed-form solution. I owe you a beer

And I’ll assume your proof for n—> infinity is also correct. Proofs aren’t my strong point...I just accept that (1 + 1/n)^n = e as n goes to infinity. Sort of like I accept the Pythagorean theorem