Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you start at position 0. You then roll 2 6-sided dice. You move to the integer, call it z, that is the sum of the two dice. You then roll again. If the result of the roll is z', you move to z+z'. You then continue in this fashion. I am looking for formulas (recursive or non-recursive) for the probability of eventually landing on spot n (where n is a positive integer). For small n, n < 10 say, these probabilities are relatively easy to compute by just checking all cases. Note, as n grows, the functions will converge relatively quickly. So, for say n > 40, this may not be a very interesting question.

share|improve this question
1  
Eventually, the probabilities should converge to 1/7. (If you try the experiment 7*n times, about n times you will come up with number k, for large k). For more precise answers, try the following recurrence: P(n+12) = P(n+10)/36 + 2P(n+9)/36 + ... + 2P(n+1)/36 + P(n)/36. Gerhard "Ask Me About System Design" Paseman, 2010.03.15 –  Gerhard Paseman Mar 15 '10 at 17:43

5 Answers 5

up vote 5 down vote accepted

The probabilities do converge to 1/7. One way to see this is to start from Tony Huynh's comment: the probability that $n$ is hit is the coefficient of $t^n$ in $$f(t) = {1 \over (1-(t+t^2+t^3+t^4+t^5+t^6)^2/36)}$$. The denominator is a polynomial of degree 12; its roots are $t = 1$ and eleven points $r_1, \ldots, r_{11}$ which are outside the unit circle. Thus we can write $$ f(t) = {A \over 1-t} + \sum_{k=1}^{11} {C_k \over 1 - t/r_k} $$ where $A$ and $C_1, C_2, \ldots, C_{11}$ are (complex) constants. This is just the usual partial fraction expansion of a rational function. Taking the $z^n$ coefficient of both sides of the above equation gives $$p(n) = A + \sum_{k=1}^{11} C_k r_k^{-n}.$$ If we want to show that $\lim_{n \to \infty} p(n) = 1/7$, we just need to show that $A = 1/7$. This is easy: $A = \lim_{t \to 1} f(t) (1-t)$. The denominator in $f(t)$ is divisible by $1-t$, so do the polynomial division and substitute $t = 1$.

I wouldn't call the closed form above a "nice" closed form for $p(n)$, though.

share|improve this answer
1  
Although I haven't thought about it too hard, this argument should generalize to show that the coefficients of $1/(1-P(z))$, where $P(z)$ is the probability generating function of some positive-integer-valued distribution, approach $1/\mu$ as $n$ gets large where $\mu$ is the mean of the distribution whose pgf is $P(z)$. (That is, $\mu = P^\prime(1)/P(1)$.) The only stumbling block would be showing $1/(1-P(z))$ has no singularities inside the unit circle, which is probably a simple bit of complex analysis. –  Michael Lugo Mar 15 '10 at 18:54
    
Can you use this to say for which n P(n) gets close to 1/7? E.g., is it true that for all n > 21 |P(n) - 1/7| < 1/216? Gerhard "Ask Me About System Design" Paseman, 2010.03.15 –  Gerhard Paseman Mar 15 '10 at 18:58
    
Gerhard, I think the "explicit" formula I gave could be used in this way, at least if one explicitly calculated the constants $C_k$ and $r_k$. I don't wish to do this. But I believe that your guess is true. The difference $p(n)-1/7$ decays exponentially fast, so any statement of that form that looks true probably is. –  Michael Lugo Mar 15 '10 at 19:30
    
@Michael. Nice answer. My complex analysis is pretty rusty, but doesn't the triangle inequality imply that $1 / (1-P(z))$ has no singularities inside the unit circle? –  Tony Huynh Mar 15 '10 at 19:34
1  
I did the computation. The maxima are at 16, 26, 34, 43, 51, 60, 69, 78, ..., with a period of approximately 9. In fact the smallest (in modulus) of the $r_k$ are a pair near $.926 \pm .811i$, or $1.231 \exp(.720i)$; thus we expect oscillations with period $2\pi/.720$ or $8.73$ as the contributions from those two roots go in and out of phase with each other. I don't know of a good reason why this number should be larger than 7. –  Michael Lugo Mar 15 '10 at 20:17

The probability of landing on the integer $n$ in $k$ steps is the coefficient of $t^n$ in $\left(\frac{t+t^2+t^3+t^4+t^5+t^6}{6}\right)^{2k}$.

share|improve this answer
    
Well, isn't it $\left(\frac{t+t^2+t^3+t^4+t^5+t^6}6\right)^{2k}$ since you'll be rolling two dice for every move? –  Mikael Vejdemo-Johansson Mar 15 '10 at 17:40
    
Yup! Corrected. –  Mariano Suárez-Alvarez Mar 15 '10 at 17:41

Let p(n) be the required probability. Then p(n) satisfies the following recursion

p(n)=1/36 p(n-12) + 2/26 p(n-11) + 3/36 p(n-10) + 4/36 p(n-9) + 5/36 p(n-8) + 6/36 p(n-7) + 5/36 p(n-6) + 4/36 p(n-5) + 3/36 p(n-4) + 2/36 p(n-3) + 1/36 p(n-2),

with the obvious initial conditions.

share|improve this answer
    
Thank you. Is there a non-recursive formula? Or is there a recursive formula that does not depend on n-k for k=2,...,12. –  Stephen Shea Mar 15 '10 at 17:38
2  
I'm not sure there is a nice closed form, but as Mariano points out below, it is the coefficient of $t^n$ in $\frac{1}{1-(t+t^2+t^3+t^4+t^5+t^6)^2/36}$. –  Tony Huynh Mar 15 '10 at 17:52

You can also solve this linear recurrence using a Markov-like method. Working from Tony Huynh's recurrence, define a 13x13 matrix $M$ such that:

$ M_{0,k} = p(k) $, where $p(k)$ is the probability of rolling the sum $k$ on the two die,

$ M_{k+1, k} = 1$, for $k > 0$,

and $M_{i,j} = 0$ otherwise.

Then the first component of applying $M^n$ to the input vector $(1, 0, 0, .... 0)$ should give the probability of landing on the $n^{th}$ square (indexed by 0). Since $M$ is finite dimensional, we can compute a closed form by taking eigenvalues (but it will be messy and highly limited by the accuracy of the eigenvalue computation). Another computational approach to this would be to use fast matrix multiplication to quickly compute $P(n)$ in $O(\log(n))$ multiply operations.

share|improve this answer

Let P(k) = probability of eventually landing on k ... there is an easy to compute recursive formula for P(k) in terms of P(k-2), P(k-3), ..., P(k-12) , right?

share|improve this answer

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.