Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 558
March 30th, 2020 at 8:40:42 PM permalink
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.
Itís all about making that GTA
ssho88
ssho88
Joined: Oct 16, 2011
  • Threads: 41
  • Posts: 427
March 30th, 2020 at 9:46:20 PM permalink
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 !
Last edited by: ssho88 on Mar 31, 2020
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 30
  • Posts: 1987
March 31st, 2020 at 3:59:47 AM permalink
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.
ssho88
ssho88
Joined: Oct 16, 2011
  • Threads: 41
  • Posts: 427
March 31st, 2020 at 4:28:35 AM permalink
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 !
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 558
March 31st, 2020 at 6:52:29 AM permalink
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
Itís all about making that GTA
ssho88
ssho88
Joined: Oct 16, 2011
  • Threads: 41
  • Posts: 427
March 31st, 2020 at 7:20:53 AM permalink
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.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 558
March 31st, 2020 at 7:25:14 AM permalink
Assumptions look good
Itís all about making that GTA
ssho88
ssho88
Joined: Oct 16, 2011
  • Threads: 41
  • Posts: 427
March 31st, 2020 at 7:32:59 AM permalink
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 ?
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 558
March 31st, 2020 at 9:51:20 AM permalink
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
Itís all about making that GTA
ChesterDog
ChesterDog
Joined: Jul 26, 2010
  • Threads: 6
  • Posts: 851
March 31st, 2020 at 6:53:25 PM permalink
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.

  • Jump to: