3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Section 3.1: Definitions and Basic Concepts
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 2 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Stochastic Process
Definition: {X (t), t 2 T } is called a stochastic process if X (t) is a rv (or possibly a random
vector) for any given t 2 T . T is referred to as the index set and is often interpreted in the
context of time. As such, X (t) is often called the state of the process at time t. We note that:
Index set T
8><>:
can be a continuum of values such as T = {t : t 0},
can be a set of discrete points such as T = {t0, t1, t2, . . .}.
Since there is a one-to-one correspondence between the sets T = {t0, t1, t2, . . .} and
N = {0, 1, 2, . . .}, we will use T = N as the general index set for a discrete-time stochastic
process (unless otherwise stated). In other words, {X (n), n 2 N} or {Xn, n 2 N} will represent
a general discrete-time stochastic process.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 3 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Discrete-time Stochastic Process
Some examples of discrete-time stochastic processes {Xn, n 2 N} might include:
(1) Xn represents the outcome of the nth toss of a die,
(2) Xn represents the price of a stock at the end of day n trading,
(3) Xn represents the maximum temperature in Waterloo during the nth month,
(4) Xn represents the number of goals scored in game n by the varsity hockey team,
(5) Xn represents the number of STAT 333 students in class for the nth lecture.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 4 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Discrete-time Markov Chain
Definition: A stochastic process {Xn, n 2 N} is said to be a discrete-time Markov chain
(DTMC) if the following two conditions hold true:
(1) For n 2 N, Xn is a discrete rv (i.e., the state space S of Xn is of discrete type).
(2) For n 2 N and all states x0, x1, . . . , xn+1 2 S, the Markov property must hold:
P(Xn+1 = xn+1|Xn = xn,Xn1 = xn1, . . . ,X1 = x1,X0 = x0) = P(Xn+1 = xn+1|Xn = xn).
In mathematical terms, this property states that the conditional distribution of any future
state Xn+1 given the past states X0,X1, . . . ,Xn1 and the present state Xn is
independent of the past states.
In a more informal way , the Markov property tells us, for a random process, that if we
know the value taken by the process at a given time, we will not get any additional
information about the future behaviour of the process by gathering more knowledge about
the past.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 5 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Discrete-time Markov Chain
Remarks:
(1) Unless otherwise stated, the state space S of a DTMC {Xn, n 2 N} will be assumed to be
N.
(2) In general, the sequence of rvs {Xn}1n=0 are neither independent nor identically distributed.
(3) The Markov property does not require “full” information on the past to ensure
independence. For example, consider the following conditional probability:
P(Xn+1 = xn+1|Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
=
P(Xn+1 = xn+1,Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
P(Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
,
which is “missing” the information for Xn1.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 6 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Discrete-time Markov Chain
However, note that
P(Xn+1 = xn+1,Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
=
1X
xn1=0
P(Xn+1 = xn+1,Xn = xn,Xn1 = xn1,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
=
1X
xn1=0
P(Xn+1 = xn+1|Xn = xn,Xn1 = xn1,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
⇥ P(Xn = xn,Xn1 = xn1,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
= P(Xn+1 = xn+1|Xn = xn)
⇥
1X
xn1=0
P(Xn = xn,Xn1 = xn1,Xn2 = xn2, . . . ,X1 = x1,X0 = x0) by Markov property
= P(Xn+1 = xn+1|Xn = xn)P(Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0).
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 7 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Discrete-time Markov Chain
We have:
P(Xn+1 = xn+1|Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
=
P(Xn+1 = xn+1,Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
P(Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
and
P(Xn+1 = xn+1,Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0)
= P(Xn+1 = xn+1|Xn = xn)P(Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0).
Substituting this latter expression into the numerator of the top equation yields
P(Xn+1 = xn+1|Xn = xn,Xn2 = xn2, . . . ,X1 = x1,X0 = x0) = P(Xn+1 = xn+1|Xn = xn).
It is straightforward to extend the above result to any number of past time points from
0, 1, . . . , n 1 with “missing” information. This is the essence of the Markov property.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 8 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
One-step Transition Probability Matrix
Definition: For any pair of states i and j , the transition probability from state i at time n to
state j at time n + 1 is given by
Pn,i ,j = P(Xn+1 = j |Xn = i), n 2 N.
Let Pn be the associated matrix containing all these transition probabilities, referred to as the
one-step transition probability matrix (TPM) from time n to time n + 1. It looks like
Pn = [Pn,i ,j ] =
26666664
0 1 2 · · · j · · ·
0 Pn,0,0 Pn,0,1 Pn,0,2 · · · Pn,0,j · · ·
1 Pn,1,0 Pn,1,1 Pn,1,2 · · · Pn,1,j · · ·
...
...
...
...
...
i Pn,i ,0 Pn,i ,1 Pn,i ,2 · · · Pn,i ,j · · ·
...
...
...
...
...
37777775,
where, for convenience, the states of the DTMC are labelled along the margins of the matrix.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 9 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
One-step Transition Probability Matrix
For each pair of states i and j , if Pn,i ,j = Pi ,j 8 n 2 N, then we say that the DTMC is
stationary or homogeneous. In this situation, the one-step TPM becomes:
P = [Pi ,j ] =
26666664
0 1 2 · · · j · · ·
0 P0,0 P0,1 P0,2 · · · P0,j · · ·
1 P1,0 P1,1 P1,2 · · · P1,j · · ·
...
...
...
...
...
i Pi ,0 Pi ,1 Pi ,2 · · · Pi ,j · · ·
...
...
...
...
...
37777775.
Remark: In STAT 333, we only consider stationary DTMCs. Moreover, from the construction
of the TPM P , it is clear that Pi ,j 0 8 i , j 2 N and
P1
j=0 Pi ,j = 1 8 i 2 N (i.e., each row
sum of P must be 1). Such a matrix whose elements are non-negative and whose row sums
are equal to 1 is said to be stochastic.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 10 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
One-step Transition Probability Matrix
Example 3.1. On a given day, the weather is either clear, overcast, or raining. If the weather
is clear today, then it will be clear, overcast, or raining tomorrow with respective probabilities
0.6, 0.3, and 0.1. If the weather is overcast today, then it will be clear, overcast, or raining
tomorrow with respective probabilities 0.2, 0.5, and 0.3. If the weather is raining today, then it
will be clear, overcast, or raining tomorrow with respective probabilities 0.4, 0.2, and 0.4.
Construct the underlying DTMC and determine its TPM.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 11 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
n-step Transition Probability Matrix
Definition: For any pair of states i and j , the n-step transition probability is given by
P(n)i ,j = P(Xm+n = j |Xm = i), m, n 2 N.
Due to the stationary assumption, this quantity is actually independent of m (which is why we
do not include m in its notation). Thus, P(n)i ,j = P(Xn = j |X0 = i), n 2 N. Furthermore, it is
evident that
P(0)i ,j = P(X0 = j |X0 = i) =
(
0 , if i 6= j ,
1 , if i = j .
In a similar manner, let P(n) =
h
P(n)i ,j
i
represent the associated n-step TPM. Clearly, when
n = 1, P(1) = P . When n = 0, P(0) = I , where I represents the identity matrix. Just as with
the one-step TPM, it follows that the row sums of P(n) must equal 1 as well.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 12 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Chapman-Kolmogorov Equations
For n 2 Z+, let us consider
P(n)i ,j = P(Xn = j |X0 = i)
=
1X
k=0
P(Xn = j |Xn1 = k ,X0 = i)P(Xn1 = k |X0 = i)
=
1X
k=0
P(n1)i ,k P(Xn = j |Xn1 = k ,X0 = i)
=
1X
k=0
P(n1)i ,k P(Xn = j |Xn1 = k) due to the Markov property
=
1X
k=0
P(n1)i ,k Pk,j . (3.1)
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 13 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Chapman-Kolmogorov Equations
We have: P(n)i ,j =
P1
k=0 P
(n1)
i ,k Pk,j (3.1)
Recall: If A = [ai ,j ], B = [bi ,j ], and C = AB where C = [ci ,j ], then ci ,j =
P
k ai ,kbk,j .
As a result, note that (3.1) implies that P(n) = P(n1)P , n 2 Z+. More generally, P(n)i ,j can be
expressed as
P(n)i ,j =
1X
k=0
P(m)i ,k P
(nm)
k,j 8 i , j 2 N and 0  m  n,
which are referred to as the Chapman-Kolmogorov equations for a DTMC. In matrix form, this
translates to
P(n) = P(m)P(nm), 0  m  n.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 14 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
n-step Transition Probability Matrix
Coming back to P(n) = P(n1)P , n 2 Z+, let us look at a few values of n:
Take n = 2 =) P(2) = P(1)P = PP = P2,
Take n = 3 =) P(3) = P(2)P = P2P = P3,
Take n = 4 =) P(4) = P(3)P = P3P = P4.
Clearly, we see that
P(n) = Pn,
and so the n-step TPM is simply the one-step TPM multiplied by itself n times.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 15 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Marginal pmf of Xn
For n 2 N, let us now introduce a particular row vector, which we will denote as either
↵n = (↵n,0,↵n,1, . . . ,↵n,k , . . .),
or
↵n =
⇥
↵n,0 ↵n,1 . . . ↵n,k . . .
⇤
,
where ↵n,k = P(Xn = k) 8 k 2 N. In other words, ↵n,k represents the marginal pmf of Xn,
n 2 N. As a consequence, it follows that P1k=0 ↵n,k = 1 8 n 2 N.
If we focus on the case when n = 0, then ↵0 is referred to as the initial probability row vector
of the DTMC, or simply the initial conditions of the DTMC.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 16 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Marginal pmf of Xn
For n 2 Z+, note that
↵n,k = P(Xn = k)
=
1X
i=0
P(Xn = k |Xm = i)P(Xm = i) where 0  m  n
=
1X
i=0
↵m,iP(Xnm = k |X0 = i) due to the stationary assumption
=
1X
i=0
↵m,iP
(nm)
i ,k .
In matrix form, the above relation implies that
↵n = ↵mP
(nm) = ↵mP
nm, 0  m  n,
which subsequently leads to
↵n = ↵0P
(n) = ↵0P
n, n 2 N.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 17 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
Having knowledge of the initial conditions and the one-step transition probabilities, one can
readily calculate various probabilities of possible interest such as
P(Xn = xn,Xn1 = xn1, . . . ,X1 = x1,X0 = x0)
= P(X0 = x0)P(X1 = x1|X0 = x0)P(X2 = x2|X1 = x1,X0 = x0) · · ·
⇥ P(Xn = xn|Xn1 = xn1,Xn2 = xn2, . . . ,X0 = x0)
= P(X0 = x0)P(X1 = x1|X0 = x0)P(X2 = x2|X1 = x1) · · ·P(Xn = xn|Xn1 = xn1)
= ↵0,x0Px0,x1Px1,x2 · · ·Pxn1,xn ,
where the second last equality follows due to the Markov property.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 18 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
Similarly,
P(Xn+m = xn+m,Xn+m1 = xn+m1, . . . ,Xn+1 = xn+1|Xn = xn)
= P(Xn+m=xn+m,Xn+m1=xn+m1,...,Xn+1=xn+1,Xn=xn)P(Xn=xn)
= P(Xn=xn)P(Xn+1=xn+1|Xn=xn)···P(Xn+m=xn+m|Xn+m1=xn+m1,Xn+m2=xn+m2,...,Xn=xn)P(Xn=xn)
= Pxn,xn+1Pxn+1,xn+2 · · ·Pxn+m1,xn+m .
The key observation here is that the DTMC is completely characterized by its one-step TPM
P and the initial conditions ↵0.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 19 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
Example 3.2. A particle moves along the states {0, 1, 2} according to a DTMC whose TPM
is given by
P =
24
0 1 2
0 0.7 0.2 0.1
1 0 0.6 0.4
2 0.5 0 0.5
35.
Let Xn denote the position of the particle after the nth move. Suppose that the particle is
equally likely to start in any of the three positions.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 20 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
(a) Calculate P(X3 = 1|X0 = 0).
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 21 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
(b) Calculate P(X4 = 2).
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 22 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Probabilities of Interest
(c) Calculate P(X6 = 0,X4 = 2).
Solution:...
(d) Calculate P(X9 = 0,X7 = 2|X5 = 1,X2 = 0).
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 23 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Accessibility and Communication
With these basic results in place, we next consider the classification of states in a DTMC.
Definition: State j is accessible from state i (denoted by i ! j) if 9 n 2 N such that
P(n)i ,j > 0. If states i and j are accessible from each other, then states i and j communicate
(denoted by i $ j). In other words, i $ j i↵ 9 m, n 2 N such that P(n)i ,j > 0 and P(m)j ,i > 0.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 24 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Accessibility and Communication
In terms of accessibility, note that the size of the components of P do not matter. All that
matters is which are positive and which are 0. In particular, if state j is not accessible from
state i , then P(n)i ,j = 0 8 n 2 N and
P(DTMC ever visits state j |X0 = i)
= P ([1n=0{Xn = j}|X0 = i)

1X
n=0
P(Xn = j |X0 = i) due to Boole’s inequality (see Exercise 1.1.1)
=
1X
n=0
P(n)i ,j
= 0,
implying that P(DTMC ever visits state j |X0 = i) = 0.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 25 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Equivalence Relation
The concept of communication forms what is known as an equivalence relation, satisfying the
following criteria:
(i) Reflexivity: i $ i .
Clearly true since P(0)i ,i = 1 > 0.
(ii) Symmetry: i $ j =) j $ i .
This is obviously true by definition.
(iii) Transitivity: i $ j and j $ k =) i $ k .
To see this holds formally, we know that 9 n 2 N such that P(n)i ,j > 0. Also, 9 m 2 N such
that P(m)j ,k > 0. Using the Chapman-Kolmogorov equations, we have that
P(n+m)i ,k =
1X
l=0
P(n)i ,l P
(m)
l ,k P(n)i ,j P(m)j ,k > 0.
Therefore, P(n+m)i ,k > 0, implying that i ! k . Using precisely the same logic, it is
straightforward to show that k ! i . Thus, by definition, i $ k .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 26 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Communication Classes
The fact that communication forms an equivalence relation allows us to partition all the states
of a DTMC into various communication classes, so that within each class, all states
communicate. However, if states i and j belong to di↵erent classes, then i $ j is not true
(i.e., at most one of i ! j or j ! i can be true).
Definition: A DTMC that has only one communication class is said to be irreducible. On the
other hand, a DTMC is called reducible if there are two or more communication classes.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 27 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Communication Classes
Example 3.2. (continued) What are the communication classes of the DTMC?
P =
24
0 1 2
0 0.7 0.2 0.1
1 0 0.6 0.4
2 0.5 0 0.5
35.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 28 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Communication Classes
Example 3.3. Consider a DTMC with TPM
P =
2664
0 1 2 3
0 0 1 0 0
1 0 0 1 0
2 0 0 0 1
3 0.5 0 0.5 0
3775.
What are the communication classes of this DTMC?
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 29 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Communication Classes
Example 3.4. Consider a DTMC with TPM
P =
266664
0 1 2 3
0 13
2
3 0 0
1 12
1
4
1
8
1
8
2 0 0 1 0
3 34
1
4 0 0
377775.
What are the communication classes of this DTMC?
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 30 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Definition: The period of state i is given by d(i) = gcd{n 2 Z+ : P(n)i ,i > 0}, where gcd{·}
denotes the greatest common divisor of a set of positive integers.
Remark: If d(i) = 1, then state i is said to be aperiodic. In fact, a DTMC is said to be
aperiodic if d(i) = 1 8 i 2 N. Furthermore, if P(n)i ,i = 0 8 n 2 Z+, then we set d(i) =1.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 31 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Example 3.5. Consider a DTMC with TPM
P =
2664
0 1 2 3
0 13 0 0
2
3
1 12
1
4
1
8
1
8
2 0 0 1 0
3 34 0 0
1
4
3775.
Determine the communication classes of this DTMC and the period of each state.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 32 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Example 3.3. (continued) Recall that {0, 1, 2, 3} is the only communication class for the
DTMC with TPM
P =
2664
0 1 2 3
0 0 1 0 0
1 0 0 1 0
2 0 0 0 1
3 0.5 0 0.5 0
3775.
Determine the period of each state.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 33 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Example 3.6. Consider the DTMC with TPM
P =
2664
0 1 2 3
0 12
1
2 0 0
1 23
1
3 0 0
2 0 0 0 1
3 0 0 1 0
3775.
Find the communication classes of this DTMC and determine the period of each state.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 34 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
The above examples illustrate some of the kinds of periodic behaviour that can be exhibited by
DTMCs. However, we do observe that among the states within a given communication class,
it seems as though the periodic behaviour is consistent. This is not a coincidence, as the next
theorem indicates.
Theorem 3.1. If i $ j , then d(i) = d(j).
Proof:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 35 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Example 3.7. Consider a DTMC with TPM
P =
264
0 1 2
0 0 12
1
2
1 12 0
1
2
2 12
1
2 0
375.
Find the communication classes of this DTMC and determine the period of each state.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 36 / 37
3. Discrete-time Markov Chains 3.1 Definitions and Basic Concepts
Periodicity
Remark: As the previous example demonstrates, it is still possible to observe aperiodic
behaviour even though the main diagonal components of P are all zero. More generally, if
d(i) = k , then this does not necessarily imply that P(k)i ,i > 0. Instead, it implies that if the
DTMC is in state i at time 0, then it is impossible to observe the DTMC in state i at time
n 2 Z+ if n is not a multiple of k (i.e., P(n)i ,i = 0 for such n).
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.1) Spring 2021 37 / 37
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Section 3.2: Transience and Recurrence
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 2 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
First Visit Probability
We now wish to take a closer look at the likelihood of a DTMC beginning in some state of
returning to that particular state. To that end, let us consider the probability that, starting
from state i , the first visit of the DTMC to state j occurs at time n 2 Z+, to be denoted by
f (n)i ,j = P(Xn = j ,Xn1 6= j , . . . ,X2 6= j ,X1 6= j |X0 = i) 8 i , j 2 N.
Clearly, we see that f (1)i ,j = Pi ,j .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 3 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
First Visit Probability
For n 2, however, the determination of f (n)i ,j becomes more complicated, and so we wish to
construct a procedure which will enable us to compute f (n)i ,j for such n. To do so, we consider
the quantity P(n)i ,j , n 2 Z+, and condition on the time that the first visit to state j is made:
P(n)i ,j = P(Xn = j |X0 = i)
=
nX
k=1
P(Xn = j , first visit to state j occurs at time k |X0 = i)
=
nX
k=1
P(Xn = j ,Xk = j ,Xk1 6= j , . . . ,X2 6= j ,X1 6= j |X0 = i)
=
nX
k=1
P(Xk = j ,Xk1 6= j , . . . ,X2 6= j ,X1 6= j |X0 = i)P(Xn = j |Xk = j)
=
nX
k=1
f (k)i ,j P
(nk)
j ,j , (3.2)
where we applied the Markov property in the second last equality.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 4 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
First Visit Probability
We have: P(n)i ,j =
Pn
k=1 f
(k)
i ,j P
(nk)
j ,j (3.2)
From (3.2), we can write
P(n)i ,j = f
(n)
i ,j P
(0)
j ,j +
n1X
k=1
f (k)i ,j P
(nk)
j ,j = f
(n)
i ,j +
n1X
k=1
f (k)i ,j P
(nk)
j ,j ,
implying that
f (n)i ,j = P
(n)
i ,j
n1X
k=1
f (k)i ,j P
(nk)
j ,j , n 2 Z+. (3.3)
For n 2, note that (3.3) yields a recursive means to compute f (n)i ,j .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 5 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Define the related quantity:
fi ,j = P(DTMC ever makes a future visit to state j |X0 = i).
Note that
fi,j =
1X
k=1
P(DTMC ever makes a future visit to state j ,DTMC visits state j for 1st time at time k|X0= i)
=
1X
k=1
P(DTMC visits state j for 1st time at time k|X0 = i)
=
1X
k=1
f (k)i,j  1.
This leads to the following important concept in the study of Markov chains.
Definition: State i is said to be transient if fi ,i < 1. On the other hand, state i is said to be
recurrent if fi ,i = 1.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 6 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Xn
Time
0
i
fi,iz }| {
visit
1
fi,iz }| {
visit
2
· · ·
· · ·
fi,iz }| {
visit
k 1
1 fi,i
visit
k
· · ·
In what follows, we proceed to look at alternative ways
of characterizing the notions of transience and recurrence.
As such, let us first define Mi to be a rv which
counts the number of (future) times the DTMC visits
state i (disregarding the possibility of starting in state
i at time 0). If we assume that fi ,i < 1, then the Markov
property and stationary assumption jointly imply that
P(Mi = k |X0 = i) =

kY
n=1
fi ,i
!
(1 fi ,i ) = f ki ,i (1 fi ,i ), k = 0, 1, 2, . . . , (3.4)
as the DTMC will return to state i k times with probability fi ,i , and then never return with
probability 1 fi ,i .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 7 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
We have: P(Mi = k |X0 = i) = f ki ,i (1 fi ,i ), k = 0, 1, 2, . . . (3.4)
We recognize (3.4) as the pmf of a GEOf (1 fi ,i ) rv, thereby implying that
E[Mi |X0 = i ] = 1 (1 fi ,i )1 fi ,i =
fi ,i
1 fi ,i <1 since fi ,i < 1.
However, if fi ,i = 1, then P(Mi =1|X0 = i) = 1, immediately implying that
E[Mi |X0 = i ] =1. Therefore, an equivalent way of viewing transience/recurrence is as
follows:
E[Mi |X0 = i ]
(
<1 , i↵ state i is transient,
=1 , i↵ state i is recurrent.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 8 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Following further on the notion of Mi , define a sequence of indicator rvs {An}1n=1 such that
An =
(
0 , if Xn 6= i ,
1 , if Xn = i .
With this definition, note that Mi =
P1
n=1 An. Now,
E[Mi |X0 = i ] = E
" 1X
n=1
An
X0 = i
#
=
1X
n=1
E[An|X0 = i ]
=
1X
n=1
{0 · P(An = 0|X0 = i) + 1 · P(An = 1|X0 = i)}
=
1X
n=1
P(Xn = i |X0 = i)
=
1X
n=1
P(n)i ,i .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 9 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
We have: E[Mi |X0 = i ] =
P1
n=1 P
(n)
i ,i
Therefore, yet another equivalent way of characterizing transience/recurrence is as follows:
1X
n=1
P(n)i ,i
(
<1 , i↵ state i is transient,
=1 , i↵ state i is recurrent.
Remark: A simple way of viewing these concepts is as follows: a recurrent state will be visited
infinitely often, whereas a transient state will only be visited finitely often.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 10 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
As was the case concerning the periodicity of states within the same communication class, the
next theorem indicates that transience/recurrence is also a class property.
Theorem 3.2. If i $ j and state i is recurrent, then state j is recurrent.
Proof:...
Remark: An obvious by-product of this theorem is that if i $ j and state i is transient, then
state j must also be transient.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 11 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
The following theorem serves as a companion result to Theorem 3.2.
Theorem 3.3. If i $ j and state i is recurrent, then
fi ,j = P(DTMC ever makes a future visit to state j |X0 = i) = 1.
Proof:...
Remark: Based on the above result, we know that, starting from any state of a recurrent class,
a DTMC will visit each state of that class infinitely many times.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 12 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
At this stage, a natural question to ask is “What do the results that we have accumulated thus
far tell us about the behaviour of states within the same communication class?” The answer
would be:
(i) these states communicate with each other,
(ii) these states all have the same period,
(iii) these states are all either recurrent or all transient.
In fact, in an irreducible DTMC, there is only one communication class and so all the states
are either recurrent or transient. When the assumption that the DTMC has a finite number of
states is included, we obtain the following important result.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 13 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Theorem 3.4. A finite-state DTMC has at least one recurrent state.
Proof:...
Remarks:
(1) Looking at the above result, it is useful to think of it in the following way. There must be
at least one recurrent state. After all, the DTMC has to spend its time somewhere, and if
it visits each of its finitely many states finitely many times, then where else could it
possibly go?
(2) As an immediate consequence of Theorem 3.4, an irreducible, finite-state DTMC must be
recurrent (i.e., all states of the DTMC are recurrent).
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 14 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Example 3.3. (continued) Recall that we considered the irreducible DTMC with TPM
P =
2664
0 1 2 3
0 0 1 0 0
1 0 0 1 0
2 0 0 0 1
3 0.5 0 0.5 0
3775.
Determine whether each state is transient or recurrent.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 15 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Another interesting property concerning recurrence can also be deduced.
Theorem 3.5. If state i is recurrent and state i does not communicate with state j , then
P(k)i ,j = 0 8 k 2 Z+.
Proof:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 16 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Example 3.4. (continued) Recall our earlier DTMC with TPM
P =
2664
0 1 2 3
0 13
2
3 0 0
1 12
1
4
1
8
1
8
2 0 0 1 0
3 34
1
4 0 0
3775.
Determine whether each state is transient or recurrent.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 17 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Remark: As the previous example illustrates, the contrapositive of Theorem 3.5 also provides a
test for transience, in that if 9 k 2 Z+ such that P(k)i ,j > 0 and states i and j do not
communicate, then state i must be transient. Moreover, this result implies that once a process
enters a recurrent class of states, it can never leave that class. For this reason, a recurrent
class is often referred to as a closed class.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 18 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Example 3.8. Consider a DTMC with TPM
P =
2664
0 1 2 3
0 14 0
3
4 0
1 0 13 0
2
3
2 0 1 0 0
3 0 25 0
3
5
3775.
Determine whether each state is transient or recurrent.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 19 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Transience and Recurrence
Remark: Instead of showing that f1,1 = 1 in the previous example, we could have used an even
simpler argument to conclude that {1, 3} is a recurrent class. In particular, after establishing
that {0} and {2} are transient classes, this DTMC has a finite number of states, and so {1, 3}
must be recurrent due to Theorem 3.4.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 20 / 21
3. Discrete-time Markov Chains 3.2 Transience and Recurrence
Random Walk
Example 3.9. Consider a DTMC {Xn, n 2 N} whose state space S is the set of all integers
(i.e., S = Z). Furthermore, suppose that the TPM for this DTMC satisfies
Pi ,i1 = 1 p and Pi ,i+1 = p 8 i 2 Z where 0 < p < 1.
In other words, from any state, either a jump up by one unit or a jump down by one unit takes
place in the next transition. As such, Xn is expressible as Xn =
Pn
k=0 Yk where {Yk}1k=0 is an
independent sequence of rvs with Y0 = X0 and P(Yk = 1) = 1 p and P(Yk = 1) = p,
k 2 Z+. This DTMC is well-studied in the literature and is the basis for many applications in
a variety of areas (particularly in finance). It is often referred to as the Random Walk or
Drunkard’s Walk. Characterize the behaviour of this DTMC in terms of its communication
classes, periodicity, and transience/recurrence.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.2) Spring 2021 21 / 21
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Section 3.3: Limiting Behaviour of DTMCs
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 2 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Limiting Behaviour of DTMCs
The concepts of periodicity and transience/recurrence play an important role in characterizing
the limiting behaviour of a DTMC. To demonstrate their influence, let us consider three
examples with varying forms of limiting behaviour.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 3 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Limiting Behaviour of DTMCs
Example 3.10. Consider a DTMC with TPM
P =
24
0 1 2
0 0 0 1
1 0 1 0
2 1 0 0
35.
Determine if limn!1 P(n) exists.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 4 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Limiting Behaviour of DTMCs
Example 3.11. Consider a DTMC with TPM
P =
264
0 1 2
0 12
1
2 0
1 12
1
4
1
4
2 0 13
2
3
375.
Determine if limn!1 P(n) exists.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 5 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Limiting Behaviour of DTMCs
Example 3.12. Consider the DTMC with TPM
P =
24
0 1 2
0 1 0 0
1 13
1
2
1
6
2 0 0 1
35.
Examine limn!1 P(n), and explain why the limiting probability of being in a state can depend
on the initial state of this DTMC.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 6 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Limiting Behaviour of DTMCs
In the above example, note that the second column of the limiting matrix contains all zeros.
Not surprisingly, this is indicative of transient behaviour, implying that one will never end up in
state 1 in the long run. This property can be proven more formally in the next theorem.
Theorem 3.6. For any state i and transient state j of a DTMC, limn!1 P
(n)
i ,j = 0.
Proof:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 7 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Mean Recurrent Time
As the previous three examples show, there is variation in the limiting behaviour of a DTMC.
In particular, it is worthwhile to determine a set of conditions which ensure the “nice” limiting
behaviour witnessed in Example 3.11. To ascertain when such conditions exist, we need to
distinguish between two kinds of recurrence. Let
Ni = min{n 2 Z+ : Xn = i},
where state i is assumed to be recurrent. Clearly, the conditional rv Ni |(X0 = i) takes on
values in Z+. Moreover, its conditional pmf is given by
P(Ni = n|X0 = i) = f (n)i ,i , n = 1, 2, 3, . . . .
We observe that this is indeed a pmf since
P1
n=1 f
(n)
i ,i = fi ,i = 1, as state i is recurrent. This
leads to the introduction of the following important quantity.
Definition: If state i is recurrent, then its mean recurrent time is given by
mi = E[Ni |X0 = i ] =
1X
n=1
nf (n)i ,i .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 8 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Positive and Null Recurrence
In words, mi represents the average time it takes the DTMC to make successive visits to state
i . Two notions of recurrence can now be defined based on the value of mi .
Definition: Suppose that state i is recurrent. State i is said to be positive recurrent if
mi <1. On the other hand, state i is said to be null recurrent if mi =1.
Remark: A fair question to ask is whether it is even possible for a discrete probability
distribution on Z+ to have an undefined mean (i.e., a mean of 1). To show that this is
indeed possible, consider a rv X with pmf
P(X = x) =
1
x(x + 1)
, x = 1, 2, 3, . . . .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 9 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Positive and Null Recurrence
Let us first confirm that this is indeed a pmf:
1X
x=1
1
x(x + 1)
= lim
n!1
nX
x=1
1
x(x + 1)
= lim
n!1
nX
x=1
✓
1
x
1
x + 1
◆
= lim
n!1
⇢✓
1 1
2
◆
+
✓
1
2
1
3
◆
+
✓
1
3
1
4
◆
+ · · ·+
✓
1
n
1
n + 1
◆
= lim
n!1
✓
1 1
n + 1
◆
= 1.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 10 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Positive and Null Recurrence
However,
E[X ] =
1X
x=1
x · 1
x(x + 1)
=
1X
x=1
1
x + 1
=1,
since the above harmonic series is known to diverge. In other words, a finite mean does not
exist!
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 11 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Positive and Null Recurrence
Some Facts About Positive and Null Recurrence:
1. If i $ j and state i is positive recurrent, then state j is also positive recurrent. This
means that positive recurrence is also a class property. An obvious by-product of this
result is that null recurrence is a class property too.
2. In a finite-state DTMC, there can never be any null recurrent states.
Remarks:
(1) The above facts are provided without formal justification, as their proofs are rather
lengthy and depend on material beyond the scope of STAT 333.
(2) Positive recurrent, aperiodic states are referred to as ergodic states.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 12 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Stationary Distribution
Before stating the main result governing the “nice” limiting behaviour demonstrated in
Example 3.11, we introduce a special type of probability distribution.
Definition: A probability distribution {pi}1i=0 is called a stationary distribution of a DTMC if
{pi}1i=0 satisfies the conditions
P1
i=0 pi = 1 and pj =
P1
i=0 piPi ,j 8 j 2 N.
Remark: If we define the row vector
p = (p0, p1, . . . , pj , . . .),
then the above conditions can be represented in matrix form as
p e 0 = 1 and p = pP ,
where e 0 = (1, 1, . . . , 1, . . .)0 denotes a column vector of ones (in general, the prime notation 0
will be used to represent column vectors).
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 13 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Stationary Distribution
A logical question to ask is “Why is such a distribution called stationary?”
To answer this question, suppose that the initial conditions of the DTMC are given by ↵0 = p.
As a result, we have that ↵0,j = P(X0 = j) = pj 8 j 2 N. Now, for any j 2 N, note that
↵1,j = P(X1 = j) =
1X
i=0
↵0,iPi ,j =
1X
i=0
piPi ,j = pj = ↵0,j .
The above equation indicates that X1 has the same probability distribution as X0 when
↵0 = p. More generally, it is straightforward to show (using mathematical induction) that each
Xi , i 2 Z+, is identically distributed to X0, provided that ↵0 = p.
In other words, if a DTMC is started according to a stationary distribution, then the
probability of being in a given state remains unchanged (i.e., stationary) over time.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 14 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Stationary Distribution
Remarks:
(1) In some texts, the stationary probability distribution is sometimes called the invariant
probability distribution or steady-state probability distribution.
(2) A known fact (which again we do not prove formally) is that a stationary distribution will
not exist if all the states of the DTMC are either null recurrent or transient. On the other
hand, an irreducible DTMC is positive recurrent i↵ a stationary distribution exists.
(3) Stationary distributions are not necessarily unique. This happens when a DTMC has more
than one positive recurrent communication class. For instance, it is not dicult to verify
that the DTMC in Example 3.10 has an infinite number of stationary distributions (left
as an upcoming exercise).
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 15 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
The Basic Limit Theorem
We are now in position to state the fundamental limiting theorem for DTMCs, generally
referred to as the Basic Limit Theorem (BLT).
Basic Limit Theorem: For an irreducible, recurrent, and aperiodic DTMC, limn!1 P
(n)
i ,j
exists and is independent of state i , satisfying
lim
n!1P
(n)
i ,j = ⇡j =
1
mj
8 i , j 2 N.
If the DTMC also happens to be positive recurrent, then {⇡j}1j=0 is the unique, positive
solution to the system of linear equations defined by(
⇡j =
P1
i=0 ⇡iPi ,j 8 j 2 N,P1
j=0 ⇡j = 1.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 16 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
The Basic Limit Theorem
Remarks:
(1) A formal proof of the BLT is beyond the scope of STAT 333. However, it is not dicult
to understand why {⇡j}1j=0 (if they exist) satisfies the above system of linear equations.
Specifically, recall the Chapman-Kolmogorov equations with m = n 1, namely
P(n)i ,j =
1X
k=0
P(n1)i ,k Pk,j 8 i , j 2 N.
Taking the limit as n!1 of both sides of this equation and assuming that it is
permissible to pass the limit through the summation sign, we obtain
lim
n!1P
(n)
i ,j = limn!1
1X
k=0
P(n1)i ,k Pk,j ,
⇡j =
1X
k=0
lim
n!1P
(n1)
i ,k Pk,j =
1X
k=0
⇡kPk,j 8 j 2 N,
which is precisely the above system of linear equations.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 17 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
The Basic Limit Theorem
Remarks:
(2) If we define the row vector of limiting probabilities
⇡ = (⇡0,⇡1, . . . ,⇡j , . . .),
then the above system of linear equations can be written succinctly in matrix form as:(
⇡ = ⇡P ,
⇡ e 0 = 1.
Therefore, if a DTMC is irreducible and ergodic, then the BLT states that the limiting
probability distribution is the unique stationary distribution.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 18 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
The Basic Limit Theorem
Remarks:
(3) When a DTMC has a finite number of states (i.e., suppose that the state space is
{0, 1, . . . ,N} where N <1), the BLT states that there are N + 1 linear equations to
consider of the form
⇡j =
NX
i=0
⇡iPi ,j , j = 0, 1, . . . ,N. (3.8)
Along with the condition
PN
j=0 ⇡j = 1, this leads to N + 2 equations in N + 1 unknowns,
of which a unique solution must exist. In fact, the first N + 1 equations given by (3.8) are
linearly dependent (implying that there is a redundancy), and so we can drop any one of
the equations given by (3.8) and solve the remaining N + 1 equations to obtain a unique
solution.
(4) If the conditions of the BLT are satisfied and state j happens to be null recurrent, then
⇡j = 0, which interestingly is similar to the limiting behaviour of a transient state.
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 19 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
The Basic Limit Theorem
Example 3.10. (continued) Recall that we previously considered a DTMC with TPM
264
0 1 2
0 12
1
2 0
1 12
1
4
1
4
2 0 13
2
3
375.
Find the limiting probabilities for this DTMC.
Solution:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 20 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Doubly Stochastic TPM
Recall that the TPM of a DTMC is stochastic, with all row sums of P being equal to 1.
However, a TPM is said to be doubly stochastic if all column sums of P are also equal to 1
(i.e.,
P1
i=0 Pi ,j = 1 8 j 2 N). The following theorem provides an interesting result concerning
the limiting behaviour of a class of such DTMCs.
Theorem 3.7. Suppose that a finite-state DTMC with state space S = {0, 1, . . . ,N 1} is
irreducible and aperiodic. If the associated TPM is doubly stochastic, then the limiting
probabilities {⇡j}N1j=0 exist and are given by
⇡j =
1
N
, j = 0, 1, . . . ,N 1.
Proof:...
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 21 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Alternative Interpretation
The primary interpretation of the limiting distribution of a DTMC is that after the process has
been in operation for a “long” period of time, the probability of finding the process in state j
is ⇡j (assuming the conditions of the BLT are met). In such situations, however, another
interpretation exists for ⇡j . Specifically, ⇡j also represents the “long-run” mean fraction of
time that the process spends in state j .
To see that this interpretation is valid, define the sequence of indicator random variables
{Ak}1k=1 as follows:
Ak =
(
0 , if Xk 6= j ,
1 , if Xk = j .
The fraction of time the DTMC visits state j during the time interval from 1 to n inclusive is
therefore given by
1
n
nX
k=1
Ak .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 22 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Alternative Interpretation
Looking at the quantity
E
"
1
n
nX
k=1
Ak
X0 = i
#
,
which is interpreted as the mean fraction of time spent in state j during the time interval from
1 to n inclusive, given that the process starts in state i , note that
E
"
1
n
nX
k=1
Ak
X0 = i
#
=
1
n
nX
k=1
E [Ak |X0 = i ]
=
1
n
nX
k=1
{0 · P(Ak = 0|X0 = i) + 1 · P(Ak = 1|X0 = i)}
=
1
n
nX
k=1
P(Xk = j |X0 = i)
=
1
n
nX
k=1
P(k)i ,j .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 23 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Alternative Interpretation
We have: E
⇥
1
n
Pn
k=1 Ak
X0 = i⇤ = 1n Pnk=1 P(k)i ,j
Recall: If {an}1n=1 is a real sequence such that an ! a as n!1, then 1n
Pn
k=1 ak ! a as
n!1.
Thus, if the conditions of the BLT are satisfied, then P(n)i ,j ! ⇡j as n!1. Therefore,
applying the above result with an = P
(n)
i ,j and a = ⇡j , we obtain
E
"
1
n
nX
k=1
Ak
X0 = i
#
! ⇡j as n!1,
implying that the long-run mean fraction of time spent in state j is also equal to ⇡j .
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 24 / 25
3. Discrete-time Markov Chains 3.3 Limiting Behaviour of DTMCs
Alternative Interpretation
Remark: If one begins in recurrent state j , we realize that the process spends one unit of time in state j every Nj
time units. On average, this amounts to one unit of time in state j every E[Nj |X0 = j ] = mj time units. If the
conditions of the BLT are satisfied, then it makes sense intuitively that ⇡j = 1/mj , as the BLT specifies. For a
more formal justification in the positive recurrent case, let {N(n)j }1n=1 be a sequence of rvs where N(n)j represents
the number of transitions between the (n 1)th and nth visits into state j , as illustrated in the diagram below.
By the Markov property and the stationary assumption of the DTMC, {N(n)j }1n=1 is actually an iid sequence of
rvs with common mean mj <1. Therefore, the long-run fraction of time spent in state j can be viewed as
⇡j = lim
n!1
nPn
i=1 N
(i)
j
= lim
n!1
1
1
n
Pn
i=1 N
(i)
j
=
1
mj
,
where the last equality follows from the SLLN.
DTMC
begins in
state j 0
N (1)j
1st visit
back to
state j
N (2)j
2nd visit
back to
state j
N (3)j
3rd visit
back to
state j
· · ·
· · · (n 2)th
visit back
to state j
N (n1)j
(n 1)th
visit back
to state j
N (n)j
nth visit
back to
state j
Time
STAT 333 Ch 3. Discrete-time Markov Chains (Section 3.3) Spring 2021 25 / 25

欢迎咨询51作业君