Markov Chains

Lecture 2

Background Readings: Durbin et. al. Section 3.1,

.
Markov Chain :
a process with a finite number of states (or outcomes, or events) in
which the probability of being in a particular state at step n + 1
depends only on the state occupied at step n.

Prof. Andrei A. Markov (1856-1922) , published his result in 1906

2
 A sequence of trials of an experiment is a Markov chain if:
1. the outcome of each experiment is one of a set of discrete states;
2. the outcome of an experiment depends only on the present state, and not on any
past states.
Categories

 If the time parameter is discrete {t1,t2,t3,.....}, it is called Discrete Time Markov

Chain (DTMC ).

 If time parameter is continues, (t≥0) it is called Continuous Time Markov Chain

(CTMC ) 3
Markov chains: Suppose that a system can be in one of m different states
at each given time

Time: 1, 2, 3, -- - k - -
RVs = Random Variables
RVs: X1, X2, - - - Xk -- -
4
If the system is in state i, the probability that it transitions to the
next state, j in the next time is given by:

5
6
7
 …Definition 2

The initial distribution for the Markov chain is the sequence of probabilities

π(x) = P {X0 = x}, x ∈ S,

or, in vector form,

π = [π(x) | x ∈ S].
8
9
 Markov Chain (cont.)
X1 X2 Xn-1 Xn

• For each integer n, a Markov Chain assigns probability to

sequences (x1…xn) over D (i.e, xi D) as follows:
n
p(( x1 , x2 ,...xn ))  p( X 1  x1 ) p( X i  xi | X i 1  xi 1 )
n
i 2

 p ( x1 ) axi1xi
i 2
Similarly, (X1,…, Xi ,…) is a sequence of probability
distributions over D. There is a rich theory which studies the
properties of these sequences. A bit of it is presented next.
10
 Markov Chain (cont.)
X1 X2 Xn-1 Xn

Similarly, each Xi is a probability distributions over D, which

is determined by the initial distribution (p1,..,pn) and the
transition matrix M.
There is a rich theory which studies the properties of such
“Markov sequences” (X1,…, Xi ,…). A bit of this theory is
presented next.

11
Suppose this person has an initial distribution among the shops as follows:

π(x) = P(X0 = x0) = 1/4, for x0 ∈ {1, 2, 3, 4}

or, in vector form,

π = (1/4, 1/4, 1/4, 1/4)
.
Show that

P(X0 = 1, X1 = 2, X2 = 4, X3 = 3) = π(1)p(1, 2)p(2, 4)p(4, 3) = 1/24.

12
Suppose this person has an initial distribution among the shops as follows
π(x) = P(X0 = x0) = 1/4, for x0 ∈ {1, 2, 3, 4}
or, in vector form,
π = (1/4, 1/4, 1/4, 1/4)
Show that

P(X0 = 1, X1 = 2, X2 = 4, X3 = 3) = π(1)p(1, 2)p(2, 4)p(4, 3) = 1/24.

Using similar reasoning, we have the general fact that:

P(X0 = x0, X1 = x1, . . . , Xn-1 = xn-1, Xn = xn) = π(x0)p(x0, x1)p(x1, x2) · · · p(xn-1, xn)
which holds for all n ≥ 0 and all choices of states in S.
13
14
15
two states => n = 1 (0, 1)
P00 = P(X t+1 = 0 | X t = 0) = ¼ ; 0 0
P01 = P(X t+1 = 1 | Xt = 0) = ¾; 0 1
P10 = P(X t+1 = 0 | Xt = 1) = ½; 1 0
P11 = P(X t+1 = 1 | Xt = 1) = ½; 1 1

16
17
18
19
Random walk with borders (gambling)

20
21
22
Chapman-Kolmogorov equation

23
Chapman Kolmogorov equations
Multiple step transition probabilities

24
2-step transition probabilities

25
n-step, m-step and (m + n)-step

26
 Interpretation

Chapman Kolmogorov is intuitive. Recall

27
 Matrix form

n-step transition probabilities

28
n-Step Transition Probabilities:

Consider a Markov chain {Xn, n = 0,1,2,...}, where Xn∈S. If X0= i, then X1=j with
probability pij. That is, pij gives us the probability of going from state i to state j in
one step. Now suppose that we are interested in finding the probability of going from
state i to state j in two steps, i.e.,

We can find this probability by applying the law of total probability. In particular, we
argue that X1 can take one of the possible values in S. Thus, we can write:

We conclude

29
Example: Happy-Sad

30
31
State Transition Matrix and Diagram

We often list the transition probabilities in a matrix. The matrix is

called the state transition matrix or transition probability matrix and is
usually shown by P. Assuming the states are 1, 2, ⋯, r, then the state
transition matrix is given by

32
 Ex2
Example:
On considère la matrice Q de taille 7 × 7 suivante :

33
34
35
36
37
38
39
40
41
42
43
Examples 1:Weather model.

Let Xn be the state of the weather on day n in Mankon town, which we

assume is either rainy or sunny. We could use a Markov chain as a
crude model for how the weather evolves day-by day. The state space is
S = {rain; sun }.

One transition matrix might be

This says that if it is sunny today, then the chance it will be sunny
tomorrow is 0.8, whereas if it is rainy today, then the chance it will be
sunny tomorrow is 0.4

44
 Transition matrix features:

It is square, since all possible states must be used both as rows

and as columns.
 All entries are between 0 and 1, because all entries represent
probabilities.
 The sum of the entries in any row must be 1, since the
numbers in the row give the probability of changing from the
state at the left to one of the states indicated across the top.

45
 Matrix Representation
A B C D The transition probabilities
0.95 0 0.05 0 Matrix M =(ast)
A
M is a stochastic Matrix:
B 0.2 0.5 0 0.3
a t st 1
0 0.2 0 0.8
C The initial distribution vector
(u1…um) defines the distribution
0 0 1 0 of X1 (p(X1=si)=ui) .
D

Then after one move, the distribution is changed

to X2 = X1M

46
 Matrix Representation
A B C D
0.95 0 0.05 0
A
Example: if X1=(0, 1, 0, 0)
B 0.2 0.5 0 0.3 then X2=(0.2, 0.5, 0, 0.3)

0 0.2 0 0.8 And if X1=(0, 0, 0.5, 0.5)

C then X2=(0, 0.1, 0.5, 0.4).
0 0 1 0
D

The i-th distribution is Xi = X1Mi-1

47
 Representation of a Markov Chain as a
Digraph
State Transition Diagram
0.95
A B C D
0.95 0 0.05 0

0.2 0.5 A
0.2 0.5 0 0.3
B

0.05 0.2 0.3 0 0.2 0 0.8

C

0.8 D
0 0 1 0

1
A state transition diagram.

Each directed edge AB is associated with the positive

transition probability from A to B.

48
80% of students who do maths work during one study period, will do the maths work at the
next study period. 30% of students who do english work during one study period, will do the
english work at the next study period.
Initially there were 60 students do maths work and 40 students do english work. Calculate,
1) The transition probability matrix
2) The number of students who do maths work, english work for the next subsequent 2 study
periods.
Solution

49
Example: Consider the Markov chain shown in Figure below:

50
Solution

51
Write any transition diagrams as transition matrices

a) b)

c)
a)

52
 Probability Distributions: State Probability Distributions:

Consider a Markov chain {Xn,n= 0,1,2,...}, where Xn∈S={1,2,⋯,r}.

Suppose that we know the probability distribution of X0. More

specifically, define the row vector π(0) as:

π(0) = [P(X0 = 1)P(X0 = 2)⋯P(X0 = r)].

How can we obtain the probability distribution of X1, X2, ⋯?

We can use the law of total probability. More specifically, for any j∈S,
we can write:

53
 If we generally define

we can rewrite the above result in the form of matrix multiplication

where P is the state transition matrix. Similarly, we can write:

More generally, we can write:

54
Our work thus far is summarized below:

Example

55
Solution

56
 Solved example
Voting Trends At the end of June in a presidential election year, 40% of the voters
were registered as liberal, 45% as conservative, and 15% as independent. Over a one-
month period, the liberals retained 80% of their constituency, while 15% switched to
conservative and 5% to independent. The conservatives retained 70% and lost 20% to
the liberals. The independents retained 60% and lost 20% each to the conservatives
and liberals. Assume that these trends continue.
a) Write a transition matrix using this information.
b) Write a probability vector for the initial distribution.
Find the percent of each type of voter at the end of each of
the following months.
c). July
d). August
e). September
f. October Transition matrix
(at time, t+1)
Solution
(at time, t)

L I C
Liberal 0.8 0.15 0.05
Conservative 0.2 0.7 0.1
a) Independent 0.2 0.2 0.6
57
b) Initial distribution
40% of the voters were registered as liberal, 45% as conservative, and 15% as
independent:
b) The probability vector for the initial distribution:
X0 = π(0) = [0.4 0.45 0.15]
c) Percent of each type of voter at the end of July:
44% L; 40.5% C; 15.5% I
d) Percent of each type of voter at the end of August:
46.4% L; 38.05% C; 15.55% I
e) Percent of each type of voter at the end of August: Apply X0 *P(n)
47.84% L; 36.705% C; 15.3355% I
f) Percent of each type of voter at the end of September:
48.704% I; 35.9605% C; 15.3355% I

58
Regular Transition Matrices
One of the many applications of Markov chains is in finding long-range predictions.
It is not possible to make long-range predictions with all transition matrices, but for a
large set of transition matrices, long-range predictions are possible. Such predictions
are always possible with regular transition matrices.
 Any transition matrix that has no zeros determines a regular Markov chain.
 However, it is possible for a regular Markov chain to have a transition matrix that
has zeros, provided certain powers have no zeros.
 An example of a non-regular Markov chain is an absorbing chain.
 A Markov chain is a regular Markov chain if its transition matrix is regular.

59
NOTE
If a transition matrix P has some zero entries, and P2 does as well, you may wonder
how far you must compute Pk to be certain that the matrix is not regular.

The answer is that if zeros occur in the identical places in both Pk and Pk+1 for any k,
they will appear in those places for all higher powers of P, so P is not regular.

Suppose that v is any probability vector. It can be shown that for a regular Markov
chain with a transition matrix P, there exists a single vector V that does not depend on
v, such that gets v.Pn closer and closer to V as n gets larger and larger 60
61
PROPERTIES OF REGULAR MARKOV CHAINS

Suppose a regular Markov chain has a transition matrix P.

1) As n gets larger and larger, the product v.Pn approaches a
unique vector V for any initial probability vector v. Vector V is
called the equilibrium vector or fixed vector.

2) Vector V has the property that V.P = P

3) To find V, solve a system of equations obtained from the

matrix equation V.P = V and from the fact that the sum of the
entries of V is 1.

4) The powers Pn come closer and closer to a matrix whose

rows are made up of the entries of the equilibrium vector V.

62
 EQUILIBRIUM VECTOR OF A MARKOV CHAIN
If a Markov chain with transition matrix P is regular, then there is a unique vector V
such that, for any probability vector v and for large values of n

Vector V is called the equilibrium vector or the fixed vector of the Markov chain.

If a Markov chain with transition matrix P is regular, then there exists a probability
vector V such that

This vector V gives the long-range trend of the Markov chain. Vector V is found by
solving a system of linear equations, as shown in the next example.

Example:

63
64
65
 Exercise 2
Suppose you eat one of three desserts every day :
1. Ice cream
2. Cake
3 . Chocolate
Assume the sequence of desserts you eat form a Markov chain with transition
matrix:

a) Transition diagram
b) what is the probability that in 2 day you seat , Ice cream given that
you ate cake today ?
c) what is the probability that you eat ice cream in 200 days given that
you ate cake today ?
Solution

a)

67
b)

68
c)

69
70
By Markov hypothesis,

71
Over the long run, with what frequency is state j visited?

As time goes to infinity , in what state is the system

most likely to be ?
Ergodic Markov Chains

A Markov chain is called an ergodic Markov chain if it is possible to

go from every state to every state (not necessarily in one move). In
many books, ergodic Markov chains are called irreducible.
Let the transition matrix of a Markov chain be defined by:

Then is clear that it is possible to move from any state to any state, so the
chain is ergodic. However, if n is odd, then it is not possible to move from
state 0 to state 0 in n steps, and if n is even, then it is not possible to move
from state 0 to state 1 in n steps, so the chain is not regular. 72
Theorem: If a Markov chain is ergodic, then the limits

73
Example:

74
Example: Consider the Markov chain with transition matrix

and state space S = {1, 2, 3}. Then,

Solving this 3 by 3 linear system we get w = x = [2/5, 1/5, 2/5] and hence
limn→∞ PN (x, y) = 2/5 for y = 1 and 3, and limn→∞ Pn (x, y) = 1/5 for y = 2.
75
Example
Consider a MC with the following transition matrix:

Sunny (state 1), Cloudy (state 2), or

rainy (state 3).

You are planning a two-day holiday to begin in seven days, i.e., you are away on day
7 and 8. A travel insurance deal will pay you $2500 if it rains on both days, nothing
if not, and the premium is $100. Should you buy this insurance if it is sunny today?

Solution
One way to make a decision would be to compare the expected pay-out
with the premium. The actual return is:

where Xn is the weather state on day n 76

77
Exercises
Exercise 1

Exercise 2

78
 Exercise 3

Consider the transition matrix

b) Show that

79
 Classification of States
The first definition concerns the accessibility of states from each other: If it is
possible to go from state i to state j, we say that state j is accessible from state i. In
particular, we can provide the following definitions.

80
On dira que deux états i et j communiquent, noté,

81
Exemple.
Considérons une chaîne de Markov d’espace d’état S = {0, 1, 2, 3} de
matrice de transition

On souhaite définir les communications entre les états. On a 0 1,

0 2 et 2 3, les états 2 et 3 sont inaccessibles des états 1 et 0, l’état 3
est inaccessible de 2. La chaîne n’est pas irréductible, on a trois classes:

Considérons une chaîne de Markov d’espace d’état S = {0, 1, 2} de matrice de transition

Conclusion????
Tous les états communiquent, la
chaîne est irréductible 82
 Example 2:

Find the communicating classes associated with the transition diagram

shown.

Solution:
{1, 2, 3}, {4, 5}.
State 2 leads to state 4, but state 4 does not lead back to state 2, so they are in
different communicating classes.
Definition: A communicating class of states is closed if it is not possible to
leave that class.

Example: In the transition diagram above:

• Class {1, 2, 3} is not closed: it is possible to escape to class {4, 5}
.• Class {4, 5} is closed: it is not possible to escape

83
Example:
Consider the Markov chain shown in Figure that follows.

It is assumed that when there is an arrow from state i to state j, then

pij>0. Find the equivalence classes for this Markov chain.
84
 There are four communicating classes in this Markov chain. Looking at Figure below,
we notice that states 1 and 2 communicate with each other, but they do not
communicate with any other nodes in the graph.

Similarly, nodes 3 and 4

communicate with each other,
but they do not communicate
with any other nodes in the
graph. State 5 does not
communicate with any other
states, so it by itself is a class.
Finally, states 6, 7, and 8
construct another class.

Thus, here are the classes:

Class 3={state 5},
Class 1={state 1,state 2},
Class 4={state 6,state 7,state 8}
Class 2={state 3,state 4},
85
A Markov chain is said to be irreducible if all states communicate with each other.
Looking at Figure below:

Notice that there are two kinds of classes. In particular, if at any time the Markov
chain enters Class 4, it will always stay in that class.

On the other hand, for other classes this is not true. For example, if X0=1, then the
Markov chain might stay in Class 1 for a while, but at some point, it will leave that
class and it will never return to that class again. The states in Class 4 are called
recurrent states, while the other states in this chain are called transient.
86
Recurrent states
In general, a state is said to be recurrent if, any time that we leave that state, we will
return to that state in the future with probability one. On the other hand, if the
probability of returning is less than one, the state is called transient. Here, we provide
a formal definition:

Consider a Markov chain and assume X0=i. If i is a recurrent state, then the
chain will return to state i any time it leaves that state. Therefore, the chain will
visit state i an infinite number of times. On the other hand, if i is a transient
state, the chain will return to state i with probability fii<1. Thus, in that case, the
total number of visits to state i will be a Geometric random variable with
parameter 1−fii.
87
Recurrent – Transient State

88
89
It follows from the above proposition that:

90
91
92
93
Example 1
Show that in a finite Markov chain, there is at least one recurrent class.

Solution

Consider a finite Markov chain with r states, S={1,2,⋯,r}.

Suppose by contradiction that all states are transient.

Then, starting from time 0, the chain might visit state 1 several times, but at some
point the chain will leave state 1 and will never return to it. That is, there exists an
integer M1>0 such that Xn≠1, for all n ≥ M1. Similarly, there exists an integer M2>0
such that Xn≠2, for all n≥M2, and so on. Now, if you choose

n ≥ max{M1,M2,⋯,Mr},

then Xn cannot be equal to any of the states 1,2,⋯,r.

This is a contradiction, so we conclude that there must be at least one recurrent state,
which means that there must be at least one recurrent class.

94
 Ex2
Sur l’ensemble S = {0, 1, . . . , n} on considère la chaîne de Markov de
matrice de transition P donnée pour 0 ≤ x ≤ n − 1 par:

l’état n étant absorbant (i.e. P(n, x) = 1 si n = x et 0 sinon), et avec 0 < p < 1.

a) Dessiner le graphe associé à cette chaîne de Markov. Quels sont les états récurrents
et les états transients de cette chaîne ?

b) Soit S = {1, . . . , 6}, compléter la matrice suivante pour qu’elle soit matrice de
transition d’une chaîne de Markov

et déterminer quels sont ses états transitoires et récurrents. 95

 Solution
a) On a deux classe d'équivalence (deux sous-chaînes irréductibles) dans cette
chaîne. La première contient les états {0, 1, . . . , n - 1} et l'autre l'état n.

L'état n est irréductible, car P {Tn < ∞|X0 = n} = 1.

Les autres états sont soit tous irréductibles soit tous transients
(car ils sont dans la même composante fortement connexe du graphe).

Étudions l'état n -1
On a
P{Tn-1<∞|X0=n-1} ≤ P{X1=0|X0=n-1}
=1–p
<1
Les états 0 à n - 1 sont donc transients

96
 … Solution
b) Dessiner le graphe de la chaîne de Markov.

????????????

On voit qu'il y a deux composantes fortement connexes fermées (avec

aucune arrête sortante) : C1 = {1, 2} et C2 = {3, 5}. L'ensemble {4, 6} est
aussi fortement connexe mais n'est pas fermé.

Si on regroupe ces composantes connexes et qu'on dessine l'arbre

associé, l'ensemble {4, 6} est la racine de l'arbre, et les noeuds C1 et C2
sont ses fils et sont des feuilles de l'arbre.

Comme le graphe est ni, on sait que les états dans les feuilles sont
récurrents et les autres sont transitoires. Montrons le dans ce cas là.

97
 … Solution

On montre de même que les états de C2 sont récurrents.

Montrons maintenant que l'état 4 n'est pas récurrent (comme il
communique avec 6, cela montrera aussi que 6 est transitoire).
Comme 6 est le seul état atteignable en un coup depuis 4 qui peut
ensuite permettre de revenir en 4, on a

P[Tx<∞|X0=4] ≤ P [X1 = 6|X0 = 4] < 1.

Donc 4 et 6 sont transitoires

98
 Periodicity
Consider the Markov chain shown in Figure below:

There is a periodic pattern in this chain. Starting from state 0, we only return to 0 at
times n=3,6,⋯. In other words, p(n)00= 0, if n is not divisible by 3. Such a state is
called a periodic state with period d(0)=3.

99
 Periodic/aperiodic

A class is said to be periodic if its states are periodic. Similarly, a class is said to be
aperiodic if its states are aperiodic. Finally, a Markov chain is said to be aperiodic if
all of its states are aperiodic.
If i↔j, then d(i)=d(j).

100
 Example 2
Consider the Markov chain

Is Class 1={state 1,state 2} aperiodic?

Is Class 2={state 3,state 4} aperiodic?

Is Class 4={state 6,state 7,state 8}

aperiodic?

Solution

101
 Irrudicible/Irréductible

A Markov chain is said to be irreducible if all states communicate with

each other.
Une chaîne de Markov est dite irréductible si elle ne posséde qu’une
seule classe, c’est `a dire si tous les états communiquent entre eux
102
103
gcd : greatest common divisor
104
 Ex 2
On considère la matrice Q de taille 7 × 7 suivante :

105
Ex4

106
Temps d’atteinte, récurrence et transience

107
 Absorbing Markov Chains
Not all Markov chains are regular. In fact, some of the most important life science
applications of Markov chains do not involve transition matrices that are regular. One
type of Markov chain that is widely used in the life sciences is called an absorbing
Markov chain.

When we use the ideas of Markov chains to model living organisms, a common state
is death. Once the organism enters that state, it is not possible to leave. In this
situation, the organism has entered an absorbing state.

For example, suppose a Markov chain has transition matrix

The matrix shows that, P12 ,the probability of

going from state 1 to state 2, is 0.6, and that,
P22 ,the probability of staying in state 2, is 1.

Thus, once state 2 is entered, it is impossible to

leave. For this reason, state 2 is called an
absorbing state.

108
The resulting transition diagram shows that it is not possible to leave
state 2.

Generalizing from this example leads to the following definition

109
Absorbing Markov Chains
Identify all absorbing states in the Markov chains having the following matrices.
Decide whether the Markov chain is absorbing

110
Solution

a) Since P11 = 1, and P33 =1 both state 1 and state 3 are absorbing states. (Once
these states are reached, they cannot be left.) The only non-absorbing state is state
2.

There is a 0.3 probability of going from state 2 to the absorbing state 1, and a 0.2
probability of going from state 2 to state 3, so that it is possible to go from the
nonabsorbing state to an absorbing state. This Markov chain is absorbing. The
transition diagram is shown in Figure.

111
b) States 2 and 4 are absorbing, with states 1 and 3 non-absorbing.
From state 1, it is possible to go only to states 1 or 3; from state 3 it is possible to go
only to states 1 or 3.

As the transition diagram in Figure below shows, neither non-absorbing state leads to
an absorbing state, so that this Markov chain is nonabsorbing.

112
Example 2:

A man walks along a three block portion of Main St. His house is at one end
of the three block section. A bar is at the other end of the three block section.
Each time he reaches a corner he randomly either goes forward one block or
turns around and goes back one block. If he reaches home or the bar, he stays
there. The four states are Home (H), Corner 1(C1), Corner 2 (C2) and Bar
(B). Write the transition matrix and identify the absorbing states. Find the
probabilities of ending up in each absorbing state depending on the initial
state.

Solution

The transition matrix is written:

Home and the Bar are absorbing states. If the man arrives home, he does not leave. If
the man arrives at the bar, he does not leave. Since it is possible to reach home or the
bar from each of the other two corners on his walk, this is an absorbing Markov
chain. 113
We can raise the transition matrix T to a high power, n. One we find a
power Tn that remains stable, it will tell us the probability of ending up
in each absorbing state depending on the initial state.

T91 = T90; the matrix does not change as we continue to examine higher powers. We
see that in the long-run, the Markov chain must end up in an absorbing state. In the
long run, the man must eventually end up at either his home or the bar.

The second row tells us that if the man is at corner C1, then there is a 2/3 chance he
will end up at home and a 1/3 chance he will end up at the bar.

The third row tells us that if the man is at corner C2, then there is a 1/3 chance he will
end up at home and a 2/3 chance he will end up at the bar. Once he reaches home or
the bar, he never leaves that absorbing state.
114
Note that while the matrix Tn for sufficiently large n has become stable
and is not changing, it does not represent an equilibrium matrix. The
rows are not all identical, as we found in the regular Markov chains that
reached an equilibrium.
We can write a smaller “solution matrix” by retaining only rows that
relate to the non-absorbing states and retaining only the columns that
relate to the absorbing states.

Then the solution matrix will have rows C1 and C2, and columns H and
B. The solution matrix is

The first row of the solution matrix shows that if the man is at corner C1, then there is
a 2/3 chance he will end up at home and a 1/3 chance he will end up at the bar.

The second row of the solution matrix shows that if the man is at corner C2, then there
is a 1/3 chance he will end up at home and a 2/3 chance he will end up at the bar. 115
Example 3:
A gambler has $3,000, and she decides to gamble $1,000 at a time at a Black Jack
table in a casino in Las Vegas. She has told herself that she will continue playing until
she goes broke or has $5,000. Her probability of winning at Black Jack is .40. Write
the transition matrix, identify the absorbing states, find the solution matrix, and
determine the probability that the gambler will be financially ruined at a stage when
she has $2,000.
Solution
The transition matrix is written below. Clearly the state 0 and state 5K are the
absorbing states. This makes sense because as soon as the gambler reaches 0, she is
financially ruined and the game is over. Similarly, if the gambler reaches $5,000, she
has promised herself to quit and, again, the game is over. The reader should note that
p00 = 1, and p55 = 1.

Further observe that since the gambler bets only $1,000 at a time, she can raise or
lower her money only by $1,000 at a time. In other words, if she has $2,000 now,
after the next bet she can have $3,000 with a probability of .40 and $1,000 with a
probability of .60.

116
To determine the long term trend, we raise the matrix to higher powers until all the
non-absorbing states are absorbed. This is the called the solution matrix.

The solution matrix is often written in the following form, where the non-absorbing
states are written as rows on the side, and the absorbing states as columns on the top.
117
The table lists the probabilities of getting absorbed in state 0 or state 5K
starting from any of the four non-absorbing states. For example, if at
any instance the gambler has $3,000, then her probability of financial
ruin is 135/211 and her probability reaching 5K is 76/211.

118
Canonical Form

Consider an arbitrary absorbing Markov chain. Renumber the states so

that the transient states come first. If there are r absorbing states and t
transient states, the transition matrix will have the following canonical
form

Here I is an r -by- r identity matrix, 0 is an r -by- t zero matrix, R

is a nonzero t-by- r matrix, and Q is an t -by- t matrix.
The first t states are transient and the last r states are absorbing
119
 Let P be the transition matrix for an absorbing Markov chain.
Rearrange the rows and columns of P so that the absorbing states come first.
Matrix P will have the form:

where Im is an identity matrix, with m equal to the number of absorbing states, and O
is a matrix of all zeros.

 The element in row i, column j of the fundamental matrix gives the number of
visits to state j that are expected to occur before absorption, given that the
current state is state i.
 The product FR gives the matrix of probabilities that a particular initial
nonabsorbing state will lead to a particular absorbing state. 120
Example :
A gambler has $3,000, and she decides to gamble $1,000 at a time at a Black Jack
table in a casino in Las Vegas. She has told herself that she will continue playing until
she goes broke or has $5,000. Her probability of winning at Black Jack is .40. Write
the transition matrix, identify the absorbing states, find the solution matrix, and
determine the probability that the gambler will be financially ruined at a stage when
she has $2,000.

Solution
The canonical form is listed below:
The canonical form divides the
transition matrix into four sub-
matrices as listed below.

121
The matrix F=(In−B)−1 is called the fundamental matrix for the absorbing Markov
chain, where In is an identity matrix of the same size as B. The i, j-th entry of this
matrix tells us the average number of times the process is in the non-absorbing state j
before absorption if it started in the non-absorbing state i.

The matrix F=(In−B)−1 for our problem is listed below.

According to the matrix, the entry 1.78 in the row 3, column 2 position says that the
gambler will play the game 1.78 times before she goes from $3K to $2K. The entry
2.25 in row 3, column 3 says that if the gambler now has $3K, she will have $3K on
the average 2.25 times before the game is over.

We now address the question of how many bets will she have to make before she is
absorbed, if the gambler begins with $3K?

122
If we add the number of games the gambler plays in each non-absorbing state, we get
the average number of games before absorption from that state. Therefore, if the
gambler starts with $3K, the average number of Black Jack games she will play before
absorption is
1.07+1.78+2.25+0.90=6.0

That is, we expect the gambler will either have $5,000 or nothing on the 7th bet.

Lastly, we find the solution matrix without raising the transition matrix to higher
powers. The matrix FA gives us the solution matrix.

which is the same as the following matrix we obtained by raising the transition matrix
to higher powers.

123
Exercises

1) At a professional school, students need to take and pass an English writing/speech

class in order to get their professional degree. Students must take the class during the
first quarter that they enroll. If they do not pass the class they take it again in the
second semester. If they fail twice, they are not permitted to retake it again, and so
would be unable to earn their degree.

Students can be in one of 4 states: passed the class (P), enrolled in the class for the
first time (C), retaking the class (R) or failed twice and can not retake (F). Experience
shows 70% of students taking the class for the first time pass and 80% of students
taking the class for the second time pass.

Write the transition matrix and identify the absorbing states. Find the probability of
being absorbed eventually in each of the absorbing states.

124
125
2)

126
Probability of Absorption
In an absorbing Markov chain, the probability that the process will be
absorbed is 1 (i.e., Qn →0 as n→∞).

The Fundamental Matrix

For an absorbing Markov chain the matrix I - Q has an inverse N and N =
I+Q+Q2+⋯

The ij-entry nij of the matrix N is the expected number of times the chain is
in state sj , given that it starts in state si.
The initial state is counted if I = j.
For an absorbing Markov chain P , the matrix
N = (I−Q)−1
is called the fundamental matrix for P.

The entry nij of N gives the expected number of times that the process is in
the transient state sj if it is started in the transient state si
127
Time to Absorption

Let ti be the expected number of steps before the chain is absorbed,

given that the chain starts in state si, and let t be the column vector
whose ith entry is ti. Then,

t = Nc
where c is a column vector all of whose entries are 1.

Absorption Probabilities
Let bij be the probability that an absorbing chain will be absorbed in the
absorbing state sj if it starts in the transient state si.
Let B be the matrix with entries bij.

Then B is an t -by- r matrix, and

B=NR

where N is the fundamental matrix and R is as in the canonical form. 128

129
130
131
132
133
134
 Hidden Markov Model
M M M M
S1 S2 SL-1 SL

T T T T
x1 x2 XL-1 xL

L
A Markov chain (s1,…,sL): p( s1 , , sL )   p( si | si 1 )
i 1
and for each state s and a symbol x we have p(Xi=x|Si=s)

Application in communication: message sent is (s1,…,sm) but we

receive (x1,…,xm) . Compute what is the most likely message sent ?
Application in speech recognition: word said is (s1,…,sm) but we
recorded (x1,…,xm) . Compute what is the most likely word said ?

135
 Hidden Markov Model
M M M M
S1 S2 SL-1 SL

T T T T
x1 x2 XL-1 xL

Notations:
Markov Chain transition probabilities: p(Si+1= t|Si = s) = ast
Emission probabilities: p(Xi = b| Si = s) = es(b)
L
For Markov Chains we know: p( s)  p( s1 , , sL )   p( si | si 1 )
i 1

What is p(s,x) = p(s1,…,sL;x1,…,xL) ?

136
 Hidden Markov Model
M M M M
S1 S2 SL-1 SL

T T T T
x1 x2 XL-1 xL

p(Xi = b| Si = s) = es(b), means that the probability of xi

depends only on the probability of si.
Formally, this is equivalent to the conditional
independence assumption:
p(Xi=xi|x1,..,xi-1,xi+1,..,xL,s1,..,si,..,sL) = esi(xi)
L

Thus p( s, x)  p( s1 , , sL ; x1 ,..., xL )   p( si | si 1 ) esi ( xi )

i 1

137