Given a sunny/rainy transition matrix, how do you compute the chance of rain two days from now?

## The transition matrix For a chain on `k` states, the one-step transition matrix `P` is the `k x k` array with ``` P[i][j] = P(X_(n+1) = j | X_n = i) ``` Every entry is non-negative and **every row sums to 1**, because from state `i` the chain must go somewhere. This is the row-stochastic convention, which pairs with distributions written as **row vectors** multiplied on the left: `v_(n+1) = v_n P`. ## Why powers give multi-step probabilities To get from `i` to `j` in two steps the chain must pass through some intermediate state `m`. Splitting on that intermediate state and adding up the disjoint routes: ``` P(X_2 = j | X_0 = i) = sum over m of P[i][m] * P[m][j] ``` That sum is exactly the definition of the (i, j) entry of the matrix product `P * P`. Iterating gives the general **Chapman-Kolmogorov** relation ``` P^(m+n) = P^m * P^n ``` so the n-step transition matrix is simply `P^n`. Nothing else is needed: no simulation, no recursion, just a matrix power. ## Worked weather example Order the states `[sunny, rainy]` and take ``` P = [ 0.8 0.2 ] [ 0.4 0.6 ] ``` Sunny days persist 80% of the time; rainy days persist 60% of the time. Squaring, entry by entry: - sunny -> sunny in two: `0.8 * 0.8 + 0.2 * 0.4 = 0.64 + 0.08 = 0.72` - sunny -> rainy in two: `0.8 * 0.2 + 0.2 * 0.6 = 0.16 + 0.12 = 0.28` - rainy -> sunny in two: `0.4 * 0.8 + 0.6 * 0.4 = 0.32 + 0.24 = 0.56` - rainy -> rainy in two: `0.4 * 0.2 + 0.6 * 0.6 = 0.08 + 0.36 = 0.44` ``` P^2 = [ 0.72 0.28 ] [ 0.56 0.44 ] ``` Rows still sum to 1 — a useful arithmetic check. Note that the two rows are already closer to each other than the rows of `P` were: information about today's weather is decaying with each step, which is the seed of long-run behaviour. ## The classic mistake A very common wrong answer squares each entry: `0.2^2 = 0.04` for two-day rain. That number answers a different question — the probability of the specific path sunny -> rainy -> rainy is `0.2 * 0.6 = 0.12`, and `0.04` is not even that. Elementwise squares also fail the sanity check, since `0.64 + 0.04 = 0.68` is not 1. Multi-step probabilities always sum over intermediate states. ## Propagating a distribution instead If you start from uncertainty rather than a known state — say a 50/50 belief about today — put it in a row vector `v_0 = [0.5, 0.5]` and push it forward: ``` v_1 = v_0 P = [0.5*0.8 + 0.5*0.4, 0.5*0.2 + 0.5*0.6] = [0.6, 0.4] v_2 = v_1 P = [0.6*0.8 + 0.4*0.4, 0.6*0.2 + 0.4*0.6] = [0.64, 0.36] ``` For a single starting distribution this is cheaper than forming `P^n`: each step costs `k^2` operations rather than the `k^3` of a matrix-matrix product. If you genuinely need `P^n` for a large `n`, repeated squaring gets there in about `log2(n)` matrix multiplications. ## Convention traps Some texts write transition matrices **column-stochastic**, with columns summing to 1, and update column vectors as `v_(n+1) = P v_n`. The mathematics is identical — that matrix is the transpose of the row-stochastic one — but the entry you read flips from (i, j) to (j, i). Interviewers do not care which convention you pick; they care that you state it and stay consistent. Checking that your rows (or columns) sum to 1 catches a transposed matrix immediately. ## Numerical notes Repeated multiplication accumulates floating-point error, and rows can drift slightly off 1; renormalising each row after many multiplications keeps things clean. Also watch the horizon: for large `n` the rows of `P^n` typically stop changing, which is a signal that you should be asking about the long-run distribution instead of computing ever-larger powers.