Combinatorial probability of multiple dice rolls

Question

I am trying to come up with a probability for a combinatorial problem that I'm working on and I'm stuck. I've managed to distil it down to a toy dice-roll problem:

What is the probability of any two dice adding up to 7 on a throw of n 6-sided dice?

Or being more general:

What is the probability of any two dice adding up to x+1 on a throw of n x-sided dice?

Note that there could be more than one 2-combination in the n dice that add to 7 - so if n = 3 and x = 6 a roll of 6, 6, 1 would satisfy the criteria.

You can assume that x is an even number, and thus there are n/2 2-combinations that sum to x+1. For example for a 6-sided dice there are 3 (x/2) combinations of 2 dice that will produce a 7: 6 & 1, 5 & 2, 4 & 3. I've tried using binomial and multinomial expressions on the expansion of these combinations but can't get this right. Can someone give me some pointers? Help gratefully received.

Thanks Chris

Answer 1

The 6-sided dice case can be encoded as a Markov chain on the state space $\{0,1,2,3,\partial\}$ where each state $0\leqslant i\leqslant3$ means that $i$ pairs from the set $\{\{1,6\},\{2,5\},\{3,4\}\}$ have already been visited but none is completed yet, and state $\partial$ means that at least one of these pairs has been completed. For example, after the results 26622 the state of the chain is $2$, after the results 266224246 the state of the chain is $3$, and after the results 2662242465 the state of the chain is $\partial$.

The probability that any two dice add to 7 on a throw of $n$ is $P_0[T\leqslant n]$ where $T$ is the hitting time of $\partial$ and the subscript $0$ refers to the starting point of the chain.

To characterize $P_0[T\leqslant n]$ for every $n$, one usually computes the generating functions $u_i=E_i[s^T]$ for $0\leqslant i\leqslant3$, where $|s|\leqslant1$. Writing down carefully the transition probabilities of the chain, one sees that the Markov property after one step yields the relations $$ u_0=su_1,\quad u_1=s(\tfrac16u_1+\tfrac46u_2+\tfrac16),\quad u_2=s(\tfrac26u_2+\tfrac26u_3+\tfrac26),\quad u_3=s(\tfrac36u_3+\tfrac36). $$ Solving this Cramér system, one gets (something similar to) $$ u_0=\frac{s^2(6+3s+s^2)}{(2-s)(3-s)(6-s)}. $$ Thus, $u_0$ is a rational fraction with respect to $s$, which can be decomposed as $$ u_0=\frac{c_2}{2-s}+\frac{c_3}{3-s}+\frac{c_6}{6-s}+as+b, $$ for some suitable constants $a$, $b$, $c_2$, $c_3$ and $c_6$. Expanding each fraction as a power series in $s$ and collecting all the terms of degree at least $n$ yields, for every $n\geqslant2$, $$ P[T\geqslant n]=\sum_k\frac{c_k}{k-1}\frac1{k^n}, $$ where the sum runs over $k$ in $\{2,3,6\}$.

If one uses some $2z$-sided dice instead, one finds similarly $$ P[T\geqslant n]=\sum_k\frac{c_k}{k-1}\frac1{k^n}, $$ for some suitable constants $c_k$, where the sum runs over $k=2z/\ell$ with $1\leqslant\ell\leqslant z$. In particular, when $n\to\infty$, $$ P[T\geqslant n]\sim\frac{c_2}{2^n}. $$ Going back to the 6-sided case, $c_2=\lim\limits_{s\to2}(2-s)u_0=16$ hence $$ P[T\geqslant n]\sim\frac{16}{2^{n}}. $$

Answer 2

[edit] Oops, I solved the wrong problem! But I'm leaving the solution here because I think it's an interesting solution, even if it doesn't solve the original problem [/edit]

Here is a generatingfunctionological approach. If you don't mind, I would rather say there are $n$ $m$-sided dice, because I have a special use in mind for $x$. We want to find the probability that the dice sum to $m+1$. I will assume $n > 1$ because that simplifies matters in a bit.

There are $m^n$ possible outcomes of rolling the dice, each of which we assume is equally likely. We want to count the number of outcomes which sum to $n+1$. Let's say the number of ways to get a sum of $r$ is $a_r$, and define $f(x) = \sum_{r=0}^{\infty} a_r x^r$. Then it's easy to see that $$f(x) = (x + x^2 + x^3 + \dots + x^m)^n$$ Applying some algebra, including the binomial theorem, we have $$f(x) = x^n (1 + x + x^2 + \dots + x^{m-1})^n = x^n \left( \frac{1-x^m}{1-x} \right) ^n$$ $$= x^n (1-x^m)^n (1-x)^{-n} = x^n \cdot \sum_{i=0}^n (-1)^i \binom{n}{i} x^{im} \cdot \sum_{j=0}^{\infty} (-1)^j \binom{-n}{j} x^j$$ We want the coefficient of $x^{m+1}$. The only combination of $i$ and $j$ above that qualifies is $i = 0$ and $j = m-n+1$. (This is where we use the assumption $n > 1$.) So $$a_{m+1} = (-1)^{m-n+1} \binom{-n}{m-n+1} = \binom{m}{m-n+1} = \binom{m}{n-1}$$ and the probability that we get a sum of $m+1$ on the dice is $$\frac {\binom{m}{n-1}} {m^n}$$