EEL6507sp09L05

From BoykinWiki

Jump to: navigation, search

Contents

EEL 6507 Spring 2009, Lecture 05, Friday 2009/01/16 (Created by Adam Flynn)

Basic Definitions for Markov Chains

The probability of a state transitioning to another in a certain number of steps is given as:

p_{ij}\ ^{(m)}\ =\ P[going\ from\ state\ i\ to\ state\ j\ in\ m\ steps]

From this, we define the following terms:

  • Irreducible: A markov chain is irreducible if for each pair of states (i,j) there is some number of steps mo such that:
p_{ij}\ ^{(m_o)}>0
  • Closed subset: A1 is a closed subset of A if p_{ij}\ ^{(m)}=0 for all m, all i \in A_1, and j \in A_1^c.
    • Example: Roach motel commercial where roaches can check in but not out
  • Absorbing state: A single state, i, such that pii = 1

Basic Theorems for Markov Chains

  • If A is closed but no proper subset is closed, then A is irreducible.
    • Proof: Assume that A is reducible in the case above and prove through contradiction.
      • By definition, a reducible Markov chain contains closed proper sets [1]. This contradicts the second requirement for the theorem.
  • Recurrence
    • Due to the Markov property, we can define: f_j\ ^{(n)}=P[first\ return\ to\ j\ is\ in\ n\ steps]
    • Return probability: f_j=\sum_{n=1}^{\infty} f_j\ ^{(n)}
    • Mean recurrence time: M_j=\sum_{n=1}^{\infty} nf_j\ ^{(n)}

References

  • [1] Leonard Kleinrock, Queueing Systems: Volume I – Theory (Wiley Interscience, New York, 1975), page 28.

Lecture Recording

lecture_recording

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