Markov Transition Kernel and The Generator Q Matrix
Markov Transition Kernel and The Generator Q Matrix
Markov Transition Kernel and The Generator Q Matrix
1 Generator Matrix
From Lemma ?? for a homogeneous CTMC X : Ω → XR+ , we can write the probability transition kernel
function P(t) = etQ , where eQ = P(1). The matrix Q ∈ RX×X is called the generator matrix for the
homogeneous CTMC X. From the Definition ?? for the exponentiation of matrix, this implies that
tn n
P(t) = I + ∑ n!
Q , t ∈ R+ . (1)
n ∈N
This relation implies that the probability transition kernel can be written in terms of this fundamental
generator matrix Q. On first glance, this relation doesn’t provide much insight into the characteristics of
the generator matrix. We will formally define generator matrix below, and relate this matrix to the jump
transition probability matrix p ∈ [0, 1]X×X of the embedded Markov chain Z : Ω → XZ+ , and transition
rate sequence ν : X → R+ .
Definition 1.1 (Generator matrix). For a homogeneous continuous time Markov chain X : Ω → XR+
with transition kernel function P : R+ → [0, 1]X×X , the generator matrix Q ∈ RX×X is defined as the
following limit when it exists
P(t) − I
Q ≜ lim .
t ↓0 t
Remark 1. From Eq. (1), it is clear that the generator matrix is the limit defined above.
Theorem 1.2. For a homogeneous CTMC X : Ω → XR+ , the generator matrix exists and is defined in terms of
sojourn time transition rates ν ∈ RX
+ , and jump transition matrix p ∈ [0, 1]
X×X as
Q xx = −νx , Q xy = νx p xy .
Proof. Consider a fixed time t ∈ R+ and states x, y ∈ X. We can expand the ( x, y)th entry of transition
matrix in terms of disjoint events { Nt = n} as
Pxy (t) = Px { Xt = y} = ∑ Px { Xt = y, Nt = n} .
n ∈Z+
We can write the upper and lower bound the transition probability Pxy (t) as
1 1
∑ Px {Xt = y, Nt = n} ⩽ Pxy (t) ⩽ ∑ Px {Xt = y, Nt = n} + P { Nt ⩾ 2} .
n =0 n =0
Since Ixy = 1{ x̸=y} , we can write the probabilities in terms of identity operator I as
Z t
Px { Xt = y, Nt = 0} = Ixy e−νx t , Px { Xt = y, Nt = 1} = (1 − Ixy ) p xy νx e−νy (t−u) e−νx u du.
0
The second equality follows from the nested conditional expectation. In particular, we have
Px { Xt = y, Nt = 1} = 1{ x̸=y} Ex 1{ Xt =y,S1 ⩽t<S2 } = 1{ x̸=y} Ex E[1{ Xt =y,T2 >t−S1 ,S1 ⩽t} |FS1 ] = (1 − Ixy ) p xy Ex 1{S1 ⩽t} e−νy (t−S1 ) .
1
Corollary 1.3. For each state x ∈ X, the generator matrix Q ∈ RX×X for a pure-jump homogeneous CTMC
satisfies
Remark 2. From the semigroup property of probability kernel function and definition of generator ma-
trix, we get the backward equation
Both these results need a formal justification of exchange of limits and summation, and we next present
a formal proof for these two equations.
Theorem 1.4 (backward equation). For a homogeneous CTMC X : Ω → XR+ with transition kernel function
P : R+ → [0, 1]X×X and generator matrix Q ∈ RX×X , we have
dP(t)
= QP(t), t ∈ R+ .
dt
( P(s)− I )
Proof. Fix states x, y ∈ X and we consider the lim inf and lim sup of ( x, y)th term of s P ( t ). For any
finite subset F ⊆ X containing x, we obtain
The above inequality holds for any finite set F ⊆ X, and thus taking supremum over increasing sets F,
we get the lower bound. For the upper bound, we observe for any finite subset F ⊆ X containing state
x, we have
!
( Pxz (s) − Ixz ) ( Pxz (s) − Ixz ) ( Pxz (s) − Ixz )
lim sup ∑ Pzy (t) ⩽ lim sup ∑ Pzy (t) − ∑ = ∑ Q xz Pzy (t) − ∑ Q xz .
s ↓0 z ∈X
s s ↓0 z∈ F
s z∈ F
s z∈ F z∈ F
The above inequality holds for any finite set F ⊆ X, and thus taking infimum over increasing sets F and
recognizing that ∑z∈X Q xz = 0, we get the upper bound.
Theorem 1.5 (forward equation). For a homogeneous CTMC X : Ω → XR+ with transition kernel function
P : R+ → [0, 1]X×X and generator matrix Q ∈ RX×X , we have
dP(t)
= P(t) Q, t ∈ R+ .
dt
( P(s)− I )
Proof. Fix states x, y ∈ X and we consider the lim inf and lim sup of ( x, y)th term of P(t) s . We take
a finite set F ⊆ X containing state y, to obtain the lower bound
By taking limiting value for increasing sequence of finite sets F ⊆ X, we obtain the lower bound. To
obtain the upper bound, we observe for any finite subset F ⊆ X containing state y, we have
!
( Pzy (s) − Izy ) ( Pzy (s) − Izy ) Pzy (s)
lim sup ∑ Pxz (t) ⩽ lim sup ∑ Pxz (t) +∑ = ∑ Pxz (t) Qzy + ∑ Qzy .
s ↓0 z ∈X
s s ↓0 z∈ F
s ∈F
z/
s z∈ F ∈F
z/
The second equality follows from monotone convergence theorem. Taking infimum over increasing
sets F and from the fact that ∑y∈X\{ x} p xy = 1, we get the upper bound.
2
Remark 3. Recall that for a homogeneous discrete time Markov chain with one-step transition proba-
bility matrix P, we can write the n-step transition probability matrix P(n) = Pn . That is, for any given
stochastic matrix P, we can construct a discrete time Marko chain. We can generalize this notion to ho-
mogeneous continuous time Markov chains as well. Given a matrix Q ∈ RX×X that satisfies the prop-
erties of a generator matrix given in Corollary 1.3, we can construct a homogeneous continuous time
Markov chain X : Ω → XR+ by finding its transition kernel P : R+ → [0, 1]X×X , by defining P(t) ≜ etQ
for all t ∈ R+ . We observe that P(1) = eQ and we have P(t) = P(1)t for all t ∈ R+ . We need to show that
such a defined function is indeed a probability transition kernel. We will first show that such a function
P satisfies some of the properties of the transition kernel, and then show that P(t) is transition matrix
at all times t ∈ R+ .
Theorem 1.6. Let Q ∈ RX×X be a matrix that satisfies the properties of generator matrix given in Corollary 1.3.
We define a function P : R+ → RX
+
×X
by P(t) ≜ etQ for all t ∈ R+ . Then the function P satisfies the following
properties.
1. P has the semigroup property, i.e. P(s + t) = P(s) P(t) for all s, t ∈ R+ .
dP(t)
2. P is the unique solution to the forward equation, dt = P(t) Q with initial conditon P(0) = I.
dP(t)
3. P is the unique solution to the backward equation, dt = QP(t) with initial condition P(0) = I.
dk P(t)
4. For all k ∈ N, we have dk (t) = Qk .
t =0
Proof. Given the definition of P and properties of Q, one can easily check these properties.
Theorem 1.7. A finite matrix Q ∈ RX×X satisfies the properties of a generator matrix given in Corollary 1.3 iff
the function P : R+ → RX
+
×X
defined by P(t) ≜ etQ is a stochastic matrix for all t ∈ R+ .
Proof. Sufficiency has already been seen before, and hence we will focus only on necessity. Accordingly,
we assume that Q ∈ RX×X satisfies the properties of a generator matrix given in Corollary 1.3, then we
will show that P(t) = etQ is a stochastic matrix. Recall that Q1 T = 0 for all ones column vector 1 T , and
hence Qn 1 T = 0 for all n ∈ N. Expanding P(t) in terms of expression for matrix exponentiation, we
tn n
write P(t) = I + ∑k∈N n! Q . This implies that P(t)1 T = 1 T .
E = ( x, y) ∈ X × X : Q xy > 0, y ̸= x .
2 Uniformization
Consider a homogeneous continuous-time Markov chain X : Ω → XR+ in which the mean time spent in
a state is identical for all states, i.e. νx = ν uniformly for all states x ∈ X. Recall that Nt = ∑n∈N 1{Sn ⩽t}
denotes the number of state transitions until time t ∈ R+ . Since the random amount of time spent in
R
each state is i.i.d. with common exponential distribution of rate ν, the counting process N : Ω → Z++ is
a Poisson process with rate ν. In this case, we can explicitly characterize the transition kernel function
P : R+ → [0, 1]X×X for this CTMC X in terms of the jump transition probability matrix p ∈ [0, 1]X×X
and uniform transition rate ν. To this end, we use the law of total probability over countable partitions
({ Nt = n} : n ∈ Z+ ) to get
(νt)n
∑ ∑
(n)
p xy e−νt
Pxy (t) = Px { N (t) = n} P({ Xt = y} { X0 = x, Nt = n}) = .
n ∈Z+ n ∈Z+
n!
This equation could also have been derived by observing that Q = −ν( I − p) and hence using the
exponentiation of matrix, we can write
(νt)n
P(t) = e−νt( I − p) = e−νt eνtp = e−νt ∑ pn
n!
. (2)
n ∈Z+
3
Eq. (2) gives a closed form expression for P(t) and also suggests an approximate computation by an
appropriate partial sum. However, its application is limited as the transition rates for all states are all
assumed to be equal. It turns out that any regular Markov chain can be transformed in this form by
allowing hypothetical transitions from a state to itself.
ξ n ≜ 1 {Y }, n ∈ N.
Tn ̸ = x
N ≜ inf {n ∈ N : ξ n = 1} .
Since ξ is i.i.d. Bernoulli, N is a geometric random variable with success probability 1 − q xx = ννx . To
show that the two Markov processes Y and X have identical distribution, it suffices to show that
To see (b), from the Markov property of process Y and its embedded jump transition matrix q, we
observe that
q xy
Px {YU = y} = ∑ Px {YU = y, N = n} = ∑ Px {Y1 = · · · = Yn−1 = x, Yn = y} = ∑ q xy qnxx−1 = = p xy .
n ∈N n ∈N n ∈N
1 − q xx
Remark 4. Any regular continuous time Markov chain X : Ω → XR+ can be thought of as being in a
process that spends a random time in state x ∈ X distributed exponentially with rate ν, and then makes
a transition to state y ∈ X with probability p∗xy . Then, one can write the probability transition kernel as
∞
(νt)n
∑
(n)
Pxy (t) = q xy e−νt .
n =0
n!
4
3 Class Properties
Definition 3.1. For a CTMC X : Ω → XR+ defined on the countable state space X ⊆ R, we say a state
y is reachable from state x if Pxy (t) > 0 for some t > 0, and we denote x → y. If two states x, y ∈ X are
reachable from each other, we say that they communicate and denote it by x ↔ y.
Proof. It suffices to show that x → y for the regular Markov process iff x → y in the embedded chain. If
x → y for embedded chain, then there exists a path x = x0 , x1 , . . . , xn = y such that p x0 x1 p x1 x2 . . . p xn−1 xn > 0
and νx0 νx1 . . . νxn−1 > 0. It follows that Sn is a proper random variable, and we can write
n −1
Pxy (t) ⩾ ∏ pxk xk+1 E[ P {Tn+1 > t − Sn }] > 0.
k =0
Conversely, if the states y is not reachable from state x in embedded chain, then it won’t be reachable in
the regular CTMC.
Corollary 3.5. A regular CTMC is irreducible iff its embedded DTMC is irreducible.
Remark 5. There is no notion of periodicity in CTMCs since there is no fundamental time-step that
can be used as a reference to define such a notion. In fact, for any state x ∈ X of a non-instantaneous
homogeneous CTMC we have Pxx (t) > e−νx t > 0 for all t ⩾ 0.
Remark 6. An irreducible regular CTMC maybe null recurrent where embedded Markov chain is posi-
tive recurrent.
Corollary 3.8. Recurrence is a class property.
Theorem 3.9. Consider an irreducible recurrent CTMC X : Ω → XR+ with sojourn time rates ν ∈ RX + and
transition matrix p ∈ [0, 1] X × X X
for the embedded Markov chain. Let u ∈ R+ be any strictly positive solution of
u = up, then
1 uy
Ex τx+ = ∑
u x y∈X νy
, x ∈ X.
5
Proof. Let X0 = x ∈ X, and Nxy be the number of visits to state y ∈ X between successive visits to state
x in the embedded Markov chain. From the recurrence of the embedded Markov chain, we know that
u (x)
for any strictly positive solution to u = uP we have Ex Nxy = uyx . Let Yk denote the sojourn time of the
CTMC X in state x during the kth visit. The random sequence Y ( x) : Ω → RN
+ is i.i.d. exponential with
rate νx . Therefore, we can write
Nxy
∑ ∑ Yk
(y)
τx+ = Y0x + .
y∈X\{ x } k =1
We recall that jump chain and sojourn times are independent given the initial state, and hence Nxy and
Y (y) sequences are independent for each state y ̸= x. Result follows from taking expectations on both
sides, exchanging summation and expectations for positive random variables, to get
Nxy
∑ ∑ Yk ∑ EYk
(y) (y)
Ex τx+ = Ex Y0x + Ex = Ex Nxy .
y∈X\{ x } k =1 y ∈X
Corollary 3.10. Consider an irreducible recurrent CTMC X : Ω → XR+ with sojourn time rates ν ∈ RX + and
the transition matrix p for the embedded Markov chain. Let u be any strictly positive solution to u = up. Then,
CTMC X is positive recurrent iff ∑ x∈X uνxx < ∞. In particular, the CTMC is positive recurrent iff ∑ x∈X uνxx = 1.
4 Stationarity
Definition 4.1. A map π : X → [0, 1] is an equilibrium distribution of a homogeneous continuous
time Markov chain X : Ω → XR+ with probability transition kernel P : R+ → [0, 1]X×X if 1π = 1 and
πP(t) = π for all t ∈ R+ .
Remark 7. Let π (0) denote the marginal distribution of initial state X0 , then by definition of probability
transition kernel for Markov process X, we can write the marginal distribution of Xt as
π ( t ) = π (0) P ( t ), t ∈ R+ .
In general, we can write π (s + t) = π (s) P(t), and hence if there exists a stationary distribution π ≜
lims→∞ π (s) for this process X, then we would have π = πP(t) for all times t ∈ R+ .
Remark 8. Recall that an irreducible DTMC is positive recurrent iff it has a strictly positive stationary
distribution.
Corollary 4.2. For a homogeneous continuous time Markov chain X : Ω → XR+ with generator matrix Q, a
distribution π : X → [0, 1] is an equilibrium distribution iff πQ = 0.
Proof. Recall that we can write the transition probability matrix P(t) at any time t ∈ R+ in terms of
generator matrix Q as P(t) = etQ . Using the exponentiation of a matrix, we can write
tn
πP(t) = etQ = π + ∑n!
πQn , t ∈ R+ .
n ∈N
Therefore, πQ = 0 iff π is an equilibrium distribution of the Markov process X.
Theorem 4.3. Let X : Ω → XR+ be an irreducible recurrent homogeneous CTMC with probability transition
kernel P : R+ → [0, 1]X×X , the transition rate sequence ν ∈ RX + , and the transition matrix for embedded jump
X
chain p ∈ [0, 1] . Then for all states x, y ∈ X the limt→∞ Pxy (t) exists, this limit is independent of the initial state
x ∈ X and denoted by πy . Let u be any strictly positive invariant measure such that u = up. If ∑ x∈X uνxx = ∞,
then π x = 0 for all x ∈ X. If ∑ x∈X uνxx < ∞ then for all y ∈ X,
uy
νy νy−1
πy = u = .
∑ x∈X νxx Ey τy+
Proof. Fix a state y ∈ X, and define a process W : Ω → {0, 1}R+ such that Wt = 1{ Xt =y} . Then, from the
regenerative property of the homogeneous CTMC and renewal reward theorem, we have
νy−1
lim Px { Xt = y} = .
t→∞ Ey τy+