Problem 11.20 Easy Free 1 variation

Running Sum Hits a Multiple of Six

A fair six-sided die is rolled repeatedly, and the results are summed as the rolls accumulate. Find the expected number of rolls needed until this running total is first a multiple of six.

Work it out, then compare with the answer.

SolutionShow the worked solution

Key idea. Whatever the running total is, exactly one face makes the new total a multiple of six.

Let $S_k=X_1+\dots+X_k$ and $N=\min\{k\ge 1: 6\mid S_k\}$ . Fix $k\ge1$ and condition on $X_1,\dots,X_{k-1}$ . Then $S_{k-1}\equiv r \pmod 6$ for some known $r\in\{0,\dots,5\}$ . The new total $S_k=S_{k-1}+X_k$ is divisible by $6$ exactly when $X_k\equiv -r\pmod 6$ .

The faces $1,\dots,6$ cover every residue mod $6$ exactly once, so exactly one face does this. Since $X_k$ is independent of the earlier rolls,

\mathbb{P}\bigl(6\mid S_k \,\big|\, X_1,\dots,X_{k-1}\bigr)=\tfrac16 .

This holds whatever the history. In particular it holds on the event $\{N>k-1\}$ , which is determined by $X_1,\dots,X_{k-1}$ . Hence $\mathbb{P}(N>k\mid N>k-1)=\tfrac56$ , and by induction $\mathbb{P}(N>k)=(5/6)^k$ .

So $N\sim\mathrm{Geom}(1/6)$ , and

\mathbb{E}[N]=\sum_{k\ge0}\mathbb{P}(N>k)=\sum_{k\ge0}\left(\tfrac56\right)^k=6 .

\boxed{\mathbb{E}[N]=6}

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 11.20a

A fair six-sided die is rolled repeatedly, and the results are summed as the rolls accumulate. Find the expected number of rolls needed until this running total is first even.

Work it out, then compare with the answer.

Solution

The same argument applies with parity in place of residues mod $6$ . Whatever the parity of $S_{k-1}$ , exactly three of the six faces make $S_k$ even: even faces if $S_{k-1}$ is even, odd faces if it is odd. Each roll therefore succeeds with conditional probability $\tfrac12$ regardless of the past.

Hence $N\sim\mathrm{Geom}(1/2)$ and $\mathbb{E}[N]=2$ . Conditioning on the first roll gives the same result: $\tfrac12\cdot1+\tfrac12(1+2)=2$ .

\boxed{\mathbb{E}[N]=2}

Spotted an error? Email us