# What is the probability that $n$ dice tie on successive rolls?

## The Question

What is the probability, rolling $n$ six-sided dice twice, that their sum each time totals to the same amount? For example, if $n = 4$, and we roll $1,3,4,6$ and $2,2,5,5$, adding them gives

$$1+3+4+6 = 14 = 2+2+5+5$$

What is the probability this happens as a function of $n$?

## Early Investigation

This problem is not too hard for $n = 1$ or $n = 2$ via brute force...

For $n = 2$:

Tie at a total of $2$: $$\frac{1}{36} * \frac{1}{36} = \frac{1}{1296}$$

Tie at a total of $3$: $$\frac{2}{36} * \frac{2}{36} = \frac{4}{1296}$$

etc.

so the answer is $$\frac{1^2 + 2^2 + 3^2 + ... + 6^6 + 5^2 + ... + 1^2}{1296} = \frac{\frac{(6)(7)(13)}{6} + \frac{(5)(6)(11)}{6}}{1296} = \frac{146}{1296}$$

Note that I use the formula: $\sum_{k=1}^{n}k^2=\frac{(n)(n+1)(2n+1)}{6}$.

Is there a way to do this in general for $n$ dice? Or at least a process for coming up with a reasonably fast brute force formula?

## The Difficulty

The problem arises that the sum of squares is not so simple when we get to three dice.

Using a spreadsheet, I figured out we need to sum these squares for 3 dice:

$$1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1$$

For a brute force answer of $\frac{4332}{46656}$. Note how we can no longer use the sum of squares formula, as the squares we need to sum are no longer linear.

## Some Thoughts

I am no closer to figuring out an answer for $n$ dice, and obviously the question becomes increasingly more difficult for more dice.

One thing I noticed: I see a resemblance to Pascal's Triangle here, except we start with the first row being six $1$, not one $1$. Se we have:

               1 1 1 1 1 1
1 2 3 4 5 6 5 4 3 2 1
1 3 6 10 15 21 25 27 27 25 21 15 10 6 3 1
1 4 9 16 25 36 46 52 54 52 46 36 25 16 9 4 1
...


but that's still a process, not a formula. And still not practical for $n = 200$.

I know how to prove the formula for any cell in Pascal's Triangle to be $C(n,r) = \frac{n!}{r!(n-r)!}$... using induction; that doesn't really give me any hints to deterministically figuring out a similar formula for my modified triangle. Also there is no immediately obvious sum for a row of this triangle like there is (powers of 2) in Pascal's Triangle.

Any insight would be appreciated. Thanks in advance!

-
Do you know about generating function? –  Jean-Sébastien Oct 28 '12 at 21:01
You have a small typo, for $n=2$ it should be $146$ on the numerator. You did $2n+1=12$ but with $n=5,$ its $11$ –  Jean-Sébastien Oct 28 '12 at 21:47
That's two typos actually :) Fixed them thanks –  durron597 Oct 28 '12 at 21:50
I don't think we can get a close form. I know sums of power of binomial coefficient relates to Generalised hypergeometric function, so this squared multinomial doesn't seem too friendly. Have a quick look at en.wikipedia.org/wiki/Pascal%27s_simplex for your Pascalish triangle –  Jean-Sébastien Oct 28 '12 at 21:59
+1. Was about to ask this question specifically for the n=2 case, as I wasn't sure if my reasoning was right. –  Cruncher Feb 18 at 21:42

It is possible to calculate this exactly if you are willing to use arbitrary precision integer arithmetic.

You can use the recursion $$f(n,k)=\sum_{j=1}^6 f(n-1,k-j)$$ starting at $f(0,0)=1$ and $f(0,k)=0$ when $k\not =0$ to find the number of ways of scoring $k$ from $n$ dice. Your result is then $$\sum_{i=n}^{6n} f(n,i)^2 / 6^{2n}$$ which is the division of two very large integers: for $n=200$ the numerator will be about $2.1\times 10^{309}$ and the denominator will be $6^{400}\approx 1.8\times 10^{311}$.

More practically using a spreadsheet and only looking for several decimal places you can use $$g(n,k)=\sum_{j=1}^6 g(n-1,k-j) / 6$$ starting at $g(0,0)=1$ and $f(0,k)=0$ when $k\not =0$ to find the probability of scoring $k$ from $n$ dice. Your result is then $$\sum_{i=n}^{6n} g(n,i)^2.$$

With $n=200$ this latter method will just over 200 columns and 1200 rows of the spreadsheet, so not difficult, and an extra column for the squares of the final column. In practice it give a value of about $0.0116752$ for the probability of matched sums rolling 200 dice twice.

This compares with about $0.0116798$ from joriki's approximation, a relative difference of around 0.04%.

-
For what it's worth, the original question (that inspired the post) was actually $n=8$, I simply mentioned $n=200$ as an example of an arbitrarily large $n$ that is conceivably meaningful. –  durron597 Oct 29 '12 at 1:06
@durron597 for $n=8$ the exact answer is $\dfrac{163112472594}{2821109907456} \approx 0.0578185$ –  Henry Oct 29 '12 at 6:33
isn't your answer basically exactly the same as my "Pascalish triangle"? –  durron597 Oct 29 '12 at 13:24
@durron597 yes: but if you do it with probabilities [my $g(n,i)$] then it is practical for $n=200$ –  Henry Oct 29 '12 at 13:31

I don't know whether you're interested in approximate and asymptotic answers – there's a straightforward estimate for large $n$. The distribution for the sum tends to a normal distribution. The variance for one die is

$$\langle x^2\rangle-\langle x\rangle^2=\frac{1+4+9+16+25+36}6-\left(\frac{1+2+3+4+5+6}6\right)^2=\frac{35}{12}\;,$$

so the variance for $n$ dice is $n$ times that. The probability of a tie is the sum over the squares of the probabilities, which we can approximate by the integral over the square of the density, so this is

$$\int_{-\infty}^\infty\left(\frac{\exp\left(-x^2/\left(2\cdot\frac{35}{12}n\right)\right)}{\sqrt{2\pi\frac{35}{12}n}}\right)^2\,\mathrm dx=\int_{-\infty}^\infty\frac{\exp\left(-x^2/\left(\frac{35}{12}n\right)\right)}{2\pi\frac{35}{12}n}\,\mathrm dx=\sqrt{\frac3{35\pi n}}\approx\frac{0.1652}{\sqrt n}\;.$$

The approximation is already quite good for $n=3$, where it yields about $0.095$ whereas your exact answer is about $0.093$.

-
I am looking for an exact answer, but this is pretty great. Upvote for you! –  durron597 Oct 28 '12 at 21:44

This is not as explicit as you may want, but it's a first step. I encourage you to read about generating function, one possible answer to your question lies in them. (Plus they are really fun!).

One can show that the number of ways to write $k=x_1+x_2+\cdots +x_n$ where $1\leq x_i\leq 6$ for all $i$ are the coefficient of $x^k$ in $$(x+x^2+x^3+x^4+x^5+x^6)^n.$$ This coefficient is the multinomial coefficient $${n\choose x_1,x_2,\cdots, x_m}$$, where $k=x_1+x_2+\cdots +x_n$ for a given $k$.

Now what you want to do is sum the square of these coefficients and divide it by $36^n$

We can write this as $$\frac{1}{36^n}\sum_{k=n}^{6n}\quad\sum_{x_1+x_2+\cdots +x_n=k}{n\choose x_1,x_2,\cdots, x_m}^2$$ Substituting $n=2$ we get $\frac{146}{1296}$ and for $n=3$ we get $\frac{4332}{46656}.$

-