When a table of moves came from steady rates

A population is sorted into a few states — employed, unemployed and out of the labour force; three grades of credit rating; the four bases of a stretch of DNA — and once a year somebody counts how many in each state are in each other state twelve months later. The result is a table of yearly moves: a square array whose row for a state lists the shares of that state’s members found in each state a year on. Each row is a probability distribution, so every entry is non-negative and every row sums to one. In the language of Markov chains it is a transition matrix, $P$.

The table is a summary of a year, and the people in it did not move once a year. They moved whenever they moved, and the natural model of that is a process that jumps between states at constant rates: from state $i$ to state $j$ at rate $q_{ij}$, meaning that in a short time $h$ the chance of that jump is about $q_{ij} h$, whatever has happened before. It is the many-state version of the rule in the equation with only one answer, where a quantity changing at a rate proportional to itself is pinned down completely by where it starts, and the waiting time in a state is exponential for the reason the constant that counts what does not happen gives for $e^{-\lambda}$: it is the chance that no jump has yet occurred. The rates form a matrix $Q$ whose off-diagonal entries are non-negative and whose rows sum to nought, the diagonal holding minus the total rate of leaving. Such a $Q$ is called a rate matrix, and the whole connection between the two descriptions is one formula that the exponential of a square made available: over one unit of time,

$$P = e^{Q} = I + Q + \tfrac{1}{2}Q^2 + \tfrac{1}{6}Q^3 + \cdots.$$

So the question a statistician asks of a yearly table — what were the rates? — is a question about a matrix logarithm, and the matrix that has no logarithm has already shown that matrix logarithms can fail to exist and can fail to be unique. Here there is a third way to fail. A logarithm can exist, be real and be perfectly good arithmetic, and still not be a rate matrix, because some entry off its diagonal is negative: a negative rate of moving from one state to another, which no process has. The question of whether a given transition matrix has a logarithm that is a valid rate matrix was posed by Gustav Elfving in 1937 and named the embedding problem by John Kingman in 1962, and the answer, when it is no, is a finding about the data: whatever produced this table, it was not a process with steady rates.

Most tables could not have come from steady rates #

The figure above is the measurement that frames the rest. For each value of $s$ from $0.05$ to $1$, four thousand three-state transition matrices were drawn as a blend $(1-s)I + sD$, where $D$ has each row chosen uniformly from all probability rows, and each matrix was tested: every real logarithm it has was computed, each one checked for negative rates, and each valid one exponentiated back to confirm that it reproduces the table to eight decimal places.

Near $s = 0$ the matrices are close to the identity, the table of a year in which almost nobody moved, and almost all of them pass — about 95% at $s = 0.05$. That is what the power series predicts. For a matrix close to the identity the principal logarithm is $\log P = (P - I) - \tfrac{1}{2}(P-I)^2 + \cdots$, and its leading term $P - I$ is already a rate matrix, with non-negative entries off the diagonal and rows summing to nought. The correction terms are smaller by a factor of the distance from the identity, so they can make an off-diagonal entry negative only when that entry was nearly nought to begin with. The 5% that fail at $s = 0.05$ are tables in which one particular move almost never happens while the moves around it do; a constant-rate process that can go from $i$ to $k$ and from $k$ to $j$ will occasionally make both moves in a year, so it cannot report a chance of going from $i$ to $j$ that is much smaller than that.

As $s$ grows the share collapses: under half by $s = 0.5$, under a quarter by $0.7$, and about 4.3% for a table drawn at random. A transition matrix is a very general object, eight free numbers for three states, and the exponentials of rate matrices are a thin family inside it: six free rates, but six numbers that have to be fitted together in exactly the way the exponential fits them. Most of the tables a person might write down for a three-state process — and many of the tables real data produce, as the applications below record — sit outside it.

The figure is also the first warning about what the rest of this essay can and cannot do. “Embeddable” is decided here by a search over logarithms, and the search is finite for a reason that only appears in the fifth figure. Before that there are the cheap tests, each of which rejects some tables at a glance, and the case in which there is nothing to search at all.

Two states are a triangle #

With two states the whole question is one inequality. Call the yearly chance of moving from state 1 to state 2 $p$ and from 2 to 1 $q$. A two-state rate matrix has rates $a$ and $b$, and its exponential can be written in closed form, because $Q^2 = -(a+b)Q$ makes the series collapse:

$$e^{Q} = I + \frac{1 - e^{-(a+b)}}{a+b}\,Q.$$

So the yearly chances are $p = a\,c$ and $q = b\,c$ with $c = (1 - e^{-(a+b)})/(a+b)$, which forces $p + q = 1 - e^{-(a+b)}$. That is less than one, and every value below one is reached. A two-state table came from constant rates exactly when $p + q < 1$, and then the rates are unique and recovered by

$$a = p\cdot\frac{-\log(1-p-q)}{p+q}, \qquad b = q\cdot\frac{-\log(1-p-q)}{p+q}.$$

The inequality $p + q < 1$ is the statement that the determinant $1 - p - q$ is positive, and it has a plain reading: $p < 1 - q$ says that someone who started in state 1 is less likely to be found in state 2 a year later than someone who started in state 2. A process with constant rates always favours where it began. The person who started in state 2 can reach state 2 a year later by staying, or by leaving and coming back; the person who started in state 1 must have left, and has had less time in which to accumulate the same chance. A table with $p + q > 1$ describes a process that switches so reliably that its members are likelier to be found in the state they did not start in, which a memoryless process with steady rates cannot do over any interval. It could be a seasonal process, or a deterministic alternation with noise, or a population counted at the wrong moment, and the table alone cannot say which; what it does say is that the model has to change.

The boundary $p + q = 1$ is the set of tables whose rows are equal, where a year is enough to forget the starting state completely. Constant rates approach that line as the rates grow, since $e^{-(a+b)}$ goes to nought, and never reach it. Nothing about two states is open.

A determinant that must be positive and smaller than the diagonal #

For three states there is no single inequality, but there are cheap conditions every embeddable matrix must satisfy, and the first is inherited from the case just done. The determinant of an exponential is the exponential of the trace, $\det e^{Q} = e^{\operatorname{tr} Q}$, and the trace of a rate matrix is minus the total rate of leaving all states, which is negative. So $0 < \det P < 1$ for every embeddable $P$. That rules out at once every table whose determinant is nought or negative, a large share of random tables.

The second condition is sharper and less obvious. David Goodman proved in 1970 that an embeddable matrix satisfies

$$\det P \;\le\; p_{11}\,p_{22}\,p_{33},$$

the determinant is at most the product of the chances of staying put. One way to see why is to split the rate matrix into its diagonal, the rates of leaving, and the rest, the rates of arriving somewhere specific. If there were no moves at all the determinant would be exactly $e^{q_{11}+q_{22}+q_{33}}$, the product of the chances of never leaving each state. Each diagonal entry $p_{ii}$ of the real table is at least the chance of never leaving, since staying put for the whole year is one way of being found in state $i$ at its end, and leaving and returning adds to it. The determinant, by contrast, is exactly $e^{\operatorname{tr} Q}$ whatever the moves are. So the product of the diagonal can only exceed the determinant, never fall short of it.

The figure shows both conditions working and also how far they are from the whole answer. The filled dots fill the wedge between the axis and the line, and nothing filled crosses either. A noticeable number of rings, about one table in seventeen, lie above the line, and those are rejected by a multiplication and a comparison. But many more rings lie inside the wedge, indistinguishable from the filled dots in this view. Goodman’s inequality is necessary and far from sufficient, and the rings inside the wedge are failing for a reason this pair of numbers cannot see: their logarithms exist, and are real, and have a negative entry off the diagonal.

Where the eigenvalues of steady rates can lie #

The next test reads the eigenvalues, which is where two numbers decide the flow located everything a linear system does over time. A rate matrix has $0$ as an eigenvalue, with the all-ones vector, and its other eigenvalues have negative real part. For three states something stronger is true: the other two eigenvalues lie within $30°$ of the negative real axis, $|\operatorname{Im}\lambda| \le |\operatorname{Re}\lambda|/\sqrt{3}$. The extreme is the rate matrix of a pure cycle, which moves from 1 to 2, 2 to 3 and 3 to 1 at the same rate and never backwards; its eigenvalues are $r(\omega - 1)$ for the cube roots of unity $\omega$, which lie exactly on the edges of that sector. Mixing in moves the other way, or uneven rates, can only bring the eigenvalues closer to the axis.

Exponentiating carries the sector to a region of the unit disc. An eigenvalue $\lambda$ of $Q$ becomes $e^{\lambda}$ for $P$, so the edges of the sector, $\lambda = -x(1 \pm i/\sqrt 3)$, become the two spirals $e^{-x}e^{\mp ix/\sqrt 3}$ winding inward from $1$. Every eigenvalue of an embeddable three-state matrix other than $1$ lies between them, a region that Jan Runnenberg described in 1962 and that becomes a more complicated curve for each further number of states.

The picture explains several things at once. The rings on the negative real axis to the left are the tables with a negative eigenvalue, which the matrix that has no logarithm already showed have no real logarithm whatever. The rings out towards the rim of the disc are tables that keep too much of their structure over a year: an eigenvalue of size near one, at an angle away from the axis, means a pattern that rotates through the states without decaying, and steady rates decay any rotation faster than they turn it. And the filled cloud piles up along the positive axis because most random rate matrices have real eigenvalues. The spiral is one curve rather than a filled region in the sense that matters: a rate matrix can put its eigenvalues anywhere in the sector, so every point between the spirals is reached by some embeddable table.

The eigenvalue test also finishes a question the census left hanging. For a table with distinct complex eigenvalues $\mu, \bar\mu$, its real logarithms differ only in which branch of $\log \mu$ they take — $\log|\mu| + i(\theta + 2\pi k)$ for whole numbers $k$, exactly as for a rotation, whose logarithms differ by whole turns. A valid rate matrix must have its eigenvalue inside the sector, $|\theta + 2\pi k| \le -\log|\mu| / \sqrt 3$, and only finitely many $k$ satisfy that. So for distinct eigenvalues the search for a valid logarithm is a finite list of candidates, each checked by its signs, and that is how the census was decided. Repeated eigenvalues are another matter: there the real logarithms come in continua, as they did for minus the identity, and a search over a continuum has no such list.

The cycle that no rates can run #

The extreme case of the sector deserves to be looked at directly, because it is the table every intuition about cycles suggests should be easy. Let $C$ be the permutation that sends state 1 to state 2, 2 to 3 and 3 to 1 with certainty: a population that rotates through three stages, every member moving one stage on per year. As a matrix it has determinant one and eigenvalues $1$, $\omega$ and $\bar\omega$, the cube roots of unity. Acting on the plane of vectors whose entries sum to nought it is exactly a rotation by a third of a turn, and that rotation has real logarithms, infinitely many of them.

None of them is a rate matrix. Goodman’s inequality says so immediately: the determinant is one and the product of the diagonal is nought. The eigenvalue picture says it too, since $\omega$ has size one and the spirals touch the unit circle only at $1$. And there is a reason that needs no inequality. A process with steady rates that can move from 1 to 2 in a year must, with positive probability, make that move early in the year and then make the next move too, and with positive probability make no move at all; its arrivals are always spread out in time. A constant-rate process cannot keep time. The logarithms in the figure describe motions that do keep time — a smooth rotation, a third of a turn per year — but a rotation of probability vectors through negative values is not a process of individuals moving between states. What constant rates can do is approximate the cycle: run the cycle at rate $r$ and the table is $e^{r(C-I)}$, which blurs the cycle more the more often it is taken, and approaches the uniform table, never $C$.

One table, two sets of rates #

When a valid logarithm exists it is usually unique, and two states never offer a choice. Three states can, and the figure shows a table with two different rate matrices behind it, each with non-negative off-diagonal rates and rows summing to nought, each exponentiating back to the same table to eight decimal places.

The two logarithms are neighbouring branches: they share the real part of the complex eigenvalue’s logarithm and differ by $2\pi$ in its imaginary part. The first describes a strong circulation round the cycle, the second something much more even, and data collected once a year cannot tell them apart. The data cannot even say whether the process has a preferred direction.

But look at the table. Its three rows are almost identical, because a year is a long time for these rates: the complex eigenvalues of the table have size about $0.0002$, so any difference between starting states has decayed to that level. That is not a coincidence of this example. A second branch shifts the eigenvalue’s imaginary part by at least $\pi$ away from the first, and the sector then demands that its real part be at least $\pi\sqrt3$ in size, so the eigenvalue of the table is below $e^{-\pi\sqrt 3} \approx 0.0043$. Two sets of rates can stand behind one table only when the table has nearly forgotten where it started. A table whose rows still differ noticeably — which is to say, any table worth estimating rates from — has at most one valid set. The ambiguity is real and it is confined to data that carries almost no information about the starting state, which is where one would expect a summary to stop distinguishing mechanisms.

Where the question is asked of real tables #

The best-documented case is credit ratings. Rating agencies publish yearly migration tables — the share of bonds rated A at the start of a year that are rated BBB, or in default, at its end — and the pricing of credit derivatives needs the corresponding tables for a quarter or a month. If the yearly table is $e^{Q}$, the monthly one is $e^{Q/12}$, so the rates are exactly what is wanted. Robert Israel, Jeffrey Rosenthal and Jason Wei examined published tables in 2001 and found that many were not embeddable: the principal logarithm had small negative rates, typically for moves between distant grades that are rare in a year but implied by chains of moves between neighbouring grades. Their proposed repairs — setting the negative rates to nought and redistributing, or searching other branches — produce a rate matrix that reproduces the table approximately rather than exactly, and the size of the discrepancy is itself a measure of how far the data is from steady rates.

Social mobility tables raised the same question earlier. Burton Singer and Seymour Spilerman in 1976 asked whether occupational mobility between generations could be described by constant rates operating continuously, and found tables in which it could not; the tables were better described by mixtures of populations moving at different speeds, the “movers and stayers” model that Isadore Blumen, Marvin Kogan and Philip McCarthy had proposed for labour mobility in 1955. A mixture of two steady processes can produce a table that no single rate matrix can, so a failed embedding is often the first evidence that a population is not one population.

Molecular evolution asks it in reverse. A substitution model for DNA is a rate matrix on the four bases, and the probability of a base changing along a branch of a phylogenetic tree is its exponential. Software that estimates trees assumes the embedding exists, and an estimated table that is not embeddable is a sign that the model’s assumption of constant rates along the branch has failed.

In every case the arithmetic is the same as in this essay’s figures. What changes is the meaning of a “no”: not “there is no logarithm”, but “this population was not moving by one steady rule”.

What the figures do not decide #

The census and the eigenvalue picture describe random tables, and the long-run behaviour that the chain that runs the same backwards and the chain that stops compute from a table is untouched by any of this: a table that has no rates behind it still has a stationary share and still has absorption times. What the embedding decides is only whether the table can be divided into shorter steps that all follow one steady rule. Random tables are not what data produces. Real yearly tables are usually close to the identity — most people do not change state in a year — and the census says that near the identity nearly all tables embed. The tables that fail in practice fail by small negative rates on rare moves, the 5% near $s = 0$, rather than by the gross violations of the random tables. The figures exaggerate how often embedding fails and understate how close a failure usually is.

The tests drawn here are necessary conditions and a finite search, and they have been assembled into a complete answer for three states: when the eigenvalues are distinct the search is finite and decisive, and when they are repeated there are explicit conditions that settle the continuum case. That complete answer for three states is recent, and it rests on casework that has no obvious general form. The figures also concern one table. A process observed at several intervals offers several tables, which must all be exponentials of the same $Q$ at different times, and that is a much more constrained and better-posed problem.

Still open: four states and beyond #

For four states the eigenvalues of a rate matrix lie within $45°$ of the negative axis rather than $30°$, the spirals change shape, and the case of distinct eigenvalues has been settled only within the last few years, by an explicit search through branches like the one used here. When eigenvalues repeat, a four-state table can have a continuum of real logarithms of more than one kind, and deciding whether any member of the continuum has non-negative off-diagonal entries is a question about a family of matrices rather than a list, for which no general procedure is known.

For any number of states the image of the sector bounds where each eigenvalue of an embeddable table can lie, but a table has several eigenvalues and they constrain each other. Which lists of eigenvalues belong together to some embeddable table is the steady-rate form of the inverse eigenvalue problem for stochastic matrices, which asks the same of any table and is itself open beyond small sizes. Nor is it known, for a table that is not embeddable, what the nearest embeddable table is in any useful sense — the repairs used for credit ratings are heuristics, and whether the closest table with steady rates behind it can be found efficiently is open.