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