Pattern Guide
Random Walk & Expected Value
"Expected number of steps in random processes. Linear system or DP on states."
Random walk problems compute expected values: expected steps to reach a target, expected number of failures before success, expected cost in stochastic processes. Technique: define E[state] = expected value from that state, write recurrence, solve backward from absorbing states. Key formulas: geometric distribution, gambler's ruin, absorbing Markov chains.
Problems you can solve with this pattern
3 problems · click any to start solving
// 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];
}**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 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];
}1. Define = expected value from state
2. Write recurrence:
3. Set base cases:
4. Compute backward from absorbing states
Common formulas:
- Geometric:
- Coupon collector:
- Gambler's ruin: starting at , (fair coin)
DP vs formula: DP when state space is finite. Formula when pattern matches known distributions.