Introduction to Markov Chains

Part A: Introduction to Markov Chains
Markov Chains are a useful matrix-based technique that is widely used in modern
probability theory. Here’s the basic idea: Suppose the components of a system can exist
in number of physical states {s1,....,sn} The components of the system will begin in one
of these states, and then successively move from one state to the next with a certain
probability. Each move (or "transition") is called a step. Suppose a component is
currently in state si, and then it moves to state sj at the next step with a probability
denoted by pij. If this probability depends only on the current state, and not on any
previous state of the system, then pij is referred to as a transition probability, and the
succession of discrete states of the system as it evolves over time is known as a Markov
chain.
Transition probabilities can be used to construct a Markov matrix. A Markov matrix has
two key properties: every entry of the matrix of non-negative (such a matrix is said to be
"regular"); and every column of the matrix adds to 1.
Consider the following definitions and theorems relevant to the theory of Markov Chains,
and then answer the questions that follow:

1. A warehouse inventory manager ensures that produce is labelled in one of three
ways: overstocked, stocked or understocked. A week after produce is labelled as
overstocked, there is a 40% chance it will remain labelled overstocked, a 40%
chance it will be labelled stocked and a 20% chance it will become understocked.
If produce is labelled as stocked one week, there is a 20% that it will become
overstocked, a 70% it will maintain its label and a 10% chance it will become
understocked the following week. Finally, if produce is labelled as understocked,
then one week later there is a 70% chance it will become overstocked, a 20% it
will be labelled stocked and a 10% chance it will remain understocked.
a) Complete the following transition matrix, P, for the warehouse system, using
Definition 1. Is this transition matrix regular?
P=
[ p11 0.2 p13
p21 0.7 p23
p31 0.1 p33 ]

From the given data, we derive the following:
p11 = 0.1 , p21 = 0.2 , p31 = 0.7 , p12 = 0.2 , p22 = 0.7 , p32 = 0.1 , p13 = 0.2 ,
p23 = 0.7, and p33 = 0.2
Therefore the transition matrix, P becomes:
P=
[ p11 p12 p13
p21 p22 p23
p31 p32 p33 ] = [0.1 0.2 0.7
0.2 0.7 0.1
0.7 0.1 0.2 ]
Transition Matrix, P = [0.1 0.2 0.7
0.2 0.7 0.1
0.7 0.1 0.2 ]
b) If at some initial state, all warehouse produce is labelled stocked, i.e., calculate
the week-by-week succession of system states using matrix multiplication (see
Theorem 1) the system state vector appears to have reached a steady state (to 3
decimal places). How many weeks does it take for the system to reach this
apparent steady state?
x(0)=
[ 0
1
0 ]
[0.2
0.7
0.1 ] [a
b
c ] = [ 0
1
0 ]
Gaussian Elimination method,
[0.2
0.7
0.1
⌊
0
1
0
¿ ¿
R2/ 0.2 → R1
[ 1
0.7
0.1
⌊
0
1
0
¿ ¿
R2 – 0.7 R1 → R2
[ 1
0
0
⌊
0
1
0
¿ ¿
The systems take approximately 1 week to reach steady state

2. Let’s confirm that the apparent steady state of the system calculated in Question
1(b) through observing a succession of system states, does indeed reflect the long-
term behavior of the system.
a) For the transition matrix, P, that you created in Question 1(a), use Theorem 2 to
determine the one-dimensional subspace containing the steady-state vector q for
the system.
Pq=q
Transition matrix, P = [0.1 0.2 0.7
0.2 0.7 0.1
0.7 0.1 0.2 ]
Steady state = [ 0
1
0 ]
[ 0.1 0.2 0.7
0.2 0.7 0.1
0.7 0.1 0.2| 0
1
0 ]
1
0.4 R1 → R1
[ 1 0.5 0.5
0.2 0.7 0.1
0.7 0.1 0.2|0
1
0 ]
R2 - 0.2 R1 → R2
[ 1 0.5 0.5
0 0.6 0
0 −0.25 −0.15|
0
1
0 ]
R2/0.6 → R2
[ 1 0.5 0.5
0 1 0
0 −0.25 −0.15| 0
5
3
0 ]
R1 - 0.5R2 → R1
[ 1 0 0.5
0 1 0
0 0 −0.15|
−5
6
5
3
5
12 ]