12
$\begingroup$

I roll a pair of fair dice $n$ times, and calculate the sum of all $2n$ faces which come up:

  • Suppose each roll of each die is independent of other rolls.
  • How many rolls are sufficient to ensure, with probability $99\%$, that the sum is greater than $100?$.

I've calculated that the expected value and variance of sum are $\mathbb{E}(X) = 7n\text{ and } \mathrm{Var}(X)=\frac{35}{6},$ where $X$ represents the random variable of sum of the $2n$ faces.

I think I need to find a lower bound on $\operatorname{Pr}(X > 100)$. I've attempted applying Markov's inequality: $\operatorname{Pr}(X \geq 100)\leq \frac{\mathbb{E}(X)}{100}$, which isn't anywhere near what I want. Any tips $?$.

$\endgroup$
7
  • $\begingroup$ You don't need mean and variance. Just go directly for the inverse survival function, or the 99-th percentile. You're summing independent random variables. As you sum more of them, the resulting random variable changes. At what point does the 99th percentile of the summed random variable cross 100 is what you're after. $\endgroup$ Commented May 11 at 23:01
  • 8
    $\begingroup$ Also, rolling a pair of die $n$ times is a strange way to frame it since its the same as rolling one die $2n$ times. $\endgroup$ Commented May 11 at 23:02
  • 2
    $\begingroup$ Try invoking the central limit theorem $\endgroup$
    – Masd
    Commented May 11 at 23:49
  • 4
    $\begingroup$ @RohitPandey: Aside from forcing an even number of dice, yes. $\endgroup$
    – Brian Tung
    Commented May 12 at 6:28
  • 1
    $\begingroup$ If we roll 1 die (not 2 dice like in this question) 35 times, the probability to obtain a sum greater than 100 is very close to 99% ; Not easy to determine if it is 98.9% or 99.1%. But good news, the question stipulates that the number of rolls is an even number. So 36 rolls, or 18 couples of rolls. $\endgroup$
    – Lourrran
    Commented May 12 at 8:15

3 Answers 3

12
$\begingroup$

Let $X_1,...,X_k$ be i.i.d. Uniform($\{1,...,m\}).$ Then the distribution of $S_k=X_1+...+X_k$ is given exactly by a recursion proved in this paper$^\dagger$, which expresses this distribution in terms of polynomial coefficients. However, an approximation based on the CLT, in our case of $m=6$, is that $S_k$ is approximately Normal with mean $\mu_k={7 k\over 2}$ and standard deviation $\sigma_k=\sqrt{35 k\over 12}$; so $$P\left(S_k\gt 100\right)\approx 1-\Phi\left({100-\mu_k\over \sigma_k }\right).$$

Here's a picture, for $k=2n$:

plots of exact and approximate P(S_{2n}>100) vs. n

The least $n$ that gives $P\left(S_{2n}\gt 100\right)\ge 0.99$ is $n=18$, according to both approaches.


Here I've posted my Python code implementing both the exact and approximate approaches, with the following numerical output:

    n=15  P(S>100)=0.6840  normal_approx=0.7035
    n=16  P(S>100)=0.8825  normal_approx=0.8929
    n=17  P(S>100)=0.9685  normal_approx=0.9718
--> n=18  P(S>100)=0.9938  normal_approx=0.9944 <--
    n=19  P(S>100)=0.9991  normal_approx=0.9991
    n=20  P(S>100)=0.9999  normal_approx=0.9999

$^\dagger$ Caiado, Camila & Rathie, Pushpa. (2007). "Polynomial coefficients and distribution of the sum of discrete uniform variables"

Here is a quick summary of how $P(S_k=s)$, and hence $P(S_k>100)$, is related to polynomial coefficients via probability generating functions (PGFs):

The PGF for each $X_i\sim$ Uniform({$1,...,m$}) is just $$G(t):=\sum_{x}P(X=x)t^x={1\over m}(t^1+t^2+...+t^m)={1\over m}t(1+t+...+t^{m-1})$$ so, by the product rule for the PGF of a sum of independent r.v.s, the PGF for $S_k$ is simply $$\sum_{s}P(S_k=s) t^s = G(t)^k = {1\over m^k}t^k(1+t+...+t^{m-1})^k.$$ Therefore $$P(S_k=s) = {1\over m^k} \times\text{coefficient of $t^s$ in $t^k(1+t+...+t^{m-1})^k$}\\ ={1\over m^k} \times\text{coefficient of $t^{s-k}$ in $(1+t+...+t^{m-1})^k$}$$ which are precisely the coefficients for which a recursion is provided in the cited paper.

$\endgroup$
0
6
$\begingroup$

While not a rigorous answer, I don't know how to get the number analytically, this should suffice.

Let $X_i $ be the result of the ith roll and $X_{i}\in\left\{ 1,2,3,4,5,6\right\} $ with equal probabilities.

Assume we roll the dice $k$ times and we want to find the minimal $k$ such that : $$ P\left(X_{1}+X_{2}+\dots X_{k}>100\right)$$ We can use the central limit theorem as suggested above by doing the following manipulations : $$ P\left(\frac{X_{1}+X_{2}+\dots X_{k}}{k}>\frac{100}{k}\right) $$ $$ P\left(\frac{X_{1}+X_{2}+\dots X_{k}}{k}-\mu>\frac{100}{k}-\mu\right)=P\left(\sqrt{k}\left[\frac{X_{1}+X_{2}+\dots X_{k}}{k}-\mu\right]>\sqrt{k}\left[\frac{100}{k}-\mu\right]\right)$$ $$ P\left(\frac{\sqrt{k}\left[\frac{X_{1}+X_{2}+\dots X_{k}}{k}-\mu\right]}{\sigma}>\frac{\sqrt{k}\left[\frac{100}{k}-\mu\right]}{\sigma}\right)\approx Q\left(\frac{\sqrt{k}\left[\frac{100}{k}-\mu\right]}{\sigma}\right)>0.99$$ note that $\mu = 3.5$ and $\sigma = \sqrt{\frac{35}{12}} $ and $Q$ is Q function.

What we are looking for is actually the variable $k$ so what we actually want is the inverse $Q$ function.

If we wanted $$ Q\left(\frac{\sqrt{k}\left[\frac{100}{k}-\mu\right]}{\sigma}\right)=0.99\iff\frac{\sqrt{k}\left[\frac{100}{k}-\mu\right]}{\sigma}=Q^{-1}\left(0.99\right)$$

Turns out scipy can do it using the function ppf (The inverse of $Q(1-x)$). the following code does it:

from scipy.stats import norm
r = norm.ppf(0.0.01)
sigma = (35/12)**0.5
mu = 3.5

f = lambda k:((k**0.5 *((100/k) - mu))/sigma)
for k in range(1,40):
    if f(k)-r <0:
        print(f"k={k}")
        break

This will print out $k = 36$ Therefore you need $36 $ dice rolls to get with probability $0.99$ that the sum of the $36$ rolls is above $100$.

$\endgroup$
5
  • $\begingroup$ Yup, my method gives 24 too. $\endgroup$ Commented May 12 at 1:20
  • 1
    $\begingroup$ There were a few bugs in my method. It now aligns with the other answers. This one might need the same fixes mine did. $\endgroup$ Commented May 12 at 6:42
  • 1
    $\begingroup$ $24$ dice rolls is clearly insufficient given $\frac{100}{3.5}\approx 28.6$. Here $36$ dice rolls (or $18$ double rolls) would be better. $\endgroup$
    – Henry
    Commented May 12 at 8:39
  • $\begingroup$ so it seems PPF is not the inverse of the Q function as is, so i read the documentation wrong, but $ppf(1-x)$ is. Edited my answer $\endgroup$ Commented May 12 at 10:08
  • $\begingroup$ +1: If you run a simulation, you may be able to check whether 36 is the best one or not (i.e., the smallest one). I guess it is, as 100 seems sufficiently large (also already approved by a known exact method used in @r.e.s. 's answer; this Henry's answer can help you on how to perform a simulation. $\endgroup$
    – Amir
    Commented May 12 at 10:49
4
$\begingroup$

One way to do this is to invoke the central limit theorem which says that as you sum more and more i.i.d random variables, their sum get close to a Gaussian. Let's assume that by the time the sum has any chance of crossing $100$, the central limit theorem will be in play. If you toss the die $n$ times, the mean of the distribution of the sum is $3.5n$ and the variance is $2.92n$. For a normal distribution, you can get the 99th percentile with many statistics libraries. For example in Python spicy:

from scipy.stats import norm
# Choose different values of n.
n=5
norm.ppf(0.01,loc=3.5*n,scale=np.sqrt(2.92*n))*np.sqrt(2.92*n)

Note that norm.ppf returns a multiplier of the standard deviation. Hence, we have to again multiply by the standard deviation.

I'll stop here since you should be able to take it forward. Look for the first $n$ where it crosses 100.

$\endgroup$
4
  • 1
    $\begingroup$ This is the minimum needed to have at least a 1% chance of getting a sum greater than 100 -- the mean of the sum of 24 dice is 84, which is clearly less than the target. You need to replace the 0.99 with 0.01. $\endgroup$ Commented May 12 at 2:52
  • $\begingroup$ norm.ppf(.01) returns -2.33. Which means norm.ppf(0.99) is what we're really after. $\endgroup$ Commented May 12 at 5:54
  • $\begingroup$ Actually, you're right. Edited my answer. $\endgroup$ Commented May 12 at 6:17
  • $\begingroup$ lol. Fixed as well. $\endgroup$ Commented May 12 at 6:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .