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

Question

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.

Answer 1

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.

Answer 2

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.

See also Probability of winning dice game and Interview Question on Probability: A and B toss a dice with 1 to n faces in an alternative way.

Answer 3

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}}$