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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Mar 15, 2010 at 17:43
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
8
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.
answered Mar 15, 2010 at 18:18
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 15, 2010 at 18:54
-
$\begingroup$ 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 $\endgroup$ Commented Mar 15, 2010 at 18:58
-
$\begingroup$ 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. $\endgroup$ Commented Mar 15, 2010 at 19:30
-
$\begingroup$ @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? $\endgroup$ Commented Mar 15, 2010 at 19:34
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 15, 2010 at 20:17
$\begingroup$
$\endgroup$
2
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}$.
answered Mar 15, 2010 at 17:36
-
2$\begingroup$ 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? $\endgroup$ Commented Mar 15, 2010 at 17:40
-
$\begingroup$
$\endgroup$
2
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.
answered Mar 15, 2010 at 17:28
-
$\begingroup$ 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. $\endgroup$ Commented Mar 15, 2010 at 17:38
-
2$\begingroup$ 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}$. $\endgroup$ Commented Mar 15, 2010 at 17:52
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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?
answered Mar 15, 2010 at 17:30