Probability & Expected Value Dynamic Programming: Markov Chains & Absorbing States

Stochastic algorithms and game theory frequently require calculating the likelihood of reaching favorable outcomes or the average number of operations until system termination. Probability & Expected Value Dynamic Programming transforms randomized Markov decision processes into structured systems of linear equations and topological recurrences.

1. Probability DP: Forward Propagation of State Likelihoods

In standard Probability DP, we calculate dp[i][state] representing the probability that the system occupies state at step i. By the Law of Total Probability, state likelihoods propagate forward:

    P(v) = ∑_{u → v} P(u) × Prob(u → v)
  

Base states start with certainty at the initial condition: dp[0][start] = 1.0, and all other states initialize to 0.0. Because probabilities satisfy Kolmogorov axioms, the sum of probabilities across all mutually exclusive states at any given step must strictly sum to 1.0.

2. Expected Value DP: Backward Recurrence & Terminal Invariants

Unlike probability which naturally flows forward from start to finish, Expected Value DP computes the expected remaining cost or steps to reach a target. Consequently, Expected Value is almost universally formulated backward from terminal absorbing states:

The Universal Expectation Recurrence

Let E[u] denote the expected number of steps to reach the target starting from state u:

      E[u] = 1 + ∑_{v} Prob(u → v) × E[v]

      Base Condition: E[target] = 0.0

The constant 1 represents taking 1 step to move from u to adjacent states v. At the target state, 0 remaining steps are needed, giving E[target] = 0.

3. Resolving Cycles: Self-Loops vs. Gaussian Elimination

When a state has a non-zero probability of remaining in place (self-loop with probability p = Prob(u → u)), the recurrence becomes self-referential:

    E[u] = 1 + p × E[u] + ∑_{v ≠ u} Prob(u → v) × E[v]

    (1 - p) × E[u] = 1 + ∑_{v ≠ u} Prob(u → v) × E[v]

    E[u] = [1 + ∑_{v ≠ u} Prob(u → v) × E[v]] / (1 - p)

For simple isolated self-loops, algebraic rearrangement solves the recurrence in O(1). However, when states exhibit arbitrary mutual cycles (e.g., state A transitions to B, and B transitions back to A), the recurrences form an N × N system of linear equations:

    M × E = B  &implies;  Solved via Gaussian Elimination in O(N^3) time
  

4. Linearity of Expectation & Indicator Random Variables

The primary engine behind Expected Value DP is the Linearity of Expectation: for any random variables X_1, X_2, ..., X_n (regardless of whether they are mutually independent or heavily coupled), E[∑ X_i] = ∑ E[X_i].

This allows algorithms to decompose intractable joint probability distributions into the sum of simple Indicator Random Variables:

    I_i = 1 if event i occurs, else 0  &implies;  E[I_i] = P(Event i occurs)
  

In the classic Coupon Collector Problem with N unique coupons, let X_k be the number of drawings required to acquire the (k+1)-th coupon after already possessing k distinct coupons. Each X_k follows a geometric distribution with success probability p_k = (N - k) / N, yielding mean E[X_k] = N / (N - k). By Linearity of Expectation:

    E[Total] = ∑_{k=0}^{N-1} E[X_k] = N × ∑_{k=0}^{N-1} 1 / (N - k) = N × H_N ≈ N ln N + γN
  

5. Absorbing Markov Chains: The Fundamental Matrix N = (I - Q)^(-1)

When stochastic systems contain multiple terminal absorbing states (e.g., Gambler's Ruin ending in bankruptcy or goal wealth), the Markov transition matrix P is partitioned into canonical block form:

    P = | Q   R |

        | 0   I |

Here, Q models transitions between transient states, and R models transitions from transient into absorbing states. The Fundamental Matrix N_mat is defined as:

    N_mat = ∑_{k=0}^{∞} Q^k = (I - Q)^(-1)
  

The (i, j) entry of N_mat calculates the exact expected number of times state j is visited starting from state i before absorption. Summing row i: t = N_mat × 1 calculates the expected time to absorption from state i in O(V^3) time.

6. Numerical Stability in Gaussian Elimination: Partial Pivoting

Solving Markov linear equation systems via naive Gaussian elimination leads to catastrophic floating-point error accumulation if diagonal coefficients approach zero.

To guarantee numerical resilience, algorithms must incorporate Partial Row Pivoting: at step k, search column k for the row with the largest absolute magnitude |M[i][k]| and swap it with row k before eliminating below. This minimizes rounding error amplification, ensuring high condition-number matrices resolve accurately.

7. Engineering Invariants & Convergence Guardrails

Absorbing Reachability Validation: Before formulating Expected Value recurrences, run BFS/DFS to verify that every transient state has a valid directed path to an absorbing state. If a disconnected cyclic component exists where escape probability is strictly 0, the expected steps to termination diverges to +∞, causing matrix singularity.
64-bit Double Precision (IEEE 754): Never use 32-bit single precision floats for probability state vectors. Subnormal underflows during repeated forward multiplications will corrupt probabilities to 0.0, destroying normalization.

8. Algorithmic Comparison: Stochastic DP Methods

Paradigm	Direction	Graph Requirement	Time Complexity	Handling of Cycles
Topological DP on DAGs	Backward	Strictly Acyclic	O(V + E)	Cycles prohibited
Self-Loop Algebraic DP	Backward	DAG with self-loops	O(V + E)	Algebraic division / (1 - p)
Gaussian Elimination	Global Matrix	Arbitrary cyclic graphs	O(V^3)	Linear system solver