Intereting Posts

Understanding this proof that a polynomial is irreducible in $\mathbb{Q}$
Calculate:$y'$ for $y = x^{x^{x^{x^{x^{.^{.^{.^{\infty}}}}}}}}$ and $y = \sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+…\infty}}}}$
Example of topological spaces with continuous bijections that are not homotopy equivalent
Find The Last 3 digits of the number $2003^{2002^{2001}}$
Proving roots with Mean Value Theorem
How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))
Category of adjunctions inducing a particular monad
Proving the inequality $|a-b| \leq |a-c| + |c-b|$ for real $a,b,c$
Finding determinant of matrix without expanding
Book in Numerical analysis
Sum of greatest common divisors
First theorem in Topological vector spaces.
Why is $\phi:\mathbb{P}^n\rightarrow \mathbb{P}^m$ constant if dim $\phi(\mathbb{P}^n)<n$?
How to prove this limit composition theorem?
Solve the factorial equation $x! = c$

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

- Toss a fair die until the cumulative sum is a perfect square-Expected Value
- Why the set of outcomes generated by a fixed strategy of one player in Gale-Stewart game is a perfect set?
- Secretary problem - why is the optimal solution optimal?
- 100-Sided Dice “Blackjack” Game
- Name for a certain “product game”
- Optimal strategy for slice weighing game

- Expected size of subset forming convex polygon.
- A form of cumulative distribution
- Infinite expected value of a random variable
- If two coins are flipped and one gets head, what is the probability that both get head?
- Conditional and Total Variance
- a question related to two competing patterns in coin tossing
- Binary matrices and probability
- $X = E(Y | \sigma(X)) $ and $Y = E(X | \sigma(Y))$
- Gambling puzzle
- Density and expectation of the range of a sample of uniform random variables

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.

**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.

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.

/* 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(); return total; }

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

- Diagonal update of the inverse of $XDX^T$
- Number of elements in a finite $\sigma$-algebra
- Combination Problem Understanding
- Continued fraction for $\frac{1}{e-2}$
- One more question about mapping quaternionic matrices into real matrices
- CDF of a sum of independent random variables
- Proof of a Limit of a Function, given the Limits of the Multiplicative Inverses of the Function
- System of non-linear equations.
- Evaluate $\lim\limits_{n\to\infty}(1+x)(1+x^2)\cdots(1+x^{2n}),|x|<1$
- Rational solutions to $a+b+c=abc=6$
- How to do \mathbf in handwriting?
- Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?
- Show that among every consecutive 5 integers one is coprime to the others
- $\sqrt{2}\notin\mathbb{Q}$ but …
- can the emphasis on “smallest” in the monotone class theorem be ignored in applications?