# 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?

Thanks.

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

-
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. – chroma Nov 30 '10 at 3:09
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. – AnonymousCoward Nov 30 '10 at 3:19
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. – Tom Dec 1 '10 at 2:05
@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. – T.. Dec 1 '10 at 6:15

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.

-
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. – Henry Jun 8 '12 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.

-
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)". – T.. Dec 1 '10 at 6:23
@BryonSchmuland (I realize that this is an old post) Is there an intuitive explanation for that formula for $\mu$? – NotNotLogical May 17 '14 at 2:04
@NotNotLogical I don't know about intuition, but this is what comes out of the Feller-Erdos-Pollard renewal theorem. – Byron Schmuland May 17 '14 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.

EDIT:

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.

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

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

http://math.stackexchange.com/a/799655/85343

http://math.stackexchange.com/questions/12433/probability-of-dice-sum-just-greater-than-100
*/
#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();
cout<<setprecision(8)<<(total/ITER)<<endl;

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();

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