Last week’s Fiddler on the Proof was a bit of a disappointment. Not that the puzzle wasn’t fun: it was delightful as always, but that there is only one! The usual format is that you have an easy version and then a hard version. But this week they were the same! Spoilers below:

The original question spoiler

The original question is finding the number of d6 dice you need to roll simultaneously such that the range is maximized at 5 (i.e. you rolled a 1 and a 6 together) with probability > 0.5.

This is just inclusion-exclusion:

\[ 1 - (1 - p_{\text{min}})^n - (1 - p_{\text{max}})^n + (1 - p_{\text{min}} - p_{\text{max}})^n \]

with \(p_{\text{min}} = 1/6\) and \(p_{\text{max}} = 1/6\). Solving this for \(n\), we get \(n=7\) (at which point the probability is \(23345/46656 \approx 0.5004\); \(n=6\) only gives \(\approx 0.4180\)).

The extra credit spoiler

The extra credit then asks us to instead roll 1000 d6s and calculate their sums. How many of these sets of dice do we need to have before the probability that the range is 5000 (i.e. we got a roll with all 1s and a roll with all 6s) surpasses 0.5?

But note we can just treat the many rolls as just a single weighted roll: only \(p_{\text{min}}\) and \(p_{\text{max}}\) change! Getting the approximation is slightly interesting: it’s a very, very big number so numerically solving this is unlikely. But we also know that when \(x\) is very small \((1 - x)^n \approx \exp(-nx)\) which lets us rearrange to give us a nice closed form1

\[ 1 - 2e^{-np} + e^{-2np} = \left(1-e^{-np}\right)^2 \]

with \(p_{\text{min}} = p_{\text{max}} = p = (1/6)^{1000}\), we set this to \(1/2\), giving

\[ n = \frac{1}{p}\ln\!\left(\frac{1}{1-1/\sqrt2}\right) = 6^{1000}\,\ln\!\left(\frac{1}{1-1/\sqrt2}\right) \approx 1.228 \times 6^{1000} \approx 1.74 \times 10^{778} \]

Extra extra credit

A harder problem would be to make this continuous. Now we no longer have this nice discrete probability: there isn’t a max. The easiest way to achieve this is to split the dice into a uniform distribution: we’ll slightly offset it between (0.5, 6.5) so we can keep the same range condition. What, then, is the probability that the range of draws is within 5 as a function of the number of draws?

Let me know if you solve this one; it actually could make a fun probability homework problem :)

My Solution spoiler

You actually have to derive the joint distribution of the extrema and integrate to find the right probability.

One would think that this would get nasty, but (for the choice of uniforms) it actually has a nice closed form.

Let \(X_{(1)}\) and \(X_{(n)}\) be the min and max of \(n\) iid draws from Uniform\((0.5, 6.5)\) (support length \(L=6\)), and \(R = X_{(n)} - X_{(1)}\) the range. The joint density of the min and max is

\[ f_{X_{(1)},X_{(n)}}(x,y) = \frac{n(n-1)}{L^n}(y-x)^{n-2}, \qquad 0.5 \le x < y \le 6.5 \]

and integrating over the region \(y - x \le r\) gives the CDF of the range:

\[ P(R \le r) = n\left(\frac{r}{L}\right)^{n-1} - (n-1)\left(\frac{r}{L}\right)^{n}, \qquad 0 \le r \le L. \]

You might be interested in interpreting this CDF!

Letting \(T_n = n(L - R)/L\) and substituting \(r = L - Lt/n\), taking \(n\to\infty\) gives \(P(T_n > t) \to 1 - e^{-t}(1+t)\), i.e. \(T_n\) converges in distribution to \(\mathrm{Gamma}(2,1)\). Indeed this is a well known result for the extreme values of the uniform distribution!


  1. Plugging the single-die case (p=1/6) into this same closed form gives n = 6*ln(1/(1-1/sqrt(2))) ≈ 7.37, vs. the exact n=7 above; the exponential approximation is already quite good even at this small n ↩︎