## Sunday, June 24, 2012

### A Dicey Problem: Solution

Problem: Waldo rolls one standard (fair) 6-sided die repeatedly, keeping a running total of what he rolls. To three decimal places, what's the probability that he eventually reaches a total of exactly 1,000,000?

Solution: On average Waldo will be adding $$\mu = (1+2+3+4+5+6)/6 = 3.5$$ per roll, so we would "intuitively" or "naively" expect that the probability of hitting a particular total that's large enough would be close to $$1/3.5$$. This turns out to be correct.

More generally, if we have any finite set of positive integers with no common factor, then the probability of hitting a particular total for large enough numbers is $$1/\mu$$, where $$\mu$$ is the expected value for a single roll. Note that the probabilities associated with the positive integers in our set don't need to be the same, either, just greater than zero and summing to $$1$$.

Proof: I'll show how you can prove this rigorously for the case where the outcomes are $$1$$ and $$2$$, each with probability $$1/2$$. Let $$p(n)$$ be the probability of totaling the value $$n$$. The only possible ways to total $$n$$ are to reach $$n-2$$ and immediately roll a $$2$$, or reach $$n-1$$ and immediately roll a $$1$$. This implies that $$p(n) = 1/2\cdot p(n-1) + 1/2\cdot p(n-2)$$, which is a linear, second order, homogeneous difference equation (recurrence relation). I'm going to apply the theory here, but for more details see Wikipedia: Recurrence relation.

In this case the associated characteristic polynomial is $$r^2 = r/2 + 1/2$$ with roots $$r_1 = 1, r_2 = -1/2$$. So we have $$p(n) = c_1 + c_2\cdot (-1/2)^n$$ for constants $$c_1, c_2$$. The boundary conditions are $$p(0) = 1$$ and $$p(1) = 1/2$$; solving we get $$c_1 = 2/3$$ and $$c_2 = 1/3$$. This implies that $$p(n)$$ converges to $$2/3$$ very rapidly; exponentially, in fact.