Contents
1 Introduction to Markov Chains 3
1.1 Why Markov Chains? . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Characteristics of Discrete-time Markov Chains . . . . . . . . . . 3
1.2.1 Discrete-time . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Countable State Space . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.4 Time-homogeneity . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Transition Diagram and Matrix . . . . . . . . . . . . . . . . . . . 3
1.3.1 Transition Diagram . . . . . . . . . . . . . . . . . . . . . 3
1.3.2 Transition Matrix . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Formulating a DTMC . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Examples and Remarks 4
2.1 Gambling or Random Walk . . . . . . . . . . . . . . . . . . . . . 4
2.2 Sanity Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Conclusion 5
4 Transient Distribution 6
4.1 Probability to Visit a Sequence of States . . . . . . . . . . . . . . 6
4.2 n-step Transition Probabilities . . . . . . . . . . . . . . . . . . . 6
4.3 Transient Distribution at Time n . . . . . . . . . . . . . . . . . . 6
5 Hitting Times 7
5.1 Hitting Times and Probabilities . . . . . . . . . . . . . . . . . . . 7
5.2 Expectation of Hitting Times . . . . . . . . . . . . . . . . . . . . 7
5.3 Conditioning on the First Step . . . . . . . . . . . . . . . . . . . 7
5.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Communicating Classes in Markov Chains 8
6.1 Definition and Properties . . . . . . . . . . . . . . . . . . . . . . 8
6.1.1 Definition (Communicating States): . . . . . . . . . 8
6.1.2 Definition (Absorbing Class): . . . . . . . . . . . . . . . . 8
6.1.3 Definition (Periodicity): . . . . . . . . . . . . . . . . . . . 8
6.1.4 Definition (Irreducibility): . . . . . . . . . . . . . . . . . . 8
7 Long-term Behavior of DTMCs 9
7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Practical Importance . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2.1 π occ : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2.2 π lim : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1
, 7.3 Finding π occ and π lim . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4 Existence π lim , π occ . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.5 Strategy for Multiclass . . . . . . . . . . . . . . . . . . . . . . . . 10
8 Costs in DTMCs 11
8.1 Long-run Average Costs . . . . . . . . . . . . . . . . . . . . . . . 11
8.2 Expected Costs in Equilibrium . . . . . . . . . . . . . . . . . . . 11
9 Exponential Distribution 12
9.1 Memorylessness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.2 Total Probability Law . . . . . . . . . . . . . . . . . . . . . . . . 13
9.3 Competing Exponentials . . . . . . . . . . . . . . . . . . . . . . . 13
10 The Poisson Process 14
10.1 Context: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.2 Definition 1 (Exponential inter-arrivals): . . . . . . . . . . . . . . 14
10.3 Definition 2 (Poisson increments): . . . . . . . . . . . . . . . . . . 14
10.4 Remark on Poisson process vs. Poisson distribution: . . . . . . . 15
10.5 Properties: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.6 Interconnection of Poisson Process Properties: . . . . . . . . . . . 15
11 Merging & Splitting for Poisson Random Variables 16
11.1 Definition of Poisson Random Variable . . . . . . . . . . . . . . . 16
11.2 Merging of Poisson Random Variables . . . . . . . . . . . . . . . 16
11.3 Splitting / Thinning of Poisson Random Variables . . . . . . . . 16
11.4 Merging & Splitting for Poisson Processes . . . . . . . . . . . . . 16
11.4.1 Merging of Poisson Processes . . . . . . . . . . . . . . . . 16
11.4.2 Splitting / Thinning of Poisson Processes . . . . . . . . . 17
2
, 1 Introduction to Markov Chains
1.1 Why Markov Chains?
• Markov Chains are tractable: analysis is feasible with many standard
procedures.
• They can predict time-average behavior, such as average costs per day or
the fraction of lost customers.
• Many real-world scenarios can be modeled using Markov Chains.
1.2 Characteristics of Discrete-time Markov Chains
1.2.1 Discrete-time
A DTMC is a sequence of random variables {X0 , X1 , X2 , . . .} where the index
n represents discrete time units.
1.2.2 Countable State Space
All possible values of Xn for n = 0, 1, 2, . . . are in a countable set S, termed the
state space.
1.2.3 Markov Chains
A sequence of random variables is a Markov Chain if it possesses the Markov
property: the next state depends only on the present state, not on any prior
history.
1.2.4 Time-homogeneity
A DTMC is time-homogeneous if its transition probabilities remain constant
over time.
1.3 Transition Diagram and Matrix
1.3.1 Transition Diagram
The transition diagram is a graphical representation of a DTMC. It provides a
visual overview of the system’s dynamics, making it easier to understand and
analyze.
• States: Each state in the state space S is represented as a node or circle
in the diagram.
• Transitions: Arrows between states represent possible transitions. The
direction of the arrow indicates the direction of the transition.
3
1 Introduction to Markov Chains 3
1.1 Why Markov Chains? . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Characteristics of Discrete-time Markov Chains . . . . . . . . . . 3
1.2.1 Discrete-time . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Countable State Space . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.4 Time-homogeneity . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Transition Diagram and Matrix . . . . . . . . . . . . . . . . . . . 3
1.3.1 Transition Diagram . . . . . . . . . . . . . . . . . . . . . 3
1.3.2 Transition Matrix . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Formulating a DTMC . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Examples and Remarks 4
2.1 Gambling or Random Walk . . . . . . . . . . . . . . . . . . . . . 4
2.2 Sanity Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Conclusion 5
4 Transient Distribution 6
4.1 Probability to Visit a Sequence of States . . . . . . . . . . . . . . 6
4.2 n-step Transition Probabilities . . . . . . . . . . . . . . . . . . . 6
4.3 Transient Distribution at Time n . . . . . . . . . . . . . . . . . . 6
5 Hitting Times 7
5.1 Hitting Times and Probabilities . . . . . . . . . . . . . . . . . . . 7
5.2 Expectation of Hitting Times . . . . . . . . . . . . . . . . . . . . 7
5.3 Conditioning on the First Step . . . . . . . . . . . . . . . . . . . 7
5.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Communicating Classes in Markov Chains 8
6.1 Definition and Properties . . . . . . . . . . . . . . . . . . . . . . 8
6.1.1 Definition (Communicating States): . . . . . . . . . 8
6.1.2 Definition (Absorbing Class): . . . . . . . . . . . . . . . . 8
6.1.3 Definition (Periodicity): . . . . . . . . . . . . . . . . . . . 8
6.1.4 Definition (Irreducibility): . . . . . . . . . . . . . . . . . . 8
7 Long-term Behavior of DTMCs 9
7.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Practical Importance . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2.1 π occ : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2.2 π lim : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1
, 7.3 Finding π occ and π lim . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4 Existence π lim , π occ . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.5 Strategy for Multiclass . . . . . . . . . . . . . . . . . . . . . . . . 10
8 Costs in DTMCs 11
8.1 Long-run Average Costs . . . . . . . . . . . . . . . . . . . . . . . 11
8.2 Expected Costs in Equilibrium . . . . . . . . . . . . . . . . . . . 11
9 Exponential Distribution 12
9.1 Memorylessness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.2 Total Probability Law . . . . . . . . . . . . . . . . . . . . . . . . 13
9.3 Competing Exponentials . . . . . . . . . . . . . . . . . . . . . . . 13
10 The Poisson Process 14
10.1 Context: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
10.2 Definition 1 (Exponential inter-arrivals): . . . . . . . . . . . . . . 14
10.3 Definition 2 (Poisson increments): . . . . . . . . . . . . . . . . . . 14
10.4 Remark on Poisson process vs. Poisson distribution: . . . . . . . 15
10.5 Properties: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.6 Interconnection of Poisson Process Properties: . . . . . . . . . . . 15
11 Merging & Splitting for Poisson Random Variables 16
11.1 Definition of Poisson Random Variable . . . . . . . . . . . . . . . 16
11.2 Merging of Poisson Random Variables . . . . . . . . . . . . . . . 16
11.3 Splitting / Thinning of Poisson Random Variables . . . . . . . . 16
11.4 Merging & Splitting for Poisson Processes . . . . . . . . . . . . . 16
11.4.1 Merging of Poisson Processes . . . . . . . . . . . . . . . . 16
11.4.2 Splitting / Thinning of Poisson Processes . . . . . . . . . 17
2
, 1 Introduction to Markov Chains
1.1 Why Markov Chains?
• Markov Chains are tractable: analysis is feasible with many standard
procedures.
• They can predict time-average behavior, such as average costs per day or
the fraction of lost customers.
• Many real-world scenarios can be modeled using Markov Chains.
1.2 Characteristics of Discrete-time Markov Chains
1.2.1 Discrete-time
A DTMC is a sequence of random variables {X0 , X1 , X2 , . . .} where the index
n represents discrete time units.
1.2.2 Countable State Space
All possible values of Xn for n = 0, 1, 2, . . . are in a countable set S, termed the
state space.
1.2.3 Markov Chains
A sequence of random variables is a Markov Chain if it possesses the Markov
property: the next state depends only on the present state, not on any prior
history.
1.2.4 Time-homogeneity
A DTMC is time-homogeneous if its transition probabilities remain constant
over time.
1.3 Transition Diagram and Matrix
1.3.1 Transition Diagram
The transition diagram is a graphical representation of a DTMC. It provides a
visual overview of the system’s dynamics, making it easier to understand and
analyze.
• States: Each state in the state space S is represented as a node or circle
in the diagram.
• Transitions: Arrows between states represent possible transitions. The
direction of the arrow indicates the direction of the transition.
3
