Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

4 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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
add comment

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]$.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
2  
@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
show 3 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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