Markov Chains

Gonzalo Mateos
Dept. of ECE and Goergen Institute for Data Science
University of Rochester
gmateosb@[Link]
[Link]

September 25, 2019

Introduction to Random Processes Markov Chains 1

Markov chains

Definition and examples

Chapman-Kolmogorov equations

Gambler’s ruin problem

Queues in communication networks: Transition probabilities

Classes of states

Introduction to Random Processes Markov Chains 2

Markov chains in discrete time

I Consider discrete-time index n = 0, 1, 2, . . .

I Time-dependent random state Xn takes values on a countable set
I In general, states are i = 0, ±1, ±2, . . ., i.e., here the state space is Z
I If Xn = i we say “the process is in state i at time n”

I Random process is XN , its history up to n is Xn = [Xn , Xn−1 , . . . , X0 ]T

I Def: process XN is a Markov chain (MC) if for all n ≥ 1, i, j, x ∈ Zn




P Xn+1 = j  Xn = i, Xn−1 = x = P Xn+1 = j  Xn = i = Pij

I Future depends only on current state Xn (memoryless, Markov property)

⇒ Future conditionally independent of the past, given the present

Introduction to Random Processes Markov Chains 3

Observations

I Given Xn , history Xn−1 irrelevant for future evolution of the process

I From the Markov property, can show that for arbitrary m > 0



P Xn+m = j  Xn = i, Xn−1 = x = P Xn+m = j  Xn = i

I Transition probabilities Pij are constant (MC is time invariant)




P Xn+1 = j  Xn = i = P X1 = j  X0 = i = Pij

I Since Pij ’s are probabilities they are non-negative and sum up to 1

∞
X
Pij ≥ 0, Pij = 1
j=0

⇒ Conditional probabilities satisfy the axioms

Introduction to Random Processes Markov Chains 4

Matrix representation

I Group the Pij in a transition probability “matrix” P

 
P00 P01 P02 . . . P0j . . .
 P10 P11 P12 . . . P1j . . . 
 .. .. .. .. .. ..
 

P=  . . . . . . 

 Pi0 Pi1 Pi2 . . . Pij . . . 
.. .. .. .. ..
 
..
. . . . . .

⇒ Not really a matrix if number of states is infinite

P∞
I Row-wise sums should be equal to one, i.e., j=0 Pij = 1 for all i

Introduction to Random Processes Markov Chains 5

Graph representation

I A graph representation or state transition diagram is also used

Pi−1,i−1 Pi,i Pi+1,i+1

Pi−2,i−1 Pi−1,i Pi,i+1 Pi+1,i+2

... i −1 i i +1 ...

Pi−1,i−2 Pi,i−1 Pi+1,i Pi+2,i+1

I Useful when number of states is infinite, skip arrows if Pij = 0

I Again, sum of per-state outgoing arrow weights should be one

Introduction to Random Processes Markov Chains 6

Example: Happy - Sad

I I can be happy (Xn = 0) or sad (Xn = 1)

⇒ My mood tomorrow is only affected by my mood today

I Model as Markov chain with transition probabilities

0.8 0.7
  0.2
0.8 0.2
P=
0.3 0.7 H S

0.3
I Inertia ⇒ happy or sad today, likely to stay happy or sad tomorrow
I But when sad, a little less likely so (P00 > P11 )

Introduction to Random Processes Markov Chains 7

Example: Happy - Sad with memory

I Happiness tomorrow affected by today’s and yesterday’s mood

⇒ Not a Markov chain with the previous state space
I Define double states HH (Happy-Happy), HS (Happy-Sad), SH, SS
I Only some transitions are possible
I HH and SH can only become HH or HS
I HS and SS can only become SH or SS
0.2

0.8 HH 0.2 HS
 
0.8 0.2 0 0
 0 0 0.3 0.7 
P=
 0.8 0.2 0
 0.8 0.7
0 
0 0 0.3 0.7
0.3
SH SS 0.7

0.3
I Key: can capture longer time memory via state augmentation
Introduction to Random Processes Markov Chains 8
Random (drunkard’s) walk

I Step to the right w.p. p, to the left w.p. 1 − p

⇒ Not that drunk to stay on the same place

p p p p

... i −1 i i +1 ...

1−p 1−p 1−p 1−p

I States are 0, ±1, ±2, . . . (state space is Z), infinite number of states

I Transition probabilities are

Pi,i+1 = p, Pi,i−1 = 1 − p

I Pij = 0 for all other transitions

Introduction to Random Processes Markov Chains 9

Random (drunkard’s) walk (continued)

I Random walks behave differently if p < 1/2, p = 1/2 or p > 1/2

p = 0.45 p = 0.50 p = 0.55
100 100 100

80 80 80

60 60 60

40 40 40
position (in steps)

position (in steps)

position (in steps)

20 20 20

0 0 0

−20 −20 −20

−40 −40 −40

−60 −60 −60

−80 −80 −80

−100 −100 −100

0 100 200 300 400 500 600 700 800 900 1000 0 100 200 300 400 500 600 700 800 900 1000 0 100 200 300 400 500 600 700 800 900 1000
time time time

⇒ With p > 1/2 diverges to the right (% almost surely)

⇒ With p < 1/2 diverges to the left (& almost surely)
⇒ With p = 1/2 always come back to visit origin (almost surely)
I Because number of states is infinite we can have all states transient
I Transient states not revisited after some time (more later)

Introduction to Random Processes Markov Chains 10

Two dimensional random walk

40

I Take a step in random direction E, W, S or N 35

30

⇒ E, W, S, N chosen with equal probability 25

Latitude (North−South)
20

I States are pairs of coordinates (Xn , Yn ) 15

10

I Xn = 0, ±1, ±2, . . . and Yn = 0, ±1, ±2, . . . 5

−5

I Transiton probs. 6= 0 only for adjacent points −10

−5 0 5 10 15 20 25 30 35 40
Longitude (East−West)


1
East: P Xn+1 = i +1, Yn+1 = j  Xn = i, Yn = j = 50

4 40


1 30

West: P Xn+1 = i −1, Yn+1 = j  Xn = i, Yn = j =

Latitude (North−South)
4 20


1 10

North: P Xn+1 = i, Yn+1 = j +1 Xn = i, Yn = j =

 0
4
−10

1
South: P Xn+1 = i, Yn+1 = j −1 Xn = i, Yn = j =
 −20

4 −30
−45 −40 −35 −30 −25 −20 −15 −10 −5 0
Longitude (East−West)

Introduction to Random Processes Markov Chains 11

More about random walks

I Some random facts of life for equiprobable random walks

I In one and two dimensions probability of returning to origin is 1

⇒ Will almost surely return home

I In more than two dimensions, probability of returning to origin is < 1

⇒ In three dimensions probability of returning to origin is 0.34
⇒ Then 0.19, 0.14, 0.10, 0.08, . . .

Introduction to Random Processes Markov Chains 12

Another representation of a random walk

I Consider an i.i.d. sequence of RVs YN = Y1 , Y2 , . . . , Yn , . . .

I Yn takes the value ±1, P (Yn = 1) = p, P (Yn = −1) = 1 − p

I Define X0 = 0 and the cumulative sum

n
X
Xn = Yk
k=1

⇒ The process XN is a random walk (same we saw earlier)

⇒ YN are i.i.d. steps (increments) because Xn = Xn−1 + Yn

I Q: Can we formally establish the random walk is a Markov chain?

I A: Since Xn = Xn−1 + Yn , n ≥ 1, and Yn independent of Xn−1



P Xn = j  Xn−1 = i, Xn−2 = x = P Xn−1 + Yn = j  Xn−1 = i, Xn−2 = x
= P (Y1 = j − i) := Pij

Introduction to Random Processes Markov Chains 13

General result to identify Markov chains

Theorem
Suppose YN = Y1 , Y2 , . . . , Yn , . . . are i.i.d. and independent of X0 .
Consider the random process XN = X1 , X2 , . . . , Xn , . . . of the form

Xn = f (Xn−1 , Yn ), n≥1

Then XN is a Markov chain with transition probabilities

Pij = P (f (i, Y1 ) = j)

I Useful result to identify Markov chains

⇒ Often simpler than checking the Markov property

I Proof similar to the random walk special case, i.e., f (x, y ) = x + y

Introduction to Random Processes Markov Chains 14

Random walk with boundaries (gambling)

I As a random walk, but stop moving when Xn = 0 or Xn = J

I Models a gambler that stops playing when ruined, Xn = 0
I Or when reaches target gains Xn = J
1 1
p p

0 ... i −1 i i +1 ... J

1−p 1−p

I States are 0, 1, . . . , J, finite number of states

I Transition probabilities are

Pi,i+1 = p, Pi,i−1 = 1 − p, P00 = 1, PJJ = 1

I Pij = 0 for all other transitions
I States 0 and J are called absorbing. Once there stay there forever
⇒ The rest are transient states. Visits stop almost surely
Introduction to Random Processes Markov Chains 15
Chapman-Kolmogorov equations

Definition and examples

Chapman-Kolmogorov equations

Gambler’s ruin problem

Queues in communication networks: Transition probabilities

Classes of states

Introduction to Random Processes Markov Chains 16

Multiple-step transition probabilities

I Q: What can be said about multiple transitions?

I Ex: Transition probabilities between two time slots

Pij2 = P Xm+2 = j  Xm = i


⇒ Caution: Pij2 is just notation, Pij2 6= Pij × Pij

I Ex: Probabilities of Xm+n given Xm ⇒ n-step transition probabilities

Pijn = P Xm+n = j  Xm = i


I Relation between n-, m-, and (m + n)-step transition probabilities

⇒ Write Pijm+n in terms of Pijm and Pijn

I All questions answered by Chapman-Kolmogorov’s equations

Introduction to Random Processes Markov Chains 17

2-step transition probabilities

I Start considering transition probabilities between two time slots

Pij2 = P Xn+2 = j  Xn = i


I Using the law of total probability

∞
X
Pij2 =



P Xn+2 = j  Xn+1 = k, Xn = i P Xn+1 = k  Xn = i
k=0

I In the first probability, conditioning on Xn = i is unnecessary. Thus

∞
X
Pij2 =



P Xn+2 = j  Xn+1 = k P Xn+1 = k  Xn = i
k=0

I Which by definition of transition probabilities yields

∞
X
Pij2 = Pkj Pik
k=0

Introduction to Random Processes Markov Chains 18

Relating n-, m-, and (m + n)-step probabilities

I Same argument works (condition on X0 w.l.o.g., time invariance)

Pijm+n = P Xn+m = j  X0 = i


I Use law of total probability, drop unnecessary conditioning and use

definitions of n-step and m-step transition probabilities
∞
X
Pijm+n =



P Xm+n = j  Xm = k, X0 = i P Xm = k  X0 = i
k=0
∞
X
Pijm+n =



P Xm+n = j  Xm = k P Xm = k  X0 = i
k=0
∞
X
Pijm+n = Pkjn Pikm for all i, j and n, m ≥ 0
k=0

⇒ These are the Chapman-Kolmogorov equations

Introduction to Random Processes Markov Chains 19

Interpretation

I Chapman-Kolmogorov equations are intuitive. Recall

∞
X
Pijm+n = Pikm Pkjn
k=0

I Between times 0 and m + n, time m occurred

I At time m, the Markov chain is in some state Xm = k

⇒ Pikm is the probability of going from X0 = i to Xm = k
⇒ Pkjn is the probability of going from Xm = k to Xm+n = j
⇒ Product Pikm Pkjn is then the probability of going from
X0 = i to Xm+n = j passing through Xm = k at time m

I Since any k might have occurred, just sum over all k

Introduction to Random Processes Markov Chains 20

Chapman-Kolmogorov equations in matrix form

I Define the following three matrices:

⇒ P(m) with elements Pijm
⇒ P(n) with elements Pijn
⇒ P(m+n) with elements Pijm+n
P∞
I Matrix product P(m) P(n) has (i, j)-th element k=0 Pikm Pkjn

I Chapman Kolmogorov in matrix form

P(m+n) = P(m) P(n)

I Matrix of (m + n)-step transitions is product of m-step and n-step

Introduction to Random Processes Markov Chains 21

Computing n-step transition probabilities

I For m = n = 1 (2-step transition probabilities) matrix form is

P(2) = PP = P2

I Proceed recursively backwards from n

P(n) = P(n−1) P = P(n−2) PP = . . . = Pn

I Have proved the following

Theorem
The matrix of n-step transition probabilities P(n) is given by the n-th
power of the transition probability matrix P, i.e.,

P(n) = Pn

Henceforth we write Pn

Introduction to Random Processes Markov Chains 22

Example: Happy-Sad

I Mood transitions in one day

0.8 0.7
0.2
 
0.8 0.2
P= H S
0.3 0.7
0.3
I Transition probabilities between today and the day after tomorrow?
0.70 0.55
0.30
 
0.70 0.30
P2 = H S
0.45 0.55
0.45

Introduction to Random Processes Markov Chains 23

Example: Happy-Sad (continued)

I ... After a week and after a month

   
0.6031 0.3969 0.6000 0.4000
P7 = P30 =
0.5953 0.4047 0.6000 0.4000

I Matrices P7 and P30 almost identical ⇒ limn→∞ Pn exists

⇒ Note that this is a regular limit

I After a month transition from H to H and from S to H w.p. 0.6

⇒ State becomes independent of initial condition (H w.p. 0.6)
I Rationale: 1-step memory ⇒ Initial condition eventually forgotten
I More about this soon

Introduction to Random Processes Markov Chains 24

Unconditional probabilities



I All probabilities so far are conditional, i.e., Pijn = P Xn = j  X0 = i
⇒ May want unconditional probabilities pj (n) = P (Xn = j)

I Requires specification of initial conditions pi (0) = P (X0 = i)

I Using law of total probability and definitions of Pijn and pj (n)

∞
X 

pj (n) = P (Xn = j) = P Xn = j  X0 = i P (X0 = i)
i=0
∞
X
= Pijn pi (0)
i=0

I In matrix form (define vector p(n) = [p1 (n), p2 (n), . . .]T )

T
p(n) = (Pn ) p(0)

Introduction to Random Processes Markov Chains 25

Example: Happy-Sad

 
0.8 0.2
I Transition probability matrix ⇒ P =
0.3 0.7
p(0) = [1, 0]T p(0) = [0, 1]T
1 1
P(Happy) P(Happy)
0.9 P(Sad) 0.9 P(Sad)

0.8 0.8

0.7 0.7

0.6 0.6
Probabilities

Probabilities
0.5 0.5

0.4 0.4

0.3 0.3

0.2 0.2

0.1 0.1

0 0
0 5 10 15 20 25 30 0 5 10 15 20 25 30
Time (days) Time (days)

I For large n probabilities p(n) are independent of initial state p(0)

Introduction to Random Processes Markov Chains 26

Gambler’s ruin problem

Definition and examples

Chapman-Kolmogorov equations

Gambler’s ruin problem

Queues in communication networks: Transition probabilities

Classes of states

Introduction to Random Processes Markov Chains 27

Gambler’s ruin problem

I You place $1 bets

(i) With probability p you gain $1, and
(ii) With probability q = 1 − p you loose your $1 bet
I Start with an initial wealth of $i
I Define bias factor α := q/p
I If α > 1 more likely to loose than win (biased against gambler)
I α < 1 favors gambler (more likely to win than loose)
I α = 1 game is fair

I You keep playing until

(a) You go broke (loose all your money)
(b) You reach a wealth of $N (same as first lecture, HW1 for N → ∞)

I Prob. Si of reaching $N before going broke for initial wealth $i?

I S stands for success, or successful betting run (SBR)

Introduction to Random Processes Markov Chains 28

Gambler’s Markov chain

I Model wealth as Markov chain XN . Transition probabilities

Pi,i+1 = p, Pi,i−1 = q, P00 = PNN = 1

1 1
p p

0 ... i −1 i i +1 ... N

q q

I Realizations xN . Initial state = Initial wealth = i

⇒ Sates 0 and N are absorbing. Eventually end up in one of them
⇒ Remaining states are transient (visits eventually stop)
I Being absorbing states says something about the limit wealth
  
lim xn = 0, or lim xn = N ⇒ Si := P lim Xn = N  X0 = i
n→∞ n→∞ n→∞

Introduction to Random Processes Markov Chains 29

Recursive relations

I Total probability to relate Si with Si+1 , Si−1 from adjacent states

⇒ Condition on first bet X1 , Markov chain homogeneous

Si = Si+1 Pi,i+1 + Si−1 Pi,i−1 = Si+1 p + Si−1 q

I Recall p + q = 1 and reorder terms

p(Si+1 − Si ) = q(Si − Si−1 )

I Recall definition of bias α = q/p

Si+1 − Si = α(Si − Si−1 )

Introduction to Random Processes Markov Chains 30

Recursive relations (continued)

I If current state is 0 then Si = S0 = 0. Can write

S2 − S1 = α(S1 − S0 ) = αS1

I Substitute this in the expression for S3 − S2

S3 − S2 = α(S2 − S1 ) = α2 S1
I Apply recursively backwards from Si − Si−1
Si − Si−1 = α(Si−1 − Si−2 ) = . . . = αi−1 S1

I Sum up all of the former to obtain

 
Si − S1 = S1 α + α2 + . . . + αi−1

I The latter can be written as a geometric series

 
Si = S1 1 + α + α2 + . . . + αi−1

Introduction to Random Processes Markov Chains 31

Probability of successful betting run

I Geometric series can be summed in closed form, assuming α 6= 1

i−1
!
X
k 1 − αi
Si = α S1 = S1
1−α
k=0

I When in state N, SN = 1 and so

1 − αN 1−α
1 = SN = S1 ⇒ S1 =
1−α 1 − αN
I Substitute S1 above into expression for probability of SBR Si

1 − αi
Si = , α 6= 1
1 − αN

i
I For α = 1 ⇒ Si = iS1 , 1 = SN = NS1 , ⇒ Si = N

Introduction to Random Processes Markov Chains 32

Analysis for large N

I Recall
(1 − αi )/(1 − αN ),

α 6= 1,
Si =
i/N, α=1

I Consider exit bound N arbitrarily large

(i) For α > 1, Si ≈ (αi − 1)/αN → 0

(ii) Likewise for α = 1, Si = i/N → 0
I If win probability p does not exceed loose probability q
⇒ Will almost surely loose all money

(iii) For α < 1, Si → 1 − αi

I If win probability p exceeds loose probability q
⇒ For sufficiently high initial wealth i, will most likely win

I This explains what we saw on first lecture and HW1

Introduction to Random Processes Markov Chains 33

Queues in communication systems

Definition and examples

Chapman-Kolmogorov equations

Gambler’s ruin problem

Queues in communication networks: Transition probabilities

Classes of states

Introduction to Random Processes Markov Chains 34

Queues in communication systems

I General communication systems goal

⇒ Move packets from generating sources to intended destinations

I Between arrival and departure we hold packets in a memory buffer

⇒ Want to design buffers appropriately

Introduction to Random Processes Markov Chains 35

Non-concurrent queue

I Time slotted in intervals of duration ∆t

⇒ n-th slot between times n∆t and (n + 1)∆t

I Average arrival rate is λ̄ packets per unit time

⇒ Probability of packet arrival in ∆t is λ = λ̄∆t

I Packets are transmitted (depart) at a rate of µ̄ packets per unit time

⇒ Probability of packet departure in ∆t is µ = µ̄∆t

I Assume no simultaneous arrival and departure (no concurrence)

⇒ Reasonable for small ∆t (µ and λ likely to be small)

Introduction to Random Processes Markov Chains 36

Queue evolution equations

I Qn denotes number of packets in queue (backlog) in n-th time slot

I An = nr. of packet arrivals, Dn = nr. of departures (during n-th slot)

I If the queue is empty Qn = 0 then there are no departures

⇒ Queue length at time n + 1 can be written as

Qn+1 = Qn + An , if Qn = 0

I If Qn > 0, departures and arrivals may happen

Qn+1 = Qn + An − Dn , if Qn > 0

I An ∈ {0, 1}, Dn ∈ {0, 1} and either An = 1 or Dn = 1 but not both

⇒ Arrival and departure probabilities are

P (An = 1) = λ, P (Dn = 1) = µ

Introduction to Random Processes Markov Chains 37

Queue evolution probabilities

I Future queue lengths depend on current length only

I Probability of queue length increasing



P Qn+1 = i + 1  Qn = i = P (An = 1) = λ, for all i

I Queue length might decrease only if Qn > 0. Probability is



P Qn+1 = i − 1  Qn = i = P (Dn = 1) = µ, for all i > 0

I Queue length stays the same if it neither increases nor decreases



P Qn+1 = i  Qn = i = 1 − λ − µ, for all i > 0


P Qn+1 = 0 Qn = 0 = 1 − λ


⇒ No departures when Qn = 0 explain second equation

Introduction to Random Processes Markov Chains 38

Queue as a Markov chain

I MC with states 0, 1, 2, . . .. Identify states with queue lengths

I Transition probabilities for i 6= 0 are

Pi,i−1 = µ, Pi,i = 1 − λ − µ, Pi,i+1 = λ

I For i = 0: P00 = 1 − λ and P01 = λ

1−λ 1−λ−µ 1−λ−µ 1−λ−µ

λ λ λ λ

0 ... i −1 i i +1 ...
µ µ µ µ

Introduction to Random Processes Markov Chains 39

Numerical example: Probability propagation

I Build matrix P truncating at maximum queue length L = 100

⇒ Arrival rate λ = 0.3. Departure rate µ = 0.33
⇒ Initial distribution p(0) = [1, 0, 0, . . .]T (queue empty)

0
10
queue length 0
queue length 10
queue length 20
I Propagate probabilities (Pn )T p(0)
I Probabilities obtained are
−1
10


Probabilities

P Qn = i  Q0 = 0 = pi (n)
−2
10 I A few i’s (0, 10, 20) shown
I Probability of empty queue ≈ 0.1
−3
10
I Occupancy decreases with i
0 100 200 300 400 500 600 700 800 900 1000
Time

Introduction to Random Processes Markov Chains 40

Classes of states

Definition and examples

Chapman-Kolmogorov equations

Gambler’s ruin problem

Queues in communication networks: Transition probabilities

Classes of states

Introduction to Random Processes Markov Chains 41

Transient and recurrent states

I States of a MC can be recurrent or transient

I Transient states might be visited early on but visits eventually stop

I Almost surely, Xn 6= i for n sufficiently large (qualifications needed)

I Visits to recurrent states keep happening forever. Fix arbitrary m

I Almost surely, Xn = i for some n ≥ m (qualifications needed)

1 0.2 0.2
T1 R1 0.3

R3 0.6 0.6 0.6 0.7

T2 R2 0.4
0.2 0.2

Introduction to Random Processes Markov Chains 42

Definitions

I Let fi be the probability that starting at i, MC ever reenters state i

∞ ∞
! !
[  [ 
fi := P Xn = i  X0 = i = P Xn = i  Xm = i
n=1 n=m+1

I State i is recurrent if fi = 1
⇒ Process reenters i again and again (a.s.). Infinitely often

I State i is transient if fi < 1

⇒ Positive probability 1 − fi > 0 of never coming back to i

Introduction to Random Processes Markov Chains 43

Recurrent states example



I State R3 is recurrent because it is absorbing P X1 = R3  X0 = R3 = 1
1 0.2 0.2
T1 R1 0.3
I State R1 is recurrent because
R3 0.6 0.6 0.6 0.7


P X1 = R1  X0 = R1 = 0.3 T2 R2 0.4

0.2 0.2
P X2 = R1 , X1 6= R1  X0 = R1 = (0.7)(0.6)


P X3 = R1 , X2 6= R1 , X1 6= R1  X0 = R1 = (0.7)(0.4)(0.6)
..
.
P Xn = R1 , Xn−1 6= R1 , . . . , X1 6= R1  X0 = R1 = (0.7)(0.4)n−2 (0.6)


∞
X 

I Sum up: fi = P Xn = R1 , Xn−1 6= R1 , . . . , X1 6= R1  X0 = R1
n=1
∞
!  
X n−2 1
= 0.3 + 0.7 0.4 0.6 = 0.3 + 0.7 0.6 = 1
n=2
1 − 0.4

Introduction to Random Processes Markov Chains 44

Transient state example

I States T1 and T2 are transient

I Probability of returning to T1 is fT1 = (0.6)2 = 0.36

⇒ Might come back to T1 only if it goes to T2 (w.p. 0.6)
⇒ Will come back only if it moves back from T2 to T1 (w.p. 0.6)

1 0.2 0.2
T1 R1 0.3

R3 0.6 0.6 0.6 0.7

T2 R2 0.4
0.2 0.2

I Likewise, fT2 = (0.6)2 = 0.36

Introduction to Random Processes Markov Chains 45

Expected number of visits to states

I Define Ni as the number of visits to state i given that X0 = i

∞
X  
Ni := I Xn = i  X0 = i
n=1

I If Xn = i, this is the last visit to i w.p. 1 − fi

I Prob. revisiting state i exactly n times is (n visits × no more visits)

P (Ni = n) = fi n (1 − fi )

⇒ Number of visits Ni + 1 is geometric with parameter 1 − fi

I Expected number of visits is

1 fi
E [Ni ] + 1 = ⇒ E [Ni ] =
1 − fi 1 − fi
⇒ For recurrent states Ni = ∞ a.s. and E [Ni ] = ∞ (fi = 1)

Introduction to Random Processes Markov Chains 46

Alternative transience/recurrence characterization

I Another way of writing E [Ni ]

∞ h  ∞
X i X
Piin

E [Ni ] = E I Xn = i  X0 = i =
n=1 n=1

I Recall that: for transient states E [Ni ] = fi /(1 − fi ) < ∞

for recurrent states E [Ni ] = ∞

Theorem
P∞
I State i is transient if and only if Piin < ∞
Pn=1
∞
I State i is recurrent if and only if n=1 Piin = ∞

I Number of future visits to transient states is finite

⇒ If number of states is finite some states have to be recurrent

Introduction to Random Processes Markov Chains 47

Accessibility

I Def: State j is accessible from state i if Pijn > 0 for some n ≥ 0

⇒ It is possible to enter j if MC initialized at X0 = i


I Since Pii0 = P X0 = i  X0 = i = 1, state i is accessible from itself

1 0.2 0.2
T1 R1 0.3

R3 0.6 0.6 0.6 0.7

T2 R2 0.4
0.2 0.2

I All states accessible from T1 and T2

I Only R1 and R2 accessible from R1 or R2
I None other than R3 accessible from itself

Introduction to Random Processes Markov Chains 48

Communication

I Def: States i and j are said to communicate (i ↔ j) if

⇒ j is accessible from i, i.e., Pijn > 0 for some n; and
⇒ i is accessible from j, i.e., Pjim > 0 for some m

I Communication is an equivalence relation

I Reflexivity: i ↔ i
I Holds because Pii0 = 1
I Symmetry: If i ↔ j then j ↔ i
I If i ↔ j then Pijn > 0 and Pjim > 0 from where j ↔ i
I Transitivity: If i ↔ j and j ↔ k, then i ↔ k
I Just notice that Pikn+m ≥ Pijn Pjkm > 0

I Partitions set of states into disjoint classes (as all equivalences do)
⇒ What are these classes?

Introduction to Random Processes Markov Chains 49

Recurrence and communication

Theorem
If state i is recurrent and i ↔ j, then j is recurrent

Proof.
I If i ↔ j then there are l, m such that Pjil > 0 and Pijm > 0

I Then, for any n we have

Pjjl+n+m ≥ Pjil Piin Pijm

P∞
I Sum for all n. Note that since i is recurrent n=1 Piin = ∞
∞ ∞ ∞
!
X X X
Pjjl+n+m ≥ Pjil Piin Pijm = Pjil Piin Pijm = ∞
n=1 n=1 n=1

⇒ Which implies j is recurrent

Introduction to Random Processes Markov Chains 50

Recurrence and transience are class properties

Corollary
If state i is transient and i ↔ j, then j is transient

Proof.
I If j were recurrent, then i would be recurrent from previous theorem

I Recurrence is shared by elements of a communication class

⇒ We say that recurrence is a class property

I Likewise, transience is also a class property

I MC states are separated in classes of transient and recurrent states

Introduction to Random Processes Markov Chains 51

Irreducible Markov chains

I A MC is called irreducible if it has only one class

I All states communicate with each other
I If MC also has finite number of states the single class is recurrent
I If MC infinite, class might be transient

I When it has multiple classes (not irreducible)

I Classes of transient states T1 , T2 , . . .
I Classes of recurrent states R1 , R2 , . . .

I If MC initialized in a recurrent class Rk , stays within the class

I If MC starts in transient class Tk , then it might
(a) Stay on Tk (only if |Tk | = ∞)
(b) End up in another transient class Tr (only if |Tr | = ∞)
(c) End up in a recurrent class Rl

I For large time index n, MC restricted to one class

⇒ Can be separated into irreducible components

Introduction to Random Processes Markov Chains 52

Communication classes example

1 0.2 0.2
T1 R1 0.3

R3 0.6 0.6 0.6 0.7

T2 R2 0.4
0.2 0.2

I Three classes
⇒ T := {T1 , T2 }, class with transient states
⇒ R1 := {R1 , R2 }, class with recurrent states
⇒ R2 := {R3 }, class with recurrent state

I For large n suffices to study the irreducible components R1 and R2

Introduction to Random Processes Markov Chains 53

Example: Random walk

I Step right with probability p, left with probability q = 1 − p

p p p p

... i −1 i i +1 ...

1−p 1−p 1−p 1−p

I All states communicate ⇒ States either all transient or all recurrent

I To see which, consider initially X0 = 0 and note for any n ≥ 1

 
2n 2n n n (2n)! n n
P00 = p q = p q
n n!n!

⇒ Back to 0 in 2n steps ⇔ n steps right and n steps left

Introduction to Random Processes Markov Chains 54

Example: Random walk (continued)
√ √
I Stirling’s formula n! ≈ nn ne −n 2π
2n
⇒ Approximate probability P00 of returning home as

2n (2n)! n n (4pq)n
P00 = p q ≈ √
n!n! nπ

I Symmetric random walk (p = q = 1/2)

∞ ∞
X
2n
X 1
P00 = √ =∞
n=1 n=1
nπ

⇒ State 0 (hence all states) are recurrent

I Biased random walk (p > 1/2 or p < 1/2), then pq < 1/4 and
∞ ∞
X
2n
X (4pq)n
P00 = √ <∞
n=1 n=1
nπ

⇒ State 0 (hence all states) are transient

Introduction to Random Processes Markov Chains 55
Example: Right-biased random walk

I Alternative proof of transience of right-biased random walk (p > 1/2)

p p p p

... i −1 i i +1 ...

1−p 1−p 1−p 1−p

Pn
I Write current position of random walker as Xn = k=1 Yk
⇒ Yk are the i.i.d. steps: E [Yk ] = 2p − 1, var [Yk ] = 4p(1 − p)

I From Central Limit Theorem (Φ(x) is cdf of standard Normal)

Pn !
k=1 Yk − n(2p − 1)
P p ≤ a → Φ(a)
n4p(1 − p)

Introduction to Random Processes Markov Chains 56

Example: Right-biased random walk (continued)

√
I Choose a = √n(1−2p) < 0, use Chernoff bound Φ(a) ≤ exp(−a2 /2)
4p(1−p)

n
! √ !
n(1 − 2p) n(1−2p)2
< e − 8p(1−p) → 0
X
P (Xn ≤ 0) = P Yk ≤ 0 →Φ p
k=1
4p(1 − p)

n
I Since P00 ≤ P (Xn ≤ 0), sum over n
∞ ∞ ∞
n(1−2p)2
e − 8p(1−p) < ∞
X X X
n
P00 ≤ P (Xn ≤ 0) <
n=1 n=1 n=1

I This establishes state 0 is transient

⇒ Since all states communicate, all states are transient

Introduction to Random Processes Markov Chains 57

Take-home messages

I States of a MC can be transient or recurrent

I A MC can be partitioned into classes of communicating states

⇒ Class members are either all transient or all recurrent
⇒ Recurrence and transience are class properties
⇒ A finite MC has at least one recurrent class

I A MC with only one class is irreducible

⇒ If reducible it can be separated into irreducible components

Introduction to Random Processes Markov Chains 58

Glossary

I Markov chain I Communication system

I State space I Non-concurrent queue
I Markov property I Queue evolution model
I Transition probability matrix I Recurrent and transient states
I State transition diagram I Accessibility
I State augmentation I Communication
I Random walk I Equivalence relation
I n-step transition probabilities I Communication classes
I Chapman-Kolmogorov eqs. I Class property
I Initial distribution I Irreducible Markov chain
I Gambler’s ruin problem I Irreducible components

Introduction to Random Processes Markov Chains 59