Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What do you mean on $n$ rolls? Do you mean getting at least one sum of $7$ when you roll a pair $n$ times? Or do you roll $n$ dice and want to find any two that sum to $7$? –  Ross Millikan Oct 17 '13 at 14:22
    
I mean rolling n dice together. So, if n = 3 for example, I would throw 3 dice at once and want to know the probability that any two of the dice will sum to 7. It could be that more than 1 combination of pairs of the dice will add to 7 (for example if I throw 6, 6, 1) –  Chris Cox Oct 17 '13 at 14:27

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Extraordinary... I am in awe and very grateful, thank you. That will take some time to digest and fully understand and I may come back with a question or two. –  Chris Cox Oct 17 '13 at 15:26
    
Please do (and thanks for the appreciation). –  Did Oct 17 '13 at 15:40

[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}$$

share|improve this answer
    
Thanks for the input. If I'm right this solution will give me the probability that the total of all the dice in the throw added together is m+1. This is helpful, although actually a slightly different question from the one I'm looking at, which is what is the probability that any 2 of the dice in the throw will sum to m + 1 –  Chris Cox Oct 18 '13 at 15:10
    
Whoops, sorry, I misread the problem! I'll think about the "any two dice" aspect. –  awkward Oct 18 '13 at 21:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.