Rolling Higher

Relevant wiki: Stars and Bars

If $X$ is the number of rolls made with an $n$ -sided dice, then $\mathbb{P}[X > N]$ is the probability that the first $N$ rolls come in ascending order. A standard stars-and-bars argument tells us that this probability is $\mathbb{P}[X > N] \; = \; \binom{N+n-1}{N} \times n^{-N}$ and hence $\mathbb{E}[X] \; = \; \sum_{N =1}^\infty \mathbb{P}[X \ge N] \; = \; \sum_{N=0}^\infty \mathbb{P}[X >N] \; = \; \sum_{N=0}^\infty \binom{N+n-1}{N} n^{-N} \; = \; \big(1 - n^{-1}\big)^{-n} \; = \; \left(\tfrac{n}{n-1}\right)^n$ With $n=6$ , this makes the answer $\boxed{\big(\tfrac65\big)^6 = 2.985984}$ . The limit as $n \to \infty$ of the expected value is $e$ .

Relevant wiki: Law of Iterated Expectation

Let $X$ be the number of rolls until a lesser number is rolled. Now let the following conditional expected values be defined:

$a = \text{E}[X \mid 1] =$ The expected value of the number of rolls given that the most recent roll was 1.

$b = \text{E}[X \mid 2] =$ The expected value of the number of rolls given that the most recent roll was 2.

$c = \text{E}[X \mid 3] =$ The expected value of the number of rolls given that the most recent roll was 3.

$d = \text{E}[X \mid 4] =$ The expected value of the number of rolls given that the most recent roll was 4.

$e = \text{E}[X \mid 5] =$ The expected value of the number of rolls given that the most recent roll was 5.

$f = \text{E}[X \mid 6] =$ The expected value of the number of rolls given that the most recent roll was 6.

It's easier to solve for $f$ first and then work your way backwards. Due to linearity of expectation:

$\begin{aligned} f &= \frac{1}{6}(1+f)+\frac{5}{6}(1) \\ f &= \frac{6}{5} \\ \\ e &= \frac{1}{6}(1+f)+\frac{1}{6}(1+e)+\frac{4}{6}(1) \\ e &= \left(\frac{6}{5}\right)^2 \\ \\ d &= \frac{1}{6}(1+f)+\frac{1}{6}(1+e)+\frac{1}{6}(1+d)+\frac{3}{6}(1) \\ d &= \left(\frac{6}{5}\right)^3 \end{aligned}$

One might notice a pattern at this point. It just so happens that this pattern holds, and $a=\left(\frac{6}{5}\right)^6.$ Then note that $\text{E}[X]= \text{E}[X\mid 1].$ Then the expected number of rolls is $\left(\frac{6}{5}\right)^6\approx \boxed{2.986}.$

Relevant wiki: Monte-Carlo Simulation

Cheater's ( Monte Carlo ) solution:

This takes me about 30 seconds to run with python 2.7 and less than 2 seconds with pypy. It will usually get the correct answer. Running it 3 times gave me the same number for the first three decimal places which is all that is necessary to answer the question.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import random

random.seed()

def simulate():
    max = 0
    count = 0
    while True:
        roll = random.randint(1, 6)
        count += 1
        if roll < max:
            return count
        max = roll

n = 10000000

print sum(simulate() for x in xrange(0,n))/float(n)