EEL6507sp09L06

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 06, Wednesday 2008/01/21 (Notes created by Kyungyong Lee)

Basic Definitions for Markov Chain

  • Transient state: fj < 1, where f_j=\sum_{n=1}^{\infty} f_j\ ^{(n)} = P[ever\ returning\ to\ E_j]
  • Recurrent state: fj = 1
    • Recurrent null: M_j=\infty, where M_j=\sum_{n=1}^{\infty} nf_j\ ^{(n)} = Average time to return to Ej
    • Recurrent non-null: M_j<\infty
  • Period: GCD of set {n: P_{jj}\ ^{(n)}>0}
    • To be periodic, the period value should be bigger than 1.(Remember that if period value is 1, it is said to be aperiodic.)
  • Ergodic state: A state Ej is said to be ergodic if it is aperiodic, and recurrent non-null.
    • Ergodic markov chain: Every state is ergodic.

Basic Theorems for Markov Chain

  • Theorem 1: The states of an irreducible Markov chain are either all transient or all recurrent nonnull or all recurrent null. If periodic, then all states have the same period value.
  • Theorem 2: In an irreducible and aperiodic homogeneous(not time dependent) Markov chain, the limiting probabilities \pi_j = \lim_{n \to \infin} \pi_j^{(n)} always exists and are independent of the initial state probability distribution.
    • (a) πj = 0 if all states are transient or recurrent null.
    • (b) \pi_j=\frac{1}{M_j}, if all states are recurrent non null.

Getting Transient State Probabilities

Define \vec \pi(z) = \sum_{n=0}^{\infty}\vec \pi^{(n)}z^n = \vec \pi^{(0)}+\sum_{n=1}^{\infty}\vec \pi^{(n)}z^n = \vec \pi^{(0)}+z[\sum_{n=0}^{\infty}\vec \pi^{(n+1)}z^n] = \vec \pi^{(0)}+z[\sum_{n=0}^{\infty}\vec \pi^{(n)}Pz^n] = \vec \pi^{(0)}+z[\sum_{n=0}^{\infty}\vec \pi^{(n)}z^n]P = \vec \pi^{(0)}+z\vec \pi(z)P

Hence, \vec \pi(z)(I-zP) = \vec \pi^{(0)}

So, \vec \pi(z) = \vec \pi^{(0)}(I-zP)^{-1}

We know that \vec \pi^{(n)} = \vec \pi^{(0)}P^n, and \vec \pi(z) = \sum_{n=0}^{\infty}\vec \pi^{(n)}z^n = \vec \pi^{(0)}\sum_{n=0}^{\infty}P^nz^n

Finally, we can derive \sum_{n=0}^\infty P^nz^n = (I-zP)^{-1}

Retrieved from "http://boykin.acis.ufl.edu/wiki/index.php/EEL6507sp09L06"