# Probability of cumulative dice rolls hitting a number

Is there a general formula to determine the probability of unbounded, cumulative dice rolls hitting a specified number?

For Example, with a D6 and 14:

5 + 2 + 3 + 4 = 14 : success

1 + 1 + 1 + 6 + 5 + 4 = 17 : failure

-
The related question mathoverflow.net/questions/18282/… at mathoverflow might be of interest. The consensus in that discussion was that there wasn't a "nice" explicit formula (although there is the partial-fraction formula that Moron gives below) but that these probabilities are easy to compute recursively. – Michael Lugo Nov 7 '10 at 0:38
I can brute force the probability up to n=10, and for large n the answer is 1/6. Can anyone brute force enough points for n=10...100 that a graphical representation of the results might indicate a good easy-to-calculate approximation of the correct answer? – Sparr Nov 7 '10 at 3:30
@Sparr: the answer is 1/6 + O(r^n) for some r < 1. How interested are you in an upper bound on r? – Qiaochu Yuan Nov 7 '10 at 10:42
(For what it's worth, r is about 0.73, but I am trying to estimate this number without the help of a machine.) – Qiaochu Yuan Nov 7 '10 at 10:49
what is O() in that context? – Sparr Nov 7 '10 at 11:54

Assuming the order matters (i,e 1+2 is a different outcome from 2+1)

The probability of getting the sum $n$ with dice numbered $1,2,\dots,6$ is the coefficient of $x^n$ in

$$\sum_{j=0}^{\infty}(\frac{x+x^2+x^3+x^4+x^5+x^6}{6})^j = \frac{6}{6-x-x^2-x^3-x^4-x^5-x^6}$$

Writing it as partial fractions (using roots of $6-x-x^2-x^3-x^4-x^5-x^6=0$) or using Cauchy's integral formula to find the coefficient of $x^n$, Taylor series, etc should work.

-
The coefficient of $x^{14}$ of the power series expansion around 0 is 22219348327/78364164096=28.354% (computed in GP/PARI Calculator). $\frac{6}{6-x-x^{2}-x^{3}-x^{3}-x^{5}-x^{6}}=$ $1+1/6x+7/36x^{2}+\ldots$ $+22219348327/78364164096x^{14}+O(x^{15})$ – Américo Tavares Nov 7 '10 at 0:13
Partial fractions or Cauchy integral or whatever are not going to be directly helpful because you can't write down the roots (poles) explicitly anyway. There is an efficient algorithm to extract any particular coefficient using matrix multiplication (which I think is more efficient than expanding this power series), or one can get an asymptotic formula by estimating the (in this case, second) largest root of the characteristic polynomial, see e.g. the example here: math.stackexchange.com/questions/4658/… – Qiaochu Yuan Nov 7 '10 at 0:54
@Qia: We can give recursive methods to compute the nth derivative (I will add that later when I get the time), which will give an O(n) time algorithm. The left hand side of the above expression itself gives an O(n^2) time algorithm. I am curious, can you please elaborate on the matrix method? Is it faster than O(n) (i.e. o(n))? (I suppose the recurrence will be a linear one, which gives an O(logn) algorithm by finding Matrix powers). – Aryabhata Nov 7 '10 at 1:08
yes, the matrix method is O(log n). Given any sequence which can be described by a recurrence we can write down a matrix M (the companion matrix of its characteristic polynomial) and vectors u, v such that uM^nv^T is the nth term of the sequence, and using binary exponentiation this is easy to compute. (This is particularly easy if the sequence has a combinatorial interpretation since it's also easy to write M down as the weighted adjacency matrix of some graph, e.g. a finite state machine recognizing the corresponding regular language.) – Qiaochu Yuan Nov 7 '10 at 1:10
@Qia: Yes, I know that method (one of my favourites to compute fibonacci in O(logn) time:-)). If you write the above as a power series and multiply that by the denominator we got above, and equate coefficients, we get a linear recurrence which can be read off from the powers of a 7x7 matrix. (I realized this immediately after writing my previous comment). So the above is useful too :-) – Aryabhata Nov 7 '10 at 1:17