On this page

Probability & Expected-Value DP

A knight stands on a small chessboard and makes three random moves. What is the chance it is still on the board? You roll a die and walk forward on a board of squares, climbing ladders and sliding down snakes. How many rolls does a game take on average? You keep drawing cards until your score reaches 17. How likely are you to finish at 21 or less?

None of these questions has one "path" you can follow. Each has thousands or millions of possible futures, each with its own probability. Listing them one by one is hopeless. But every one of them has the same shape as the DP problems you already know: the answer for a state is built from the answers for the states one random step away. The only new ingredient is that instead of taking a min or a max over the next states, you take a weighted average, where the weights are probabilities.

This lesson is about that ingredient: how to push probability forward through a table, how to pull expected values backwards, what to do when a state can lead back to itself, and when a clever counting argument (linearity of expectation) lets you skip the DP altogether.

It assumes you know DP Foundations (state, transition, base case, fill order) and the basic language of probability: events, independence, random variables and expectation. If those words are new, read Probability for System Design first; its sections on expectation and the coupon collector are used here.

Why this exists

Probability theory itself was born as a dynamic programme. In 1654 Blaise Pascal and Pierre de Fermat exchanged letters about the problem of points: two gamblers are interrupted in the middle of a match, so how should the stakes be split fairly? Pascal's answer was a recursion: the fair share in the current position is the average of the fair shares in the two positions that one more round could lead to. That is an expected-value DP, three hundred years before Richard Bellman gave the technique its name.

Today the same recursion runs in places that have nothing to do with gambling:

  • Speech and gene recognisers use the forward algorithm of hidden Markov models: a table where alpha[t][state] is the probability of seeing the first t observations and ending in state, filled one time step at a time.
  • Reinforcement learning is built on Bellman's expected-value equation: the value of a state is the immediate reward plus the average value of the next state (Reinforcement Learning).
  • Reliability engineers compute the mean time until a RAID array loses data as the expected number of steps for a Markov chain to reach a "data lost" state.
  • Game designers balance board and card games by computing exact win probabilities and average game lengths.

All of these are the patterns in this lesson, scaled up.

Pattern triggers

If the problem says or has…Think of…
"what is the probability that…", answer is a real number with tolerance like Probability DP
"expected number of steps / moves / rolls / days"Expected-value DP, usually filled backwards from the goal
A random walk that stops after exactly stepsForward DP over (step, position); one layer per step
"each turn, with probability … otherwise stays the same"Self-loop: solve for algebraically
States that can lead back to earlier states (snakes, resets, "start over")A linear system: Gaussian elimination, or value iteration
"expected number of X" where X is a count of thingsLinearity of expectation: sum the probability of each thing, maybe no DP needed
"output the answer as "Same DP, but divide with modular inverses
Transition is "average of the previous values"Sliding-window sum, per state (New 21 Game)
"keep drawing until the total reaches "DP over the running total, stop states vs continue states
Two quantities decrease randomly until one runs out2-D DP over the remaining amounts (Soup Servings, Bag of Mice)
Huge number of steps () on a small state spaceMatrix exponentiation of the transition matrix

The meta-trigger: the future is random, but the rules for one step are fixed and known. If you can write "from state , with probability we go to state ", you can write a DP.

Intuition & first principles

Two questions you can ask about a random process

Picture a token moving between states. Each step, it picks the next state at random according to fixed rules. There are two natural questions, and they lead to two opposite fill orders.

  1. "Where is the token likely to be after steps?" Start with all probability (1.0, think "100% of a pile of sand") on the start state. Each step, every state splits its sand among the states it can move to, in proportion to the move probabilities. After steps, read off how much sand sits where. This is forward DP: the table is indexed by "steps taken so far", and it flows from the start outward.

  2. "How long, on average, until the token reaches the goal?" Here the start is the last thing you know the answer for. The goal is easy: from the goal, 0 more steps are needed. A state one step from the goal is easy next. This is backward DP: the table is indexed by "where am I now", and it flows from the goal back to the start.

An everyday picture for the second kind: you are queueing at a bakery and want to know how long you'll wait. You don't simulate everything since the shop opened. You think: "From where I am now, the next step takes about a minute, and then I'm in the position of the person in front of me." The future from a state does not care how you got there. That property, called the Markov property, is the reason both DPs work.

Two laws that do all the work

Both directions rest on one idea: split the future by what happens on the next step.

Law of total probability. If the next step goes to state with probability (and the add to 1), then

Law of total expectation (called first-step analysis when used this way). If is the expected number of steps from to the goal, then

The "1" counts the step you are about to take; the sum is the average of what remains.

A tiny example you can hold in your head

Roll two fair six-sided dice. What is the chance the total is 7?

Forward DP: after zero dice, the total is 0 with probability 1. Each die spreads every total's probability evenly over the next six totals.

  • After die 1: totals 1..6, each with probability .
  • After die 2: total 7 can come from (1 then 6), (2 then 5), …, (6 then 1). Each route has probability , and there are 6 routes, so .

The full table for two dice is the familiar triangle: for totals 2 to 12. Add a third die and the same rule gives, for example, . A Monte Carlo run (200,000 simulated triples) gave 0.1255, close to 0.125.

Now a backward example. You roll a die until you see a six. How many rolls on average? Call the answer . You roll once (that's the 1). With probability you are done; with probability you are back exactly where you started, facing the same question:

Notice what happened: the state "haven't seen a six yet" points to itself. A naive recursive function would call itself forever. But the equation has an unknown on both sides, and plain algebra solves it. That trick, the self-loop, appears again and again.

Forward or backward? A picture

flowchart LR
    subgraph fwd["Forward: probability of being somewhere"]
        S0["start: 1.0"] -->|"p"| A1["state A"]
        S0 -->|"1-p"| B1["state B"]
        A1 --> C1["after k steps"]
        B1 --> C1
    end
    subgraph bwd["Backward: expected steps to the goal"]
        G["goal: E = 0"] --> X1["one step away"]
        X1 --> X2["two steps away"]
        X2 --> ST["start: the answer"]
    end

In the forward picture, the answer sits at the far end (sum over the final layer). In the backward picture, the answer sits at the start state, and the base case is the goal.

Forward probability DPBackward expected-value DP
Typical question"probability of X after k steps""expected time / cost until X"
Base casestart state has probability 1goal states have expectation 0
Transitionpush: next[t] += cur[s] * p(s→t)pull: E[s] = cost + Σ p(s→t) · E[t]
Answera sum over the last layer (or over stop states)E[start]
Fill orderby step numberby "distance" to the goal (reverse topological order)

You can sometimes answer the same question either way (the knight problem below can be filled backwards as "probability of surviving more moves from here"). Pick the direction where the state is smallest and the order is obvious.

Mechanics

1. Forward probability: sums of dice

State: dp[i][s] = probability that the first i dice add up to s. Transition: dp[i][s] = (1/6) · Σ_{f=1..6} dp[i-1][s-f]. Base: dp[0][0] = 1. Order: by i.

This is the cleanest forward DP: each layer depends only on the previous one. Here are the first two layers, as exact fractions (computed with Python's fractions module):

Total s23456789101112
dp[2][s]1/361/181/121/95/361/65/361/91/121/181/36

And the third layer, totals 3 to 18: 1/216, 1/72, 1/36, 5/108, 5/72, 7/72, 25/216, 1/8, 1/8, 25/216, 7/72, 5/72, 5/108, 1/36, 1/72, 1/216. Every layer sums to 1, which is a free sanity check you should always run.

from fractions import Fraction


def dice_sum_distribution(num_dice: int, faces: int = 6) -> dict:
    """Exact probability of every total for num_dice fair dice."""
    dp = {0: Fraction(1)}                       # zero dice: total 0 for sure
    for _ in range(num_dice):
        nxt = {}
        for total, p in dp.items():
            for f in range(1, faces + 1):       # push p/faces to each next total
                nxt[total + f] = nxt.get(total + f, 0) + p / faces
        dp = nxt
    return dp


d3 = dice_sum_distribution(3)
assert d3[10] == Fraction(1, 8) and sum(d3.values()) == 1
assert dice_sum_distribution(2)[7] == Fraction(1, 6)

Notice the push style: each state hands its probability to its successors. The pull style (dp[i][s] = Σ dp[i-1][s-f] / 6) gives the same table. Pushing is often easier to write when the moves are "from here, go there", and pulling is easier when the question is "what can lead here".

Exact fractions are your test oracle

Python's Fraction and Java's BigInteger pairs give exact answers on small inputs. Floating-point DP is what you submit, but compare it against the exact version on tiny cases. If the two disagree beyond , your transition is wrong, not the rounding.

2. Knight probability on a chessboard (forward, k layers)

An board. A knight starts at (row, col) and makes exactly moves. Each move picks one of the 8 knight moves uniformly at random, even if it leaves the board. Once off the board it stays off. What is the probability the knight is still on the board after the moves?

graph TD
    K["knight at (r, c)"] -->|"1/8"| M1["(r-2, c-1)"]
    K -->|"1/8"| M2["(r-2, c+1)"]
    K -->|"1/8"| M3["(r-1, c-2)"]
    K -->|"1/8"| M4["(r-1, c+2)"]
    K -->|"1/8"| M5["(r+1, c-2)"]
    K -->|"1/8"| M6["(r+1, c+2)"]
    K -->|"1/8"| M7["(r+2, c-1)"]
    K -->|"1/8"| M8["(r+2, c+1)"]

State: dp[r][c] after step moves = probability that the knight is on (r,c) after step moves (and never left). Transition (push): for each on-board cell, give dp[r][c] / 8 to each of the 8 targets that are on the board. Mass sent off the board is simply dropped: that is the probability of having fallen off. Base: dp[row][col] = 1 at step 0. Answer: the sum of the final layer.

Dry run: , , start (0,0). Exact values from the test script:

After stepProbability on each cell (row by row)Total on boardWhy
0[1, 0, 0] / [0, 0, 0] / [0, 0, 0]1start
1[0, 0, 0] / [0, 0, 1/8] / [0, 1/8, 0]1/4from (0,0) only (1,2) and (2,1) are on the board; 6 of 8 moves fall off
2[1/32, 0, 1/64] / [0, 0, 0] / [1/64, 0, 0]1/16(1,2) sends 1/64 to each of (0,0), (2,0); (2,1) sends 1/64 to each of (0,0), (0,2)

So the answer is , matching the LeetCode example. Check with brute force: there are equally likely move sequences, and exactly 4 keep the knight on the board (two first moves, each followed by two good second moves). . ✔

A few more exact answers the test code checks: on a 3×3 board, from the corner gives ; on an 8×8 board, from the corner (0,0) gives exactly , and from (3,3) near the centre gives . A 200,000-trial Monte Carlo simulation gave 0.0624 and 0.1254 for the first two.

Deeper: why the probabilities on the board add up to less than 1

The table is a sub-probability distribution: its total is the probability of the event "still alive". The missing mass is the probability of having died at some earlier step. You could add an explicit "off-board" state that absorbs the dropped mass, and then each layer would sum to 1 again. That extra state is exactly an absorbing state of a Markov chain, a state you can enter but never leave. Keeping it implicit is a small optimisation; making it explicit is a great debugging check (alive + dead must equal 1).

3. Expected value, filled backwards: dice rolls on a board

A board has squares 0 to . You start on square 0 and must land exactly on square . Each turn you roll a fair die with faces . If the roll would take you past , you stay where you are (the turn is wasted). Some squares are the foot of a ladder: landing there moves you instantly up to the ladder's top. How many rolls does the game take on average?

Small example: , a three-sided die (faces 1, 2, 3; think of a spinner), and a ladder from square 2 to square 5.

graph LR
    S0["0 start"] --> S1["1"] --> S2["2 ladder foot"] --> S3["3"] --> S4["4"] --> S5["5"] --> S6["6"] --> S7["7 goal"]
    S2 -.->|"ladder"| S5

State: E[i] = expected number of further rolls when standing on square i. Base: E[n] = 0. Transition: for each face : target . If , the roll is wasted and you stay on (a self-loop). Otherwise follow the ladder if there is one. So

where is the number of faces that overshoot. Move the terms to the left and solve:

You never stand on square 2 (the ladder whisks you away), so it gets no entry. Ladders only go up, so every target is a higher square: filling from down to 0 means every value we read is already final.

Square iFaces 1, 2, 3 lead toOvershoot faces sComputationE[i]
7——goal0
67, stay, stay2(3 + 0) / (3 − 2)3
56, 7, stay1(3 + 3 + 0) / (3 − 1)3
45, 6, 70(3 + 3 + 3 + 0) / 33
34, 5, 60(3 + 3 + 3 + 3) / 34
2ladder foot—never stood on—
15 (via ladder), 3, 40(3 + 3 + 4 + 3) / 313/3 ≈ 4.333
01, 5 (via ladder), 30(3 + 13/3 + 3 + 4) / 343/9 ≈ 4.778

The game takes rolls on average. A 100,000-game Monte Carlo simulation gave 4.773. Two more checked values: a 10-square board with a normal die and exact finish takes rolls; add a ladder from 3 to 8 and it drops to .

Look at row 6: the right-hand side reads itself (two of three faces overshoot). That self-loop is handled by the division by ; no iteration and no infinite recursion.

The order must be reverse topological

"Fill from down to 0" works only because every move goes to a higher square (or stays put). The moment a square can lead to a lower one (a snake), there is no safe order: needs and needs . Section 5 handles that.

4. Self-loops: solving E = 1 + p·E

The board's "stay put" rule is a special case of a pattern that shows up everywhere: a state can lead to itself. Write the equation with the unknown on both sides, then isolate it.

General form. From state , with probability you stay in ; otherwise you go to other states with probabilities (so ). Each step costs 1:

This is valid as long as . If , you are stuck forever and the expected time is infinite; the formula would divide by zero, which is the honest answer.

stateDiagram-v2
    direction LR
    S: state s
    T: other states t
    S --> S: stay, probability p
    S --> T: leave, probability 1 - p

Three quick uses:

  • Geometric waiting time. Success with probability each try: , so . A six: 6 rolls. A 1% event: 100 tries.

  • Coupon collector. There are coupon types, each draw is a uniformly random type. Let be the expected number of further draws when you already have distinct types. A draw is a repeat with probability (self-loop) and new with probability :

    Unrolling from : , where is the -th harmonic number. For a die (): rolls to see every face. The DP with fractions gives exactly , and 100,000 simulated runs averaged 14.67. For it is about 224.96 ().

  • AtCoder "Sushi". plates with 1, 2 or 3 pieces; each turn you pick a random plate, and eat a piece if there is one. The state is "how many plates have 1, 2, 3 pieces" and picking an empty plate is a self-loop. Same algebra (full solution in the practice ladder).

from fractions import Fraction


def coupon_collector(n: int) -> Fraction:
    e = Fraction(0)                          # E[n] = 0: all types collected
    for k in range(n - 1, -1, -1):
        e = Fraction(n, n - k) + e           # E[k] = n/(n-k) + E[k+1]
    return e


assert coupon_collector(6) == Fraction(147, 10)

5. Cycles: when states point back to earlier states

Add a snake to the board: landing on square 6 slides you back to square 1. Now square 5 can lead to square 1, and square 1 can lead (through 3, 4, 5) back to square 5. There is no fill order. But the equations are still perfectly good equations. There is one per square, each linear in the unknowns:

That is a system of linear equations, and the general tool is Gaussian elimination: for unknowns. It is covered in Linear Algebra for Algorithms. For the 7-square board (three-sided die, ladder 2→5, snake 6→1), the five unknowns are squares 0, 1, 3, 4, 5. Solving with exact fractions:

Square01345
E13/2669/29/2

The snake pushes the average game from 4.78 to 6.5 rolls; 200,000 simulated games averaged 6.504.

from fractions import Fraction


def solve_board_with_snakes(n, faces, jumps):
    """E[start] for a board whose jumps may go down. Exact Gaussian elimination."""
    squares = [i for i in range(n) if i not in jumps]       # where you can stand (goal excluded)
    idx = {s: k for k, s in enumerate(squares)}
    m = len(squares)
    A = [[Fraction(0)] * (m + 1) for _ in range(m)]          # augmented matrix [A | b]
    for s in squares:
        row = A[idx[s]]
        row[idx[s]] += 1                                     # E[s] ...
        row[m] += 1                                          # ... = 1 + ...
        for d in range(1, faces + 1):
            t = s + d
            t = s if t > n else jumps.get(t, t)
            if t != n:                                       # E[n] = 0 contributes nothing
                row[idx[t]] -= Fraction(1, faces)
    for c in range(m):                                       # Gauss-Jordan elimination
        p = next(r for r in range(c, m) if A[r][c] != 0)
        A[c], A[p] = A[p], A[c]
        A[c] = [x / A[c][c] for x in A[c]]
        for r in range(m):
            if r != c and A[r][c] != 0:
                f = A[r][c]
                A[r] = [x - f * y for x, y in zip(A[r], A[c])]
    return A[idx[0]][m]


assert solve_board_with_snakes(7, 3, {2: 5, 6: 1}) == Fraction(13, 2)
assert solve_board_with_snakes(7, 3, {2: 5}) == Fraction(43, 9)   # agrees with the backward DP

Value iteration is the alternative when is large: start with and repeatedly apply . Each sweep is cheap and the error shrinks geometrically. On the snake board, the value at square 0 after 10, 50, 100 and 200 sweeps was 5.710, 6.49987, 6.4999999975 and 6.5 (to 15 digits). This is exactly how reinforcement-learning value iteration and PageRank's power iteration work.

A third option: if the cycles are only short and local (a few states pointing to each other), substitute by hand. Example: expected rolls to get two sixes in a row. States: (last roll not a six), (last roll was a six).

Substitute into the first equation: , so . (Simulation: 42.12 over 200,000 runs.)

When there is no finite answer

The linear system has a unique solution exactly when, from every state, the goal is reachable with positive probability. If some set of states can trap you forever (a snake loop with no exit), the expected time is infinite and the matrix is singular. Check reachability with a BFS on the reversed transition graph before you solve.

6. Linearity of expectation: the shortcut that skips the DP

Linearity of expectation says , always, even when and are dependent. Combine it with indicator variables (a variable that is 1 if some event happens and 0 otherwise, so its expectation is the event's probability), and many "expected count" questions collapse to one line:

Worked example. Roll a die 6 times. What is the expected number of distinct faces you see?

  • DP way. State = number of distinct faces so far. From distinct, the next roll is old with probability and new with probability . Six layers of a forward DP give the full distribution, e.g. , and the mean .
  • Linearity way. Face is never seen with probability . So . Same number, one line, no table.

More one-liners: a random permutation of items has on average exactly 1 fixed point (each item stays put with probability , and there are items; checked by enumerating all permutations for ). In random insertions into hash buckets, the expected number of empty buckets is .

The coupon collector is the same idea in disguise: the total time is a sum of the waiting times for the 1st, 2nd, …, -th new type, and each waiting time is geometric with mean . Linearity adds them up. See Probability for System Design for why it matters for cache warm-up and load testing.

When to reach for linearity first

If the question is "expected number of something" or "expected sum of something", try writing the quantity as a sum of indicators before designing any DP. If each indicator's probability is easy, you're done. If not (because the probability itself needs a DP), you have still split one hard DP into many easy ones. CSES "Moving Robots" is the classic example: one small probability DP per robot, combined with linearity.

7. Probabilities modulo a prime

Competitive programming problems often say: "the answer is a rational number ; print ". Floating point is not allowed, and exact fractions grow huge. The fix: do the same DP, but in the field of integers modulo a prime . Every operation (add, subtract, multiply) is done mod , and "divide by " becomes "multiply by the modular inverse ", the number with . For a prime , Fermat's little theorem gives , computed with fast exponentiation in (the full theory is in Modular Arithmetic).

Why this is legal: the DP only ever adds, multiplies and divides by non-zero numbers. All those operations behave the same way in the integers mod a prime as they do in the rationals, so the final residue is exactly , provided no denominator you divide by is a multiple of .

MOD = 10**9 + 7


def inv(a: int) -> int:
    return pow(a, MOD - 2, MOD)            # Fermat: a^(M-2) is a^(-1) mod a prime M


def coupon_collector_mod(n: int) -> int:
    e = 0
    for k in range(n - 1, -1, -1):
        e = (n * inv(n - k) + e) % MOD     # E[k] = n/(n-k) + E[k+1], all mod M
    return e


assert inv(6) == 166666668                  # 1/6, e.g. P(two dice total 7)
assert coupon_collector_mod(6) == 900000021 # 147/10 mod 1e9+7
assert 900000021 * 10 % MOD == 147

The residue 900000021 means nothing on its own; it is just . You cannot compare residues with <, so problems that need "maximise the probability" cannot be solved this way. They need real numbers.

Check that you can actually divide

The trick needs every denominator to be invertible mod . Dividing by or by a die's face count is safe when these are smaller than . Dividing by a quantity that might itself be (for example a probability you computed earlier, used as a denominator) is not; that case needs a different formulation.

8. New 21 Game: a sliding-window probability DP

Alice starts at 0 points. While her score is less than , she draws a number uniformly from and adds it. Once her score is at least she stops. What is the probability her final score is at most ? (LeetCode 837.)

State: dp[i] = probability that the score is ever exactly i. Transition: you can arrive at i from any score j in [i-W, i-1] at which you were still drawing (j < k), with probability 1/W:

Answer: , the probability of stopping at a score between and . (Each stop score is reached at most once, so these events are disjoint.)

Done directly, each dp[i] costs : total , which is for the upper limits. The fix is the sliding window idea: keep a running sum window of the last "still drawing" values. When dp[i] is computed, add it to window if ; drop dp[i-W] as it slides out. Each step is ; total .

Two quick exits: if she never draws (score 0 ≤ n); and the largest possible final score is , so if the answer is 1.

Dry run: , , . Exact fractions from the test script:

iWindow = sum of dp[j], j in [i−3, i−1], j < 4dp[i] = window / 3Stop or continue?
0—1continue (base)
1dp[0] = 11/3continue
21 + 1/3 = 4/34/9continue
31 + 1/3 + 4/9 = 16/916/27continue
41/3 + 4/9 + 16/27 = 37/2737/81stop (≥ k)
54/9 + 16/27 = 28/2728/81stop (≥ k)

Answer: (simulation: 0.8040). Row 5 shows the window rule: dp[2] and dp[3] are in range, dp[4] is not (at 4 she had already stopped). The missing probability is the chance of ending at 6: be at 3 (probability ) and draw a 3.

The LeetCode examples check out as well: , , and (exact value ; simulation 0.7321).

9. Soup servings: a 2-D probability DP with a twist

Two soups A and B start with ml each. Each turn, one of four operations is chosen with probability : serve (100, 0), (75, 25), (50, 50) or (25, 75) ml of (A, B), serving whatever is left if there isn't enough. Return (LeetCode 808).

Shrink the state. All amounts are multiples of 25, so measure in units of 25 ml: , and the operations become (4,0), (3,1), (2,2), (1,3).

State: f(a, b) = the requested quantity when and units remain. Base: ; ; . Transition: f(a, b) = (f(a-4, b) + f(a-3, b-1) + f(a-2, b-2) + f(a-1, b-3)) / 4.

Exact values: , , .

The twist: can be , giving a -squared table. But the operations remove 2.5 units of A per turn on average and only 1.5 of B, so for large soup A almost surely runs out first and the answer tends to 1. Running the DP upward, the answer was increasing for every we computed (up to 200 units), and first drops below (the problem's tolerance) at , i.e. . So: if (many solutions use a safer 4800 or 5000), return 1; otherwise run the DP on at most states. This "the answer converges, so cut off" argument is common in probability problems and always needs a numeric check like this one.

The ladder: brute force → better → optimal

Problem: knight probability, board, moves.

Rung 1: enumerate every move sequence

There are equally likely sequences. Simulate each one; count the ones that stay on the board; divide by .

from itertools import product

KNIGHT = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)]


def knight_brute(n, k, row, col):
    alive = 0
    for seq in product(KNIGHT, repeat=k):         # all 8^k sequences, equally likely
        r, c = row, col
        for dr, dc in seq:
            r, c = r + dr, c + dc
            if not (0 <= r < n and 0 <= c < n):
                break
        else:
            alive += 1
    return alive / 8**k


assert knight_brute(3, 2, 0, 0) == 0.0625

Time . For that is about steps; for the problem's limit it is hopeless. Still worth writing: it is the exact oracle the DP is tested against.

Rung 2: Monte Carlo simulation

Simulate random games and report the fraction that survive. Time , any . But the error shrinks only like : for accuracy you need on the order of trials. Great for checking a DP (every number in this lesson was checked this way), useless for exact answers.

Rung 3: memoised recursion over (moves left, cell)

f(m, r, c) = probability of surviving m more moves from (r,c). f(0, r, c) = 1 on the board; off the board it is 0; otherwise f(m, r, c) = (1/8) Σ f(m-1, next). There are distinct states, each with 8 transitions: time and space. This is the backward version of the same DP.

Rung 4: forward tabulation with two layers

Fill layer by layer (the code in Implementation). Same time, but only two layers: space, no recursion.

Rung 5: matrix exponentiation (huge k)

The step is a linear map on a vector of probabilities: multiply by a fixed matrix. steps = the -th power, computed with repeated squaring in . Only worth it if is astronomically large and the board is tiny; see Matrix Exponentiation.

RungMethodTimeSpaceWhy it is better than the rung above
1Enumerate all sequencesBaseline; exact; obviously correct
2Monte CarloPolynomial, any , but only approximate ()
3Memoised recursionExact and polynomial: sequences that reach the same cell at the same step are merged
4Two-layer tabulationNo recursion, memory of two layers
5Matrix powerLogarithmic in for tiny boards

The key jump is from rung 1 to rung 3: there are sequences but only distinct situations. Probability DP merges every sequence that leads to the same situation, by adding their probabilities, exactly as path counting merges routes by adding their counts.

Correctness

Forward probability DP (dice, knight). Claim: after step , dp[s] equals the probability that the process is in state after steps (and has not been absorbed). Induction on . Base: at step 0, all mass is on the start. Step: the event "in after steps" is the disjoint union, over states , of "in after steps, then moved to ". The moves are independent of the past (the Markov property), so the probability of each piece is , and the law of total probability adds them. That is exactly the push update.

Backward expected value on a DAG (ladders board). Let be the number of rolls from to the goal. Condition on the first roll: , where is the random next state. Taking expectations (law of total expectation) gives . If every move goes to a strictly later state, induction in reverse order proves each E[i] is correct when computed. With the stay-put self-loop, the equation contains on both sides; it has the unique finite solution because , and is finite because the goal is reachable (the number of rolls is dominated by a geometric random variable).

Cyclic systems. For an absorbing Markov chain (every state can reach an absorbing goal), write for the transitions among the non-goal states. The expected-steps vector satisfies , and is invertible: its inverse is the fundamental matrix, whose entry is the expected number of visits to starting from . The series converges because when absorption is certain (Kemeny and Snell, Finite Markov Chains, 1960). So Gaussian elimination finds the one and only answer, and value iteration converges to it.

Linearity of expectation. follows directly from the definition of expectation as a sum over outcomes; independence is never used. That is why it works for dependent indicators like "face is seen".

New 21 Game. Every final score is reached through a unique last draw from a score . The probability of passing through score is the sum, over in the window, of , because "passing through and then drawing " are disjoint events for different (the draw from is the one that took her past ). The sliding window computes exactly that sum.

Complexity

ProblemTimeSpaceNotes
Sum of dice with faces naive, with a prefix-sum window layers × up to totals × faces
Knight probability8 moves per cell per layer
Expected rolls, ladders onlyone backward pass
Expected rolls with snakes Gaussian elimination = squares; or by value iteration
Coupon collectoror with modular inverses
New 21 Gamesliding window; without it
Soup servings after the cut-off states below the cut-off

Numerical precision. Probability DPs add many small positive numbers, which is numerically gentle: the relative error stays around per operation with doubles. Two things can bite: subtracting nearly equal numbers (the sliding-window subtraction in New 21 can lose a few digits when is large; still well inside ), and probabilities so small they underflow below (e.g. the probability of one particular path of length 5,000). The second is why HMM implementations work with log-probabilities or rescale each layer.

Implementation

Three complete programs: knight probability (forward), expected rolls on a ladders board with an exact-finish rule (backward, with self-loops), and New 21 Game (sliding window). Each block runs its own tests on this lesson's examples. They were also compared against exact-fraction versions and Monte Carlo simulation.

Knight probability (forward DP)

from itertools import product
from typing import List

MOVES = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)]


def knight_probability(n: int, k: int, row: int, col: int) -> float:
    """Probability a knight making k uniformly random moves stays on an n x n board."""
    cur: List[List[float]] = [[0.0] * n for _ in range(n)]
    cur[row][col] = 1.0
    for _ in range(k):
        nxt = [[0.0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                p = cur[r][c]
                if p == 0.0:
                    continue
                for dr, dc in MOVES:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:   # mass sent off the board is dropped
                        nxt[nr][nc] += p / 8
        cur = nxt
    return sum(map(sum, cur))


def knight_brute(n: int, k: int, row: int, col: int) -> float:
    """Test oracle: try all 8^k move sequences."""
    alive = 0
    for seq in product(MOVES, repeat=k):
        r, c = row, col
        for dr, dc in seq:
            r, c = r + dr, c + dc
            if not (0 <= r < n and 0 <= c < n):
                break
        else:
            alive += 1
    return alive / 8 ** k


if __name__ == "__main__":
    assert abs(knight_probability(3, 2, 0, 0) - 0.0625) < 1e-12
    assert knight_probability(1, 0, 0, 0) == 1.0
    assert abs(knight_probability(3, 3, 0, 0) - 1 / 64) < 1e-12
    assert abs(knight_probability(8, 3, 0, 0) - 0.125) < 1e-12
    assert abs(knight_probability(8, 3, 3, 3) - 159 / 256) < 1e-12
    for n in range(1, 6):
        for k in range(0, 4):
            assert abs(knight_probability(n, k, 0, n // 2) - knight_brute(n, k, 0, n // 2)) < 1e-12
    print("knight tests passed")
public class KnightProbability {
    static final int[][] MOVES = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};

    static double knightProbability(int n, int k, int row, int col) {
        double[][] cur = new double[n][n];
        cur[row][col] = 1.0;
        for (int step = 0; step < k; step++) {
            double[][] nxt = new double[n][n];
            for (int r = 0; r < n; r++)
                for (int c = 0; c < n; c++) {
                    double p = cur[r][c];
                    if (p == 0.0) continue;
                    for (int[] m : MOVES) {
                        int nr = r + m[0], nc = c + m[1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n)
                            nxt[nr][nc] += p / 8;          // off-board mass is dropped
                    }
                }
            cur = nxt;
        }
        double total = 0;
        for (double[] line : cur) for (double p : line) total += p;
        return total;
    }

    public static void main(String[] args) {
        check(Math.abs(knightProbability(3, 2, 0, 0) - 0.0625) < 1e-12);
        check(knightProbability(1, 0, 0, 0) == 1.0);
        check(Math.abs(knightProbability(3, 3, 0, 0) - 1.0 / 64) < 1e-12);
        check(Math.abs(knightProbability(8, 3, 0, 0) - 0.125) < 1e-12);
        check(Math.abs(knightProbability(8, 3, 3, 3) - 159.0 / 256) < 1e-12);
        System.out.println("knight tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

double knightProbability(int n, int k, int row, int col) {
    const int MOVES[8][2] = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
    vector<vector<double>> cur(n, vector<double>(n, 0.0));
    cur[row][col] = 1.0;
    for (int step = 0; step < k; step++) {
        vector<vector<double>> nxt(n, vector<double>(n, 0.0));
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {
                double p = cur[r][c];
                if (p == 0.0) continue;
                for (const auto& m : MOVES) {
                    int nr = r + m[0], nc = c + m[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n)
                        nxt[nr][nc] += p / 8;              // off-board mass is dropped
                }
            }
        cur.swap(nxt);
    }
    double total = 0;
    for (const auto& line : cur)
        for (double p : line) total += p;
    return total;
}

int main() {
    assert(fabs(knightProbability(3, 2, 0, 0) - 0.0625) < 1e-12);
    assert(knightProbability(1, 0, 0, 0) == 1.0);
    assert(fabs(knightProbability(3, 3, 0, 0) - 1.0 / 64) < 1e-12);
    assert(fabs(knightProbability(8, 3, 0, 0) - 0.125) < 1e-12);
    assert(fabs(knightProbability(8, 3, 3, 3) - 159.0 / 256) < 1e-12);
    cout << "knight tests passed\n";
    return 0;
}
const MOVES: Array<[number, number]> = [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]];

function knightProbability(n: number, k: number, row: number, col: number): number {
  let cur: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  cur[row][col] = 1;
  for (let step = 0; step < k; step++) {
    const nxt: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
    for (let r = 0; r < n; r++)
      for (let c = 0; c < n; c++) {
        const p = cur[r][c];
        if (p === 0) continue;
        for (const [dr, dc] of MOVES) {
          const nr = r + dr, nc = c + dc;
          if (nr >= 0 && nr < n && nc >= 0 && nc < n) nxt[nr][nc] += p / 8; // off-board mass is dropped
        }
      }
    cur = nxt;
  }
  let total = 0;
  for (const line of cur) for (const p of line) total += p;
  return total;
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(Math.abs(knightProbability(3, 2, 0, 0) - 0.0625) < 1e-12);
check(knightProbability(1, 0, 0, 0) === 1);
check(Math.abs(knightProbability(3, 3, 0, 0) - 1 / 64) < 1e-12);
check(Math.abs(knightProbability(8, 3, 0, 0) - 0.125) < 1e-12);
check(Math.abs(knightProbability(8, 3, 3, 3) - 159 / 256) < 1e-12);
console.log("knight tests passed");

Expected rolls on a board (backward DP with self-loops)

The board has squares 0..n, a die with faces 1..f, an exact-finish rule (overshooting rolls are wasted), and ladders given as foot → top. The function refuses snakes (a jump downwards), because then the backward order does not exist and you need the linear-system solver from section 5.

import random
from typing import Dict


def expected_rolls(n: int, faces: int, ladders: Dict[int, int]) -> float:
    """Expected rolls to land exactly on square n, starting from 0. Ladders only go up."""
    for foot, top in ladders.items():
        if not (0 < foot < top <= n) or top in ladders:
            raise ValueError("ladders must go up, start after 0, and not chain")
    E = [0.0] * (n + 1)                       # E[n] = 0: already at the goal
    for i in range(n - 1, -1, -1):
        if i in ladders:
            continue                          # you never stand on a ladder's foot
        stay, total = 0, 0.0
        for d in range(1, faces + 1):
            t = i + d
            if t > n:
                stay += 1                     # overshoot: wasted roll, a self-loop
            else:
                total += E[ladders.get(t, t)]
        E[i] = (faces + total) / (faces - stay)   # E = 1 + (total + stay*E)/faces, solved for E
    return E[0]


def simulate(n: int, faces: int, ladders: Dict[int, int], games: int, rng: random.Random) -> float:
    rolls = 0
    for _ in range(games):
        pos = 0
        while pos != n:
            rolls += 1
            t = pos + rng.randint(1, faces)
            if t <= n:
                pos = ladders.get(t, t)
    return rolls / games


if __name__ == "__main__":
    assert abs(expected_rolls(7, 3, {2: 5}) - 43 / 9) < 1e-12
    assert abs(expected_rolls(10, 6, {}) - 1639 / 216) < 1e-12
    assert abs(expected_rolls(10, 6, {3: 8}) - 265 / 36) < 1e-12
    assert abs(expected_rolls(6, 6, {}) - 6.0) < 1e-12
    assert expected_rolls(1, 6, {}) == 6.0          # need exactly a 1
    mc = simulate(7, 3, {2: 5}, 50_000, random.Random(42))
    assert abs(mc - 43 / 9) < 0.05
    try:
        expected_rolls(7, 3, {6: 1})                # a snake: not allowed here
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
    print("board tests passed")
import java.util.HashMap;
import java.util.Map;

public class BoardExpectedRolls {
    /** Expected rolls to land exactly on square n from 0. Ladders (foot -> top) only go up. */
    static double expectedRolls(int n, int faces, Map<Integer, Integer> ladders) {
        for (Map.Entry<Integer, Integer> e : ladders.entrySet()) {
            int foot = e.getKey(), top = e.getValue();
            if (!(0 < foot && foot < top && top <= n) || ladders.containsKey(top))
                throw new IllegalArgumentException("ladders must go up, start after 0, and not chain");
        }
        double[] E = new double[n + 1];                    // E[n] = 0
        for (int i = n - 1; i >= 0; i--) {
            if (ladders.containsKey(i)) continue;          // never stand on a ladder's foot
            int stay = 0;
            double total = 0;
            for (int d = 1; d <= faces; d++) {
                int t = i + d;
                if (t > n) stay++;                         // wasted roll: self-loop
                else total += E[ladders.getOrDefault(t, t)];
            }
            E[i] = (faces + total) / (faces - stay);
        }
        return E[0];
    }

    public static void main(String[] args) {
        Map<Integer, Integer> one = new HashMap<>();
        one.put(2, 5);
        check(Math.abs(expectedRolls(7, 3, one) - 43.0 / 9) < 1e-12);
        check(Math.abs(expectedRolls(10, 6, new HashMap<>()) - 1639.0 / 216) < 1e-12);
        Map<Integer, Integer> l38 = new HashMap<>();
        l38.put(3, 8);
        check(Math.abs(expectedRolls(10, 6, l38) - 265.0 / 36) < 1e-12);
        check(Math.abs(expectedRolls(6, 6, new HashMap<>()) - 6.0) < 1e-12);
        Map<Integer, Integer> snake = new HashMap<>();
        snake.put(6, 1);
        boolean threw = false;
        try { expectedRolls(7, 3, snake); } catch (IllegalArgumentException ex) { threw = true; }
        check(threw);
        System.out.println("board tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <stdexcept>
#include <vector>
using namespace std;

// Expected rolls to land exactly on square n from 0. Ladders (foot -> top) only go up.
double expectedRolls(int n, int faces, const map<int, int>& ladders) {
    for (const auto& [foot, top] : ladders)
        if (!(0 < foot && foot < top && top <= n) || ladders.count(top))
            throw invalid_argument("ladders must go up, start after 0, and not chain");
    vector<double> E(n + 1, 0.0);                          // E[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        if (ladders.count(i)) continue;                    // never stand on a ladder's foot
        int stay = 0;
        double total = 0;
        for (int d = 1; d <= faces; d++) {
            int t = i + d;
            if (t > n) { stay++; continue; }               // wasted roll: self-loop
            auto it = ladders.find(t);
            total += E[it == ladders.end() ? t : it->second];
        }
        E[i] = (faces + total) / (faces - stay);
    }
    return E[0];
}

int main() {
    assert(fabs(expectedRolls(7, 3, {{2, 5}}) - 43.0 / 9) < 1e-12);
    assert(fabs(expectedRolls(10, 6, {}) - 1639.0 / 216) < 1e-12);
    assert(fabs(expectedRolls(10, 6, {{3, 8}}) - 265.0 / 36) < 1e-12);
    assert(fabs(expectedRolls(6, 6, {}) - 6.0) < 1e-12);
    bool threw = false;
    try { expectedRolls(7, 3, {{6, 1}}); } catch (const invalid_argument&) { threw = true; }
    assert(threw);
    cout << "board tests passed\n";
    return 0;
}
// Expected rolls to land exactly on square n from 0. Ladders (foot -> top) only go up.
function expectedRolls(n: number, faces: number, ladders: Map<number, number>): number {
  for (const [foot, top] of ladders)
    if (!(0 < foot && foot < top && top <= n) || ladders.has(top))
      throw new Error("ladders must go up, start after 0, and not chain");
  const E: number[] = new Array(n + 1).fill(0); // E[n] = 0
  for (let i = n - 1; i >= 0; i--) {
    if (ladders.has(i)) continue; // never stand on a ladder's foot
    let stay = 0, total = 0;
    for (let d = 1; d <= faces; d++) {
      const t = i + d;
      if (t > n) stay++; // wasted roll: self-loop
      else total += E[ladders.get(t) ?? t];
    }
    E[i] = (faces + total) / (faces - stay);
  }
  return E[0];
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(Math.abs(expectedRolls(7, 3, new Map([[2, 5]])) - 43 / 9) < 1e-12);
check(Math.abs(expectedRolls(10, 6, new Map()) - 1639 / 216) < 1e-12);
check(Math.abs(expectedRolls(10, 6, new Map([[3, 8]])) - 265 / 36) < 1e-12);
check(Math.abs(expectedRolls(6, 6, new Map()) - 6) < 1e-12);
let threw = false;
try { expectedRolls(7, 3, new Map([[6, 1]])); } catch { threw = true; }
check(threw);
console.log("board tests passed");

New 21 Game (sliding-window probability)

import random


def new21_game(n: int, k: int, w: int) -> float:
    """P(final score <= n) when drawing 1..w uniformly while the score is below k."""
    if k == 0 or n >= k - 1 + w:
        return 1.0                       # never draws, or can never exceed n
    dp = [0.0] * (n + 1)
    dp[0] = 1.0
    window = 1.0                         # sum of dp[j] for j in [i-w, i-1] with j < k
    answer = 0.0
    for i in range(1, n + 1):
        dp[i] = window / w
        if i < k:
            window += dp[i]              # still drawing from i: feeds later scores
        else:
            answer += dp[i]              # stopped at i (k <= i <= n)
        if 0 <= i - w < k:
            window -= dp[i - w]          # slides out of the window
    return answer


def new21_naive(n: int, k: int, w: int) -> float:
    """O(n*w) version without the window, as a test oracle."""
    top = k - 1 + w
    dp = [0.0] * (top + 1)
    dp[0] = 1.0
    for i in range(1, top + 1):
        dp[i] = sum(dp[j] for j in range(max(0, i - w), min(i, k))) / w
    return sum(dp[k:n + 1]) if k > 0 else 1.0


if __name__ == "__main__":
    assert new21_game(10, 1, 10) == 1.0
    assert abs(new21_game(6, 1, 10) - 0.6) < 1e-12
    assert abs(new21_game(21, 17, 10) - 0.73278) < 1e-5
    assert abs(new21_game(5, 4, 3) - 65 / 81) < 1e-12
    assert new21_game(0, 0, 1) == 1.0
    rng = random.Random(3)
    for _ in range(300):
        k = rng.randint(0, 12)
        w = rng.randint(1, 8)
        n = rng.randint(k, k + w + 2)
        assert abs(new21_game(n, k, w) - new21_naive(n, k, w)) < 1e-12
    print("new21 tests passed")
public class New21Game {
    static double new21Game(int n, int k, int w) {
        if (k == 0 || n >= k - 1 + w) return 1.0;      // never draws, or can never exceed n
        double[] dp = new double[n + 1];
        dp[0] = 1.0;
        double window = 1.0, answer = 0.0;            // window = sum of dp[j], j in [i-w, i-1], j < k
        for (int i = 1; i <= n; i++) {
            dp[i] = window / w;
            if (i < k) window += dp[i];               // still drawing from i
            else answer += dp[i];                     // stopped at i
            if (i - w >= 0 && i - w < k) window -= dp[i - w];
        }
        return answer;
    }

    public static void main(String[] args) {
        check(new21Game(10, 1, 10) == 1.0);
        check(Math.abs(new21Game(6, 1, 10) - 0.6) < 1e-12);
        check(Math.abs(new21Game(21, 17, 10) - 0.73278) < 1e-5);
        check(Math.abs(new21Game(5, 4, 3) - 65.0 / 81) < 1e-12);
        check(new21Game(0, 0, 1) == 1.0);
        System.out.println("new21 tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

double new21Game(int n, int k, int w) {
    if (k == 0 || n >= k - 1 + w) return 1.0;        // never draws, or can never exceed n
    vector<double> dp(n + 1, 0.0);
    dp[0] = 1.0;
    double window = 1.0, answer = 0.0;              // window = sum of dp[j], j in [i-w, i-1], j < k
    for (int i = 1; i <= n; i++) {
        dp[i] = window / w;
        if (i < k) window += dp[i];                 // still drawing from i
        else answer += dp[i];                       // stopped at i
        if (i - w >= 0 && i - w < k) window -= dp[i - w];
    }
    return answer;
}

int main() {
    assert(new21Game(10, 1, 10) == 1.0);
    assert(fabs(new21Game(6, 1, 10) - 0.6) < 1e-12);
    assert(fabs(new21Game(21, 17, 10) - 0.73278) < 1e-5);
    assert(fabs(new21Game(5, 4, 3) - 65.0 / 81) < 1e-12);
    assert(new21Game(0, 0, 1) == 1.0);
    cout << "new21 tests passed\n";
    return 0;
}
function new21Game(n: number, k: number, w: number): number {
  if (k === 0 || n >= k - 1 + w) return 1; // never draws, or can never exceed n
  const dp: number[] = new Array(n + 1).fill(0);
  dp[0] = 1;
  let window = 1, answer = 0; // window = sum of dp[j], j in [i-w, i-1], j < k
  for (let i = 1; i <= n; i++) {
    dp[i] = window / w;
    if (i < k) window += dp[i]; // still drawing from i
    else answer += dp[i]; // stopped at i
    if (i - w >= 0 && i - w < k) window -= dp[i - w];
  }
  return answer;
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(new21Game(10, 1, 10) === 1);
check(Math.abs(new21Game(6, 1, 10) - 0.6) < 1e-12);
check(Math.abs(new21Game(21, 17, 10) - 0.73278) < 1e-5);
check(Math.abs(new21Game(5, 4, 3) - 65 / 81) < 1e-12);
check(new21Game(0, 0, 1) === 1);
console.log("new21 tests passed");

Notes on the choices: the knight code skips cells with zero probability, which makes small fast (the reachable region grows slowly). The board code divides by faces - stay, which is never zero because a roll of 1 always lands (every non-goal square has a square after it). New 21 checks i - w < k before subtracting, because only values with were ever added to the window.

Real-world uses

  • Hidden Markov models (speech, handwriting, genomics). The forward algorithm is a forward probability DP: . Its "max" twin, the Viterbi algorithm, finds the most likely hidden state sequence. Classic speech recognisers and gene finders such as GENSCAN ran these tables (Rabiner, Proc. IEEE 1989; Burge and Karlin, 1997).
  • Reinforcement learning and planning. Markov decision processes are expected-value DPs with a max over actions: . Value iteration is the "sweep until it converges" method from section 5 (Bellman, 1957; Sutton and Barto, Reinforcement Learning, 2nd ed. 2018). See Reinforcement Learning.
  • PageRank. A random surfer's long-run probability of being on each page is the stationary distribution of a Markov chain, computed by repeated forward steps (power iteration), the same push update as the knight DP (Brin and Page, 1998).
  • Storage reliability. Mean time to data loss for RAID and erasure-coded storage is computed from Markov models whose states are "number of failed disks" and whose absorbing state is "data lost": exactly the expected-time-to-absorption system of section 5 (Patterson, Gibson and Katz, SIGMOD 1988, give the RAID MTTF formulas).
  • Game design and analysis. Snakes and Ladders, Monopoly and Risk are classic absorbing-chain exercises; Althoen, King and Schilling analysed the length of a Snakes and Ladders game this way ("How long is a game of Snakes and Ladders?", The Mathematical Gazette, 1993). Blackjack strategy tables are expected-value DPs over (player total, dealer card).
  • Retry and timeout budgets. "How many attempts until success with per-try success probability ?" is the geometric self-loop ; "what is the chance all of retries fail?" is a forward product. See Probability for System Design.
  • Sports analytics. Win-probability models in tennis (point → game → set → match) and expected-points models in American football are probability DPs over the score state.

Pitfalls & edge cases

  • Counting the probability, not the paths. Adding path counts and dividing by the total only works when all paths are equally likely. In the knight problem they are ( sequences); in the board problem with exact finish they are not (games have different lengths). Push probabilities, not counts.
  • Forgetting the self-loop. Writing E[i] = 1 + avg(E[next]) and skipping the "stay put" outcomes gives a number that is too small. Every outcome of a step, including "nothing changed", must appear in the average.
  • Dividing by zero in the self-loop formula. means the state is a trap: the expectation is infinite. Decide what the problem wants (often it guarantees this cannot happen).
  • Recursing on a cycle. A memoised recursion that calls E(1) while computing E(1) either overflows the stack or reads an uninitialised value. Cycles need algebra, a linear system, or iteration.
  • Wrong absorption rule. In the knight problem, mass leaving the board must never come back. In New 21, scores must not feed later scores. Both are "absorbing state" rules; forgetting them over-counts.
  • Floating-point comparisons. Test with a tolerance (abs(a - b) < 1e-9), never ==, except when the value is exactly representable.
  • Underflow. The probability of a specific long sequence can drop below the smallest double. Use logarithms or rescale per layer (standard in HMMs).
  • Modular answers and "maximise". Residues cannot be compared; a DP with max over probabilities needs real numbers.
  • Inverting zero mod p. If a denominator is a multiple of the modulus, the modular inverse does not exist. With or and denominators below this cannot happen, but check if denominators are products of large numbers.
  • Soup-style cut-offs without a check. "For large the answer is about 1" must be backed by computing where the error drops below the tolerance.

Variations

  • Expected value of a sum (rewards on edges). Replace the "+1" with the reward of the step: .
  • Optimal stopping and decisions. Add a max over actions: "stop now and take the reward, or continue and take the expected value". This is a Markov decision process. Example: the "secretary" family and most dice-game strategy problems.
  • Expectiminimax. Game trees with chance nodes (backgammon): max nodes, min nodes and average nodes. The deterministic part is covered in Game DP.
  • Probability over subsets. When the state is "which items are still alive", use a bitmask: Bitmask DP.
  • Probability on trees. "Probability that node is reached / infected" is a probability DP over a tree: Tree DP.
  • Huge step counts. steps on a small chain: the transition matrix to the -th power. See Matrix Exponentiation.
  • Expected value of the maximum/minimum. , and for independent uniform draws. No DP needed.
  • Inclusion–exclusion and generating functions. For sums of many independent variables, multiply polynomials (probability generating functions); with FFT this becomes instead of . See FFT and NTT.
  • The full theory. Expected value, variance, conditional expectation and the classic distributions are treated in Probability & Expected Value in the math module.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Dice Probability (CSES 1725) — Throw dice; find the probability that the total lies between and . Teaches the basic forward layer DP.

Solution

The dice-sum DP from section 1 with floats, then sum the range. .

def dice_probability(n, a, b):
    dp = [1.0]                                   # dp[s] after 0 dice
    for _ in range(n):
        nxt = [0.0] * (len(dp) + 6)
        for s, p in enumerate(dp):
            if p:
                for f in range(1, 7):
                    nxt[s + f] += p / 6
        dp = nxt
    return sum(dp[a:b + 1])


assert abs(dice_probability(2, 9, 10) - 7 / 36) < 1e-12
assert abs(dice_probability(3, 10, 10) - 1 / 8) < 1e-12

2. Knight Probability in Chessboard (LeetCode 688) — The forward knight DP from this lesson.

Hint

Two layers; drop mass that leaves the board. The Implementation section is a full solution.

3. Coins (AtCoder DP Contest I) — (odd) coins, coin shows heads with probability . Probability that heads outnumber tails. Teaches the "number of successes so far" forward DP with unequal probabilities.

Solution

dp[h] = probability of exactly h heads among the coins seen so far. Each coin: dp[h] = dp[h] * (1 - p) + dp[h-1] * p, updated right to left so each coin is used once (same in-place trick as 0/1 knapsack). Answer: sum of dp[h] for h > N/2. .

def coins(ps):
    dp = [1.0] + [0.0] * len(ps)
    for i, p in enumerate(ps, 1):
        for h in range(i, -1, -1):             # right to left: each coin used once
            dp[h] = dp[h] * (1 - p) + (dp[h - 1] * p if h else 0.0)
    return sum(dp[len(ps) // 2 + 1:])


assert abs(coins([0.30, 0.60, 0.80]) - 0.612) < 1e-9
assert abs(coins([0.50]) - 0.5) < 1e-9

4. Airplane Seat Assignment Probability (LeetCode 1227) — The first passenger sits in a random seat; everyone else takes their own seat if free, otherwise a random free seat. Probability the last passenger gets their own seat. Teaches writing the DP, then spotting the closed form.

Solution

Let be the answer. Passenger 1 picks seat 1 (prob , everyone happy), seat (prob , last passenger loses), or seat in between: then passengers sit normally and passenger is in the same situation as passenger 1 with seats. So . Computing it shows and for every (a symmetry argument: seats 1 and are equally likely to be taken first).

from fractions import Fraction


def seat_dp(n):
    f = [Fraction(0), Fraction(1)]
    for m in range(2, n + 1):
        f.append(Fraction(1, m) + Fraction(1, m) * sum(f[2:m]))
    return f[n]


assert seat_dp(1) == 1
assert all(seat_dp(n) == Fraction(1, 2) for n in range(2, 30))

5. Little Pony and Expected Maximum (Codeforces 453A) — Expected maximum of rolls of an -sided die. Teaches "" thinking instead of a DP.

Hint

. Use pow on doubles; for it is 3.5 and for it is 1.75.

6. New 21 Game (LeetCode 837) — The sliding-window DP from section 8.

Hint

dp[i] = window / W; add to the window only while i < k. Shortcut: if k == 0 or n >= k - 1 + W, return 1.

7. Ilya and Escalator (Codeforces 518D) — Each second, the person at the head of a queue steps on an escalator with probability . Expected number of people on the escalator after seconds. Teaches a forward DP over (time, people boarded) with an absorbing "everyone boarded" state.

Hint

dp[i][j] = probability that after i seconds exactly j people boarded. If j < n: dp[i+1][j+1] += p·dp[i][j], dp[i+1][j] += (1-p)·dp[i][j]; if j == n, all mass stays. Answer: .

8. Soup Servings (LeetCode 808) — Section 9's 2-D DP plus the large- cut-off.

Hint

Units of 25 ml; memoise f(a, b); return 1 when is above a numerically checked threshold (≈ 4475; 4800 is a common safe choice).

9. Sushi (AtCoder DP Contest J) — plates with 1 to 3 pieces each; roll a fair -sided die and eat from that plate if it isn't empty. Expected number of rolls to eat everything. Teaches self-loops with a multi-dimensional state.

Solution

Plates are interchangeable, so the state is = number of plates with 1, 2, 3 pieces; are empty. Choosing an empty plate (probability ) is a self-loop. Solving for :

Fill in increasing order of , then , then (eating from a 3-plate raises , so must be the outer loop).

def sushi(plates):
    n = len(plates)
    cnt = [plates.count(i) for i in range(4)]
    A, B, C = cnt[1] + cnt[2] + cnt[3], cnt[2] + cnt[3], cnt[3]   # upper bounds per count
    E = [[[0.0] * (C + 1) for _ in range(B + 1)] for _ in range(A + 1)]
    for c in range(C + 1):
        for b in range(B + 1 - c):
            for a in range(A + 1 - b - c):
                s = a + b + c
                if s == 0:
                    continue
                v = n
                if a:
                    v += a * E[a - 1][b][c]
                if b:
                    v += b * E[a + 1][b - 1][c]
                if c:
                    v += c * E[a][b + 1][c - 1]
                E[a][b][c] = v / s
    return E[cnt[1]][cnt[2]][cnt[3]]


assert abs(sushi([1, 1, 1]) - 5.5) < 1e-9
assert abs(sushi([3]) - 3.0) < 1e-9
assert abs(sushi([1, 2]) - 4.5) < 1e-9
assert abs(sushi([1, 3, 2, 3, 3, 2, 3, 2, 1, 3]) - 54.48064457488221) < 1e-9

10. Bag of mice (Codeforces 148D) — A princess and a dragon take turns drawing mice from a bag of white and black; the first to draw white wins; each time the dragon draws, one more mouse jumps out at random. Probability the princess wins. Teaches a 2-D DP with several random events per turn.

Solution

P(w, b) = princess's winning probability when it's her turn. She wins at once with . Otherwise she drew black, the dragon must also draw black, and then one random mouse escapes (white or black). Two terms, each a product of three fractions.

from functools import lru_cache


@lru_cache(maxsize=None)
def princess(w, b):
    if w <= 0:
        return 0.0
    if b <= 0:
        return 1.0
    total = w + b
    win = w / total
    if b >= 2:                                   # princess black, dragon black
        pb = b / total * (b - 1) / (total - 1)
        rest = total - 2
        if rest > 0:
            win += pb * (w / rest) * princess(w - 1, b - 2)          # a white mouse jumps out
            if b >= 3:
                win += pb * ((b - 2) / rest) * princess(w, b - 3)    # a black mouse jumps out
    return win


assert abs(princess(1, 3) - 0.5) < 1e-9
assert abs(princess(5, 5) - 0.658730159) < 1e-9

11. Moving Robots (CSES 1726) — 64 robots on a chessboard, each moving to a random neighbouring square times. Expected number of empty squares. Teaches linearity plus one small DP per robot.

Hint

For each robot, a forward DP gives . Square is empty with probability (robots move independently). Sum over squares by linearity.

12. Probability of a Two Boxes Having The Same Number of Distinct Balls (LeetCode 1467) — Shuffle coloured balls and split them into two halves. Probability that both halves contain the same number of distinct colours. Teaches counting with multinomials (or a DP over colours with the balance as state).

Hint

For each colour, choose how many of its balls go to box 1. Track (balls in box 1, distinct colours in box 1, distinct colours in box 2) and weight each choice by . Divide by .

13. Toss Strange Coins (LeetCode 1230, premium) — Probability that exactly target of biased coins show heads. Teaches the same DP as "Coins", with an exact target.

Hint

Identical to problem 3; return dp[target] instead of a suffix sum.

Common mistakes & interview follow-ups

"Why can't you just count paths and divide?" Only if every path has the same probability. Show New 21 or the exact-finish board, where paths have different lengths and probabilities.

"What if the knight's board is 1000 × 1000 and ?" cell updates × 8 moves: borderline. Mention that only cells within of the start are reachable, and that the board's symmetry can cut the work by up to 8.

"Do it for ." Matrix exponentiation of the transition matrix, if the state space is small.

"Your board has snakes now." The backward order breaks. Explain the linear system, Gaussian elimination in , value iteration as the scalable alternative, and the reachability condition for a finite answer.

"Expected number of X" — and you start writing a DP. Interviewers love to see linearity of expectation. Try indicators first.

"Is linearity of expectation valid if the events are dependent?" Yes. That is its whole power. Variance, however, does not add for dependent variables.

"Print the probability modulo ." Same DP, every division becomes multiplication by a modular inverse via Fermat's little theorem.

Mistakes interviewers watch for: forgetting self-loops; letting absorbed mass re-enter; integer division (1/8 == 0 in Java/C++); comparing doubles with ==; recursion on cyclic states; using counts instead of probabilities.

Quick quiz

1. A step succeeds with probability ; on failure you start over. Expected number of steps?

Answer

, so .

2. In the 3×3 knight dry run, why is the probability on (0,0) after two moves and not ?

Answer

Two different cells, (1,2) and (2,1), each hold after move 1 and each send to (0,0). The two routes add: .

3. On the ladder board, why does square 6 have even though it is one step from the goal?

Answer

Only one of the three faces (a 1) lands exactly on 7; the other two overshoot and waste the roll. It is a geometric wait with success probability : .

4. You throw 10 balls into 10 bins uniformly at random. Expected number of empty bins?

Answer

By linearity, .

5. In New 21 Game, why must dp[i] for not be added to the window?

Answer

At a score of or more Alice has stopped drawing, so no later score can be reached from it. Adding it would create probability from nowhere.

6. Why does Gaussian elimination on the snakes board always give a unique answer, and when would it fail?

Answer

If the goal is reachable from every square, the matrix is invertible (absorbing Markov chain theory), so the solution is unique. It fails (singular matrix, infinite expectation) if some squares form a trap with no way to the goal.

Further reading / sources

  • John G. Kemeny and J. Laurie Snell, Finite Markov Chains (1960) — absorbing chains, the fundamental matrix, expected time to absorption.
  • Sheldon Ross, A First Course in Probability — conditioning, first-step analysis, linearity of expectation, the coupon collector.
  • Richard Bellman, Dynamic Programming (1957), and Ronald A. Howard, Dynamic Programming and Markov Processes (1960).
  • Lawrence R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition", Proceedings of the IEEE 77(2), 1989.
  • Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (2018) — value iteration and Bellman equations.
  • Michael Mitzenmacher and Eli Upfal, Probability and Computing (2nd ed., 2017) — linearity of expectation, coupon collector, Markov chains for algorithms.
  • S. C. Althoen, L. King and K. Schilling, "How long is a game of Snakes and Ladders?", The Mathematical Gazette 77(478), 1993.
  • cp-algorithms, Gauss method for solving a system of linear equations and Binary exponentiation.
  • AtCoder Educational DP Contest, problem list — I (Coins) and J (Sushi) are probability DPs.
  • CSES Problem Set, Mathematics section — Dice Probability, Moving Robots, Candy Lottery, Inversion Probability.

Lessons: previous — Counting DP · next — Game DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Probability for System Design · Probabilistic Data Structures · Sliding Window · Grid & Path DP · Reinforcement Learning · Randomized Algorithms · Matrix Exponentiation.