Applications Least Squares Markov Chains: Notes and FAQs

Least squares and Markov chains are two of the most applied ideas in linear algebra. Least squares finds the best approximate solution to an unsolvable system Ax = b by minimizing the error, while a Markov chain models a system hopping between states with fixed probabilities, and its long-run behavior is governed by eigenvectors.

Real data never fits a model exactly and real processes evolve randomly. Least squares powers every regression line; Markov chains power weather models, web ranking, and genetics.

Key Concepts

• Overdetermined system. Ax = b with more equations than unknowns, usually unsolvable exactly.
• Normal equations. A^T A x̂ = A^T b; the solution minimizes ‖Ax − b‖² by projecting b onto the column space of A.
• Residual. r = b − Ax̂, orthogonal to every column of A.
• Markov chain. States where the next depends only on the current one, with transition matrix P.
• Stationary distribution. π with πP = π: the long-run fraction of time in each state.

Formulas

• Least squares: x̂ = (A^T A)^−1 A^T b, valid when A's columns are independent.
• Markov steady state: solve πP = π with the entries of π summing to 1.
• n-step evolution: pn = p0 P^n for initial row distribution p0.
• Assumptions and limits: least squares needs independent columns; a unique stationary distribution needs a regular (irreducible, aperiodic) chain.

Worked Example

Fit the line y = mx + c to the points (1, 1), (2, 3), (3, 4) by least squares, then find the steady state of a 2-state chain.

1. Set up A = [[1, 1], [1, 2], [1, 3]] and b = (1, 3, 4), solving for x̂ = (c, m).
2. A^T A = [[3, 6], [6, 14]] and A^T b = (8, 19), since sums of y give 8 and sums of xy give 1 + 6 + 12 = 19.
3. Determinant: 3 × 14 − 6 × 6 = 42 − 36 = 6. So c = (8 × 14 − 6 × 19)/6 = (112 − 114)/6 = −1/3, and m = (3 × 19 − 6 × 8)/6 = (57 − 48)/6 = 3/2.
4. Best-fit line: y = 1.5x − 1/3. The three residuals sum to zero, as theory predicts when a constant term is fitted.
5. Markov chain with P = [[0.8, 0.2], [0.3, 0.7]] (rows sum to 1). Solve πP = π: 0.8π1 + 0.3π2 = π1 with π1 + π2 = 1.
6. From the first equation, 0.3π2 = 0.2π1, so π2 = (2/3)π1. Then π1 + (2/3)π1 = 1 gives π1 = 0.6 and π2 = 0.4. In the long run the chain spends 60% of its time in state 1.

Common Misconceptions

• Expecting the fit to pass through the points. Least squares minimizes total squared error; it is not interpolation.
• Thinking the steady state depends on the start. For a regular chain every starting distribution converges to the same π.
• Mixing row/column conventions. Row-stochastic P pairs with πP = π; column-stochastic pairs with Pπ = π.

Real-World Applications

• Regression: trend lines, demand forecasting, and calibration curves are all least-squares fits.
• PageRank: Google's original ranking is the stationary distribution of a Markov chain on the web graph.
• Weather and finance: regime-switching models use Markov chains for rainy/sunny days and bull/bear markets.

Least squares solves A^T A x̂ = A^T b to get the closest possible fit, and a Markov chain's future is captured by its stationary distribution πP = π. One minimizes error, the other predicts the long run, and both are linear algebra doing real work.