View source

= 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:
<center><math>p_{ij}\ ^{(m)}\ =\ P[going\ from\ state\ i\ to\ state\ j\ in\ m\ steps]</math> </center>

From this, we define the following terms:

*'''Irreducible:''' A markov chain is irreducible if for each pair of states <math>(i,j)</math> there is some number of steps <math>m_o</math> such that:
<center><math>p_{ij}\ ^{(m_o)}>0</math></center>

*'''Closed subset:''' <math>A_1</math> is a closed subset of <math>A</math> if <math>p_{ij}\ ^{(m)}=0</math> for all <math>m,</math> all <math>i \in A_1,</math> and <math>j \in A_1^c.</math>
**Example: Roach motel commercial where roaches can check in but not out

*'''Absorbing state:''' A single state, <math>i</math>, such that <math>p_{ii}=1</math>

== Basic Theorems for Markov Chains ==
*If <math>A</math> is closed but no [http://mathworld.wolfram.com/ProperSubset.html proper subset] is closed, then <math>A</math> is irreducible.
**'''Proof:''' Assume that <math>A</math> 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: <math>f_j\ ^{(n)}=P[first\ return\ to\ j\ is\ in\ n\ steps]</math>
**Return probability: <math>f_j=\sum_{n=1}^{\infty} f_j\ ^{(n)}</math>
**Mean recurrence time: <math>M_j=\sum_{n=1}^{\infty} nf_j\ ^{(n)}</math>

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

== Lecture Recording ==
[http://www.filedropper.com/6507lecture5090116recording lecture_recording]