POW: Dice Running Total

Home   /   Hackathons, Mathematics   /   POW: Dice Running Total
POW: Dice Running Total
24
Sep
by

At QED there are a number of weekly exercises we participate in, to help keep our minds sharp and also just have some fun. One of them is Purdue University’s Math Problem of the Week (POW), a fun event has been going strong since the year 2000. During the spring and fall semesters of each academic year, a new problem is released, similar to those seen in math contests. Participants who mail in the correct answer will have their names and affiliations listed in the official solution that is released later. We’ve archived our writeups for some of our favorite problems at http://qed.ai/fun/#purdue, and thank the administrators for facilitating so many years of interesting problems.

The latest POW problem we like involves rolling a die repeatedly and keeping a running total. We are then challenged with the following question: which of the following numbers is most likely to appear as one of the totals: 2, 6, or 1006?

We can think of at least three different approaches for solving this problem:

dynamic programming

Let p(i,j) be the probability of generating a sum of i in j rolls. Then

    \begin{align*} p(i,1) &= \left\{ \begin{array}{ll} 1/6 & \quad \textrm{for } i \in \{1,2,3,4,5,6\} \\ 0 & \quad \textrm{else } \end{array} \right. \\ p(i,j) &= 0 \quad \textrm{for } i<j \textrm{="" or="" }="" i<1,="" \end{align*}

=”” by=”” conditioning=”” on=”” the=”” first=”” roll,=”” we=”” have=”” recurrence=””

*** QuickLaTeX cannot compile formula:
\begin{align*}="" p(i,j)="" &="\frac{1}{6}" \sum_{m="1}^6" p(i-m,j-1).="" lastly,="" summing="" over="" all="" possible="" numbers="" of="" rolls,="" probability="" seeing="" $i$="" occur="" is="" row="" sum="" $\sum_j="" p(i,j)$.="" below="" a="" short="" computer="" program="" to="" fill="" table="" $p(i,j)$="" using="" dynamic="" programming:="" <pre="" class="lang:python theme:twilight" title="dynamic programming">
#!/usr/bin/env python
import numpy as np
n = 1006
p = np.zeros((n,n))
q = float(1)/6
for i in xrange(0,6): p[i,0] = q
for i in xrange(1,n):
    for j in xrange(1,n):
        for m in xrange(1,7):
            if i-m >= 0: p[i,j] += p[i-m,j-1]
        p[i,j] *= q
for t in [2,6,1006]:
    print "Probability of {0}: {1}".format(t, np.sum(p[t-1,:]))
</j>
A short moment later, we get our answer:
Probability of 2: 0.194444444444
Probability of 6: 0.36023233882
Probability of 1006: 0.285714285714
<h2>linear recurrence</h2>
An alternative approach is to compute these probabilities directly through a closed-form expression. Let $p(i)$ be the probability of seeing a sum of $i$. Then, by conditioning on the first roll, we have the recurrence
\begin{align*}
p(i) = \frac{1}{6} \sum_{m=1}^6 p(i-m)
\end{align*}

*** Error message:
Error: Not allowed command sequence

which has characteristic equation 6x^6 - x^5 - x^4 - x^3 - x^2 - x - 1 = 0. Denoting the roots of this equation by r_1,r_2,\ldots,r_6, the general solution to the recurrence is given by p(i) = \sum_{k=1}^6 c_k r_k^i. The coefficients c_k can be solved by supplying six initial conditions, which are easily computed by direct evaluation: p(1) = 1/6, p(2) = 7/36, p(3) = 49/216, p(4) = 343/1296, p(5) = 2401/7776 and p(6) = 16807/46656. Then we have a polynomial expression that yields the same results as the dynamic programming approach.

induction

A slicker approach that does not involve computing any dirty numbers, which we learned from discussions with our associate Dr. Eric Freeman and which was also used in Purdue’s official solution, is to use induction. Starting with initial values p(1) < p(2) < p(3) < p(4) < p(5) < p(6), the next value p(7) is the average of these initial values, and is smaller than p(6). As we continue computing a running average of the preceding six values, that average will stay below p(6).

Do you have other approaches for solving the problem? Let us know!