2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think where you write "since $4\lt6$" you mean "since $4\le6$"? (Otherwise it should be "weakly increasing" instead of "strictly increasing".) $\endgroup$ – joriki Sep 2 '18 at 5:36
  • $\begingroup$ Please correct the question. The question should be understandable on its own, without the comments. $\endgroup$ – joriki Sep 2 '18 at 9:58
  • $\begingroup$ You could've just changed $4\lt6$ to $4\le6$. :-) $\endgroup$ – joriki Sep 2 '18 at 11:16
  • $\begingroup$ 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. $\endgroup$ – joriki Sep 2 '18 at 22:25
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.