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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.