Prerequisites & Notation

Prerequisites

This chapter introduces discrete-time Markov chains (DTMCs), building on your knowledge of conditional probability, discrete random variables, and basic linear algebra. The Markov property reduces the complexity of multi-step dependence to a single-step transition; the resulting theory is both elegant and computationally tractable.

Conditional probability and Bayes' theorem(Review fsp/ch02)
Self-check: Can you compute $\mathbb{P}(A \mid B)$ and apply the law of total probability?
Discrete random variables, PMFs, and expectation(Review fsp/ch05)
Self-check: Can you compute $\mathbb{E}[X]$ for a discrete random variable with a given PMF?
Matrix multiplication, eigenvalues, and left eigenvectors
Self-check: Can you multiply two $3 \times 3$ matrices and find eigenvectors of a given matrix?
Geometric series and convergence
Self-check: Do you know when $\sum_{n=0}^{\infty} r^n$ converges and what it equals?

Chapter Notation

We introduce notation specific to discrete-time Markov chains. The state space is always countable and denoted $\mathcal{S}$ .

Symbol	Meaning	Introduced
$\mathbf{P}$	Transition matrix with entries $p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i)$	s01
$\mathbf{P}^{n}$	$n$ -step transition matrix with entries $p_{ij}^{(n)}$	s01
$\boldsymbol{\pi}$	Stationary (invariant) distribution: row vector satisfying $\boldsymbol{\pi} = \boldsymbol{\pi}\mathbf{P}$	s03
$\mathcal{S}$	State space (countable set)	s01
$i \leftrightarrow j$	States $i$ and $j$ communicate	s02
$i \to j$	State $j$ is accessible from state $i$	s02
$d(i)$	Period of state $i$	s02
$f_{ii}$	Return probability: $\mathbb{P}(\text{ever return to } i \mid X_0 = i)$	s02
$\mathbf{1}$	Column vector of all ones	s01

← Ch 16 Definition and Transition Probabilities