Tell me more ×
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.
up vote 7 down vote favorite
1

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

share|improve this question
2  
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
show 4 more comments

2 Answers

up vote 8 down vote

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.

share|improve this answer
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 u*M^n*v^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
up vote 3 down vote

The short answer is not really, but it doesn't matter. If you're interested in computing the exact probability there is a way to do it reasonably quickly by writing down a certain matrix and using binary exponentiation, but I'll let you in on a secret: for large $n$, the answer is exponentially close to $\frac{1}{6}$ (that is, it's exactly what you would naively expect). A very similar result is proven in the MO thread Michael linked to. So if that's all you wanted to know, then you know it. If you really wanted to estimate how close it was to $\frac{1}{6}$ then you'd need to estimate the next largest root of the characteristic polynomial $x^6 = \frac{x^5 + ... + 1}{6}$.

share|improve this answer

Your Answer

 
discard

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