Matrices and vectors

Why you need this

A Markov chain's transition table is a matrix. "Where will the chain probably be after one step" is a row vector times that matrix. "After two steps" is the same vector times the matrix squared. That is all the linear algebra the layout and regime stages need, and this page covers exactly that and nothing more: no determinants, no inverses.

The idea

Vectors

A vector is an ordered list of numbers. Its length is the number of entries. Written horizontally it is a row vector, $v = (0.5, 0.3, 0.2)$; written vertically it is a column vector. The numbers are the same either way; the shape only matters when you multiply. $v_i$ is the $i$-th entry, counting from 1 in math and from 0 in code.

In this cluster, a vector of state probabilities is a row vector: $v_i = P(\text{the chain is in state } i)$, with $N$ entries for $N$ states.

Matrices

A matrix is a grid of numbers with $n$ rows and $m$ columns, called an $n \times m$ matrix. The entry $A_{ij}$ sits in row $i$, column $j$: row first, column second, always. A matrix is square when $n = m$.

$$A = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}, \qquad A_{12} = 1, \quad A_{21} = 0$$

Matrix times column vector

$Av$ is a column vector whose $i$-th entry is row $i$ of $A$ multiplied entry-wise with $v$ and summed:

$$(Av)_i = \sum_j A_{ij} v_j$$

$$\begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} \begin{pmatrix} 4 \\ 5 \end{pmatrix} = \begin{pmatrix} 2 \cdot 4 + 1 \cdot 5 \\ 0 \cdot 4 + 3 \cdot 5 \end{pmatrix} = \begin{pmatrix} 13 \\ 15 \end{pmatrix}$$

Row vector times matrix

$vA$ is a row vector whose $j$-th entry is $v$ multiplied entry-wise with column $j$ of $A$ and summed:

$$(vA)_j = \sum_i v_i A_{ij}$$

$$\begin{pmatrix} 4 & 5 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 4 \cdot 2 + 5 \cdot 0 & 4 \cdot 1 + 5 \cdot 3 \end{pmatrix} = \begin{pmatrix} 8 & 19 \end{pmatrix}$$

Same matrix, same numbers, different answer from $Av$. Order matters, and Markov chains use the row-vector form.

Matrix times matrix

$(AB)_{ij}$ is row $i$ of $A$ against column $j$ of $B$: $(AB)_{ij} = \sum_k A_{ik} B_{kj}$. The result has as many rows as $A$ and as many columns as $B$. $A^2$ means $AA$.

Row-stochastic matrix

A square matrix is row-stochastic when every entry is non-negative and every row sums to 1. Each row is then a categorical distribution. The transition matrix of a Markov chain is row-stochastic by definition:

$$A_{ij} = P(X_{t+1} = j \mid X_t = i)$$

where $X_t$ is the state at time $t$. Row $i$ answers "from state $i$, where next?" and its entries must sum to 1 because the chain has to go somewhere.

Why $vA$ is the next step

Let $v_i = P(X_t = i)$. The law of total probability says

$$P(X_{t+1} = j) = \sum_i P(X_t = i)\,P(X_{t+1} = j \mid X_t = i) = \sum_i v_i A_{ij} = (vA)_j$$

That last expression is the row-vector-times-matrix formula. So $vA$ is the distribution over states one step later. It is still a probability vector: its entries sum to 1 because each row of $A$ does.

Powers are steps

Two steps is $(vA)A = vA^2$. The entry $(A^2)_{ij} = \sum_k A_{ik} A_{kj}$ is the probability of going from $i$ to $j$ in exactly two steps, summed over every intermediate state $k$. In general $A^n$ holds the $n$-step probabilities.

One sentence on the long run: a stationary distribution is a row vector $v$ with $vA = v$, a mix of states that one more step does not change, and for most chains repeated multiplication settles onto it.

Worked example

Three column states: flat (1), gap (2), climb (3).

$$A = \begin{pmatrix} 0.6 & 0.3 & 0.1 \\ 0.7 & 0.0 & 0.3 \\ 0.5 & 0.2 & 0.3 \end{pmatrix}$$

Rows sum to 1.0, 1.0, 1.0, so it is row-stochastic. $A_{23} = 0.3$ says a gap is followed by a climb 30 percent of the time. $A_{22} = 0$ says a gap never follows a gap.

Start certain in flat: $v = (1, 0, 0)$. Then $vA = (0.6, 0.3, 0.1)$, which is just row 1. If you know you are in flat, the next-step distribution is flat's row.

Two steps: multiply again, column by column.

$j$	$\sum_i v_i A_{ij}$	value
1	$0.6 \cdot 0.6 + 0.3 \cdot 0.7 + 0.1 \cdot 0.5$	$0.36 + 0.21 + 0.05 = 0.62$
2	$0.6 \cdot 0.3 + 0.3 \cdot 0.0 + 0.1 \cdot 0.2$	$0.18 + 0.00 + 0.02 = 0.20$
3	$0.6 \cdot 0.1 + 0.3 \cdot 0.3 + 0.1 \cdot 0.3$	$0.06 + 0.09 + 0.03 = 0.18$

So $vA^2 = (0.62, 0.20, 0.18)$, summing to 1.00. Because $v$ was $(1, 0, 0)$, this is also row 1 of $A^2$.

One entry of $A^2$ by hand: from gap to flat in two steps, $$(A^2)_{21} = 0.7 \cdot 0.6 + 0.0 \cdot 0.7 + 0.3 \cdot 0.5 = 0.42 + 0 + 0.15 = 0.57$$ Read it as three routes: gap, flat, flat; gap, gap, flat (impossible here); gap, climb, flat.

A mixed start: $v = (0.5, 0.5, 0)$ gives $vA = (0.65, 0.15, 0.20)$.

In code, then iterated:

function rowTimesMatrix(v, A) {
  const out = new Array(A[0].length).fill(0);
  for (let i = 0; i < v.length; i++)
    for (let j = 0; j < A[0].length; j++) out[j] += v[i] * A[i][j];
  return out;
}
const A = [[0.6, 0.3, 0.1], [0.7, 0.0, 0.3], [0.5, 0.2, 0.3]];
let v = [1, 0, 0];
for (let t = 1; t <= 3; t++) {
  v = rowTimesMatrix(v, A);
  console.log(t, v.map(x => x.toFixed(3)).join(" "));
}
// 1 0.600 0.300 0.100
// 2 0.620 0.200 0.180
// 3 0.602 0.222 0.176

Keep going to 60 steps and the vector stops moving at about $(0.604, 0.217, 0.179)$. That is the stationary distribution: in the long run about 60 percent of columns are flat, 22 percent gaps, 18 percent climbs, regardless of where the level started.

In a map generator

• Layout. The parameter file stores $A$ as an array of rows. Sampling a level uses one row at a time; predicting the mix of a level uses $vA^n$. The initial distribution $\pi$ is a row vector too.
• Regime over time. $vA^k$ tells you the expected mix of regimes after $k$ ticks without simulating anything. The stationary distribution is a design target: if you want regions calm 60 percent of the time, tune $A$ until its stationary vector says so. See Regime chains.
• Fill. A hidden Markov model's emission matrix $B$ is also row-stochastic, one row per hidden state. The forward algorithm is a row-vector-times-matrix product with an entry-wise scaling by a column of $B$ after each step.
• Export. Matrices ship as nested arrays; the check "every row sums to 1 within rounding" belongs in the loader.

Common mistakes

• Transposed matrix. Columns sum to 1 instead of rows. Symptom: $vA$ no longer sums to 1; probability leaks or piles up over many steps.
• Using $Av$ where $vA$ was meant. Symptom: the same leak, and a "next step" that depends on the wrong row.
• Indexing A[j][i] in code. Symptom: a chain designed so gap never follows gap produces gap, gap anyway.
• Rounded rows. A row summing to 0.999 loses a tenth of a percent per step. Symptom: after 500 ticks the regime vector sums to 0.6. Renormalize, or store the last entry as one minus the rest.
• Reading $A^n$ as a path. $A^n$ gives the distribution of where you end up, not a sequence of states. Symptom: someone draws a level from the entries of $A^n$ and gets a smeared average with no structure.
• Off by one between math and code. Math counts states from 1, code from 0. Symptom: state 1's row is read for state 2.

Cost

With $N$ states, $vA$ costs $O(N^2)$ time and the matrix takes $O(N^2)$ memory, the vector $O(N)$. Advancing a vector $k$ steps is $O(k N^2)$. Computing $A^k$ explicitly by repeated multiplication is $O(k N^3)$, which is worth it only if you reuse $A^k$ for many starting vectors. For the $N$ of 6 to 30 in this cluster none of this registers; it starts to hurt when $N$ is the number of tiles, in the hundreds, and then the matrix is mostly zeros and a sparse representation pays off.

Going further

• Markov chains, where this matrix becomes a generator.
• Hidden Markov models, which add the emission matrix $B$.
• Forward algorithm, a vector-matrix product with scaling.
• Regime chains, where the stationary distribution is the design knob.
• The matrix multiplication and Markov matrix chapters of any first linear algebra text.