Transcript Document

Markov Processes
What is a Markov Process?
A stochastic process which contains the Markovian property.
A process has the Markovian property if:
P{ X t 1  j | X 0  k0 , X 1  k1 ,... X t 1  kt 1 , X t  i}  P{ X t 1  j | X t  i},
for t = 0,1,… and every sequence i,j, k0, k1,…kt-1.
In other words, any future state is only dependent on it’s prior
state.
Markov Processes cont.
This conditional probability
P{ X t 1  j | X t  i},
is called the one-step transition probability.
P{ X t 1  j | X t  i}  P{ X 1  j | X 0  i}
And if
for all t = 1,2,…
then the one-step transition probability is said to be stationary
and therefore referred to as the stationary transition
probability.
Markov Processes cont.
Let pij =
P=
P{ X t 1  j | X t  i},
state
0
1
2
3
0
p00
p10
p20
p30
1
p01
p11
p21
p31
2
3
p02 p03
p12 p13
p22 p23
p32 p33
P is referred to as the probability transition matrix.
Markov Processes cont.
Suppose the probability you win is based on if you won the
last time you played some game. Say, if you won last time,
then there is a 70% chance of winning the next time.
However, if you lost last time, there is a 60% chance you lose
the next time.
Can the process of winning and losing be modeled as a
Markov process?
Let state 0 be you win, and state 1 be you lose, then:
P=
state
0
1
0
1
.70 .30
.40 .60
Markov Processes cont.
See handout on n-step transition matrix.
Markov Processes cont.
Let,
Pn =
n 
state
0
1
2
3
Then P [p0
probabilities.
,
p1
0
1
p0
p0
p0
p0
,
p2
p1
p1
p1
p1
,
2 ... N
p2 … pN
p2 … pN
p2 … pN
p2 … pN
p3 …pN ] are the steady state
Markov Processes cont.
Observing that P(n)  P(n-1)P,
as
, P  PP.
n 
[p0 , p1 ,,p2 ,…pN ] = [p0 , p1 ,,p2 ,…pN ]
p00 p01 p02 … p0N
p10 p11 p12 … p1N
p20 p21 p22 … p2N
pN0 pN1 pN2 … p3N
The inner product of this matrix equation results in N+1 equations
and N+1 unknowns, however rank of the P matrix is N.
However, note that p0 + p1 + p2+ p3 …pN = 1. Therefore N+1
equations and N+1 unknowns.
Markov Processes cont.
Observing that P(n)  P(n-1)P,
as
, P  PP.
n 
[p0 , p1 ,,p2 ,…pN ] = [p0 , p1 ,,p2 ,…pN ]
p00 p01 p02 … p0N
p10 p11 p12 … p1N
p20 p21 p22 … p2N
pN0 pN1 pN2 … p3N
The inner product of this matrix equation results in N+1 equations
and N+1 unknowns, however rank of the P matrix is N.
However, note that p0 + p1 + p2+ p3 …pN = 1. Therefore N+1
equations and N+1 unknowns.
Markov Processes cont.
Show example of obtaining P  PP from transition matrix:
P=
state
0
1
0
1
.70 .30
.40 .60
Markov Processes cont.
Break for Exercise
Markov Processes cont.
State diagrams:
P=
state
0
1
0
1
.70 .30
.40 .60
0
1
Markov Processes cont.
State diagrams:
P=
state
0
1
2
3
0
.5
.5
.25
0
1
.5
.5
.25
0
2
3
0
0
0 0
.25 .25
0
1
0
1
2
3
Markov Processes cont.
Classification of States:
1. A state j is accessible from some state i if it is possible to
transition from i to j in a finite number of steps. i  j
2. State i and j communicate if j  i and i  j ,  i  j .
3. The communicating class of state i is the set C(i) where
C(i) ={j: i  j}
4. If the communicating class C(i) = f then i is a non-return
state.
5. A process is said to be irreducible if all states within the
process communicate.
Markov Processes cont.
6. A closed communicating class is such that there is no escape
from the class. Note: An ergodic process can have at most 1
closed communicating class.
7. If i is the only member of C(i) and no state j is accessible
from i, then i is an absorbing or capturing state, pii = 1.
8. A return state may be revisited infinitely often (recurrent) or
finitely often (non-recurrent or transient) in the long run.
Markov Processes cont.
First Passage Times:
1. The first passage time for a state i to j, Tij is the number of
transitions required to enter state j for the first time given
we start in state i.
2. The recurrence time from state i, Tii = number of
transitions to get back to state i.
3. The first passage probability, fij(n), is the probability that
the first passage time from state i to j is equal to n:
fij(n) = P[Tij = n]
fij(1) = pij
(1)
fij(2) = P[Xn+2 = j | Xn = i, Xn+1  j ] =  pik f kj
k j
Markov Processes cont.
First Passage Times:
4. The mean first passage time:
mij = E[Tij] =

 nf
n 1
(n)
ij
mij = mean recurrence time.
if mij =  then i is null recurrent
if mij <  then i is positive recurrent
5. Probability of absorption – probability of ever going from
state i to k.
M
let fii =  pij f jk for i = 0,1, 2 …M
j o
if fii = 1, then i is recurrent.
fii < 1, then i is transient
Markov Processes cont.
Expected Average Value(Cost) per Unit Time :
How does one find the long run average reward (cost) of a
Markov process?
Let V(Xt) be a function that represents the reward for being in
state X.
1 n
 M
Then lim E  V ( X t )   p jV ( X t )
n 
 n t 1
 j 0