Probabilities and rolling 2 dice 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.  
 A: 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.
A: 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}$.
A: 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.  
A: 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.
A: 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?
