DICE | Peter Lorenz

To solve the wide variety of dice problems efficiently, it’s helpful to recognize common patterns and techniques. Below is a categorized summary of key patterns and strategies that appear frequently in the problems you’ve shared. By identifying which pattern a problem falls into, you can minimize effort and apply the appropriate method.

Source

1. Expected Number of Rolls Until a Condition is Met

Pattern: Problems ask for the average number of rolls needed to achieve a specific outcome (e.g., rolling a 6, getting all faces, etc.).

Key Techniques:
- Geometric Distribution: For a single event (e.g., rolling a 6), the expected number of rolls is ( \frac{1}{p} ) (e.g., 6 rolls for a fair die).
- Markov Chains/Recursion: For multi-step conditions (e.g., “until two 6’s appear in a row”), set up recursive equations or use states to model the problem.
- Coupon Collector’s Problem: For “collecting all faces,” the expected number of rolls is ( n \sum_{k=1}^n \frac{1}{k} ) (e.g., 14.7 for a 6-sided die).

Example Problems: 1, 2, 3, 9, 10, 11, 19, 25, 26.

2. Probability of Specific Sequences or Outcomes

Pattern: Questions about the probability of sequences (e.g., non-decreasing rolls), subsets (e.g., all faces appearing), or sums (e.g., sum is prime).

Key Techniques:
- Inclusion-Exclusion Principle: For “at least one” or “all faces” problems (e.g., Problem 5: probability all faces appear in ( n ) rolls).
- Generating Functions: For sums, use polynomials to model dice outcomes (e.g., ((x + x^2 + \dots + x^6)^n) for ( n ) dice).
- Dynamic Programming/Recursion: For sequences (e.g., non-decreasing rolls), build up probabilities step-by-step.

Example Problems: 5, 6, 7, 15, 16, 20, 22, 28, 29, 30.

3. Non-Standard Dice Problems

Pattern: Questions about biased dice, custom dice, or alternative definitions (e.g., sums, re-rolling rules).

Key Techniques:
- Linear Algebra: For non-transitive dice (e.g., Efron’s dice), construct probability matrices.
- Renumbering/Transformation: For “find dice with the same sum probabilities,” use generating functions or brute-force search.
- Conditional Probability: For re-rolling rules (e.g., Problem 44: sum with rerolls on 6s).

Example Problems: 48, 49, 50, 51, 53, 54.

Pattern: Focus on sums of dice (e.g., distribution, stopping rules, or hitting a target sum).

Key Techniques:
- Convolution: For sums of multiple dice, convolve their probability distributions.
- Recursion: For “sum reaching ( n )” (e.g., Problem 36: ( E_n = 1 + \frac{1}{6} \sum_{k=1}^6 E_{n-k} )).
- Markov Chains: For sums modulo ( n ) (e.g., Problem 37: expected rolls until sum is divisible by ( n )).

Example Problems: 29, 31, 32, 34, 36, 37, 38, 39, 40.

5. Optimal Stopping Strategies

Pattern: Decide when to stop rolling to maximize score or minimize loss (e.g., “stop when the current roll is higher than the expected future rolls”).

Key Techniques:
- Backward Induction: Calculate expected values from the end of the game (e.g., Problem 14: stop if roll > future expectation).
- Dynamic Programming: For multi-stage decisions (e.g., Problem 72: stop before rolling a repeated face).

Example Problems: 14, 72, 73, 74, 77.

6. Markov Chains and State Transitions

Pattern: Problems where the outcome depends on previous states (e.g., runs, consecutive differences, or memory-based conditions).

Key Techniques:
- Transition Matrices: Model states and transitions (e.g., Problem 25: consecutive differences).
- Absorbing States: For “game ends when X happens” (e.g., Problem 26: rolls until all faces are distinct).

Example Problems: 4, 6, 7, 25, 26, 35.

7. Asymptotic Behavior and Approximations

Pattern: Questions about limits or large numbers (e.g., “probability all faces appear equally as ( n \to \infty )”).

Key Techniques:
- Stirling’s Approximation: For factorials in large ( n ) (e.g., Problem 24: equal face counts in ( 6k ) rolls).
- Central Limit Theorem: For sums of many dice, approximate with normal distributions.

Example Problems: 24, 36, 39.

8. Symmetry and Uniformity

Pattern: Exploit symmetry to simplify calculations (e.g., identical dice, uniform distributions).

Key Techniques:
- Symmetry Arguments: e.g., Problem 37: expected rolls until sum is divisible by ( n ) is ( n ), due to uniformity.
- Renumbering Faces: For custom dice, relabel to match standard probabilities.

Example Problems: 37, 52, 54.

How to Apply These Patterns

Classify the Problem: Identify which category the problem falls into (e.g., expected rolls, sum probabilities).
Choose the Technique: Use the corresponding method (e.g., recursion for expected rolls, generating functions for sums).
Simplify with Symmetry: Look for symmetries or uniform distributions to reduce complexity.
Verify Edge Cases: Check small ( n ) or trivial cases to ensure correctness.

By recognizing these patterns, you can tackle most dice problems systematically. For example:

Problem 9 (Coupon Collector): Use the harmonic series formula.
Problem 29 (Identical Sum Probabilities): Use generating functions to compare coefficients.
Problem 72 (Optimal Stopping): Use backward induction to find the stopping rule.

Let me know if you’d like a deeper dive into any specific pattern!