Stochastic Modeling

__Markov Chains__

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

"The next
state X_{n+1} of the process is independent
of the past states X_{0},….., X_{n-1 provided that the present state }X_{n}_{ is known" }

_{ }

P{ X_{n+1} = j\ X_{0},….., X_{n}} = P { X_{n+1} = j\ X_{n}}

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{ X_{n+m}_{ }= j\ X_{n} = i} =
P^{m}(i,j)

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

P^{m+n}(i,j) = SP^{m}(i,k) P^{n}(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 m^{th} 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