Probability That All Faces Appear in Consecutive Rolls

Worked Solution

How to Think About It: Start with the simplest case: $n = 6$. You have exactly one window of 6 rolls, and you need all 6 faces to appear -- that is just the probability that 6 independent die rolls are all distinct. For larger $n$, you get $n - 5$ overlapping windows, and you want the probability that at least one of them is a full permutation. The overlapping windows share 5 rolls each, so they are heavily dependent, which makes naive union bounds loose. The right tool here is a DP that tracks whether we have already succeeded, and what the last few rolls looked like.

Quick Estimate: For a single window, $P(\text{all 6 distinct}) = 6!/6^6 = 720/46656 = 5/324 \approx 0.0154$. With $n$ rolls, there are $n - 5$ windows. If they were independent (they are not), the probability of at least one success would be roughly $1 - (1 - 5/324)^{n-5}$. For $n = 50$, that gives $1 - (319/324)^{45} \approx 1 - 0.935^{45} \approx 1 - 0.046 \approx 0.50$. The actual value is somewhat lower because adjacent windows are positively correlated (they share 5 rolls), so success in one window makes success in the next more likely. As a rough guide, you need around $n \approx 50$ rolls for about a coin-flip chance.

Approach: We compute $P(\text{at least one window has all 6 faces}) = 1 - P(\text{no window has all 6 faces})$, using either direct combinatorics for $n = 6$ or a Markov chain / DP for general $n$.

Formal Solution:

*Case $n = 6$:* There is exactly one window. The number of sequences of 6 rolls where all faces appear is $6! = 720$. The total number of sequences is $6^6 = 46656$. So $$P = \frac{6!}{6^6} = \frac{720}{46656} = \frac{5}{324} \approx 0.01543.$$

*General $n$ via DP:* Define the event $B$ = "no window of 6 consecutive rolls is a permutation of all 6 faces." We want $P(B^c) = 1 - P(B)$.

Set up a Markov chain where the state after roll $t$ (for $t \geq 5$) is the tuple of the last 5 rolls $(X_{t-4}, X_{t-3}, X_{t-2}, X_{t-1}, X_t)$. The state space has $6^5 = 7776$ elements.

Transition: from state $(a_1, a_2, a_3, a_4, a_5)$, we roll a new face $f \in \{1,\ldots,6\}$ each with probability $1/6$. The resulting window of 6 is $(a_1, a_2, a_3, a_4, a_5, f)$.

• If $\{a_1, a_2, a_3, a_4, a_5, f\} = \{1,2,3,4,5,6\}$, this window is a permutation. The sequence has "succeeded," and we absorb into a success state.
• Otherwise, we transition to state $(a_2, a_3, a_4, a_5, f)$ and continue.

The initial distribution is uniform over all $6^5$ states (the first 5 rolls). Let $q_n$ be the probability that after $n$ rolls we have never had a complete window. Then: $$q_5 = 1 \quad (\text{no window has been completed yet}),$$ and for each subsequent roll, we multiply by the transition matrix restricted to non-absorbing states. The answer is $$P(\text{success in } n \text{ rolls}) = 1 - q_n.$$

*Symmetry reduction:* By symmetry over face labels, we can reduce the state space dramatically. Instead of tracking the exact tuple of 5 rolls, track the "partition pattern" -- for instance, the number of distinct values among the last 5 rolls and how many times each appears (up to relabeling). This reduces $6^5 = 7776$ states to a much smaller set of equivalence classes (there are 7 integer partitions of 5 into at most 6 parts: $5, 4{+}1, 3{+}2, 3{+}1{+}1, 2{+}2{+}1, 2{+}1{+}1{+}1, 1{+}1{+}1{+}1{+}1$). However, the transition probabilities depend on which face the oldest roll was and whether the new face matches an existing one, so the partition alone is not quite a sufficient statistic. The exact implementation requires care, but the full $6^5$-state DP is perfectly tractable by computer.

*Checking the window condition:* In state $(a_1, a_2, a_3, a_4, a_5)$, the new roll $f$ completes all 6 faces if and only if $f$ is the unique face missing from $\{a_1, \ldots, a_5\}$. This requires that $a_1, \ldots, a_5$ already contain exactly 5 distinct faces. The probability of absorbing on this step is $1/6$ if the current state has 5 distinct faces, and $0$ otherwise.

Answer: For $n = 6$, the probability is $\frac{5}{324}$. For general $n$, there is no simple closed-form expression. The answer is computed via a Markov chain DP with state = last 5 rolls, absorbing whenever a window of 6 consecutive rolls contains all 6 faces. The result is $P = 1 - q_n$, where $q_n$ is obtained by iterating the $(7776 \times 7776)$ non-absorbing transition matrix $n - 5$ times from the uniform initial distribution.