29: Discrete-Time Markov Chains

"The ultimate Markov observation: Today is the first day of the rest of your life." - quoted in Lester Lipsky's 'Queueing theory - a Linear Algebraic Approach'."To one who is accustomed to thinking a lot, every new thought that he hears or reads about immediately appears as a link in a chain" - NietzscheLecture outline: How to model computer systems/ networks using Markov Models

1. Discrete-time Markov Chain (DTMC): an example

Modeling Lahore’s weather as a DTMC

State probabilities of a DTMC

Time evolution of a DTMC

Transient analysis of a DTMC

Steady-state analysis of a DTMC

2. State properties of a DTMC

Main state properties of DTMCs:

Recurrent states; transient states; periodic states;

Ergodic states; absorbing states; communicating states class;

Main chain properties of a DTMC:

Irreducible chain; homogeneous chain; ergodic chain

Ergodic DTMCs: irreducible, homogeneous, aperiodic, recurrent non-null DTMCs

3. Solution of a DTMC

Solving a DTMC through balanced equations

DTMC example: finite states

DTMC example: countably infinite states

Primary reference for this lecture:

1. “Performance Modeling of Communication Networks with Markov Chains” by Jeonghoon Mo

2. “Performance analysis of the IEEE 802.11 distributed coordination function” by G. Bianchi published in IEEE Journal on Selected Areas in Communication (JSAC) [link].