Can someone please guide me to a way by which I can solve the following problem. There is a die and 2 players. Rolling stops as soon as some exceeds 100(not including 100 itself). Hence you have the following choices: 101, 102, 103, 104, 105, 106. Which should I choose given first choice. I'm thinking Markov chains, but is there a simpler way?


EDIT: I wrote dice instead of die. There is just one die being rolled

  • 4
    $\begingroup$ I'm guessing you want to know the probability they sum > 100 in N rolls as a function of N. (As you never expanded on what the actual problem was.) EDIT: Or rather, you want to know which case {101,..,106} is most probable. $\endgroup$
    – chroma
    Nov 30, 2010 at 3:09
  • $\begingroup$ Could you perhaps count the number of ways to add 1,2,3,4,5,6 to get each choice? This is an easy generating function problem. This is perhaps an oversimplistic answer. edit: if this is not right I would be interested to know why, Im not particularly good at probability. $\endgroup$ Nov 30, 2010 at 3:19
  • $\begingroup$ Please make the question more clear. As @chroma stated, you don't really ask a clear question. Are you interested in which of {101, ..., 106} has the highest probability? That's what I'm assuming. $\endgroup$
    – Tom
    Dec 1, 2010 at 2:05
  • $\begingroup$ @Tom: it is a Markov chain with initial state 0 and terminal states 101,102,103,104,105,106. There is a probability distribution on the six terminal states and the question is which terminal state has the highest probability under this distribution. $\endgroup$
    – T..
    Dec 1, 2010 at 6:15

6 Answers 6


My attempt: a combination of my comment and Shai's comment.

A partition means a partition of n using only 1,2,3,4,5,6.

Number of ways to get to 101: Number of partitions of 101.

Number of ways to get to 102: partitions of 96 + partitions of 97... + partitions of 100. Since we can have 96+6, 97+5, ...100+2.


Number of ways to get to 106: Partitions of 100. Since we can get to 106 only by adding to 100 then rolling 6.

A partition of n will be the nth coefficient x in $\prod_{k=0}^6 \frac{1}{1-x^k}$ using the geometric series. But an easier observation is that $a_n = a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}+a_{n-6}$. Using this

Number of ways to get to 101 is $a_{101}=a_{100}+a_{99}+a_{98}+a_{97}+a_{96}+a_{95}$ Number of ways to get to 102 is $a_{100}+a_{99}+a_{98}+a_{97}+a_{96}$


Number of ways to get to 106 is $a_{100}$

Since $a_n > 0$ we see that 101 will occur the most frequently.

  • $\begingroup$ I don't see quite this: I would have thought you wanted compositions rather than partitions, but even then the compositions with different numbers of parts have different probabilities. I think you want the probabilities of hitting 95, 96, 97, 98, 99 and 100 followed by getting the suitable result to get a particular value over 100. $\endgroup$
    – Henry
    Jun 8, 2012 at 21:40

It's a nice problem. The chance of hitting $101$ first is surprisingly large. Let $a(x)$ be the chance of hitting $101$ first, starting at $x$.

We solve recursively by setting $a(106)=a(105)=a(104)=a(103)=a(102)=0$ and $a(101)=1$. Then, for $x$ from $100$ to $0$, put $a(x)={1\over 6}\sum_{j=1}^6 a(x+j)$. By the renewal theorem, $a(x)$ converges to $1/\mu$, where $\mu=(1+2+3+4+5+6)/6=7/2$. The value $a(0)$ is very close to this limit.

In fact, the whole hitting distribution is approximately $[6/21,5/21,4/21,3/21,2/21,1/21]$.

Added: Let $a^\prime(x)$ be the chance of hitting $102$ first, starting at $x$. Then $a^\prime(x)$ satisfies the same recurrence as $a(x)$ for $x\leq 100$, but with different boundary conditions $a^\prime(106)=a^\prime(105)=a^\prime(104)=a^\prime(103)=a^\prime(101)=0$ and $a^\prime(102)=1$. Therefore
$$a^\prime(x)=a(x-1)-a(100)a(x)$$ and $$a^\prime(0)\approx {1\over \mu}-{1\over 6}{1\over \mu}={5\over 21}. $$ The rest of the hitting distribution can be analyzed in a similar way.

  • 1
    $\begingroup$ The 6:5:4:3:2:1 pattern can be seen by looking at orbits of the (probability-conserving) transformation "if the final dice toss is K and leads to terminal state higher than 101, replace K by (K-1)". $\endgroup$
    – T..
    Dec 1, 2010 at 6:23
  • $\begingroup$ @BryonSchmuland (I realize that this is an old post) Is there an intuitive explanation for that formula for $\mu$? $\endgroup$
    – user142299
    May 17, 2014 at 2:04
  • $\begingroup$ @NotNotLogical I don't know about intuition, but this is what comes out of the Feller-Erdos-Pollard renewal theorem. $\endgroup$
    – user940
    May 17, 2014 at 21:52

Maybe I didn't understand the question, but it seems clear, considering $\lbrace 95 + j + k:j = 0, \ldots ,5;k = 1, \ldots 6 \rbrace$, that you should choose $101$. Here, $95+j$ corresponds to the sum just before exceeding $100$ for the first time, and $95+j+k$ to the sum when exceeding $100$ for the first time.


Let me elaborate a little on my argument above. First, you can easily show by induction on $j$ that if the current sum is $100 - j$, $j=0,\ldots,4$, then there is no strictly better choice than $101$ (the base case $j=0$ is trivial). Then consider the case where the current sum is $95$, to conclude that $101$ is strictly the best choice.

  • $\begingroup$ Why 95? Other than because its six less than 101. $\endgroup$ Nov 30, 2010 at 3:26
  • $\begingroup$ Since you can exceed $100$ in a single roll, only if the current sum is between $95$ and $100$. $\endgroup$
    – Shai Covo
    Nov 30, 2010 at 3:33
  • $\begingroup$ I think I see you reasoning. I misread where you said 95+j is the sum before exceeding 100 $\endgroup$ Nov 30, 2010 at 3:37
  • 2
    $\begingroup$ @Shai. Your answer is correct only if the total after the 2nd last roll is equally likely to be 95,96,...,100. $\endgroup$
    – TCL
    Nov 30, 2010 at 3:56
  • $\begingroup$ @TCL: I think my reasoning is fine. I assume nothing on the total after the 2nd last roll. $\endgroup$
    – Shai Covo
    Nov 30, 2010 at 4:21

101 is the most probable stop state.

The operation "replace the final toss of the dice by the one that gives a sum of 101" is a probability-conserving transformation on the set of possible games. It does not cover the whole set (i.e. the image of the transformation is a subset) of possible games stopping at 101, such as the ones with a transition from 95 to 101 by a roll of 6. This shows that all the terminal states higher than 101 have a smaller probability than that of finishing at 101.


I see it's a very old question, but let me add my two cents. It's only an approximate solution and at times it involves some guesswork, but it turns out to be quite good. (Also, it doesn't need a computer and the math is pretty elementary.)

Let $a_n$ denote the probability of rolling total of $n$ in any number of rolls (now without the "stop when > 100" condition). After some thinking, we get a recurrence relation for these: $$ a_n = (a_{n-1} + a_{n-2} + \ldots + a_{n-6})/6,\quad a_{-5} = a_{-4} = \ldots = a_{-1} = 0, a_0 = 1. $$

This is a linear recurrence, which can be solved "easily" by forming the characteristic equation $6\lambda^6 - \lambda^5 - \lambda^4 - \lambda^3 - \lambda^2 - \lambda - 1 = 0$. If we denote its roots by $l_1$ to $l_6$, the explicit formula for the recurrence has the form of $$ a_n = \sum_{0 < i < 7} C_i l_i^n. $$

(The $C$'s are obtained from the boundary conditions.) Since the $a_n$'s represent probabilities, they should be in the interval of $<0;1>$. From this it seems to be reasonable that $|l_i| \leq 1$. If there were any that don't satisfy this condition, the $a_n$'s would be unbounded (since the powers, and even differences of two of them with different bases, would be unbounded).

Now we see it has a root of $\lambda = 1$. So, $a_n$'s eventually converge to $C_1$ (which we don't know, but we don't care), since all other $C_i l_i^n$ converge to 0 (because of the $|l_i|<1$ condition).

So probability of getting 101 is $a_{101}$. Getting 102 has a probability of $a_{102} - a_{101}/6$, since we can't obtain it by rolling 101+1. Similarly, rolling 103 has a probability of $a_{103} - (a_{102} + a_{101})/6$ (no 101+2 nor 102+1), etc. Now we guess that the $a_n$'s converge so well that $a_{101}$ through $a_{106}$ are essentially equal. That gives the 6:5:4:3:2:1 ratio, and furthermore, the (correct) limit of $a_n$'s, 2/7.

I know this is somewhat estimatory (some may say, "physicist's") approach, but even with that, I hope it could have some value.

/* diceMoreThan100.cc  Felix Marin 17-may-2014


#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
using namespace std;
const unsigned long long ITER = 100000000ULL; // One Hundred Million.
double randSum();

inline unsigned char rand16()
 return static_cast<unsigned char>(1 + rand()%6);

int main()
 double total = 0;

 srand(size_t(time((time_t *)0)));
 for ( unsigned long long n = 0; n < ITER ; ++n ) total += randSum();

 return 0;

double randSum()
 static const unsigned char oneHundredOne = static_cast<unsigned char>(101);
 static unsigned char total;

 for ( total = 0; total < oneHundredOne ;) total += rand16();
 return total;

Result $\displaystyle{= \color{#88f}{102.6667}}$.

  • $\begingroup$ I think you could expand on this to show why a computer simulation is accurate: because the distribution is roughly normal. Monte carlo style approaches to expectation like this tend to break down if you have a rare chance of a significantly large or small value. It is because all the probabilities and states are roughly equal that this works. $\endgroup$
    – DanielV
    May 20, 2014 at 21:39

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.