# Expected value of dice rolls to get a non decreasing sequence of roll values.

What is the expected number of rolls to get a non decreasing sequence of dice roll values ? Suppose one rolls 1-2-5-6-4, then after rolling 6 he will stop, since 4 > 6.

• I think where you write "since $4\lt6$" you mean "since $4\le6$"? (Otherwise it should be "weakly increasing" instead of "strictly increasing".) – joriki Sep 2 '18 at 5:36
• Please correct the question. The question should be understandable on its own, without the comments. – joriki Sep 2 '18 at 9:58
• You could've just changed $4\lt6$ to $4\le6$. :-) – joriki Sep 2 '18 at 11:16
• Now you've changed "strictly increasing" to "non-decreasing". That turns this into a whole new question. That's a very bad idea, since there are already three answers to the original question. Please reinstate the original question; if you want to ask the same question about non-decreasing sequences, please ask a new, separate question. – joriki Sep 2 '18 at 22:25

Ross has already shown that the expected sum is simply $n$.

For the expected number of rolls, note that $\binom nk$ out of the $n^k$ possible results of $k$ rolls are strictly increasing sequences. Thus the expected value of the number $K$ of rolls including the last, non-increasing roll is

$$\mathsf E[K]=\sum_{k=0}^n\mathsf P(K\gt k)=\sum_{k=0}^n\binom nk\left(\frac1n\right)^k=\left(1+\frac1n\right)^n\to\mathrm e\quad\text{as n\to\infty}\;.$$

I'm not sure whether you wanted to count the last roll; if not, you'd obviously have to subtract $1$ from that.

Start from the top. If you roll a $6$ the expected sum is $6$ because you have to stop. If you roll a $5$ the expected sum is $5+\frac 16\cdot 6$ because you have $\frac 16$ chance to roll a $6$. If you roll a $4$ the expected sum is $4 + \frac 16\cdot 6 + \frac 16\cdot 6$ because you have $\frac 16$ chance to roll each of $5$ or $6$. You should be able to see the pattern-the expected value is $6$

For $n$ sided dice, the pseudocode for the sum would be
return n

The same approach works for number of rolls. If you roll a $6$ there will be just $1$. If you roll a $5$ the expected number is $\frac 76$. Keep going down the chain, then average them all for the first roll.

• If you roll a 4, why is the expected sum 4+(1/6)⋅6 [why is this 6?] +(1/6) ⋅6? – Robinson Crusoe Sep 4 '18 at 12:31
• @BibhasRanjanDas: Because the expected addition for rolling a $5$ is $6$ as I just calculated. – Ross Millikan Sep 4 '18 at 13:58

Let $X_1,X_2,....X_m,...$ be the dice rolls for an $n$-sided dice.

P(Rolls > $m$) = $\sum_{i_1 < i_2 < i_3 ... < i_{m}} \prod_{j=1}^{m} P(X_j = i_{j})$ = ${n \choose m} \frac{1}{n^{m}}$