Calculate the probability that the running total is exactly n. (homework help)

I am working through Harvard's public Stat 110 (probability) course.

Question:

5. A fair die is rolled repeatedly, and a running total is kept (which is, at each time, the total of all the rolls up until that time). Let $p_n$ be the probability that the running total is ever exactly n (assume the die will always be rolled enough times so that the running total will eventually exceed n, but it may or may not ever equal n).

   (a) Write down a recursive equation for $p_n$ (relating $p_n$ to earlier terms $p_k$ in a simple way). Your equation should be true for all positive integers n, so give a definition of $p_0$ and $p_k$ for $k < 0$ so that the recursive equation is true for small values of n.

   (b) Find $p_7$.

   (c) Give an intuitive explanation for the fact that $p_n \rightarrow 1/3.5=2/7$ as $n \rightarrow \infty$.

My work so far:

I am working on part a. So far, my ideas for a recursive formula are as follows.

We can get to $n$ by being at $n-1$ and rolling a 1, being at $n-2$ and rolling a 2, and so on. So,

$p_n = \frac{1}{6}p_{n-1} + \cdots + \frac{1}{6}p_{n-6}$.

In order for this to work for small values of $n$, let $p_0 = 1$ and $p_n = 0$ for all $n < 0$.

After working out $p_n$ for some small values of $n$, I believe the above is equivalent to

$p_n = \sum\limits_{k=n-6}^n \frac{1}{6^k}{n \choose k} = \sum\limits_{k=1}^6 \frac{1}{6^{n-k}}{n \choose 6-k}$

However, in either case, it seems that as $n \rightarrow \infty$, $p_n \rightarrow \infty$ (looking at part c given my definition of $p_n$ so far). Can someone point out where I've gone astray?

Edit: It seems I was overcomplicating the problem by assuming that I'd need a closed form equation for $p_n$. This means that I have what I need for part a, and I can calculate part b. I'm still working on an intuitive answer for part c.

Solution 1:

I think there's a bit of bookkeeping to get the first few cases $p_0 ... p_6$. Those you can hit on the first roll (but may not).

First, $p_0 = 1$, because you start there.

Next, $p_1 = 1/6$. You roll a $1$ on the first roll, or not.

Next, $p_2 = 1/6^2 + 1/6$. You can roll a $2$, or two $1$s.

Next, $p_3 = 1/6^3 + 2/6^2 + 1/6$. Three $1$s, a $1$ and a $2$ (two ways), or one $3$.

Next, $p_4 = 1/6^4 + 3/6^3 + 3/6^2 + 1/6$. Four $1$s, two $1$s and a $2$, two $2$s or a $1$ and a $3$, or one $4$.

Next, $p_5 = 1/6^5 + 4/6^4 + 6/6^3 + 4/6^2 + 1/6$. Five $1$s, three $1$s and a $2$, two $2$s and a $1$ or two $1$s and a $3$, a $2$ and a $3$ or a $4$ and a $1$, or a $5$.

Next, $p_6 = 1/6^6 + 5/6^5 + 10/6^4 + 10/6^3 + 5/6^2 + 1/6$. Six $1$s, four $1$s and a $2$, two $2$s and two $1$s or one $3$ and three $1$s, one $4$ and two $1$s or $1,2,3$ or three $2$s, any two numbers that add to $6$, or one $6$.

Now, we can look at your recurrence relation.

$$p_7 = 1/6^7 + 6/6^6 + 15/6^5 + 20/6^4 + 15/6^3 + 6/6^2.$$

So far, so good. But I think this is different than your formula. Looking at this I'd see:

$$p_n = \sum_{k=0}^{5}\frac{1}{6^{n-k}}{n-1 \choose k}.$$

Does this continue? I'd have to work it out myself but maybe you can give it a try. :)

Solution 2:

Expanding on John's answer, which answers parts a and b. For part c, if $X$ is the random event of rolling a die, then $E(X) = 3.5$. We can interpret this as meaning the roll will "hit" 1 in every 3.5 numbers. More intuitively, we will hit 2 in 7 numbers on average. This explains why $p \rightarrow 2/7$ as $n \rightarrow \infty$.