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
Best Answer
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}}. $$