Likelihood of sum of dice roll is exactly 1 million

Question

A board game is set up such that there is a number line with squares numbered 0..1 million. You roll a standard 6 sided die and move forward the number of spaces that you roll. Eventually you will either land on, or pass the 1 millionth spot. What is the probability you land exactly on the 1 millionth spot?

In other words, what is the probability that after a number of rolls the sum is exactly 1 million

Answer 1

The simple answer is that the average roll is $\frac 72$, so you will hit $\frac 27$ of the squares in the long run. Since you are very far from the start, this will be very close. There is a slight perturbation at the start, as the chance you hit $1$ is $\frac 16$, the chance of $2$ is $\frac 7{36}$, and so on, but it washes out quickly.

Answer 2

Let $S(\omega) \subset \mathbb{N}$ be the spaces that are landed on during trial $\omega$. That is, if $d_k(\omega) \in \{1,...,6\}$ are the die rolls, then $S(\omega) = \{ \sum_{k=1}^n d_k(\omega) \}_{n=1}^\infty $.

For $k \ge 1$, let $r_k(\omega) = \min \{ j-k | j \ge k, \ j \in S(\omega) \}$. Note that $r_k(\omega) = 0$ iff space $k$ was landed on. Also, note that $r_k(\omega) \in \{0,...,5\}$, and that if $r_k(\omega) >0$, then $r_{k+1}(\omega) = r_k(\omega) +1$.

To simplify notation, for $n \in \{0,...,5\}$ let $\pi_k(n) = p\{ \omega | r_k(\omega) = n \}$.

We have $\pi_1(n) = \frac{1}{6}$ (initial roll must land on one of $\{1,...6\}$ with probability $\frac{1}{6}$).

Then for $k >1$, we can compute $\pi_k(n) = \sum_{m=0}^{5} p \left(\{ \omega | r_k(\omega) = n \} | \{ \omega | r_{k-1}(\omega) = m \} \right) \pi_{k-1}(m)$.

If $m \in \{1,...,5\}$, then $p \left(\{ \omega | r_k(\omega) = n \} | \{ \omega | r_{k-1}(\omega) = m \} \right) = \begin{cases} 1, & n=m-1 \\ 0, & \text{otherwise}\end{cases}$.

If $m = 0$, then $p \left(\{ \omega | r_k(\omega) = n \} | \{ \omega | r_{k-1}(\omega) = 0 \} \right) = \frac{1}{6}$.

Letting $\pi_k = (\pi_k(0),...,\pi_k(5))^T$, we can write the above as $\pi_k = M \pi_{k-1}$, where $M= \begin{bmatrix} \frac{1}{6} & 1 & 0 & 0 & 0 & 0 \\ \frac{1}{6} & 0 & 1 & 0 & 0 & 0 \\ \frac{1}{6} & 0 & 0 & 1 & 0 & 0 \\ \frac{1}{6} & 0 & 0 & 0 & 1 & 0 \\ \frac{1}{6} & 0 & 0 & 0 & 0 & 1 \\ \frac{1}{6} & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}$.

The solution is then given by $\pi_{1000000}(0) = e_1^T M^{999999} \pi_1$.

Solving $M \hat{\pi} = \hat{\pi}$, gives the solution $\hat{\pi} = c(1, \frac{5}{6}, \frac{4}{6}, \frac{3}{6}, \frac{2}{6}, \frac{1}{6})^T$. Choosing $c= \frac{7}{2}$ gives the stationary distribution $\hat{\pi} = \frac{2}{7}(1, \frac{5}{6}, \frac{4}{6}, \frac{3}{6}, \frac{2}{6}, \frac{1}{6})^T$, hence we get the limiting $\hat{\pi}(0) = \frac{2}{7}$, as Ross pointed out with much less work.

(Thanks to my friend Takis Konstantopolos for his 'random set' approach ($S(\omega)$ in this instance) and introducing the $r_k$ to simplify my life.)

Answer 3

You can also analyze this problem via generating functions.

Let $P_{n,k}$ be the probability that you land on square $n$ after exactly $k$ turns, and let $P_n$ be the probability that you ever land on square $n$. So we're trying to find $P_{10^6}$. Also, note that $P_n=\sum_{k=0}^\infty P_{n,k}$: every number on the die is positive, so we can only land on a given square at most once.

Now, let $p(z)=\frac{1}{6}z+\frac{1}{6}z^2+\frac{1}{6}z^3+\frac{1}{6}z^4+\frac{1}{6}z^5+\frac{1}{6}z^6$ be the probability-generating function of the distribution of an individual die roll. Then the probability-generating function for the distribution of your position after $k$ turns is given by $\left[p(z)\right]^k$. That is, we have

$$ \left[p(z)\right]^k=\sum_{n=0}^\infty P_{n,k} z^n \, . $$

Combining this formula with the above infinite sum, it follows that the generating function for the sequence $P_n$ is:

$$ f(z)=\sum_{k=0}^\infty \left[p(z)\right]^k=\frac{1}{1-p(z)} $$

by summing the geometric series.

We can study the asymptotic behavior of this sequence by examining the poles of $f(z)$: that is, the complex roots of the polynomial $1-p(z)$. As we can see:

• The strictly smallest-magnitude pole is $z=1$.
• The next-smallest poles are roughly at $0.551685 \pm 1.253349i$, and so they have magnitude $\rho \approx 1.36939$.

Since the smallest-magnitude pole is at $z=1$, the sequence $\{P_n\}$ has a nonzero limit $A$, where the principal part of $f(z)$ at $z=1$ is $\frac{A}{1-z}$. Applying the residue formula gives

\begin{align*} A&=\lim_{z \to 1} (1-z)f(z)\\ &=\lim_{z \to 1}\frac{1-z}{1-p(z)}\\ &=\frac{-1}{-p'(1)}&&\text{(by L'Hopital's rule)}\\ &=\frac{1}{p'(1)} \, . \end{align*}

Since $p'(1)=\frac{1}{6}+\frac{2}{6}+\frac{3}{6}+\frac{4}{6}+\frac{5}{6}+\frac{6}{6}=\frac{7}{2}$, we recover the limit $\lim_{n \to \infty} P_n=\frac{2}{7}$ as in the other answers.

Since the next-smallest poles have magnitude $\rho$, we have $P_n=\frac{2}{7}+O(\rho^{-n})$. For $n=10^6$, $\rho^{-10^6} \approx 10^{-136527}$, so the error in the approximation $P_{10^6} \approx \frac{2}{7}$ is too small to care about.