Probability of dice sum just greater than 100

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

Solutions Collecting From Web of "Probability of dice sum just greater than 100"

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.

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.

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.

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.

/*  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}}$.