Pattern Reference
Random Walk
"Expected time to absorption, probability of reaching boundary, gambler's ruin, 1D/2D walk, drunkard's walk."
Loading...
Deep Dive Tutorial
**Core recurrence:** $E[s] = \text{cost}(s) + \sum_i P(s \to s_i) \cdot E[s_i]$ For absorbing states (terminal): $E[\text{absorbed}] = 0$. Work backward — compute $E$ for states closest to the absorbing state first, then propagate. **Geometric distribution:** If each trial succeeds with probability $p$, the expected number of trials to first success is $E = \frac{1}{p}$. **Games with restart:** If reaching the restart costs $c$ steps and happens with probability $q$, then $E = c + q \cdot E$ — solve to get $E = \frac{c}{1-q}$.
Expected value DP template
// Expected number of rolls of a fair die to reach sum >= n
// Recurrence: E[i] = 1 + (1/6) * sum(E[min(i+j, n)] for j=1..6)
// Base case: E[i] = 0 for i >= n (already reached)
function expectedRolls(n) {
const E = new Array(n + 6).fill(0); // E[i]=0 for i>=n (absorbed)
for (let i = n - 1; i >= 0; i--) {
let sumNext = 0;
for (let j = 1; j <= 6; j++) sumNext += E[Math.min(i + j, n)];
E[i] = 1 + sumNext / 6;
}
return E[0];
}Worked Problems
dices
Expected value DP recipe:
1. Define $E[s]$ = expected value from state $s$
2. Write recurrence: $E[s] = \text{cost} + \sum_i P(s \to s_i) \cdot E[s_i]$
3. Set base cases: $E[\text{absorbing}] = 0$
4. Compute backward from absorbing states
Common formulas:
- Geometric: $E[\text{trials until success}] = \frac{1}{p}$
- Coupon collector: $E[\text{collect all } n] = n \cdot H_n \approx n \ln n$
- Gambler's ruin: starting at $x$, $P(\text{reach } n \text{ before } 0) = \frac{x}{n}$ (fair coin)
DP vs formula: DP when state space is finite. Formula when pattern matches known distributions.
1. Define $E[s]$ = expected value from state $s$
2. Write recurrence: $E[s] = \text{cost} + \sum_i P(s \to s_i) \cdot E[s_i]$
3. Set base cases: $E[\text{absorbing}] = 0$
4. Compute backward from absorbing states
Common formulas:
- Geometric: $E[\text{trials until success}] = \frac{1}{p}$
- Coupon collector: $E[\text{collect all } n] = n \cdot H_n \approx n \ln n$
- Gambler's ruin: starting at $x$, $P(\text{reach } n \text{ before } 0) = \frac{x}{n}$ (fair coin)
DP vs formula: DP when state space is finite. Formula when pattern matches known distributions.