The route round that rates cannot avoid

When a table of moves came from steady rates asked of a table of yearly moves between three states — the share of each state’s members found in each state a year later — whether it could have been produced by a process jumping between the states at constant rates. Such a process turns a rate matrix $Q$ into the yearly table $P = e^{Q}$, so the question is whether $P$ has a logarithm with non-negative rates off the diagonal. For three states the answer was yes for about one table in twenty-three drawn at random, and its last section noted that four states and beyond were harder.

This essay takes the count to six states and finds the share collapsing — but the collapse is not the interesting part. Tables close to doing nothing, which have steady rates behind them almost always when there are two or three states, fail more and more often as states are added, and they all fail the same way. The reason is a route round: steady rates that move anyone from 1 to 2 and from 2 to 3 inevitably move some of them from 1 to 3 within the year, by way of 2, and a table that does not show that traffic could not have been made by rates. With $n$ states there are $n(n-1)$ ordered pairs, each a separate chance to fall short.

Testing a table of any size #

The test is the one the three-state essay used, generalised. A real logarithm of $P$, when its eigenvalues are distinct, is a sum over the eigenvalues, $\log P = \sum_i \log(\lambda_i)\, Z_i$, where each $Z_i$ is the matrix that projects onto one eigenvalue’s direction — computable from $P$ and the eigenvalues alone by Sylvester’s formula. A real eigenvalue has one real logarithm if it is positive and none if it is negative; a complex pair has a whole infinite family of logarithms, $\log|\lambda| \pm i(\theta + 2\pi k)$ for every whole number $k$, and the matrix that has no logarithm found that each choice of $k$ gives a different real logarithm of the same matrix.

So the test is: find the eigenvalues; give up if one is real and negative; for each complex pair try every branch $k$ that could possibly give a rate matrix; and for each combination check whether every off-diagonal entry of the logarithm is non-negative. The branches are finite in number because a rate matrix’s eigenvalues cannot have large imaginary parts — no larger than the largest rate of leaving a state, which is at most $-\log$ of the smallest chance of staying put — so only a handful of $k$ need trying. For six states with two complex pairs that is a few dozen combinations, and the census here runs it on 40,000 tables.

The tables are drawn as in the three-state essay: a random table $D$, each row chosen uniformly from all probability rows, blended with staying put as $(1 - s)I + sD$. At $s = 0$ nothing moves; at $s = 1$ the table is entirely random. The parameter $s$ measures how much moving happens in a year.

Half, a twenty-fourth, a two-thousandth, and none #

Tables drawn entirely at random, $s = 1$, are where the collapse is starkest, and the cheap conditions the three-state essay used show how the thinning happens.

The first condition is that the determinant be positive, since $\det e^{Q} = e^{\operatorname{tr} Q} > 0$. Exactly half of all random tables pass, at every size, and the reason is a symmetry rather than a calculation: swapping two rows of a table gives another table, equally likely, with the opposite determinant. The second is David Goodman’s condition, that the determinant be no larger than the product of the diagonal entries — the chances of staying put. It keeps 50% of two-state tables, where it adds nothing, 21% of three-state tables, 9.6% of four and 4.9% of five, halving with each state.

The exact test thins them much faster. Two-state tables pass exactly when their determinant is positive, a half. Three-state tables pass 4.2% of the time, the three-state essay’s one in twenty-three. Four-state tables pass 115 times in 200,000, about one in 1,700. Five-state tables passed in none of 400,000 draws here, and one in an earlier run of the same size — a share of a few in a million. Six-state tables did not pass at all.

A table of $n$ states has $n(n-1)$ free numbers, since each row must sum to one. A rate matrix has the same number — and, as the curve that is its own slope found for a single rate, a constant rate is fixed completely by what it does in one unit of time, so counting free numbers does not rule anything out. So the embeddable tables are not a lower-dimensional sliver; they have positive volume at every size, and a small enough neighbourhood of staying put lies entirely inside them. What collapses is their share of the whole space, and the hero figure shows that the collapse begins close to staying put.

A direct move rarer than the route round #

The hero figure’s most surprising curves are at small $s$. With three states, 95% of tables a twentieth of the way from staying put have steady rates behind them; with six, 58%. A table that is $95\%$ staying put is hardly moving at all, and still it often cannot have come from rates. Every one of those failures is a negative rate somewhere in the logarithm, and the expansion of the logarithm near the identity says where.

Write the table as $P = I + sE$ with $E = D - I$. For small $s$ its logarithm is a series in the same way the ordinary logarithm is,

$$\log P = sE - \frac{s^2}{2}E^2 + \frac{s^3}{3}E^3 - \cdots$$

— the matrix version of $\log(1 + x)$, which the exponential of a square justified for the exponential and which works for the logarithm near the identity in the same way. The off-diagonal entry from 1 to 3 is $s D_{13}$ to first order, which is non-negative. The second-order term subtracts $\frac{s^2}{2}(E^2)_{13}$, and $(E^2)_{13}$ contains $\sum_k D_{1k} D_{k3}$ over the states $k$ other than 1 and 3: the chance of going from 1 to 3 in two steps by way of somewhere else.

In the example, $D_{12} D_{23} = 0.79 \times 0.7 = 0.553$, so the second-order term is large, while the first-order term is $s \times 0.01$. They balance at

$$s = \frac{2 D_{13}}{(E^2)_{13}} \approx 0.037,$$

and the exact rate, computed from the full logarithm, turns negative at $0.040$. From there on, every logarithm of the table has a negative rate from 1 to 3, and the table has no steady rates behind it.

The meaning is direct. Over a year, steady rates do not only move people one step. Anyone moved from 1 to 2 early in the year is exposed to the rate from 2 to 3 for the rest of it, so steady rates that move many people from 1 to 2 and from 2 to 3 necessarily move some from 1 to 3 within the year — about $\frac{s^2}{2}D_{12}D_{23}$ of them, to second order. A table whose direct entry from 1 to 3 is smaller than that has fewer people making the trip than the route round alone would deliver. To produce it, rates would have to carry some people back out of 3 into 1 at exactly the rate that cancels the route — a negative rate. This is the mechanism the three-state essay found in published credit-rating tables, where moves between distant grades were rarer than chains of moves between neighbouring grades implied; here it is the whole story near staying put.

Two states have no route round #

The two-state curve in the hero figure is flat at 100% until $s = 0.5$, and the expansion says why. With two states there is no third state to go round through: $(E^2)_{12}$ is $E_{11}E_{12} + E_{12}E_{22}$, a multiple of $E_{12}$ itself, so the second-order term only rescales the first and can never overturn its sign. The same holds at every order, and the exact criterion is the one the three-state essay drew as a triangle — a two-state table with chances $p$ and $q$ of switching has steady rates behind it exactly when $p + q < 1$, when its determinant is positive. A blend with staying put has $p + q = s(p_D + q_D)$, which is below one for every $D$ as long as $s < 1/2$.

So the two-state case, the one everybody computes first, is misleading in exactly the way that matters. It suggests that a table close to staying put is always safe and that trouble only begins far from it, at a table that tends to swap. With three or more states trouble begins at once, because the route round exists from the first step, and the only question is how small $s$ must be before every route round is smaller than the direct move it competes with. For any particular table there is such an $s$ — the identity is surrounded by embeddable tables — but for a random table it can be very small, and the hero figure shows that at six states a fifth of tables are already lost by $s = 0.02$.

The same counting explains why a walk that samples a distribution is usually described by a table of single steps rather than by rates: a chain built step by step has no route round within a step, and any table at all is a legitimate one-step rule. Rates are a stronger assumption than steps, and the embedding problem is the price of making it.

Every pair is a chance to fall short #

Near staying put, then, a table fails when, for some ordered pair of states, the direct entry is too small compared with the two-step routes through the other states. A random row has some small entries — the chance that a uniformly random probability row has an entry below a small threshold grows with the number of entries — and each small entry is a candidate.

If each ordered pair failed independently with the same small chance, the share passing would be $e^{-c\, n(n-1)}$ for a constant $c$, and minus its logarithm would be a straight line against the number of pairs. The measurement is close to that and bends slightly upwards: the chance for each pair grows with $n$ too, because with more states there are more routes round to compete with each direct move — the sum $\sum_k D_{ik}D_{kj}$ has $n - 2$ terms — while the direct entry, a random share of a row of $n$, gets smaller. At $s = 0.05$ the share passing falls from 95% at three states to 58% at six.

The scaling has a practical reading. A table estimated from data, for a system with many states and short periods between observations, is close to staying put — and it is exactly that kind of table which the expansion says will fail, since sampling noise makes many small entries smaller than the routes round predict. The more states, the more pairs, and the more certain it becomes that some pair falls short, even when the process really did run at steady rates and only the estimate is off.

Two ways to fail #

Far from staying put the failures change character.

Close to staying put all the eigenvalues are close to one, and no failure in the census is a negative eigenvalue: they are all negative rates, the route round. Half-way, at $s = 0.5$, the same is true, though now almost every table fails. For tables drawn at random most failures are a negative real eigenvalue, a table that tends to swap states back and forth from one year to the next, which a steady flow cannot do — two numbers decide the flow found steady linear flows spiralling or decaying, never flipping sign at fixed intervals. The eigenvalues of $e^{Q}$ are $e^{\mu}$ for the eigenvalues $\mu$ of $Q$, and $e^{\mu}$ is never a negative real number unless $\mu$ is complex and comes in a pair, which a single real eigenvalue cannot. With four states two-thirds of random tables have such an eigenvalue, and among the rest the route round finishes the job.

What the census does not settle #

Every test here assumes distinct eigenvalues. A random table has them with probability one, so the census loses nothing, but particular tables of interest — tables with symmetries, or with states that cannot be told apart — have repeated eigenvalues, and then a matrix can have a continuum of logarithms, as the matrix that has no logarithm found for minus the identity. Deciding whether any member of a continuum is a rate matrix is a different problem, and the method here does not touch it.

One family of tables escapes the branch search altogether. A table that is reversible — one where, in the long run, as many people move from each state to each other state as move back, the property the chain that runs the same backwards studied — is similar to a symmetric matrix, so its eigenvalues are all real. Then there are no complex pairs and no branches: the table has steady rates behind it exactly when every eigenvalue is positive and its one real logarithm has no negative rate. The route round still applies, and it is the only way such a table near staying put can fail.

The uniform distribution over tables is also a choice. Real tables are not random; they usually have most of their weight on the diagonal and structure off it, as mobility and credit tables do. The census describes the space of possibilities, not the tables anyone collects, and its value is in the mechanism it isolates rather than in its particular percentages. The finite census of shares — 1,500 or 800 tables a point — puts a few percentage points of noise on each, visible as small wobbles in the hero figure’s curves.

Still open: the nearest table with rates behind it #

Given a table with no steady rates behind it, what is the nearest one that has them, and can it be found efficiently? The repairs used in practice for credit tables are heuristics: compute the principal logarithm, set the negative rates to zero, and adjust the diagonal so that rows still sum to zero, or redistribute the negative mass among the positive rates of the same row. Each gives a table with rates behind it, but not the nearest one in any stated sense, and the set of embeddable tables is not convex, so the nearest point may not be unique. For three states the problem can be settled by search; for many states no efficient method with a guarantee is known.

There is also a sharper version of the census question. The share of embeddable tables among random ones is about $10^{-0.3}$, $10^{-1.4}$, $10^{-3.2}$ and around $10^{-5.5}$ for two to five states; whether it falls like $e^{-cn^2}$, as the count of pairs near staying put would suggest, or faster, is not known, and the figures here are too few to tell. The three-state essay recorded the case of four states with distinct eigenvalues as settled only recently by an explicit search through branches of the kind used here; a formula for the share at any size is not in sight.

Rates always make the route round #

Steady rates that move people from 1 to 2 and from 2 to 3 must also move some from 1 to 3 within a year, and a table that shows fewer direct moves than that route round cannot have come from steady rates. That one fact, the second-order term of a matrix logarithm, explains why tables close to staying put fail more and more often as states are added: every ordered pair of states is a separate chance for the direct move to fall short, and at a twentieth of the way from staying put the share with rates behind them falls from 95% for three states to 58% for six. Drawn entirely at random, half of two-state tables, one in twenty-four three-state tables, about one in 1,700 four-state tables and almost no larger tables have steady rates behind them — exactly half pass the first condition at every size, and the rest is the route round and the negative eigenvalue.