xi. DAG and Expected-Value DP

Every DP is a computation over a DAG of states. When the states form an actual graph, process them in topological order (or condense SCCs first). Probability DPs push mass forward from the start; expectation DPs pull backward from terminal states. Self-loops are solved algebraically, general cycles by Gaussian elimination, and cycles with special structure (a line, a tree) by expressing each value as a linear function of one neighbour. The probability theory itself is in Probability and Expectation.

DP on a DAG

Question	Recurrence in topological order
longest / shortest path (any weights)	`dp[v] = max/min(dp[u] + w)`
number of paths	`cnt[v] += cnt[u]`
number of shortest paths	carry (dist, count), reset the count on strict improvement
reachability for all pairs	reverse order, `reach[u]
lexicographically smallest optimal path	build backwards so the choice at each vertex is local
cyclic graph, value collected per vertex	condense SCCs, weight each by its total (SCC)

Longest path is NP-hard in general graphs and linear on DAGs: with no cycles, the best path to $v$ extends the best path to some predecessor.

Most classical DPs are exactly this, in disguise — recognising the DAG gives the complexity immediately (states × transitions):

Problem	The DAG
grid paths	cells; edges right and down
LCS	$(i, j)$ pairs; edges advance one or both indices
LIS	indices; edge $i \to j$ when $i < j$ and $a_{i} < a_{j}$
knapsack	(item, capacity)
interval DP	intervals; edges to shorter sub-intervals
bitmask DP	subsets; edges add one element
course scheduling / build systems	prerequisites / dependencies

Two pitfalls specific to path-counting: a zero-weight cycle is still a cycle — verify the graph is genuinely acyclic before trusting a path count; and unreachable states must not contribute (initialise to 0 for counts, $- \infty$ for maxima, and skip them during relaxation rather than letting stale values leak in). For lexicographically-smallest reconstruction, break ties on the parent’s label at relaxation time, not by post-processing afterwards.

Probability and expectation DPs

Forward: $P [start] = 1$ ; push $P [t] + = P [s] \cdot p_{s \to t}$ in topological order. Answers “probability of ending in state $X$ ”.
Backward: $E [s] = \sum_{t} p_{s \to t} (c_{s \to t} + E [t])$ , terminal states 0. Answers “expected cost/time from $s$ ”.
Linearity first: $E [\sum X_{i}] = \sum E [X_{i}]$ always; many “expected count” problems are a sum of per-item probabilities and need no DP. E.g. expected fixed points of a random permutation: each element is fixed with probability $1/ n$ , so the answer is $n \cdot \frac{1}{n} = 1$ , with no DP at all.
Randomness plus optimal play: when both players play optimally and some transitions are random, it’s game DP with an expectation taken at the chance nodes, not a pure expectation DP.
$E [max]$ or $E [min]$ of integer variables: $E [X] = \sum_{k \geq 1} Pr [X \geq k]$ .
Modular answers: represent $p / q$ as $p \cdot q^{- 1} mod P$ ; everything above stays exact.

// Bad Luck Island (r rocks, s scissors, p papers meet uniformly at random): survival probabilities, forward DP
array<double, 3> island(int R, int S, int P) {
    vector dp(R + 1, vector(S + 1, vector<double>(P + 1)));
    array<double, 3> ans{}; dp[R][S][P] = 1;
    for (int r = R; r >= 0; r--) for (int s = S; s >= 0; s--) for (int p = P; p >= 0; p--) {
        double c = dp[r][s][p], tot = r * s + s * p + p * r; if (c == 0) continue;
        if (tot == 0) { ans[r ? 0 : s ? 1 : 2] += c; continue; }
        if (s) dp[r][s - 1][p] += c * r * s / tot;                 // rock beats scissors
        if (p) dp[r][s][p - 1] += c * s * p / tot;                 // scissors beat paper
        if (r) dp[r - 1][s][p] += c * p * r / tot;                 // paper beats rock
    }
    return ans;
}

Self-loops and cycles

Self-loop: $E = 1 + pE + (1 - p) E^{'}$ gives $E = \frac{1 + ( 1 - p ) E ^{'}}{1 - p}$ . In particular, the expected number of trials until a success of probability $p$ is $1/ p$ .

General cycles: the system $E_{i} = c_{i} + \sum_{j} p_{ij} E_{j}$ is solved by Gaussian elimination in $O (n^{3})$ (modulo a prime, or in doubles with partial pivoting) (Gaussian Elimination). Absorbing Markov chains: with transient block $Q$ , the expected steps are $(I - Q)^{- 1} 1$ and the absorption probabilities $(I - Q)^{- 1} R$ .

Line or tree structure: express each value as a linear function of its parent’s value, $E_{v} = A_{v} E_{par (v)} + B_{v}$ , computed bottom-up, then evaluate top-down. $O (n)$ (times a modular inverse per vertex).

Proof: the tree elimination and the $2 size - 1$ hitting time

Random walk on a tree moving to a uniform neighbour, target = the root. For a vertex $v$ with degree $d$ and children $c$ , $E_{v} = 1 + \frac{1}{d} (E_{par} + \sum_{c} E_{c})$ . Suppose every child satisfies $E_{c} = A_{c} E_{v} + B_{c}$ (true for leaves with $A = B = 1$ ). Substituting, $E_{v} (d - \sum A_{c}) = d + E_{par} + \sum B_{c}$ , so $E_{v} = A_{v} E_{par} + B_{v}$ with $A_{v} = \frac{1}{d - \sum A _{c}}$ , $B_{v} = \frac{d + \sum B _{c}}{d - \sum A _{c}}$ (the denominator is positive since by induction $A_{c} = 1$ , see below). At the root $E = 0$ is known, and values propagate down.
Closed form: the expected time $T_{v}$ to go from $v$ to its parent satisfies $T_{v} = 1 + \frac{1}{d} \sum_{c} (T_{c} + T_{v})$ (each step into child $c$ costs the return time $T_{c}$ plus starting over), so $\frac{T _{v}}{d} = 1 + \frac{\sum T _{c}}{d}$ , $T_{v} = d + \sum_{c} T_{c}$ . By induction $T_{c} = 2 sz_{c} - 1$ , hence $T_{v} = (k + 1) + \sum_{c} (2 sz_{c} - 1) = 1 + 2 \sum_{c} sz_{c} = 2 sz_{v} - 1$ . The expected time from $v$ to the root is the sum of $T$ along the path.

Decisions with restarts: fixed points

“Play optimally, you may restart at any time; minimise the expected total time” (speedrun problems): the value $E$ of the start state appears inside the recurrence through the restart option, $E = f (E)$ where $f (x)$ is computed by an ordinary DP that uses $x$ as the cost of restarting. $f$ is nondecreasing with slope $< 1$ (as long as some run finishes with positive probability without restarting), so binary search on $x$ : if $f (x) < x$ , the answer is below $x$ .

Proof: binary search on the fixed point

$f (x)$ is the optimum of finitely many strategies, each of the form $a_{i} + b_{i} x$ where $b_{i}$ = probability of restarting under strategy $i$ ; a minimum of nondecreasing linear functions is nondecreasing and concave. If some strategy has $b_{i} < 1$ , then $g (x) = f (x) - x$ is strictly decreasing for large $x$ , and since $g$ is concave, it crosses zero exactly once from above: $g > 0$ before the true answer $E^{*}$ and $g < 0$ after. The true expected value is that fixed point, because the optimal policy’s value satisfies $E^{*} = f (E^{*})$ and any other fixed point would contradict uniqueness. So “is $f (x) < x$ ?” is a monotone predicate in $x$ .

A few closed forms worth having memorised rather than re-derived:

Problem	Answer
expected rolls to see all $n$ faces (coupon collector)	$n H_{n} \approx n ln n$
expected number of comparisons in quicksort	$2 n ln n$
expected length of the longest run of heads in $n$ flips	$\approx lo g_{2} n$
expected number of inversions in a random permutation	$(2 n) /2$
expected number of cycles in a random permutation	$H_{n}$
random walk on $[0, N]$ , absorbing at both ends, start $i$	reaches $N$ w.p. $i / N$ ; expected time $i (N - i)$
birthday paradox	collision after $\approx 1.18 n$ draws

Hidden Markov models: Viterbi and forward

Most likely hidden state sequence for observations $o_{1} .. o_{T}$ : $δ_{t} (j) = max_{i} δ_{t - 1} (i) + lo g A_{ij} + lo g B_{j, o_{t}}$ , with backpointers; $O (T S^{2})$ . Replacing $max$ by log-sum-exp (or $max$ by $+$ in probability space) gives the forward algorithm, i.e. the total probability of the observations: the same trellis in a different semiring.

vector<int> viterbi(const vector<int>& obs, const vector<double>& logPi, const vector<vector<double>>& logA, const vector<vector<double>>& logB) {
    int T = sz(obs), S = sz(logPi);
    vector<vector<double>> dp(T, vector<double>(S, -1e18)); vector<vector<int>> par(T, vector<int>(S, -1));
    for (int j = 0; j < S; j++) dp[0][j] = logPi[j] + logB[j][obs[0]];
    for (int t = 1; t < T; t++) for (int j = 0; j < S; j++) for (int i = 0; i < S; i++) {
        double v = dp[t - 1][i] + logA[i][j] + logB[j][obs[t]];
        if (v > dp[t][j]) dp[t][j] = v, par[t][j] = i;
    }
    vector<int> path(T); path[T - 1] = max_element(all(dp[T - 1])) - dp[T - 1].begin();
    for (int t = T - 1; t > 0; t--) path[t - 1] = par[t][path[t]];
    return path;
}

Proof: Viterbi's optimal substructure

By the Markov property, the joint probability of a state sequence and the observations factorises as $π_{s_{1}} B_{s_{1}, o_{1}} \prod_{t > 1} A_{s_{t - 1} s_{t}} B_{s_{t}, o_{t}}$ , so in log space it is a sum of terms each depending on two consecutive states. A best sequence ending in state $j$ at time $t$ consists of a best sequence ending in some $i$ at time $t - 1$ plus the last term (otherwise swapping in a better prefix would improve it). This is a longest path in the layered trellis DAG, which the recurrence computes by induction on $t$ .

Numerical care

long double for products of probabilities; logs when they get tiny.
Avoid iterating a self-referential recurrence to convergence when an algebraic solution exists; when iterating is the only option (value iteration, e.g. $1 0^{5}$ rounds for a self-loop structure with a specified target precision), bound the error by the contraction factor.
Watch for states with total outgoing probability $< 1$ (implicit absorption) and for unreachable states with $0/0$ .
Modular-answer problems are now the more common convention in contests — check the statement before assuming floating point.

Viterbi’s applications beyond HMM decoding itself: convolutional-code decoding (its original 1967 use, still in modems and satellite links), GPS map-matching (snapping noisy traces to a road network), speech recognition and POS tagging. For huge state spaces, beam search prunes the trellis heuristically instead of keeping every state. Baum–Welch (forward-backward) solves the dual problem of learning the HMM’s parameters rather than decoding with them.

whoashish's cp notes

Directory