Continuous-Time Markov Chains (CTMC)

WarningDraft

This lecture note is still being edited: the text may contain typos, inaccuracies, and locally unpolished spots. If you find something, please let the author know (contact details on the course page).

1 General information

1.1 The Markov property

Let \(\mathcal{X}\) be an at most countable set.

Definition 1 A random process \(\left(X_{t}, t \geqslant 0\right)\) with values in an at most countable space \(\mathcal{X}\) is called a continuous-time Markov chain (abbreviated CTMC) if it satisfies the Markov property: \[ \mathbb {P}\left(X_{t_{n+1}} = s_{n+1} \quad \left| \quad \begin{array}{rl} X_{t_n} & = s_{n} \\ X_{t_{n-1}} & = s_{n-1} \\ \cdots & \cdots \\ X_{t_0} & = s_{0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{t_{n+1}} = s_{n+1} \mid X_{t_n} = s_{n}\right) \] for any \(n \in \mathbb {N}\), \(0 \leq t_0 < t_1 < \ldots < t_{n} < t_{n+1}\), \(s_0, s_1, \ldots , s_{n+1} \in \mathcal{X}\).

The terminology repeats the discrete case.

• The set \(\mathcal{X}\) is called the phase space or state space of the Markov chain;

• The conditional probabilities

  \[ \mathbb {P}\left(X_{t}=j \mid X_{s}=i\right) \]

  are called the transition probabilities of the Markov chain.

• From the transition probabilities one can build transition probability matrices from time point \(s\) to time point \(t\):

  \[ \mathbf{P}_{s \to t} := \left( \mathbb {P}\left(X_{t}=j \mid X_{s}=i\right) \right)_{i, j \in \mathcal{X}}, \]

  where \(i\) is the row index and \(j\) is the column index of the matrix.

• \(\Pi^{(0)} = \left(\mathbb {P}\left(X_0 = j\right), j \in \mathcal{X}\right)\) is the initial distribution of the chain.

• \(\Pi^{(t)} = \left(\mathbb {P}\left(X_{t}=j\right), j \in \mathcal{X}\right)\) is the distribution of the chain at time \(t \geqslant 0\).

As in the discrete case, the finite-dimensional distributions are uniquely determined by the transition probabilities and the initial distribution. The properties of the transition probabilities remain the same.

Lemma 1 The transition probabilities \(\mathbf{P}_{s \to t}\), \(0 \leq s \leq t\), of a Markov chain satisfy the following properties.

1. \(\mathbf{P}_{s \to t}\) is a stochastic matrix (i.e. consisting of nonnegative entries, with every row summing to \(1\)) for any \(s,t\);

2. \(\mathbf{P}_{t \to t} = \mathbf{E}\) for any time \(0 \leq t\);

3. The Chapman-Kolmogorov equations hold: \(\forall s \leqslant u \leqslant t\)

   \[ \mathbf{P}_{s \to t} = \mathbf{P}_{s \to u} \cdot \mathbf{P}_{u \to t} \]

As in the discrete case, the properties listed are not only necessary but also sufficient for the existence of a Markov chain.

Theorem 1 Let \(\mathcal{X} \subset \mathbb {R}\) be an at most countable set, \(\Pi^{(0)}\) a probability distribution on \(\mathcal{X}\), and \(\mathbf{P}_{s \to t},\; 0 \leqslant s \leqslant\) \(t\), matrices possessing the properties from lemma Lemma 1. Then there exists a CTMC \(\left(X_{t}, t \geqslant 0\right)\) with phase space \(\mathcal{X}\) such that \(\Pi^{(0)}\) is its initial distribution and \(\mathbf{P}_{s\to t}\) are its transition probabilities.

A CTMC is called homogeneous if

\[ \mathbf{P}_{s \to t} = \mathbf{P}_{s + u \to t + u} \]

holds for any \(0 \leq s \leq t\), \(0 \leq u\).

From now on, unless stated otherwise, we consider only homogeneous CTMCs.

1.2 Standard stochastic semigroup

For a homogeneous CTMC we have

\[ \mathbf{P}_{s \to t} = \mathbf{P}_{0 \to t-s} \]

i.e. all transition probabilities are determined by the transition probabilities out of zero. As in the discrete case, let us introduce the notation

\[ \mathbf{P}_{t} := \mathbf{P}_{0 \to t} \]

For a homogeneous DTMC, the transition probabilities were completely determined by a single stochastic matrix \(\mathbf{P}\) of one-step transitions. In the continuous case, unlike discrete time, the distribution of a homogeneous Markov chain is determined not by a single matrix, but by an entire continuum of stochastic matrices \(\mathbf{P}_t, t \geq 0\). Moreover, we have

1. \(\mathbf{P}_0 = \mathbf{E}\);

2. \(\mathbf{P}_{t + s} = \mathbf{P}_{t} \cdot \mathbf{P}_{s}\) (the Chapman-Kolmogorov equations)

A family of stochastic matrices satisfying these properties is called a stochastic semigroup.

For any stochastic semigroup of (stochastic) matrices one can construct a homogeneous CTMC.

We have already imposed the homogeneity condition on our CTMC. In the discrete case we stopped there: the homogeneity condition turned out to be sufficient to obtain a fairly rich theory, characterize limiting behavior, and so on. In the continuous case, homogeneity alone is not enough, since some pathological examples arise. Let us look at them.

ExampleExample 1

Let \((X_t, t \geq 0)\) be a random process such that for any finite collection of time points \(0 \leq t_0 < \ldots < t_{n}\) the random variables \(X_{t_0}, \ldots , X_{t_n}\) are independent (jointly) and \(X_{t} \sim \operatorname {Ber}(1/2)\).

1. Prove that such a process exists;

2. Is this process a CTMC? If so, is it a homogeneous CTMC? If so, find the stochastic semigroup of transition probabilities.

3. Can one construct a modification of this process with a.s. right-continuous paths?

SolutionSolution

Enum-item(1)

Apply Kolmogorov’s extension theorem for consistent finite-dimensional distributions: define the finite-dimensional distributions as products of \(\operatorname {Ber}(1/2)\) at each time point — independence makes checking consistency trivial.

Enum-item(2)

This is a homogeneous CTMC. Transition matrices:

\[ \mathbf{P}_{t} = \begin{cases} \left(\begin{smallmatrix} 1 & 0\\ 0 & 1 \end{smallmatrix}\right), & t = 0 \\ \left(\begin{smallmatrix} 1/2 & 1/2\\ 1/2 & 1/2 \end{smallmatrix}\right), & t > 0 \end{cases} \]

Enum-item(3)

No. Let \((Y_t)\) be a modification with a.s. right-continuous paths. The modification has the same finite-dimensional distributions, so \(\mathbb {P}\left(Y_{t + h} = Y_t\right) = \frac{1}{2}\) for any \(h > 0\). But by right-continuity \(Y_{t + h} \to Y_t\) a.s. as \(h \to 0+\), and the process only takes the values \(0\) and \(1\) — hence \(\mathbb {P}\left(Y_{t+h} = Y_t\right) \to 1\). A contradiction.

The chain considered in the example can, in an arbitrarily small amount of time, make arbitrarily many jumps (from state \(0\) to \(1\) and back). To rule this out, let us impose on the stochastic semigroup the property of continuity at zero:

\[ \mathbf{P}_{t} \xrightarrow [t \to 0+]{} \underbrace{\mathbf{P}_0}_{= \mathbf{E}} \]

By this we mean the entrywise limit: for any \(i,j \in \mathcal{X}\),

\[ \begin{align} \underbrace{\left(\mathbf{P}_t\right)_{ij}}_{= \mathbb {P}_{i}\left(X_{t} = j\right)} & \xrightarrow [t \to 0+]{} \\ & \quad \underbrace{\left(\mathbf{P}_{0}\right)_{ij}}_{= \left(\mathbf{E}\right)_{ij} = \delta _{i}^{j}} \end{align} \]

A stochastic semigroup \((\mathbf{P}_t, t \geq 0)\) (and the corresponding CTMC) possessing continuity at zero is called standard. From now on, unless stated otherwise, we consider only standard homogeneous CTMCs.

Mn-extraAdditional material

In fact, continuity at zero implies right-continuity at every point \(s \geq 0\): \[ \mathbf{P}_{s + t} = \mathbf{P}_{s} \cdot \mathbf{P}_{t} \xrightarrow [t \to 0+]{} \mathbf{P}_{s} \cdot \mathbf{E} \] In the case of finite matrices, passing to the limit is straightforward, since a finite sum and a limit can be interchanged freely: \[ \begin{align} \lim _{t \to 0+}\left(\mathbf{P}_{s + t}\right)_{i,j} & = \lim _{t \to 0+}\left(\mathbf{P}_{s} \cdot \mathbf{P}_{t}\right)_{i,j} = \\ & = \lim _{t \to 0+}\left(\sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\mathbf{P}_{s}\right)_{i,l} \cdot \left(\mathbf{P}_{t}\right)_{l,j}\right) = \\ & = \sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \lim _{t \to 0+} \left(\mathbf{P}_{t}\right)_{l,j} \right) = \\ & =\sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \delta _{l}^j\right) = \left(\mathbf{P}_{s}\right)_{i,j} \end{align} \] In the case of infinite matrices, continuity is not so obvious: the limit and an infinite sum cannot always be interchanged. Here the Lebesgue dominated convergence theorem (in its version for series) comes to the rescue: the \(l\)-th term is bounded in absolute value by \(\left(\mathbf{P}_{s}\right)_{i,l}\), and \(\sum_{l}\left(\mathbf{P}_{s}\right)_{i,l} = 1 < \infty\) is a summable dominating sequence. For arbitrary states \(i,j \in \mathcal{X}\) we have \[ \begin{align} \lim _{t \to 0+}\left(\mathbf{P}_{s + t}\right)_{i,j} & = \lim _{t \to 0+}\left(\mathbf{P}_{s} \cdot \mathbf{P}_{t}\right)_{i,j} = \\ & = \lim _{t \to 0+}\left(\sum _{l \in \mathcal{X}} \left(\mathbf{P}_{s}\right)_{i,l} \cdot \left(\mathbf{P}_{t}\right)_{l,j}\right) = \\ & = \sum _{l \in \mathcal{X}} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \lim _{t \to 0+} \left(\mathbf{P}_{t}\right)_{l,j} \right) = \\ & =\sum _{l \in \mathcal{X}} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \delta _{l}^j\right) = \left(\mathbf{P}_{s}\right)_{i,j} \end{align} \] Left-continuity (and with it full, even uniform, continuity on \(\mathbb {R}_+\)) also holds — see the problem below.

ProblemProblem 1

Prove that the transition probabilities \(p_{i j}(t) := \left(\mathbf{P}_t\right)_{ij}\) of a standard stochastic semigroup are uniformly continuous on \(\mathbb {R}_{+}\) (in \(t\), for fixed \(i,j\)).

1.3 The generator (\(Q\)-matrix) of a CTMC

The following result, proved by Kolmogorov, is far from obvious: it turns out that if a stochastic semigroup is (entrywise) continuous at zero, then it is differentiable at zero.

Lemma 2 Let \((\mathbf{P}_t, t \geqslant 0)\) be a standard stochastic semigroup. Then a right derivative at zero exists for each entry: \[ \begin{align} \frac{d^+}{dt}\left(\mathbf{P}_{t}\right)_{ij}\bigg\rvert _{t=0} & = \\ & \quad \lim _{t \to 0+} \frac{\left(\mathbf{P}_t\right)_{ij} - \overbrace{\left(\mathbf{P}_0\right)_{ij}}^{=\delta _i^j}}{t} =: \mathbf{Q}_{ij} \end{align} \] where \(\forall i \neq j\) we have \(0 \leq \mathbf{Q}_{ij} < +\infty\), and \(\mathbf{Q}_{ii} \in [-\infty , 0]\).

See the proof in (Булинский and Ширяев 2005, chap. 4, § 16, Thm. 9).

The matrix \(\mathbf{Q}\) can be written concisely as

\[ \begin{align} & \qquad \qquad \qquad \qquad \qquad \qquad \mathbf{Q} = \mathbf{P}'_0 \\ & \text{(meaning the entrywise right derivative)} \end{align} \]

It is called the infinitesimal matrix, the generator, or the transition rate matrix of the CTMC \((X_t, t \geq 0)\) or of its stochastic semigroup \((\mathbf{P}_{t}, t \geq 0)\) (after all, \(\mathbf{Q}\) does not depend on the initial distribution of the chain, only on the transition probabilities, i.e. on the stochastic semigroup). From the lemma we know that the diagonal of \(\mathbf{Q}\) consists of nonpositive numbers, possibly even \(-\infty\). Off the diagonal are nonnegative (finite) numbers. The name generator is given to the matrix \(\mathbf{Q}\) because it can be used, in most cases, to uniquely recover the stochastic semigroup. Looking ahead, the formula is:

\[ \mathbf{P}_t = e^{\mathbf{Q}t} := \sum _{k=0}^{\infty }\frac{1}{k!}t^k \mathbf{Q}^k \]

Examples of generators:

\[ \begin{pmatrix} -1 & 1 \\ 3 & -3 \end{pmatrix}, \qquad \begin{pmatrix} -5 & 4 & 1 \\ 2 & -10 & 8 \\ 3 & 3 & -6 \end{pmatrix}, \qquad \begin{pmatrix} -14& 7 & 5 & 2\\ 0 & 0 & 0 & 0 \\ 3 & 7 & -10 & 0 \\ 1 & 1 & 1 & -3 \end{pmatrix} \tag{1}\]

Consider, for example, the 3rd generator. A CTMC with this generator (more precisely, one of its possible modifications with càdlàg paths) behaves as follows:

• If the chain finds itself in state \(i\), it stays in this state for a random time, distributed as \(\operatorname {Exp}(-\mathbf{Q}_{ii})\). For example, if it is in state \(1\), it will wait a time \(\operatorname {Exp}(14)\).

• When the waiting time in state \(i\) ends, the chain needs to jump to a new state. It picks the new state \(j\) at random, independently of past behavior, jumping to a given state with probability proportional to \(\mathbf{Q}_{ij}\). For example, if the chain was in state \(i=1\), it jumps from there to state \(2\) with probability \(\frac{7}{14}\), to state \(3\) with probability \(\frac{5}{14}\), and to state \(4\) with probability \(\frac{2}{14}\).

• A special case is a state with a zero diagonal entry: for the 3rd generator \(\mathbf{Q}_{22} = 0\), i.e. the waiting time in state \(2\) is distributed as \(\operatorname {Exp}(0)\), which it is natural to interpret as \(+\infty\): once the chain enters state \(2\), it stays there forever (an absorbing state).

ExampleExample 2

Let \(N_t\) be a stationary Poisson process of rate \(\lambda\).

1. Show that \(N_t\) is a CTMC, find its stochastic semigroup;

2. Show that the stochastic semigroup is standard;

3. Find the generator of the Poisson process.

SolutionSolution

Enum-item(1)

Let us prove the Markov property. Consider integers \(0 \leq a_1 \leq \dots \leq a_n \leq i \leq j\) (only these are worth considering). Then, due to independence of increments, we have

\[ \begin{align} \mathbb {P}\left(N_t = j \; \left| \; \begin{array}{rl} N_s & = i \\ N_{s_n} & = a_n \\ \cdots & \cdots \\ N_{s_1} & = a_1 \end{array}\right.\right) & = \mathbb {P}\left(N_t - N_s = j - i \; \left| \; \begin{array}{rl} N_s & = i \\ N_{s_n} & = a_n \\ \cdots & \cdots \\ N_{s_1} & = a_1 \end{array}\right.\right) = \\ & = \frac{(\lambda (t-s))^{j-i}}{(j-i)!}e^{-\lambda (t-s)} \\ \mathbb {P}\left(N_t = j \mid N_s = i\right) & = \mathbb {P}\left(N_t - N_s = j - i \mid N_s = i\right) = \frac{(\lambda (t-s))^{j-i}}{(j-i)!}e^{-\lambda (t-s)} \end{align} \]

The chain is homogeneous, since the transition probabilities depend only on the difference \(t-s\).

Enum-item(2)

The transition probability matrix:

\[ \begin{align} \mathbf{P}_t & = \begin{pmatrix} e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \frac{(\lambda t)^4}{4!}e^{-\lambda t} & \frac{(\lambda t)^5}{5!}e^{-\lambda t} & \dots \\ 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \frac{(\lambda t)^4}{4!}e^{-\lambda t} & \dots \\ 0 & 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \dots \\ 0 & 0 & 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix}\\ & = e^{-\lambda t}\begin{pmatrix} 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \frac{(\lambda t)^5}{5!} & \dots \\ 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \dots \\ 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \dots \\ 0 & 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \end{align} \]

Let us check standardness, i.e. the entrywise convergence \(\mathbf{P}_t \to \mathbf{E}\) as \(t \to 0+\). Diagonal entries: \(e^{-\lambda t} \to 1\). Off-diagonal entries (for \(j > i\)): \(\frac{(\lambda t)^{j - i}}{(j-i)!}e^{-\lambda t} \to 0\). In total \(\left(\mathbf{P}_t\right)_{ij} \to \delta_i^j\), so the semigroup is standard.

Enum-item(3)

The infinitesimal matrix:

\[ \begin{align} \mathbf{P}_t' & = -\lambda e^{-\lambda t}\begin{pmatrix} 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \frac{(\lambda t)^5}{5!} & \dots \\ 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \dots \\ 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \dots \\ 0 & 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} + \\ & \qquad + e^{-\lambda t}\begin{pmatrix} 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \frac{\lambda ^4 t^3}{3!} & \frac{\lambda ^5 t^4}{4!} & \dots \\ 0 & 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \frac{\lambda ^4 t^3}{3!} & \dots \\ 0 & 0 & 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \dots \\ 0 & 0 & 0 & 0 & \lambda & \lambda ^2 t & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \\ \mathbf{Q} & = \mathbf{P}_t'\vert _{t=0} = \begin{pmatrix} -\lambda & \lambda & 0 & 0 & 0 & 0 & \dots \\ 0 & -\lambda & \lambda & 0 & 0 & 0 & \dots \\ 0 & 0 & -\lambda & \lambda & 0 & 0 & \dots \\ 0 & 0 & 0 & -\lambda & \lambda & 0 & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \end{align} \]

This agrees with the intuition from the description above: in each state \(n\) the process waits a time \(\operatorname {Exp}(\lambda )\) (the interval between jumps of the Poisson process!), after which it jumps to \(n+1\) with probability \(\frac{\lambda }{\lambda } = 1\). Rate graph:

Rate graph of a Poisson process: transition \(n\to n+1\) at the constant rate \(\lambda\). A rate graph has no self-loops — the diagonal of the generator \(Q\) is recovered from the conservation condition (each row sums to zero).

The Poisson process is simultaneously a renewal process and a Markov chain. A natural question: is every renewal process Markovian?

ProblemProblem 2

Is every renewal process a Markov chain?

We call a \(Q\)-matrix any square matrix \(\mathbf{Q}\) of dimension \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\) such that

1. all diagonal entries are in \([-\infty , 0]\);

2. all off-diagonal entries are in \([0,+\infty )\);

3. \(\sum_{j \neq i}\mathbf{Q}_{ij} \leq -\mathbf{Q}_{ii}\) for every \(i \in \mathcal{X}\).

If all entries of the \(Q\)-matrix (namely, the diagonal entries) are finite and equality holds in the last item, i.e.

\[ \sum _{j \neq i}\mathbf{Q}_{ij} = -\mathbf{Q}_{ii} \quad \text{ for every } i \in \mathcal{X} \]

then such a \(Q\)-matrix is called conservative.

The generator of any CTMC is a \(Q\)-matrix, and in the case of finitely many states it will always be conservative. In the infinite case it can turn out to be non-conservative (and the diagonal may even contain \(-\infty\) — such states are called instantaneous); in our course we will not consider such chains, and details can be found in (Булинский and Ширяев 2005, chap. 4, § 16) and (Liggett 2010, sec. 2.4).

As in the discrete case, it is convenient to depict a chain as a directed graph: vertices are states, edges are nonzero off-diagonal rates \(\mathbf{Q}_{ij} > 0\). Such a graph is called a rate graph. Note two differences from the transition probability graph of a DTMC:

• the rate graph has no loops: the diagonal of a conservative \(Q\)-matrix is recovered from the off-diagonal entries (\(\mathbf{Q}_{ii} = -\sum_{j \neq i}\mathbf{Q}_{ij}\)), so it is not drawn;

• the edge weights are not probabilities but rates: they are nonnegative, but can exceed \(1\), and the sum of weights of outgoing edges can be anything.

For example, here is the rate graph for the 2nd generator from Equation 1:

Rate graph for the generator \(Q=\begin{pmatrix}-5&4&1\\2&-10&8\\3&3&-6\end{pmatrix}\): all six off-diagonal rates are positive, so the chain is irreducible.

1.4 Distribution of the chain vs. stochastic semigroup vs. generator

We are interested in the relationship between the distribution of the process, the stochastic semigroup, and the generator for a standard homogeneous CTMC. Can one uniquely recover one object given another? The stochastic semigroup is uniquely determined by the distribution of a homogeneous chain (it is simply the transition probabilities out of time zero), and the generator is uniquely determined (given standardness) by the stochastic semigroup (see lemma Lemma 2). Can one go in the other direction?

We have already stated a theorem (see Theorem 1) on constructing a chain from an initial distribution and transition probabilities in the general case. Let us state it for the homogeneous case.

Theorem 2 (Existence of a homogeneous CTMC) Let \(\mathcal{X}\) be a finite or countable set, let \((\mathbf{P}_t, t \geq 0)\) be a stochastic semigroup of dimension \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\), and let \(\Pi\) be some distribution on \(\mathcal{X}\). Then there exists a unique (in terms of the distribution of the process) homogeneous CTMC \((X_{t}, t \geq 0)\) with initial distribution \(\Pi\) and transition probabilities equal to \(\mathbf{P}_t\).

The distribution of the chain and the stochastic semigroup (together with the initial distribution) uniquely determine each other. But what about the generator (in the standard case)? It turns out that in the finite case the generator must be conservative, and the (standard) stochastic semigroup is uniquely recovered from it by the formula

\[ \mathbf{P}_t = e^{\mathbf{Q}t}, \quad t \geq 0 \]

In the infinite case things are not so simple: the generator does not always uniquely determine the stochastic semigroup (and correspondingly the process). In other words, for one and the same generator one can propose several chains with that given generator but with different distributions, different transition probabilities. The reason is the phenomenon of explosion; see the details in the section on countably many states below.

2 CTMCs with a finite number of states

Throughout this section we assume \(\mathcal{X}\) to be a finite set. As in the discrete-time case, the theory becomes much simpler in continuous time when the state space is finite.

2.1 Conservativeness of the generator

We know that the sum of any row of \(\mathbf{P}_t\) equals \(1\). Consequently, since for finite sums a limit and a sum can be freely interchanged, the sum of the row-wise derivatives at zero (i.e. the sum of a row of \(\mathbf{Q}\)) equals \(0\): for arbitrary \(i \in \mathcal{X}\) we have

\[ \begin{align} \sum _{j=1}^{\left|\mathcal{X}\right|} \mathbf{Q}_{ij} & = \\ & \quad \sum _{j=1}^{\left|\mathcal{X}\right|} \lim _{t \to 0+} \frac{\left(\mathbf{P}_t\right)_{ij} - \left(\mathbf{P}_0\right)_{ij}}{t} = \\ & = \lim _{t \to 0+} \sum _{j=1}^{\left|\mathcal{X}\right|} \frac{\left(\mathbf{P}_t\right)_{ij} - \left(\mathbf{P}_0\right)_{ij}}{t} = \\ & = \lim _{t \to 0+} \frac{1 - 1}{t} = 0 \end{align} \]

We know (see lemma Lemma 2) that off the diagonal, the entries of the matrix \(\mathbf{Q}\) are nonnegative and finite. Hence the diagonal entry is also a finite number.

Lemma 3 (Conservativeness of the generator of a CTMC with a finite number of states) If \(\mathcal{X}\) is finite, then

• all entries of \(\mathbf{Q}\) are finite;

• the sum of any row equals \(0\). In other words, off the diagonal are nonnegative numbers, and

  \[ -\mathbf{Q}_{ii} = \sum _{\substack {j \in \mathcal{X}\\ j \neq i}}\mathbf{Q}_{ij} \in [0, +\infty ) \]

2.2 Kolmogorov’s forward and backward equations: recovering the stochastic semigroup from the generator

The matrix \(\mathbf{Q}\) completely determines the entire stochastic semigroup. From it one can recover the transition probabilities using Kolmogorov’s differential equations.

Theorem 3 (Kolmogorov’s equations) Let \((X_t, t \geq 0)\) be a CTMC with a finite number of states, let \(\mathbf{P}_{t}, t \geq 0\), be its stochastic semigroup, and let \(\mathbf{Q} = \mathbf{P}'_t \mid_{t= 0}\) be its generator. Then

• Kolmogorov’s backward equations hold: \(\mathbf{P}'_t = \mathbf{Q} \cdot \mathbf{P}_t\) for all \(t \geq 0\);

• Kolmogorov’s forward equations hold: \(\mathbf{P}'_t = \mathbf{P}_t \cdot \mathbf{Q}\) for all \(t \geq 0\);

In the theorem, the entrywise derivative is meant. In other words, for any \(i,j \in \mathcal{X}\) we have

\[ \frac{d}{dt} \left(\mathbf{P}_t\right)_{ij} = \left(\mathbf{Q} \cdot \mathbf{P}_t\right)_{ij} = \left(\mathbf{P}_t \cdot \mathbf{Q}\right)_{ij} \]

for any \(t \geq 0\).

The forward and backward equations form a system of differential equations. They are named this way based on the position of the generator. In the forward equations the generator stands “in back” (on the right): \(\mathbf{P}_t \cdot \mathbf{Q}\). In the backward equations, correspondingly, “in front” (on the left): \(\mathbf{Q} \cdot \mathbf{P}_t\).

Kolmogorov’s equations allow us to derive equations for the distribution of the chain \(\Pi^{(t)}\) at an arbitrary time \(t \geq 0\) (recall that we understand \(\Pi^{(t)}\) as a row vector).

Lemma 4 We have \[ \left(\Pi ^{(t)}\right)' = \Pi ^{(t)} \cdot \mathbf{Q} \]

ProblemProblem 3

1. Prove both systems of Kolmogorov’s differential equations.

2. Prove the formula \(\left(\Pi^{(t)}\right)' = \Pi^{(t)} \cdot \mathbf{Q}\).

Theorem 4 (Recovering \(\mathbf{P}_t\) from the generator \(\mathbf{Q}\)) Let \(\mathbf{Q}\) be a (conservative) \(Q\)-matrix. The family of matrices \[ \mathbf{P}_t := e^{\mathbf{Q}t} = \sum _{k=0}^{\infty }\frac{1}{k!}\mathbf{Q}^k t^k, \qquad t \geq 0 \] satisfies the following conditions:

• \((\mathbf{P}_t, t \geq 0)\) is a stochastic semigroup;

• \((\mathbf{P}_t, t \geq 0)\) is the unique solution of Kolmogorov’s forward and backward equations with initial condition \(\mathbf{P}_0 = \mathbf{E}\);

• \(\frac{d^n}{dt^n}\mathbf{P}_t = \mathbf{P}_t \cdot \mathbf{Q}^n = \mathbf{Q}^n \cdot \mathbf{P}_t\).

ExampleExample 3

Consider a general \(Q\)-matrix of dimension \(2 \times 2\): \[ \mathbf{Q} = \left(\begin{array}{cc} -\alpha & \alpha \\ \beta & -\beta \end{array}\right), \quad \alpha , \beta \geqslant 0 . \] Rate graph:

Rate graph of a two-state continuous-time Markov chain: transition \(1\to 2\) at rate \(\alpha\), and \(2\to 1\) at rate \(\beta\).

Recover \(\mathbf{P}_t\). Try to find the entrywise limit of \(\mathbf{P}_t\) as \(t \to \infty\).

SolutionSolution

If \(\alpha =\beta =0\), i.e. \(\mathbf{Q} = \mathbf{0}\), then the solution is: \(\mathbf{P}_t = e^{\mathbf{0}t} = \mathbf{E}\) for any \(t \geq 0\). From now on we assume they are not both zero. Equivalently: \(\alpha + \beta > 0\).

The eigenvalues \(\lambda_{1,2}\) of the matrix \(\mathbf{Q}\) are roots of the equation

\[ \operatorname {det}\left(\begin{array}{cc} -\lambda -\alpha & \alpha \\ \beta & -\lambda -\beta \end{array}\right)=(\lambda +\alpha )(\lambda +\beta )-\alpha \beta =\lambda (\alpha +\beta +\lambda )=0, \]

i.e.

\[ \lambda _1=0, \quad \lambda _2=-(\alpha +\beta ) . \]

The eigenvalues are distinct, so the matrix can be diagonalized, namely \(\mathbf{Q} =\mathbf{U} \mathbf{D} \mathbf{U}^{-1}\), where

\[ \mathbf{D} = \begin{pmatrix} 0 & 0 \\ 0 & -\alpha - \beta \end{pmatrix} \]

Thus,

\[ \begin{align} \mathbf{P}_t & = \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{Q}^k = \\ & = \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{U} \mathbf{D}^k \mathbf{U}^{-1} = \\ & = \mathbf{U} \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{D}^k \mathbf{U}^{-1} = \mathbf{U} e^{t \mathbf{D}}\mathbf{U}^{-1} = \\ & =\mathbf{U}\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{-t(\alpha +\beta )} \end{array}\right) \mathbf{U}^{-1} . \end{align} \]

Hence all entries of the matrix \(\mathbf{P}_t\) have the form

\[ \left(\mathbf{P}_t\right)_{ij} = A_{ij}+B_{ij} e^{-t(\alpha +\beta )}, \]

where

\[ \left(\mathbf{P}_0\right)_{ij}=A_{ij}+B_{ij}=\delta _{i j} \]

and

\[ \left.\left(\mathbf{P}_t\right)_{ij}'\right|_{t=0}=-(\alpha +\beta ) B_{ij} = \mathbf{Q}_{ij}. \]

For example, for the upper-left entry

\[ A_{11}+B_{11}=1, \quad -(\alpha +\beta ) B_{11}=-\alpha \]

hence

\[ A_{11}=\frac{\beta }{\alpha +\beta }, \quad B_{11}=\frac{\alpha }{\alpha +\beta } . \]

Therefore the matrix \(\mathbf{P}_t\) equals

\[ \mathbf{P}_{t}=\left(\begin{array}{cc} \frac{\beta }{\alpha +\beta }+\frac{\alpha }{\alpha +\beta } e^{-(\alpha +\beta ) t} & \frac{\alpha }{\alpha +\beta }-\frac{\alpha }{\alpha +\beta } e^{-(\alpha +\beta ) t} \\ \frac{\beta }{\alpha +\beta }-\frac{\beta }{\alpha +\beta } e^{-(\alpha +\beta ) t} & \frac{\alpha }{\alpha +\beta }+\frac{\beta }{\alpha +\beta } e^{-(\alpha +\beta ) t} \end{array}\right) ; \]

as \(t \rightarrow \infty\) there is entrywise convergence to the matrix

\[ \left(\begin{array}{cc} \frac{\beta }{\alpha +\beta } & \frac{\alpha }{\alpha +\beta } \\ \frac{\beta }{\alpha +\beta } & \frac{\alpha }{\alpha +\beta } \end{array}\right) . \]

ProblemProblem 4

Consider a \(Q\)-matrix of dimension \(3 \times 3\) of the form \[ \mathbf{Q} = \left(\begin{array}{ccc} -1 & 1 / 2 & 1 / 2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{array}\right) \] Rate graph (note: there is no edge \(3 \to 1\), since \(\mathbf{Q}_{31} = 0\)):

Rate graph of a continuous-time Markov chain with generator \(Q=\begin{pmatrix}-1&1/2&1/2\\3&-6&3\\0&4&-4\end{pmatrix}\): edges \(1\leftrightarrow2\), \(1\to3\), \(2\leftrightarrow3\); there is no transition \(3\to1\), since \(Q_{31}=0\).

Find a formula for \(\left(\mathbf{P}_{t}\right)_{11}\). What is the limit of \(\left(\mathbf{P}_{t}\right)_{11}\) as \(t \to +\infty\)?

2.3 A digression: properties of the exponential distribution

Recall (see the chapter on renewal processes): the exponential distribution is the unique absolutely continuous distribution on \([0, +\infty )\) with the memoryless property: for \(\xi \sim \operatorname {Exp}(\lambda )\) and \(s, t > 0\),

\[ \mathbb {P}\left(\xi > t + s \mid \xi > s\right) = \mathbb {P}\left(\xi > t\right) \]

This is exactly why the exponential distribution inevitably arises in continuous-time Markov chains: the time the chain will spend in its current state must not depend on how long it has already spent there (otherwise the Markov property would be violated). Let us state two more properties that will be needed below.

Lemma 5 (Race of independent exponentials) Let \(I\) be an at most countable set, and let \(\eta_k\), \(k \in I\), be independent random variables, \(\eta_k \sim \operatorname {Exp}(q_k)\), with \(0 < q := \sum_{k \in I} q_k < \infty\). Set \(\eta := \inf_{k \in I} \eta_k\). Then the infimum is a.s. attained at a unique random index \(K\), with \[ \eta \sim \operatorname {Exp}(q), \qquad \mathbb {P}\left(K = k\right) = \frac{q_k}{q}, \] and the random variables \(\eta\) and \(K\) are independent.

Mn-proofProof

The probability that two independent absolutely continuous random variables coincide is zero, and there are at most countably many pairs \((j,k)\) — hence a.s. all \(\eta_k\) are distinct and the minimum (if attained) is attained at a unique index. Let us compute, for \(k \in I\), \(t \geq 0\), using independence (the law of total probability conditioned on the value of \(\eta_k\)): \[ \begin{align} \mathbb {P}\left(K = k, \; \eta \geq t\right) & = \mathbb {P}\left(\eta _k \geq t, \; \eta _j > \eta _k \; \forall j \neq k\right) = \\ & = \int _t^{+\infty } q_k e^{-q_k s} \prod _{j \neq k} \underbrace{\mathbb {P}\left(\eta _j > s\right)}_{=e^{-q_j s}} \, ds = \\ & = \int _t^{+\infty } q_k e^{-q s} \, ds = \frac{q_k}{q} \, e^{-q t} \end{align} \] At \(t = 0\) we get \(\mathbb {P}\left(K = k\right) = \frac{q_k}{q}\); summing over \(k\) gives \(1\), i.e. the minimum is a.s. attained. The right-hand side factors as \(\mathbb {P}\left(K=k\right) \cdot e^{-qt}\), from which we get the independence of \(\eta\) and \(K\), and \(\eta \sim \operatorname {Exp}(q)\).

Lemma 6 (On sums of independent exponentials) Let \(\xi_1, \xi_2, \ldots\) be independent, with \(\xi_n \sim \operatorname {Exp}(\lambda_n)\). Then

• if \(\sum_{n=1}^{\infty } \frac{1}{\lambda_n} < \infty\), then \(\mathbb {P}\left(\sum_{n=1}^{\infty } \xi_{n} < \infty \right) = 1\);

• if \(\sum_{n=1}^{\infty } \frac{1}{\lambda_n} = \infty\), then \(\mathbb {P}\left(\sum_{n=1}^{\infty } \xi_{n} = \infty \right) = 1\).

In other words, the sum \(\sum_n \xi_n\) is either a.s. finite or a.s. infinite, and this is determined by the convergence of the series of expectations \(\sum_n \frac{1}{\lambda_n}\).

Mn-proofProof

Let \(S := \sum_{n=1}^{\infty }\xi_n\) (the limit of a monotone sequence, possibly \(+\infty\)).

• If \(\sum_n \frac{1}{\lambda_n} < \infty\): by the monotone convergence theorem \(\mathbb {E}\left[S\right] = \sum_n \mathbb {E}\left[\xi_n\right] = \sum_n \frac{1}{\lambda_n} < \infty\), and a random variable with finite expectation is a.s. finite.

• If \(\sum_n \frac{1}{\lambda_n} = \infty\): let us compute \(\mathbb {E}\left[e^{-S}\right]\). By independence and monotone (dominated) convergence,

  \[ \begin{align} \mathbb {E}\left[e^{-S}\right] & = \prod _{n=1}^{\infty } \mathbb {E}\left[e^{-\xi _n}\right] = \\ & = \prod _{n=1}^{\infty } \frac{\lambda _n}{1 + \lambda _n} = \prod _{n=1}^{\infty } \left(1 + \frac{1}{\lambda _n}\right)^{-1} \end{align} \]

  Divergence of \(\sum_n \frac{1}{\lambda_n}\) is equivalent to divergence of \(\sum_n \ln \left(1 + \frac{1}{\lambda_n}\right)\) (if \(\frac{1}{\lambda_n} \to 0\), then \(\ln (1+x) \sim x\); if it does not tend to zero, both series diverge trivially). Hence the product equals \(0\), i.e. \(\mathbb {E}\left[e^{-S}\right] = 0\). But \(e^{-S} \geq 0\), so \(e^{-S} = 0\) a.s., i.e. \(S = \infty\) a.s.

For more on these properties: (Norris 1997, sec. 2.3).

Mn-extraAdditional material

Another beautiful fact from the same family — about the Poisson process (which, as we have seen, is built entirely out of exponential intervals).

Lemma 7 Let \(\left(N_t\right)_{t \geq 0}\) be a Poisson process, and \(J_1, \ldots , J_n\) its jump times. Then, conditioned on the event \(\left\{ N_t=n\right\}\), the vector \((J_1, \ldots , J_n)\) has joint density \[ f\left(t_1, \ldots , t_n\right)=n!\, t^{-n} \, \; \mathbb {1}_{0 \leq t_1 \leq \ldots \leq t_n \leq t} \] In other words, conditioned on \(\left\{ N_t=n\right\}\), the jump times are distributed as an ordered sample of size \(n\) from the uniform distribution on \([0, t]\). This conditional distribution does not depend on the rate \(\lambda\), nor on the exponential nature of the times as such — the jumps are “uniformly scattered” over the interval.

See the proof in (Norris 1997, Theorem 2.4.6).

2.4 The jump-and-hold construction: building a càdlàg version of a CTMC

Let us return to the informal description of the chain’s behavior given after the examples of generators (see Equation 1), and state it carefully. Intuition: the Markov property implies that

1. the time until the next jump (the future) does not depend on the time elapsed since the last jump (the past) \(\; \Rightarrow \;\) waiting times are memoryless \(\; \Rightarrow \;\) they are exponential;

2. the next state visited (the future) does not depend on the previously visited states (the past) \(\; \Rightarrow \;\) the sequence of visited states forms a discrete-time Markov chain.

Theorem 5 (Holding time and distribution of the jump) Let \((X_t, t \geq 0)\) be a standard CTMC with a finite number of states, with generator \(\mathbf{Q}\) and càdlàg paths. Let \(H := \inf \left\{ s > 0 \; : \; X_{s} \neq X_0\right\}\) be the time of the first jump (the holding time). Then, conditioned on \(X_0 = i\):

• if \(\mathbf{Q}_{ii} = 0\), then \(H = +\infty\) a.s., i.e. \(i\) is an absorbing state;

• if \(\mathbf{Q}_{ii} < 0\), then \(H \sim \operatorname {Exp}(-\mathbf{Q}_{ii})\), and the next state is chosen with probabilities

  \[ \mathbb {P}_{i}\left(X_{H} = j\right) = \frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}, \qquad j \neq i, \]

  where \(H\) and \(X_{H}\) are independent.

See the proof in (Norris 1997, Theorem 2.8.2).

The converse is also true: given a conservative \(Q\)-matrix, a chain can be constructed according to the following algorithm (which is also the recipe for simulating a CTMC on a computer):

1. construct the embedded DTMC \((\tilde{X}_n, n \geq 0)\) (a formal definition follows in the next section) with transition matrix \(\tilde{\mathbf{P}}\), where \(\tilde{\mathbf{P}}_{ij} = \frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}\) for \(i \neq j\) and \(\tilde{\mathbf{P}}_{ii} = 0\) (absorbing states are handled separately: \(\tilde{\mathbf{P}}_{ii} = 1\));

2. take independent (and independent of \(\tilde{X}\)) random variables \(E_1, E_2, \ldots \sim \operatorname {Exp}(1)\) and set the waiting times \(W_n := \frac{E_n}{-\mathbf{Q}_{\tilde{X}_{n-1}, \tilde{X}_{n-1}}}\), the jump times \(J_n := W_1 + \ldots + W_n\);

3. set \(X_t := \tilde{X}_{n}\) for \(t \in [J_{n}, J_{n+1})\).

The resulting process is a standard CTMC with generator \(\mathbf{Q}\) and càdlàg paths (Norris 1997, sec. 2.6).

One possible realization of such a path (for some 3-state chain) looks like this: One realization of a sample path of a continuous-time Markov chain, built via the “jump-hold” construction: the chain waits in state \(i\) for a random time \(W_n \sim \operatorname{Exp}(-\mathbf{Q}_{ii})\), then jumps to a state \(j \neq i\) with probability \(\tilde{\mathbf{P}}_{ij} = \mathbf{Q}_{ij} / (-\mathbf{Q}_{ii})\) (the embedded chain). Click the “New realization” button to regenerate the holding times and jumps — the point will run along a new trajectory in real time. The sliders set the rates \(\mathbf{Q}_{ij}\) (\(i \neq j\)) of the generator; the diagonal \(\mathbf{Q}_{ii} = -\sum_{j \neq i} \mathbf{Q}_{ij}\) is recomputed automatically.

The chain started in state \(1\), stayed there for a random time \(W_1\), jumped to state \(3\), stayed for a time \(W_2\), and so on.

Mn-extraAdditional material

An alternative way of viewing the same mechanism is “racing clocks.” Standing in state \(i\), start independent exponential clocks \(\eta_j \sim \operatorname {Exp}(\mathbf{Q}_{ij})\) for all \(j \neq i\) (a clock with zero rate never rings), and jump to whichever state’s clock rings first. By the lemma on the race of independent exponentials (lemma Lemma 5):

• the time until the jump \(H = \min_{j \neq i} \eta_j \sim \operatorname {Exp}\left(\sum_{j \neq i}\mathbf{Q}_{ij}\right) = \operatorname {Exp}(-\mathbf{Q}_{ii})\) (conservativeness!);

• the jump goes to state \(j\) with probability \(\frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}\), independently of the jump time.

This gives exactly theorem Theorem 5. This interpretation explains why \(\mathbf{Q}_{ij}\) is called the transition rate \(i \to j\): it is the “ringing speed” of the clock responsible for that transition.

From this point on, for any CTMC we consider precisely the version with càdlàg paths.

2.5 Communicating states, recurrence, the embedded discrete-time chain

As in the case of discrete-time chains, states \(i,j\) are called communicating if there exist \(t_1, t_2 \geq 0\) such that

\[ \left(\mathbf{P}_{t_1}\right)_{i,j} > 0, \qquad \left(\mathbf{P}_{t_2}\right)_{j,i} > 0 \]

Let \(T_{i} := \inf \left\{ t > 0 \; : \; X_{t-} \neq X_{t} = i\right\}\), where \(X_{t-} := \lim_{s \to t - 0} X_{s}\) is the left limit of the process at \(t\) (all our paths are càdlàg, so the limit always exists at every point). \(T_{i}\) is the continuous analogue of the (first) return time to state \(i\). State \(i\) is called recurrent if

\[ \mathbb {P}_{i}\left(T_{i} < \infty \right) = 1 \]

Otherwise the state is called transient¹.

A difference from discrete time: in continuous time there is no notion of the period of a state.

Let \(J_{0} := 0\),

\[ J_{n} := \min \left\{ t > J_{n - 1} \; : \; X_{t-} \neq X_{t}\right\} \]

be the time of the \(n\)-th jump of the chain. Let

\[ \tilde{X}_{n} := X_{J_{n}} \]

Lemma 8 The process \((\tilde{X}_{n}, n \geq 0)\)

• is a discrete-time Markov chain,

• has the same initial distribution as \(X_{t}\),

• has transition probability matrix \[ \tilde{\mathbf{P}} = \begin{pmatrix} 0 & \frac{\mathbf{Q}_{12}}{-\mathbf{Q}_{11}} & \frac{\mathbf{Q}_{13}}{-\mathbf{Q}_{11}} & \cdots & \frac{\mathbf{Q}_{1n}}{-\mathbf{Q}_{11}} \\ \frac{\mathbf{Q}_{21}}{-\mathbf{Q}_{22}} & 0 & \frac{\mathbf{Q}_{23}}{-\mathbf{Q}_{22}} & \cdots & \frac{\mathbf{Q}_{2n}}{-\mathbf{Q}_{22}} \\ \frac{\mathbf{Q}_{31}}{-\mathbf{Q}_{33}} & \frac{\mathbf{Q}_{32}}{-\mathbf{Q}_{33}} & 0 & \cdots & \frac{\mathbf{Q}_{3n}}{-\mathbf{Q}_{33}} \\ \vdots & \vdots & \cdots & \ddots & \vdots \\ \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,1}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,2}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & \cdots & \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|-1}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & 0 \end{pmatrix}, \] if \(\mathbf{Q}_{ii} \neq 0\) for all states. If for some state \(i\) we still have \(\mathbf{Q}_{ii} = 0\), then \(i\) is an absorbing state both for \(X_t\) itself and for \(\tilde{X}_{n}\), i.e. the \(i\)-th row of the matrix \(\tilde{\mathbf{P}}\) is the \(i\)-th basis vector:

  \[ \left(\tilde{\mathbf{P}}\right)_{ij} = \delta _{ij} \]

The DTMC \(\tilde{X}_n, n \geq 0\), is called the embedded chain for the CTMC \(X_t, t \geq 0\).

Lemma 9 (Relation between a CTMC and its embedded chain) A CTMC \((X_{t}, t \geq 0)\) and its embedded DTMC \((\tilde{X}_{n}, n \geq 0)\) have the same communicating states, the same recurrent states, and the same transient states.

2.6 Stationary distribution

A distribution (row vector) \(\Pi\) on \(\mathcal{X}\) is called stationary for a CTMC \((X_{t}, t \geq 0)\) with transition probabilities \((\mathbf{P}_t, t \geq 0)\) if

\[ \Pi \cdot \mathbf{P}_{t} = \Pi , \qquad \forall \; t \geq 0 \]

Lemma 10 Let \(\Pi\) be some distribution on \(\mathcal{X}\). Then \[ \Pi \text{ is a stationary distribution} \quad \iff \quad \Pi \cdot \mathbf{Q} = \mathbf{0} \] In other words, a distribution is stationary if and only if it is a left eigenvector (row vector) of the matrix \(\mathbf{Q}\) with eigenvalue \(0\).

ExampleExample 4

Prove the preceding lemma.

SolutionSolution

• \(\stackrel{?}{\; \Rightarrow \; }\). Use Kolmogorov’s forward equations:

  \[ \Pi \cdot \mathbf{Q} = \Pi \cdot \mathbf{P}'_t = \left(\Pi \cdot \mathbf{P}_t\right)' = \Pi ' = \mathbf{0} \]

  (throughout, entrywise derivatives are meant)

• \(\stackrel{?}{\Leftarrow }\). Use Kolmogorov’s backward equations:

  \[ \left(\Pi \cdot \mathbf{P}_t\right)' = \Pi \cdot \mathbf{P}'_t = \underbrace{\Pi \cdot \mathbf{Q}}_{=\mathbf{0}} \cdot \mathbf{P}_t = \mathbf{0} \]

  Hence \(\Pi \cdot \mathbf{P}_t\) is (entrywise) independent of time. In that case \(\Pi \cdot \mathbf{P}_t =\Pi \cdot \mathbf{P}_0\). But \(\mathbf{P}_0 = \mathbf{E}\). In the end we obtain

  \[ \Pi \cdot \mathbf{P}_t =\Pi \]

2.7 Irreducible (ergodic) chain: limiting properties

Let \((X_t, t \geq 0)\) be an irreducible chain. An irreducible, positive recurrent CTMC is called ergodic. A difference from the discrete case: the aperiodicity requirement is gone.

In the case of a finite number of states, any recurrent state will be positive recurrent, and correspondingly any irreducible chain will be ergodic.

Theorem 6 (The ergodic theorem) An irreducible CTMC with a finite number of states (i.e. an ergodic CTMC) has only one stationary distribution \(\Pi = \Pi^{\operatorname {erg}}\), called the ergodic distribution. Properties:

• \(\Pi^{\operatorname {erg}}\) is a left eigenvector of the matrix \(\mathbf{Q}\) for eigenvalue \(0\);

• \(\Pi^{\operatorname {erg}}_{i} = \frac{1}{-\mathbf{Q}_{ii}} \cdot \frac{1}{\mathbb {E}_{i}\left[T_i\right]} > 0\);

• \[ \mathbf{P}_{t} \quad \xrightarrow [t \to +\infty ]{} \quad \begin{pmatrix} \Pi ^{\operatorname {erg}} \\ \Pi ^{\operatorname {erg}} \\ \vdots \\ \Pi ^{\operatorname {erg}} \end{pmatrix} = \begin{pmatrix} \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \\ \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \end{pmatrix} \]

The same result as for discrete Markov chains, with two differences:

1. Aperiodicity is not defined in continuous time / not needed for the ergodic theorem;

2. \(\frac{1}{\mathbb {E}_{i}\left[T_i\right]}\) is replaced by \(\frac{1}{-\mathbf{Q}_{ii}} \cdot \frac{1}{\mathbb {E}_{i}\left[T_i\right]}\). In discrete time, one visit to \(i\) is one unit of time at \(i\); in continuous time, one visit to \(i\) equals \(1/-\mathbf{Q}_{ii}\) units of time at \(i\) (on average).

ProblemProblem 5

The transition probabilities of a Markov chain \(\left(X_{t}, t \geqslant 0\right)\) with phase space \(\mathcal{X} = \left\{ 1,2,3\right\}\) have the form: \[ \begin{align} p_{11}(h)& =1-\lambda h+o(h), & p_{12}(h)& =\lambda h+o(h), & p_{13}(h)& =o(h) \\ p_{21}(h)& =o(h), & p_{22}(h)& = 1 - \mu h + o(h), & p_{23}(h)& = \mu h + o(h) \\ p_{31}(h)& = \nu h + o(h), & p_{32}(h)& = o(h), & p_{33}(h)& =1 - \nu h + o(h), \end{align} \] as \(h \to 0+\), where \(\lambda , \mu , \nu > 0\). Prove that such a chain satisfies the condition of the ergodic theorem. Find its infinitesimal matrix and stationary distribution.

ProblemProblem 6

A “queueing” system consists of a machine and a repair facility. The machine works for a random time having an exponential distribution with parameter \(\alpha\). Repairing the machine takes a random time having an exponential distribution with parameter \(\beta\). Denote \[ \begin{align} \Pi _1^{(t)} & = \mathbb {P}\left(\text{the machine is working at time }t\right) \\ \Pi _2^{(t)} & = \mathbb {P}\left(\text{the machine is being repaired at time }t\right) \end{align} \] Find \(\Pi_1^{(t)}, \Pi_2^{(t)}\), given \(\Pi_1^{(0)} = \Pi_2^{(0)} = 1/2\), assuming that the process forms a Markov chain. What is the limit of this distribution as \(t \to +\infty\)? Does it depend on the initial distribution?

The “machine-repair” chain: the probability \(\Pi_1^{(t)}\) that the machine is working at time \(t\), given by \(\Pi_1^{(t)} = \frac{\beta}{\alpha+\beta} + \left(\Pi_1^{(0)} - \frac{\beta}{\alpha+\beta}\right) e^{-(\alpha+\beta)t}\). Move the sliders \(\alpha\), \(\beta\) and \(\Pi_1^{(0)}\) (the last one sets a fourth, highlighted curve) — all curves shrink exponentially toward the same stationary level \(\frac{\beta}{\alpha+\beta}\): the chain “forgets” its initial distribution.

\(\alpha\) = 1.0 \(\beta\) = 2.0 \(\Pi_1^{(0)}\) = 0.75

ProblemProblem 7

Consider the CTMC \((X_t, t\geq 0)\) from problem Problem 4, with transition rate matrix \[ \mathbf{Q} = \begin{pmatrix} -1 & 1 / 2 & 1 / 2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{pmatrix} \]

1. Find all stationary distributions of the chain.

2. Find the stationary distributions for the embedded chain \(\tilde{X}_n\). Is it ergodic? If so, find the ergodic distribution.

3. Is the chain \(X_t\) irreducible? Is it ergodic? If so, find the ergodic distribution.

4. Find the limit of \(\mathbf{P}_t\) as \(t \to +\infty\).

5. Find the limit in distribution of \(X_t\), depending on the initial distribution \(\Pi^{(0)}\).

6. Find the mean return time \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\).

Ergodicity “made visible” for the chain \((X_t)\) from the problem with matrix \(\mathbf{Q} = \begin{pmatrix} -1 & 1/2 & 1/2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{pmatrix}\): one simulated trajectory “runs” through time (via the jump-hold method), while the fractions of time \(\frac{1}{t}\int_0^{t} \;\mathbb{1}_{X_s = i}\, ds\) spent in each of the three states update live and converge to the stationary distribution \(\Pi = \left(\frac{24}{41}, \frac{8}{41}, \frac{9}{41}\right)\) (dashed levels). The “New trajectory” button regenerates the realization.

2.8 Limiting properties in the general case

What if a finite chain is reducible, i.e. consists of several communicating classes? The picture is completely analogous to the discrete case (see the chapter on DTMCs): states split into transient and recurrent classes (the type of a class is determined by closedness, as before, via the embedded chain); starting from a transient class, the chain reaches, in a.s. finite time, one of the recurrent classes and remains there forever; within each recurrent class the ergodic theorem applies.

The one — pleasant — difference from the discrete case: for a finite CTMC the entrywise limit \(\lim_{t \to \infty } \mathbf{P}_t\) always exists (not merely the Cesàro limit). The periodic effects that could prevent the limit \(\mathbf{P}^n\) from existing for a DTMC are absent in continuous time: the waiting time in a state is continuous and “smears out” any periodicity.

3 CTMCs with countably many states

The definitions carry over from the case of finitely many states: communicating states and classes, irreducibility, recurrence, stationary distributions, the embedded chain, etc. As in the discrete case, some of the “nice” properties of finite chains cease to be automatic: a recurrent state can be null recurrent (\(\mathbb {E}_{i}\left[T_i\right] = +\infty\)), an irreducible chain may have no stationary distribution, and so on. But two fundamentally new effects appear that have no discrete analogue: explosion and the associated non-uniqueness of recovering the chain from the generator. Let us start with these.

3.1 Explosion

Let us recall the jump-and-hold construction (§ Section 2.4): the chain stays in states for random times \(W_1, W_2, \ldots\) and jumps at times \(J_n = W_1 + \ldots + W_n\). In the finite case \(J_n \to +\infty\) a.s. (waiting times are exponentials with a finite set of rates). In the countable case, the rates \(-\mathbf{Q}_{ii}\) can grow without bound along a trajectory, and the waiting times can decrease fast enough that their sum converges:

\[ \zeta := \sup _n J_n = \sum _{n=1}^{\infty } W_n < \infty \]

The event \(\left\{ \zeta < \infty \right\}\) is called explosion, and \(\zeta\) the explosion time: in a finite amount of time the chain manages to make infinitely many jumps. If \(\mathbb {P}_{i}\left(\zeta = +\infty \right) = 1\) for every initial state \(i\), the chain is called non-explosive.

ExampleExample 5

Consider a pure birth process: \(\mathcal{X} = \mathbb {N}\), from state \(n\) the only possible transition is \(n \to n+1\) with rate \[ \mathbf{Q}_{n,n+1} = -\mathbf{Q}_{nn} = \mu \cdot n^{\alpha }, \] where \(\mu , \alpha > 0\). Rate graph:

Rate graph of a pure birth process with \(\lambda_n = \mu\cdot n^\alpha\) (at \(\alpha=1\) — the Yule process; a general birth process can “explode” in finite time).

Let \(X_0 = 1\). For which \(\alpha\) does the chain explode?

SolutionSolution

The embedded chain is deterministic: \(1 \to 2 \to 3 \to \ldots\). By the jump-and-hold construction, the waiting times \(W_n\) are independent, \(W_n \sim \operatorname {Exp}(\mu n^{\alpha })\), and \[ \zeta = \sum _{n=1}^{\infty } W_n \] By lemma Lemma 6 on sums of independent exponentials, everything is determined by the convergence of the series \[ \sum _{n=1}^{\infty } \frac{1}{\mu n^{\alpha }} \]

• If \(\alpha > 1\), the series converges, so \(\mathbb {P}_{1}\left(\zeta < \infty \right) = 1\): the chain explodes a.s. — it “runs through” all the natural numbers in finite time and escapes to infinity.

• If \(\alpha \leq 1\), the series diverges, so \(\mathbb {P}_{1}\left(\zeta = \infty \right) = 1\): there is no explosion.

The boundary case \(\alpha = 1\) is the Yule process: a population of \(n\) particles, each independently splitting at rate \(\mu\); by the race-of-exponentials lemma (lemma Lemma 5) the total splitting rate equals \(\mu n\). The population grows exponentially fast, but does not explode.

Explosion of a pure birth process: \(\mathbf{Q}_{n,n+1} = \mu n^{\alpha}\), \(\mu = 1\), \(X_0 = 1\). Move the \(\alpha\) slider — as it crosses \(1\), the series \(\sum_n n^{-\alpha}\) starts to converge, and the simulated trajectory (red curve) acquires a finite explosion time \(\zeta\) (dashed vertical asymptote). The dashed blue curve is the Yule process (\(\alpha = 1\)) for comparison: it grows exponentially fast but never explodes. The button regenerates both trajectories.

\(\alpha\) = 2.00

What happens to the chain after an explosion? The formula \(X_t = \tilde{X}_n\) for \(t \in [J_n, J_{n+1})\) only defines the process up to time \(\zeta\). The standard way out is to consider the minimal chain: extend the definition by \(X_t := \partial\) for \(t \geq \zeta\), where \(\partial \notin \mathcal{X}\) is a special “cemetery” state. But then \(\sum_{j \in \mathcal{X}}\left(\mathbf{P}_t\right)_{ij} = \mathbb {P}_{i}\left(\zeta > t\right)\) can be less than \(1\) — the matrices become substochastic. Alternatively, one can “restart” the chain after an explosion at some state of \(\mathcal{X}\) — but exactly which one is not dictated by the generator \(\mathbf{Q}\)! Different restart rules give different stochastic semigroups (and different chains) with one and the same generator. This is exactly the non-uniqueness, promised above, of recovering a chain from its generator in the infinite case. Details: (Norris 1997, sec. 2.7), (Liggett 2010, sec. 2.4) (including the famous example due to Blackwell).

It is useful to have simple sufficient conditions for the absence of explosion.

Theorem 7 Let \((X_t, t \geq 0)\) be a (minimal) CTMC with conservative generator \(\mathbf{Q}\). The chain does not explode if at least one of the following conditions holds:

1. \(\mathcal{X}\) is finite;

2. the exit rates are bounded: \(\sup_{i \in \mathcal{X}}\left(-\mathbf{Q}_{ii}\right) < \infty\);

3. the chain starts at a state \(i\) that is recurrent for the embedded chain \(\tilde{X}_n\).

See the proof in (Norris 1997, Theorem 2.7.1).

3.2 Stationary distribution and limiting properties

For irreducible, non-explosive chains, the picture of limiting behavior is completely analogous to the discrete case — and even simpler, since aperiodicity is not needed.

Theorem 8 Let \((X_t, t \geq 0)\) be an irreducible, non-explosive CTMC with conservative generator \(\mathbf{Q}\), where \(-\mathbf{Q}_{ii} > 0\) for all \(i\). Then exactly two cases are possible.

• The positive recurrent case: \(\mathbb {E}_{i}\left[T_i\right] < \infty\) for some (equivalently: for every) state \(i\). Then the chain has a unique stationary distribution \(\Pi\), with

  \[ \begin{align} \Pi _j & = \frac{1}{-\mathbf{Q}_{jj}} \cdot \frac{1}{\mathbb {E}_{j}\left[T_j\right]} > 0, \qquad \\ & \quad \left(\mathbf{P}_t\right)_{ij} \xrightarrow [t \to +\infty ]{} \Pi _j \quad \forall i, j \in \mathcal{X} \end{align} \]

  Moreover, the fraction of time spent in state \(j\) converges a.s. to \(\Pi_j\):

  \[ \frac{1}{t}\int _0^{t} \; \mathbb {1}_{X_s = j} \, ds \quad \xrightarrow [t \to +\infty ]{\text{a.s.}} \quad \Pi _j \]

• The null recurrent or transient case: no stationary distribution exists, and

  \[ \left(\mathbf{P}_t\right)_{ij} \xrightarrow [t \to +\infty ]{} 0 \qquad \forall i, j \in \mathcal{X} \]

See the proof in (Norris 1997, sec. 3.8).

Mn-extraAdditional material

Caution: although recurrence/transience coincide for a CTMC and its embedded chain, positive recurrence does not! The chain \(X_t\) can be positive recurrent while the embedded chain is null recurrent, and vice versa: compare the stationary distributions \(\Pi_i \propto \tilde{\Pi }_i / (-\mathbf{Q}_{ii})\) — “reweighting” by holding times can turn a summable distribution into a non-summable measure and vice versa.

3.3 Birth-death processes

A birth-death process is a CTMC on \(\mathcal{X} = \mathbb {Z}_+\) in which only transitions to neighboring states are possible:

\[ \mathbf{Q}_{n, n+1} = \lambda _n \; (n \geq 0), \qquad \mathbf{Q}_{n, n-1} = \mu _n \; (n \geq 1), \qquad \mathbf{Q}_{nn} = -(\lambda _n + \mu _n), \]

where \(\lambda_n \geq 0\) are the birth rates, \(\mu_n \geq 0\) are the death rates (\(\mu_0 := 0\)). Rate graph:

Rate graph of a general birth-death process: transition \(n\to n+1\) at rate \(\lambda_n\), and \(n\to n-1\) at rate \(\mu_n\).

Interpretation via the jump-and-hold construction: in state \(n\) the chain waits a time \(\operatorname {Exp}(\lambda_n + \mu_n)\) and jumps up with probability \(\frac{\lambda_n}{\lambda_n + \mu_n}\), down with probability \(\frac{\mu_n}{\lambda_n + \mu_n}\). Many processes already familiar to us are special cases: the Poisson process (\(\lambda_n \equiv \lambda\), \(\mu_n \equiv 0\)), the pure birth process (\(\mu_n \equiv 0\)), the Yule process (\(\lambda_n = n\mu\), \(\mu_n \equiv 0\)).

For birth-death processes, the stationary distribution can be found explicitly. The key observation: for these processes, stationarity is equivalent to the seemingly stronger condition of detailed balance.

Lemma 11 (Detailed balance) Let \((X_t, t \geq 0)\) be a birth-death process, and \(\Pi\) a distribution on \(\mathbb {Z}_+\). Then \[ \Pi \cdot \mathbf{Q} = \mathbf{0} \qquad \iff \qquad \Pi _n \lambda _n = \Pi _{n+1}\mu _{n+1} \quad \forall n \geq 0 \] The right-hand condition (detailed balance) means: in steady state, the “probability flow” across each edge \(n \leftrightarrow n+1\) is balanced.

Mn-proofProof

Let us introduce the “flow across an edge” \(F_n := \Pi_n \lambda_n - \Pi_{n+1}\mu_{n+1}\), \(n \geq 0\). Let us write out the \(j\)-th component of the equation \(\Pi \mathbf{Q} = \mathbf{0}\) (in column \(j\) of \(\mathbf{Q}\) the nonzero entries lie in rows \(j-1\), \(j\), \(j+1\)): \[ \begin{align} j = 0& : \quad -\lambda _0 \Pi _0 + \mu _1 \Pi _1 = 0 \quad \iff \quad F_0 = 0 \\ j \geq 1& : \quad \lambda _{j-1}\Pi _{j-1} - (\lambda _j + \mu _j)\Pi _j + \mu _{j+1}\Pi _{j+1} = 0 \quad \iff \quad F_{j-1} = F_{j} \end{align} \] So stationarity is equivalent to the chain \(0 = F_0 = F_1 = F_2 = \ldots\), i.e. to detailed balance.

Corollary 1 Let all \(\lambda_n > 0\) (\(n \geq 0\)) and \(\mu_n > 0\) (\(n \geq 1\)). From detailed balance \(\Pi_{n+1} = \Pi_n \frac{\lambda_n}{\mu_{n+1}}\), by induction we obtain \[ \Pi _n = \Pi _0 \cdot \prod _{k=1}^{n} \frac{\lambda _{k-1}}{\mu _{k}}, \qquad n \geq 1 \] Hence a normalizable solution of the equation \(\Pi \cdot \mathbf{Q} = \mathbf{0}\) exists if and only if \[ Z := 1 + \sum _{n=1}^{\infty }\prod _{k=1}^{n} \frac{\lambda _{k-1}}{\mu _{k}} < \infty , \] and in that case it is unique: \(\Pi_0 = \frac{1}{Z}\). If, in addition, the chain does not explode (for example, if one of the conditions of theorem Theorem 7 holds), then this solution is the stationary distribution of the chain in the full sense (\(\Pi \cdot \mathbf{P}_t = \Pi\) for all \(t\)). Caution: for an explosive chain, the equivalence \(\Pi \mathbf{Q} = \mathbf{0} \iff \Pi \mathbf{P}_t = \Pi\) can fail — we proved it only in the finite case.

ExampleExample 6

The M/M/1 queue: customers arrive at the jump times of a Poisson process of rate \(\lambda\); a single server serves customers one at a time, service time \(\sim \operatorname {Exp}(\mu )\), all times independent. \(X_t\) is the number of customers in the system (being served + waiting). Rate graph:

Rate graph of the M/M/1 queue: a customer arrival is a “birth” at rate \(\lambda\), and a service completion is a “death” at rate \(\mu\).

Find the stationary distribution when \(\rho := \frac{\lambda }{\mu } < 1\). What happens when \(\rho \geq 1\)?

SolutionSolution

This is a birth-death process with constant rates \(\lambda_n \equiv \lambda\), \(\mu_n \equiv \mu\) (the memorylessness of the exponential distribution guarantees the Markov property). The chain does not explode: the exit rates are bounded by the number \(\lambda + \mu\) (condition (ii) of theorem Theorem 7). By corollary Corollary 1:

\[ \Pi _n = \Pi _0 \cdot \prod _{k=1}^{n}\frac{\lambda }{\mu } = \Pi _0 \, \rho ^n, \qquad Z = \sum _{n=0}^{\infty }\rho ^n \]

For \(\rho < 1\) the series converges: \(Z = \frac{1}{1-\rho }\), and

\[ \Pi _n = (1 - \rho )\, \rho ^n, \qquad n \geq 0 \]

— a geometric distribution. In particular, in steady state the server is idle a fraction of time \(\Pi_0 = 1 - \rho\), and the mean number of customers in the system equals \(\sum_n n \Pi_n = \frac{\rho }{1 - \rho }\) — this blows up as \(\rho \to 1-\): a system loaded to nearly \(100\%\) performs poorly.

For \(\rho \geq 1\) the series \(Z\) diverges, and no stationary distribution exists: the queue “drifts off to infinity” (for \(\rho > 1\) the chain is transient, for \(\rho = 1\) it is null recurrent, cf. the simple random walk). By theorem Theorem 8, in this case \(\mathbb {P}\left(X_t = n\right) \to 0\) for any fixed \(n\).

The M/M/1 queue at \(\mu = 1\) (number of customers in the system \(X_t\)): move the load slider \(\rho = \lambda/\mu\) to see the “phase transition” at \(\rho = 1\) — for \(\rho < 1\) (ergodic regime) the queue keeps returning to zero, while for \(\rho \geq 1\) (transient regime) it drifts off to infinity. On the right, for \(\rho < 1\): the empirical fraction of time in each state (from a long separate simulation) against the theoretical geometric distribution \(\Pi_n = (1-\rho)\rho^n\). The button regenerates the trajectory.

For ρ ≥ 1 there is no stationary distribution — comparison with the geometric distribution is not defined.

\(\rho\) = 0.80

ProblemProblem 8

The M/M/\(\infty\) queue: customers arrive according to a Poisson process of rate \(\lambda\), but now there are infinitely many servers: each customer immediately starts being served by its own server, service time \(\sim \operatorname {Exp}(\mu )\), all times independent. \(X_t\) is the number of customers in the system. Show that \(X_t\) is a birth-death process, find its rates and stationary distribution.

References

Liggett, T. M. 2010. Continuous Time Markov Processes: An Introduction. Continuous Time Markov Processes. American Mathematical Society.

Norris, J. R. 1997. Markov Chains. Cambridge University Press.

Булинский, А. В., and А. Н. Ширяев. 2005. Теория Случайных Процессов. Физматлит.

Footnotes

1. As in the case of discrete-time chains, all recurrent states of a continuous-time chain with a finite number of states are positive recurrent.