Stochastic Modeling

 

Markov Chains

 

Definition: A Markov chain is a sequence of random variables such that for any n Î N = {0, 1, …}, Xn+1 is conditionally independent of X0,….., Xn-1 given Xn

 

"The next state Xn+1 of the process is independent of the past states X0,….., Xn-1 provided that the present state Xn is known"

 

P{ Xn+1 = j\ X0,….., Xn} = P { Xn+1 = j\ Xn}

 

Each state is represented by a circle with arrows going from and to the circle representing the probabilities that the process will move from one state to the other.

P7
 
 


The above diagram is called the "Transition Graph" of the Markov chain.

 

 

 

 

 

 

 

 

 

 

From the transition graph a transition matrix is produced

 

 

P(i,j) = Transition matrix or Markov matrix "P"

 

Provided that

 

1)   P(i,j) ³ 0

2)   SP(i,j) = 1

"Row summation" = 1

 

 

 


          P1     P2     0       0

P  =   P3     P4     P5     0

          0       P6     P7     P8

          0       0       P9     0

 

 

 


The transition matrix depends on the transition graph representation of the real biological system

 

The probabilities of the transition graph represent the initial probabilities of moving the processes from one state to the other in one step (movement).

 

Classification of states

 

1)   State j is called recurrent if

 

Pj { T < ∞ } = 1

 

T = time of first visit to state j

 

2)   Sate j is called transient if

 

Pj { T = + ∞ } > 0

 

For any m Î N,

 

P{ Xn+m = j\ Xn = i} = Pm(i,j)

 

The probability that the process moves from state i to state j in m steps is the (i,j) entry of the mth power of the transition matrix P

 

Pm+n(i,j) = SPm(i,k) Pn(k.j)

 

"Chapman-Kolmogorov" equation

 

 

It states that starting at state i, in order for the process X to be in state j after m+n steps, it must be in some intermediate state k after the mth step and then move from state k into state j during the remaining n steps

 

 

 

 

 

 

Computation of the two matrices R(i,j) and F(i,j)

 

 

R(i,j) is the expected number of visits starting from state i to state j

 

F(i,j) is the probability of ever reaching state j starting from state i

 

 

If j is a recurrent state, then

 

R(i,j) = + ∞

 

and

 

F(i,j) = 1

 

If j can be reached from i, then

 

F(i,j) > 0

 

and

 

R(i,j) = ∞

 

If j can not be reached from i, then

 

F(i,j) = 0

 

and

 

R(i,j) = 0

 

 

 

 

If j is transient and i recurrent, then j can not be reached from i and

 

F(i,j) = 0

 

and

 

R(i,j) = 0

 

 

If both states are transient, then

 

Let Q and S be the matrices obtained from P and R respectively by deleting all the rows and columns corresponding to the recurrent states

 

S = (I – Q)-1

 

I = identity matrix of the same number of rows and columns as matrix Q

 

Example

 

 


        0.4           0.6              0

Q=   0             0                 0.2

        0.6           0                 0

 

 

 

 

 

 

 

 

 


S = (I – Q)-1

 

 

 


              125             75               15

 = 1/66   15              75               15

              75               45               75

 

 

 


Therefore, when both i and j are transient

 

R(i,j) = S(i,j)

 

To compute F(i,j)

 

If i and j are both recurrent then F(i,j) = 1

 

If i is recurrent and j transient

 

F(i,j) = 0

 

If both i and j are transient then

 

F(j,j) = 1 – (1/R(j,j))

 

F(i,j) =  R(i,j) / R(j,j)

 

If i is transient and j recurrent then

 

F(i,j) = 1