💻 computer science

Equivalence of Continuous-Time Markov Chains and Linear Dynamical Systems

This short note establishes that the dynamics of a continuous-time $d$ -state Markov chain are equivalent to a linear dynamical system of dimension at most $d-1$ , demonstrating that such systems can be mutually embedded.

Original authors: Mihir Vahanwala

Published 2026-06-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mihir Vahanwala

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two different ways of describing how a system changes over time: one is a Markov Chain (like a board game where you move between states based on probabilities), and the other is a Linear Dynamical System (like a machine where numbers grow, shrink, or rotate based on fixed rules).

For a long time, mathematicians knew that in the "discrete" world (where time ticks forward in steps, like seconds on a clock), these two systems are essentially the same thing in disguise. You can turn one into the other without losing any information.

This short paper says: "Guess what? The same magic trick works in the 'continuous' world too." In the continuous world, time flows smoothly like a river, not in steps. The author, Mihir Vahanwala, proves that you can translate between these two smooth-flowing systems just as easily.

Here is the breakdown using simple analogies:

1. The Two Characters

The Continuous Markov Chain: Think of this as a group of people in a room. At any moment, people might move from one corner to another.
- The rules are strict: The total number of people must always stay the same (100% probability).
- The "engine" driving this is a special matrix (a grid of numbers) where the columns add up to zero. This ensures that if someone leaves a corner, they must arrive somewhere else.
The Linear Dynamical System: Think of this as a set of dials on a control panel. The numbers on the dials change smoothly over time based on a mathematical formula.
- These dials don't have to represent "people" or "probabilities." They can be any numbers.
- However, the paper shows that if you have a system with $d$ states, you can actually describe its entire movement using a control panel with only $d-1$ dials.

2. The Big Discovery (The "Translation")

The paper proves two main things, which are like two sides of the same coin:

Theorem 1: Shrinking the Machine
If you have a complex Markov Chain with $d$ states (like a room with $d$ corners), you don't actually need all $d$ dimensions to describe how it moves.

The Analogy: Imagine a puppet show with $d$ puppets. The paper says you can actually describe the whole show's movement using a smaller, simpler machine with only $d-1$ levers.
How it works: The author shows you can mathematically "compress" the Markov Chain. You separate the "steady state" (where the system eventually settles down) from the "moving parts." The moving parts can be described by a smaller, simpler linear system. It's like realizing that while the whole orchestra is playing, the melody can be written down on a single sheet of music with fewer notes than the total number of instruments.

Theorem 2: Expanding the Machine
Conversely, if you have a simple linear system with $d-1$ dials, you can "embed" it into a Markov Chain with $d$ states.

The Analogy: If you have a simple machine with $d-1$ gears, you can build a slightly larger room with $d$ corners and design the movement rules so that the people in the corners move exactly in sync with your gears.
The Catch: You have to add a little bit of "padding" (a specific constant value) to make sure the probabilities add up correctly, but the core movement is identical.

3. Why is this cool? (The "Zero" Secret)

The paper relies on a clever mathematical trick involving a "zero eigenvalue."

The Metaphor: In a Markov Chain, there is always a "zero" hidden in the math. This zero represents the fact that the total probability is always conserved (it never disappears or appears out of nowhere).
Because this "zero" is special, it acts like a pivot point. The author proves that because of this pivot, the system effectively has one less degree of freedom than it looks like it has. It's like a spinning top: it looks like it's moving in 3D space, but because it's balanced on a point, its essential movement can be described in fewer dimensions.

Summary

The paper is a mathematical bridge. It tells us that Continuous-Time Markov Chains (probability flows) and Linear Dynamical Systems (smooth number flows) are not two different species. They are the same animal wearing different costumes.

If you have a probability system, you can strip away the "probability" rules and see the underlying linear machine underneath.
If you have a linear machine, you can dress it up in "probability" clothes and watch it behave like a Markov Chain.

The author provides the exact blueprints (the matrices and formulas) to build these costumes, proving that the complexity of a $d$ -state system is mathematically equivalent to a $(d-1)$ -dimensional linear system.

Technical Summary: Equivalence of Continuous-Time Markov Chains and Linear Dynamical Systems

Problem Statement
This short note addresses the structural relationship between continuous-time linear dynamical systems and continuous-time Markov chains (CTMCs). While it is a known result in the discrete-time setting that the dynamics of a $d$ -state Markov chain are governed by a linear dynamical system of dimension at most $d-1$ (and vice versa), the author investigates whether an analogous equivalence holds in the continuous-time domain. Specifically, the paper seeks to establish that the evolution of a $d$ -state CTMC can be reduced to a linear dynamical system of dimension $d-\ell$ (where $\ell$ is the multiplicity of the zero eigenvalue), and conversely, that a linear dynamical system of dimension $d-1$ can be embedded into a $d$ -state CTMC.

Methodology
The paper employs linear algebraic techniques, specifically spectral decomposition and matrix exponentiation, to derive the equivalence. The methodology relies on the following core steps:

Spectral Analysis of Generator Matrices: The author first establishes a lemma regarding stochastic generator matrices ( $A$ ). It is proven that 0 is always an eigenvalue of $A$ with equal algebraic and geometric multiplicity ( $\ell$ ), and all other eigenvalues possess strictly negative real parts. This is derived by relating $A$ to a discrete stochastic matrix $M = I + aA$ and applying Perron-Frobenius theory.
Subspace Decomposition: The state space $\mathbb{C}^d$ is decomposed into two orthogonal subspaces: $V_0$ , spanned by the eigenvectors corresponding to the eigenvalue 0, and $W$ , spanned by the generalized eigenvectors of all non-zero eigenvalues.
Matrix Transformation: Using a change-of-basis matrix $R = [P \mid Q]$ , where columns of $P$ and $Q$ form bases for $V_0$ and $W$ respectively, the generator matrix $A$ is transformed into a block-diagonal form. This allows the matrix exponential $\exp(At)$ to be separated into a constant term (associated with the steady state) and a dynamic term (associated with the transient behavior).
Embedding Construction: For the converse direction, the paper constructs a specific embedding matrix $Q$ and a scalar $\rho$ to map a lower-dimensional generator matrix $C$ into a higher-dimensional stochastic generator matrix $A$ , ensuring the resulting system satisfies the properties of a CTMC (non-negative off-diagonal entries and column sums of zero).

Key Contributions and Results
The paper presents two primary theorems that formalize the equivalence:

Theorem 1 (Reduction): Given a distribution $v$ and a stochastic generator matrix $A \in \mathbb{Q}^{d \times d}$ with eigenvalue 0 having multiplicity $\ell \ge 1$ , one can compute a reduced generator matrix $B \in \mathbb{Q}^{(d-\ell) \times (d-\ell)}$ , an embedding matrix $Q$ , a steady-state distribution $s$ , and a vector $u$ such that for all $t \ge 0$ :
$\exp(At)v = s + Q \exp(Bt)u$
Crucially, the choice of $Q$ is independent of the initial distribution $v$ . The term $Q \exp(Bt)u$ converges to 0 as $t \to \infty$ , leaving only the steady state $s$ .
Theorem 2 (Embedding): Given a vector $u \in \mathbb{Q}^{d-1}$ and a generator matrix $C \in \mathbb{Q}^{(d-1) \times (d-1)}$ , one can compute parameters $\rho, \eta$ , a distribution $v$ , and a stochastic generator matrix $A \in \mathbb{Q}^{d \times d}$ such that for all $t \ge 0$ :
$\exp(At)v = s + \eta e^{-\rho t} \cdot Q \exp(Ct)u$
Here, $s$ and $Q$ are fixed choices ( $s = \mathbf{1}_d/d$ and a specific block matrix $Q$ ). The scalar $\rho$ is chosen sufficiently large to ensure the off-diagonal entries of the constructed generator matrix remain non-negative.

Significance and Claims
The author explicitly states that the purpose of this note is to "record" that the core results known for discrete-time linear dynamical systems (specifically referencing prior work in [1] and [2]) also hold in the continuous-time setting. The paper does not propose new applications or experimental validations. Instead, its significance lies in providing a rigorous mathematical proof of this structural equivalence, demonstrating that the dynamics of a $d$ -state continuous-time Markov chain are fundamentally governed by a linear dynamical system of dimension at most $d-1$ , and that any such lower-dimensional system can be embedded into a Markov chain. The proofs mirror the logic found in the cited discrete-time literature, adapted to the properties of generator matrices and matrix exponentials.

1. The Two Characters

2. The Big Discovery (The "Translation")

3. Why is this cool? (The "Zero" Secret)

Summary

Technical Summary: Equivalence of Continuous-Time Markov Chains and Linear Dynamical Systems

More like this