Continuous-time Markov chain

A continuous-time Markov chain waits an exponential time of rate $q_i$ in state $i$ and then jumps according to probabilities $p_{ij}=q_{ij}/q_i$.

For a finite-state continuous-time Markov chain, a transition intensity matrix has nonnegative off-diagonal rates $q_{rs}$ and $q_{rr}=-{\sum }_{s\ne r}{q}_{rs}$. Every row sums to zero. In the time-homogeneous case its transition probability matrix is the matrix exponential $P(t)=e^{tQ}$. An absorbing state has a zero row.

For a finite irreducible Markov chain in continuous time, time averages converge almost surely to averages under its unique stationary distribution, from any initial state. Applying this to an activation indicator yields the corresponding throughput.

A continuous-time Markov chain is nonexplosive when it makes only finitely many jumps in every finite time interval, almost surely. Uniformly bounded total jump rates suffice. Another useful criterion bounds the states visited over each finite interval by a random finite set on which rates are bounded.

Global balance equates total stationary incoming and outgoing transition intensities at each state. Detailed balance for a continuous-time Markov chain is sufficient but stronger: it equates each pair separately.

A jump process with event types $k$, increments ${\nu }_k$, and rates $a_k(X)$ can be represented as $X(t)=X(0)+{\sum }_k{\nu }_k{P}_k({\int }_0^t{a}_k(X(s-))ds)$, with independent unit-rate Poisson processes. This represents the Markov jump-process generator through time-changed counts.

Place one distinct label at each vertex of a finite connected weighted graph. At rate $c_{uv}=c_{vu}\ge 0$, interchange the labels at $u$ and $v$. This continuous-time Markov chain has a uniform distribution on a finite set as its stationary distribution. The position of one label is the random walk with the same rates.

On a finite connected weighted graph, the interchange process and the single-label random walk with the same symmetric rates have equal spectral gaps. This is a substantial theorem, not just the elementary inclusion of the single-label spectrum in the full spectrum. A proof is given in Proof of Aldous' spectral gap conjecture, Theorem 1.1.

For an equilibrium chain with strictly positive stationary probabilities, reversed jump rates are $q_{ij}^{\ast }={\pi }_j{q}_{ji}/{\pi }_i$. Under detailed balance they equal the original rates, making the stationary path law reversible. Holding times and jump directions reverse together; this is more than symmetry of one-time distributions.

A partition-valued Markov chain in which every unordered pair of current blocks merges at rate one. On $n$ initial singleton blocks, the holding time with $j$ blocks is exponential with rate $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$. Restrictions to subsets of labels have the same law.

The consistent partition process on $\mathbb{N}$ whose finite restrictions are Kingman's coalescent. It starts with infinitely many singleton blocks.

For $t>0$, the number $B_t$ of blocks is finite almost surely. On a finite restriction, the expected time to reach $m$ blocks is at most ${\sum }_{j>m}2/[j(j-1)]=2/m$. Markov inequality, followed by increasing the restriction, gives $\mathbb{P}(B_t>m)\le 2/(mt)$. Let $m\to \infty$, then use rational times and monotonicity to obtain the assertion simultaneously for every $t>0$.

The entry count $N_s(t)$ counts jumps of a continuous-time Markov chain into state $s$ by time $t$, excluding initial occupation. It is a counting process. For homogeneous transition intensities, its mean has derivative ${\sum }_{i\ne s}{p}_{ri}(t)q_{is}$ conditional on initial state $r$, so its expected value is the sum of incoming rates times the expected occupation times of a continuous-time Markov chain. This density is an expected count rate, not necessarily a normalized probability density function.

The occupation time records the duration spent in a state of a continuous-time Markov chain. Conditional on $Z(0)=r$, its expected value is ${\int }_0^t{p}_{rs}(u)du$, where $p_{rs}$ is the transition probability.

The holding time of a continuous-time Markov chain is the time spent in its current state before the next jump. In state $i$ it has an exponential distribution of rate equal to the total outgoing rate $q_i$.

A state's holding time in a time-homogeneous continuous-time Markov chain is exponentially distributed with rate $-q_{rr}>0$. Its mean is $-1/q_{rr}$; the probability that its next jump is to state $s$ is $q_{rs}/(-q_{rr})$. An absorbing state has infinite holding time.

For an exponential distribution with positive rate $\lambda$, the mean is $1/\lambda$. A confidence interval for the rate transforms to one for the mean by reversing and inverting its endpoints. The monotonic transformation preserves the coverage event; it does not give a prediction interval for one realized holding time.

For transition rate $w_{ij}$ from state $i$ to state $j$, the master equation is

For edge current $J_{ij}=w_{ij}{P}_i-w_{ji}{P}_j$, the total entropy production rate isIt vanishes precisely when every occupied edge satisfies detailed balance.

A continuous-time random walk waits a random time at each site before jumping. Constant outgoing rates produce an exponential residence time, while the relative transition rates determine the destination of the next jump.

A finite-state process has generator $Q$ exactly when, for every function $f$ on the state space,is a martingale with respect to the process filtration.

A Q-matrix has nonnegative off-diagonal entries and row sums zero. Its diagonal entry is the negative total rate out of the state.

For a continuous-time Markov chain, $P_{ij}(t)={\mathbb{P}}_i(X_t=j)$ and the matrices satisfy $P(s+t)=P(s)P(t)$. On a finite state space with Q-matrix $Q$, $P(t)=e^{tQ}$.

Sample a finite-state continuous-time Markov chain with generator $Q$ at the independent arrival times of a rate-$\lambda$ Poisson process. The sampled states form a discrete-time Markov chain with transition matrixIts invariant distributions are exactly those of the continuous-time chain.

For a finite-state continuous-time Markov chain with Q-matrix $Q$, the backward and forward equations are $P^{\prime }(t)=QP(t)$ and $P^{\prime }(t)=P(t)Q$, respectively.

A Markov reward model attaches a reward rate to each state and integrates it over the time spent there.

For transition rates $q_{nm}$, the generator acts on a function $f$ byWhenever the expectations are finite,Choosing polynomial functions $f$ gives differential equations for the moments.

For jumps $x\mapsto x+{\nu }_r$ of rates $a_r(x)$, the forward operator acts on a probability mass function byIt is adjoint to the Markov jump-process generator $Lf(x)={\sum }_r{a}_r(x)[f(x+{\nu }_r)-f(x)]$.

Conditioned on a finite jump path $i_0,\dots ,i_n$, the holding times are independent exponentials with the corresponding rates. Multiplying the probability of occupying $i_n$ at time $t$ by $q_{i_n}$ turns its simplex density into a product symmetric under reversal of the time portions and the state sequence.

For $h>0$, the fixed-time skeleton has matrix $P(h)$. If $q_i$ is the holding rate, then for $nh\le t\le (n+1)h$,Thus ${\int }_0^{\infty }{p}_{ii}(t)dt$ diverges exactly when ${\sum }_n{p}_{ii}(nh)$ does, proving recurrence equivalence for an irreducible chain.

The jump chain records the successive states visited by a continuous-time Markov chain while discarding its holding times.

On $\mathbb{N}$, let the chain jump from every $i\ge 1$ to $i+1$ with probability $p$ and to $i-1$ with probability $1-p$, and jump from zero to one. It is recurrent exactly when $p\le 1/2$; at $p=1/2$ it is null recurrent.

For holding rates $q_i$, a measure $\pi$ satisfies $\pi Q=0$ exactly when ${\mu }_i=q_i{\pi }_i$ is invariant for the jump chain. Thus ${\pi }_i={\mu }_i/q_i$ when normalization is possible.

Even when the jump chain has invariant probability $\mu$, the continuous-time invariant measure ${\mu }_i/q_i$ may have infinite mass if holding rates become too small, producing infinite mean return time.

A recurrent jump chain with infinite invariant measure $\mu$ can yield a positive-recurrent continuous-time chain when ${\sum }_i{\mu }_i/q_i<\infty$.

If the jump chain visits a state of finite holding rate infinitely often, the sum of its independent positive holding times at that state diverges almost surely, preventing explosion.

For a continuous-time Markov chain whose jump times tend to infinity, the chain and its jump chain have the same directed paths of positive-probability jumps. They are therefore irreducible simultaneously, and a state is recurrent for one exactly when it is recurrent for the other: the event of returning after departure depends only on the sequence of visited states.

Explosion occurs when infinitely many jumps take place in finite time.

If every holding rate of a continuous-time Markov chain is at most $C<\infty$, its holding times can be coupled as $E_n/q_{Y_n}\ge E_n/C$, where the $E_n$ are independent rate-one exponential random variables. The strong law of large numbers gives ${\sum }_n{E}_n=\infty$ almost surely, so the jump times tend to infinity and the chain cannot explode.

Conditional on a jump path $(Y_n)$, if ${\sum }_{n}1/q_{Y_n}<\infty$, then the sum of exponential holding times has finite expectation and is finite almost surely.

Suppose a transient nearest-neighbour jump chain on $\mathbb{N}$ has uniformly bounded expected visits to each state and the holding rate at $i$ grows geometrically. Thenso the continuous-time chain explodes almost surely.

For a finite-state chain with transition semigroup $P(t)=e^{tQ}$, a probability row vector $\pi$ is invariant when $\pi P(t)=\pi$ for every $t\ge 0$. Equivalently,

Every closed communicating class of a finite Markov chain has its own invariant probability distribution. All invariant distributions are convex combinations of those class distributions. In particular, a finite irreducible chain has a unique invariant distribution, while a reducible chain may have many.

An explosive chain can have a summable solution of $\pi Q=0$ despite being transient. Nonexplosion is needed for the usual equivalence between invariant distributions and positive recurrence.

A batch-birth linear-death process has transitionsWriting $P_n(t)=\mathbb{P}(N_t=n)$ and taking $P_j=0$ for $j<0$, its master equation is

For $m=\mathbb{E}N$ and $v=\mathrm{var}N$, the Markov jump-process generator applied to $n$ and $n^2$ givesConsequently

A birth-death process moves only between neighbouring nonnegative integer states, with state-dependent birth and death rates.

A pure birth process on ${\mathbb{N}}_0$ jumps only from $n$ to $n+1$, at a strictly positive rate ${\lambda }_n$. Its successive holding times are independent exponential variables of rates ${\lambda }_n$.

A pure birth process is nonexplosive exactly whenIts explosion time is the sum of independent exponential holding times. If the displayed series converges, that sum has finite expectation. If it diverges, the Laplace transform of the sum isforcing the sum to be infinite almost surely.

The pure birth process with rates ${\lambda }_n=\alpha n+\beta$, where $\alpha ,\beta >0$, combines linear reproduction with immigration. Starting from zero, its mean satisfiesand hence

The Yule process is the pure birth process with rate $n\lambda$ in population state $n$. Starting from one individual, it is nonexplosive because the independent holding times have divergent total almost surely.

For the Yule process starting from one individual, the generator applied to $f(n)=n$ givesand hence $\mathbb{E}{X}_t=e^{\lambda t}$.

Given $X_t=n+1$, the $n$ birth times in a Yule process have the law of the order statistics of independent variables with densityThis follows by dividing the joint holding-time density by
$\mathbb{P}(X_t=n+1)=e^{-\lambda t}(1-e^{-\lambda t}{)}^n$.

For individual birth and death rates $\lambda ,\mu$ and one initial individual, the finite-time extinction probability satisfiesWhen $\lambda \ne \mu$,

For birth rates $b_i$ and death rates $d_i$, a reversible measure satisfiesThus ${\pi }_{i+1}/{\pi }_i=b_i/d_{i+1}$, and it is an invariant distribution when the resulting measure is summable and the chain is nonexplosive.

For birth rates $b_n$, death rates $d_n$, and state probabilities $P_n$,

Since births and deaths change the state by $+1$ and $-1$,

For per-capita birth and death rates $B$ and $D$, the rates are $b_n=Bn$ and $d_n=Dn$. If $\mu =\mathbb{E}{N}_t$ and ${\sigma }^2=\mathrm{var}{N}_t$, thenThe expected value sees only the net growth rate $B-D$, whereas the variance also sees the total event rate $B+D$.

The $r$th falling factorial moment is $\mathbb{E}[(N{)}_r]$, where $(N{)}_r=N(N-1)\cdots (N-r+1)$.

If $N$ is Poisson with mean $\lambda$, then $\mathbb{E}[(N{)}_r]={\lambda }^r$; in particular, $\mathbb{E}N=\lambda$ and $\mathbb{E}[N(N-1)]={\lambda }^2$.

Approximating the population law by a Poisson law replaces its first two factorial moments by $\lambda$ and ${\lambda }^2$, closing a quadratic first-moment equation as a Riccati equation for $\lambda$.

For unit jumps with birth and death rates $b(x),d(x)$, the Fokker--Planck drift and diffusion in the conventionare $u=b-d$ and $D=(b+d)/2$.

Near a stable deterministic equilibrium, replace the drift by its linearization and the diffusion coefficient by its equilibrium value. The resulting Ornstein-Uhlenbeck approximation has a stationary normal distribution.

If boundary fluxes decay sufficiently fast, two integrations by parts givewhile the diffusion term contributes zero to the first moment.

For constant birth rate $\lambda$ and death rate $\delta$ away from zero, the chain is transient when $\lambda >\delta$, null recurrent when $\lambda =\delta$, and positive recurrent when $\lambda <\delta$.

The queue length in an $M/M/1$ queue is a birth-death process with constant arrival rate $\lambda$ and service rate $\mu$ while nonempty.

If potential arrivals form a Poisson process of rate $\lambda$ and an arrival seeing $n$ customers joins with probability $p(n)$, the queue length is a birth-death process with birth rate $b_n=\lambda p(n)$ and death rate $d_n=\mu$ for $n\ge 1$. Its stationary ratios, when normalizable, are

An $M/M/1$ queue is positive recurrent exactly when its traffic intensity $\rho =\lambda /\mu$ is below one.

When $\rho <1$, the equilibrium queue length has distribution ${\pi }_n=(1-\rho ){\rho }^n$ and mean $\rho /(1-\rho )$.

At equilibrium, the departure process of a stable $M/M/1$ queue is Poisson with the same rate as the arrival process.

If a served customer returns with probability $p$, thinning service completions gives effective external departure rate $\mu (1-p)$ for the queue-length process.

In equilibrium, a Bernoulli-feedback $M/M/1$ queue has the same queue-length process as an ordinary queue with service rate $\mu (1-p)$, so its external departures form a Poisson process of rate $\lambda$.

Starting with one customer, the mean busy period of an $M/M/1$ queue iswhen $\lambda <\mu$. It is infinite when $\lambda \ge \mu$.

An $M/M/\infty$ queue has Poisson arrivals of rate $\lambda$, independent exponential service times of rate $\mu$, and infinitely many servers. Its occupancy is a birth-death process with birth rate $\lambda$ and death rate $n\mu$ in state $n$.

For every $\lambda ,\mu >0$, an $M/M/\infty$ queue is positive recurrent and has the Poisson distribution with mean $\rho =\lambda /\mu$ as its unique stationary distribution:

In stationarity, the departure process of an $M/M/\infty$ queue is a Poisson process of rate $\lambda$. By time reversibility, the departures before any fixed time are independent of the occupancy at that time.

If $X_0=n$ and $p_t=e^{-\mu t}$, thenwith independent summands. The binomial term counts surviving initial customers; Poisson thinning gives the surviving later arrivals.

Writing $\rho =\lambda /\mu$, the stationary empty probability is $e^{-\rho }$. Alternating idle periods of mean $1/\lambda$ with busy periods and applying the renewal-reward theorem gives

An $M/M/s/K$ queue has arrivals forming a Poisson process of rate $\lambda$, $s$ servers with independent service times having an exponential distribution of rate $\mu$, and total system capacity $K\ge s$. Its occupancy is the finite birth-death process on $\{0,\dots ,K\}$ with

Put $\rho =\lambda /\mu$. The unique stationary distribution of an $M/M/s/K$ queue iswhere $Z$ is the sum of the displayed weights. Adjacent terms satisfy detailed balance for a birth-death process, so the queue is reversible in equilibrium.