Probability and Markov generators

How does a list of random transitions become an equation for probabilities? A continuous-time Markov generator records the rate of every allowed change and the corresponding loss of probability from its starting state. You will construct that matrix, solve a two-state process, and identify which transpose acts on observables. These tools lead directly to the finite-ring TASEP lesson.

Required background. Fractions, elementary probability, and multiplication of a finite matrix by a column. A derivative will mean an instantaneous rate of change; the needed first-order equation is solved below. No quantum-mechanical background is required.

Helpful background. The stochastic conventions reference collects the distribution, observable and current conventions used in this sequence.

Random jumps and their rates

Let $X_t$ take values in a finite set of states $\{1,\ldots,K\}$. In a time-homogeneous Markov process, the probabilities of future changes depend on the present state and elapsed time, not on the earlier path. Specify a constant rate $w_{j\leftarrow i}\geq0$ for each transition from $i$ to a different state $j$:

$$\Pr(X_{t+\Delta t}=j\mid X_t=i) =w_{j\leftarrow i}\Delta t+o(\Delta t), \qquad j\ne i.$$

The remainder divided by $\Delta t$ tends to zero as $\Delta t\to0^+$. Rates have units of inverse time. A rate of two per second is not a probability of two; it describes the slope of a small-time probability.

Define the total exit rate from $i$ by

$$\gamma_i=\sum_{j\ne i}w_{j\leftarrow i}.$$

Over a short interval, the probability of remaining in $i$ is $1-\gamma_i\Delta t+o(\Delta t)$. This linear expression is a small-time expansion, not an exact probability for arbitrarily large $\Delta t$.

If the process starts in $i$, let $T_i$ be the time until its first jump. The Markov property gives the survival equation $S_i'(t)=-\gamma_iS_i(t)$ with $S_i(0)=1$, so

$$\Pr(T_i\gt t)=e^{-\gamma_i t}, \qquad \mathbb E[T_i]=\frac1{\gamma_i}\quad(\gamma_i\gt0).$$

Conditional on a jump, its destination is $j$ with probability $w_{j\leftarrow i}/\gamma_i$. Independent exponential clocks for the possible exits give precisely this rule. If $\gamma_i=0$, the state is absorbing: no jump occurs while the process remains there.

Entry check and repair

A state has two possible exits, with rates $2r$ and $r$, where $r\gt0$. Is its mean waiting time $1/(2r)$, $1/r$, or $1/(3r)$? What is the probability that the first exit is the faster one?

Repair. The minimum of the two exponential clocks has survival probability

$$e^{-2rt}e^{-rt}=e^{-3rt}.$$

Thus the mean waiting time is $1/(3r)$. The destination probabilities are $2/3$ and $1/3$. The process does not take both exits at once, and choosing equally between the exits would ignore their unequal rates.

Assemble a probability-column generator

Write $p_i(t)=\Pr(X_t=i)$ and put these numbers in the column $p(t)$. Probability enters state $j$ from all other states and leaves it at rate $\gamma_jp_j$:

$$\frac{dp_j}{dt} =\sum_{i\ne j}w_{j\leftarrow i}p_i-\gamma_jp_j.$$

This is $dp/dt=Qp$, with

$$Q_{ji}=w_{j\leftarrow i}\quad(j\ne i), \qquad Q_{ii}=-\gamma_i.$$

A column describes departures from one starting state. First put its outgoing rates in the destination rows, then put minus their sum on its diagonal. Every column therefore sums to zero:

$$\mathbf1^{\mathsf T}Q=0, \qquad \frac d{dt}\sum_i p_i(t)=0.$$

Together with nonnegative off-diagonal entries, this constructs a finite continuous-time Markov generator. Its transition matrix is $e^{tQ}$ for $t\geq0$: columns remain normalized and entries are nonnegative. One way to see the latter facts is to approximate evolution by many sufficiently small steps $I+(t/n)Q$, whose entries are nonnegative and columns sum to one, and then take $n\to\infty$.

This is the same destination-row, source-column convention used for exclusion processes in Golinelli and Mallick 2006, § II.A, printed pp. 2–3, equations (1)–(2), PDF. Their Markov matrix is called $M$; we call it $Q$ to reserve $M$ for particle number in the next lesson.

A two-state process worked through

Use states $0,1$ with $0\to1$ at rate $\alpha\gt0$ and $1\to0$ at rate $\beta\gt0$. In that order,

$$Q=\begin{pmatrix}-\alpha&\beta\\\alpha&-\beta\end{pmatrix}, \qquad p_0+p_1=1.$$

The second component obeys

$$p_1'=\alpha p_0-\beta p_1 =\alpha-(\alpha+\beta)p_1.$$

Subtract the constant $\alpha/(\alpha+\beta)$ from both sides. The difference decays exponentially, giving

$$p_1(t)=\frac{\alpha}{\alpha+\beta} +\left(p_1(0)-\frac{\alpha}{\alpha+\beta}\right) e^{-(\alpha+\beta)t}.$$

The stationary distribution, meaning a normalized nonnegative column $\pi$ with $Q\pi=0$, is

$$\pi=\frac1{\alpha+\beta}\begin{pmatrix}\beta\\\alpha\end{pmatrix}.$$

For $\alpha=2r$, $\beta=r$, and an initial state certainly equal to $0$,

$$p_1(t)=\frac23(1-e^{-3rt}), \qquad p_0(t)=\frac13+\frac23e^{-3rt}.$$

State $1$ is more frequent at stationarity because it is entered more quickly and left more slowly. Both probabilities sum to one at every time. Reporting results with $r=1$ means using the dimensionless time $rt$; it does not remove the model’s time scale.

Observables use the transpose

An observable is a list of values $f_i=f(i)$, such as whether a site is occupied or how many moves are currently possible. It need not be nonnegative or sum to one. Its mean is

$$\mathbb E[f(X_t)]=f^{\mathsf T}p(t).$$

For a real observable independent of time,

$$\frac d{dt}\mathbb E[f(X_t)] =f^{\mathsf T}Qp(t) =(Q^{\mathsf T}f)^{\mathsf T}p(t).$$

The observable generator is therefore $\mathcal L=Q^{\mathsf T}$. Its action has an especially useful form:

$$(\mathcal Lf)_i =\sum_{j\ne i}w_{j\leftarrow i}\,[f_j-f_i].$$

Each allowed jump contributes its rate times the change in the observable. For the two-state example and the indicator $f=(0,1)^{\mathsf T}$,

$$\mathcal Lf=(\alpha,-\beta)^{\mathsf T}, \qquad \frac d{dt}\mathbb E[f]=\alpha p_0-\beta p_1.$$

The same transpose governs the conditional expected future value $g_i(t)=\mathbb E[f(X_t)\mid X_0=i]$: $g(t)=e^{tQ^{\mathsf T}}f$. Here $i$ labels a starting state, while $p_i(t)$ labels a probability at the observation time. Distinguishing these meanings prevents a common direction error.

Distributions, trajectories and decay modes

A trajectory is one random sequence of states and waiting times. A probability column describes the distribution of trajectories at a specified time. Sampling every trajectory at the same observation time estimates $p(t)$; listing the states seen immediately after jumps uses a different sampling rule. States with shorter holding times can appear more often in such a list. The TASEP laboratory will test this distinction explicitly.

A vector $v$ with $Qv=Ev$ and $E\ne0$ is a decay or oscillation mode, not automatically a probability distribution. Indeed,

$$0=\mathbf1^{\mathsf T}Qv =E\,\mathbf1^{\mathsf T}v \quad\Longrightarrow\quad \sum_i v_i=0.$$

If $v$ is nonzero and real, it must have both positive and negative components. A physical distribution can contain a small real mode as a perturbation of a stationary distribution, provided the resulting probabilities remain nonnegative. Complex modes require an appropriate real combination. The word “eigenvector” alone imposes neither positivity nor normalization.

Exercises

Guided practice: build a three-state generator

In the state order $(A,B,C)$, allow $A\to B$ at rate $2r$, $A\to C$ at rate $r$, $B\to A$ at rate $r$, and $C\to B$ at rate $3r$. There are no other jumps. Construct $Q$, find the initial derivative from $p(0)=(1,0,0)^{\mathsf T}$, and solve for the stationary distribution.

Hint

The exit rates are $(3r,r,3r)$. In $Q\pi=0$, the first and third rows give $\pi_B=3\pi_A$ and $\pi_C=\pi_A/3$; normalization fixes the remaining scale.

Solution

The generator and the initial derivative are

$$Q=r\begin{pmatrix}-3&1&0\\2&-1&3\\1&0&-3\end{pmatrix}, \qquad p'(0)=r\begin{pmatrix}-3\\2\\1\end{pmatrix}.$$

All off-diagonal entries are nonnegative and every column sums to zero. The derivative transfers probability out of $A$ and into precisely its two permitted destinations. Solving the stationary equations gives

$$\pi=\frac1{13}(3,9,1)^{\mathsf T}.$$

Substitution checks the remaining row: $2(3)-9+3(1)=0$. The stationary probabilities are unequal even though all three states participate in the process. From $A$, the waiting time has mean $1/(3r)$ and the next state is $B$ with probability $2/3$.

Independent practice: a signed vector inside a probability

Return to the two-state process with $\alpha=2r$ and $\beta=r$. Show that $v=(1,-1)^{\mathsf T}$ is an eigenvector of $Q$. Find all real $a$ for which

$$p(t)=\pi+a e^{-3rt}v$$

is a probability distribution for every $t\geq0$. For the observable $f=(1,-1)^{\mathsf T}$, compute its mean and initial rate of change, using $Q^{\mathsf T}f$ as a check.

Hint

The components sum to one because $v$ sums to zero. Check nonnegativity at $t=0$ and note that the exponential then shrinks toward zero. An observable can have the same entries as a mode without having the same role.

Solution

Direct multiplication gives $Qv=-3rv$. Since $\pi=(1/3,2/3)^{\mathsf T}$, nonnegativity at $t=0$ requires

$$-\frac13\leq a\leq\frac23.$$

For such $a$, later distributions are convex combinations of $p(0)$ and $\pi$, so the same condition suffices for all later times. The mean observable is

$$\mathbb E[f(X_t)]=-\frac13+2a e^{-3rt}, \qquad \left.\frac d{dt}\mathbb E[f(X_t)]\right|_{t=0}=-6ra.$$

Independently, $Q^{\mathsf T}f=(-4r,2r)^{\mathsf T}$; its average in $p(0)$ equals $-6ra$. Applying $Q$ to $f$ instead would be the wrong observable calculation. The bare vector $v$ is never a probability distribution, but it supplies a valid direction of change inside the stated interval of $a$.

Transfer: remove a return transition

Set $\beta=0$ while keeping $\alpha\gt0$, and start certainly in state $0$. Find the new stationary distribution and $p_1(t)$. What is the waiting time in state $1$? Finally compare taking $t\to\infty$ before $\alpha\to0^+$ with taking those limits in the opposite order.

Hint

There is now only the transition $0\to1$. The matrix formula remains valid with a zero exit rate. For the order of limits, begin with $p_1(t)=1-e^{-\alpha t}$ at fixed positive $\alpha$.

Solution

Now

$$Q=\begin{pmatrix}-\alpha&0\\\alpha&0\end{pmatrix}, \qquad \pi=(0,1)^{\mathsf T}, \qquad p_1(t)=1-e^{-\alpha t}.$$

State $1$ is absorbing, so its holding time is infinite with probability one. For every positive $\alpha$, eventual absorption occurs with probability one. Accordingly,

$$\lim_{\alpha\to0^+}\lim_{t\to\infty}p_1(t)=1, \qquad \lim_{t\to\infty}\lim_{\alpha\to0^+}p_1(t)=0.$$

The diverging time scale $1/\alpha$ explains the mismatch. At exactly $\alpha=0$ as well as $\beta=0$, $Q=0$ and every initial distribution is stationary. A stationary-state statement must retain the assumptions about which rates are positive.

From rates to exclusion

You can now translate a list of allowed jumps into a probability equation, predict holding times, and compute an observable’s instantaneous change. In TASEP on a finite ring, the states will be particle configurations and each allowed move will carry the same microscopic rate. Their total exit rates will still differ because exclusion permits different numbers of moves.

References

• Golinelli, Olivier, and Kirone Mallick. “The asymmetric simple exclusion process: an integrable model for non-equilibrium statistical mechanics.” Journal of Physics A: Mathematical and General 39 (2006), 12679–12705. DOI. Author version arXiv:cond-mat/0611701v1; Open PDF. Locators refer to its printed page labels.