Markov Chains and Queuing Basics

A discrete-time Markov chain is a sequence of random variables $\{X_n\}_{n \geq 0}$ taking values in a countable state space $\mathcal{S}$ and satisfying the Markov property: for all $n \geq 0$ and all states $i, j, i_{n-1}, \ldots, i_0 \in \mathcal{S}$,

$$P(X_{n+1} = j \mid X_n = i,\, X_{n-1} = i_{n-1},\, \ldots,\, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i).$$

In words: given the present state $X_n = i$, the conditional distribution of the future $X_{n+1}$ is independent of the past $X_0, X_1, \ldots, X_{n-1}$.

The chain is time-homogeneous if the transition probabilities do not depend on the time index $n$:

$$P(X_{n+1} = j \mid X_n = i) = p_{ij} \quad \text{for all } n.$$

Throughout this section, we consider only time-homogeneous chains unless stated otherwise.

For a time-homogeneous DTMC on a finite state space $\mathcal{S} = \{1, 2, \ldots, M\}$, the transition probability matrix is the $M \times M$ matrix $\mathbf{P}$ with entries

$$[\mathbf{P}]_{ij} = p_{ij} = P(X_{n+1} = j \mid X_n = i), \quad i, j \in \mathcal{S}.$$

The matrix $\mathbf{P}$ has two fundamental properties:

1. Non-negativity: $p_{ij} \geq 0$ for all $i, j$.
2. Row stochasticity: each row sums to one, $\displaystyle\sum_{j \in \mathcal{S}} p_{ij} = 1$ for all $i$.

A matrix satisfying both properties is called a (row) stochastic matrix.

The $n$-step transition probability $p_{ij}^{(n)} = P(X_{m+n} = j \mid X_m = i)$ is given by the $(i,j)$-entry of $\mathbf{P}^n$:

$$\mathbf{P}^{(n)} = \mathbf{P}^n.$$

Thus, the probability distribution of the chain after $n$ steps, starting from initial distribution $\boldsymbol{\pi}_0^T$, is

$$\boldsymbol{\pi}_n^T = \boldsymbol{\pi}_0^T \mathbf{P}^n.$$

For any non-negative integers $m$ and $n$, the $n$-step and $m$-step transition probabilities satisfy the Chapman--Kolmogorov equations:

$$p_{ij}^{(m+n)} = \sum_{k \in \mathcal{S}} p_{ik}^{(m)}\, p_{kj}^{(n)}.$$

In matrix form, this becomes

$$\mathbf{P}^{m+n} = \mathbf{P}^m \, \mathbf{P}^n.$$

The interpretation is intuitive: to go from state $i$ to state $j$ in $m + n$ steps, the chain must pass through some intermediate state $k$ after $m$ steps. Summing over all possible intermediate states $k$ gives the total probability.

This equation is the discrete-time analogue of the semigroup property of matrix exponentials in continuous-time systems.

Communication. State $j$ is accessible from state $i$ (written $i \to j$) if $p_{ij}^{(n)} > 0$ for some $n \geq 1$. States $i$ and $j$ communicate (written $i \leftrightarrow j$) if $i \to j$ and $j \to i$. Communication is an equivalence relation and partitions $\mathcal{S}$ into communicating classes.

Irreducibility. A Markov chain is irreducible if $\mathcal{S}$ consists of a single communicating class, i.e., every state is accessible from every other state. Equivalently, for every pair $(i, j)$ there exists $n \geq 1$ such that $p_{ij}^{(n)} > 0$.

Period. The period of state $i$ is

$$d(i) = \gcd\{n \geq 1 : p_{ii}^{(n)} > 0\}.$$

If $d(i) = 1$, the state is aperiodic; if $d(i) > 1$, the state is periodic with period $d(i)$.

Aperiodic chain. An irreducible chain is aperiodic if every state is aperiodic. Since all states in an irreducible chain share the same period, it suffices to check a single state.

A Markov chain that is both irreducible and aperiodic is sometimes called ergodic (in the Markov chain sense). For such chains, the long-run fraction of time spent in each state converges to a unique stationary distribution.

A probability vector $\boldsymbol{\pi} = [\pi_1, \pi_2, \ldots, \pi_M]^T$ is a stationary distribution (or steady-state distribution) of the Markov chain with transition matrix $\mathbf{P}$ if

$$\boldsymbol{\pi}^T \mathbf{P} = \boldsymbol{\pi}^T, \qquad \sum_{i=1}^{M} \pi_i = 1, \qquad \pi_i \geq 0 \;\;\forall\, i.$$

Component-wise, this reads

$$\pi_j = \sum_{i=1}^{M} \pi_i \, p_{ij}, \quad j = 1, \ldots, M.$$

Eigenvector interpretation. The stationarity condition $\boldsymbol{\pi}^T \mathbf{P} = \boldsymbol{\pi}^T$ says that $\boldsymbol{\pi}$ is a left eigenvector of $\mathbf{P}$ corresponding to eigenvalue $\lambda = 1$. Equivalently, $\mathbf{P}^T \boldsymbol{\pi} = \boldsymbol{\pi}$, so $\boldsymbol{\pi}$ is a right eigenvector of $\mathbf{P}^T$ with eigenvalue $1$.

By the Perron--Frobenius theorem, every row-stochastic matrix has $\lambda = 1$ as its largest eigenvalue (in magnitude), so the stationary distribution is associated with the dominant eigenvalue --- the very eigenvector that the power method of Chapter 1 converges to.

A birth--death process is a Markov chain on the non-negative integers $\mathcal{S} = \{0, 1, 2, \ldots\}$ in which transitions occur only to adjacent states:

$$p_{i,\,i+1} = \lambda_i \quad (\text{birth rate}), \qquad p_{i,\,i-1} = \mu_i \quad (\text{death rate}), \qquad p_{i,i} = 1 - \lambda_i - \mu_i,$$

with $\mu_0 = 0$ (no deaths in state $0$) and all other transition probabilities equal to zero.

Balance equations. For a stationary distribution $\boldsymbol{\pi}$, the detailed balance equations (also called local balance) equate the probability flow across each boundary:

$$\pi_i \, \lambda_i = \pi_{i+1} \, \mu_{i+1}, \quad i = 0, 1, 2, \ldots$$

These are stronger than the global balance equations ($\boldsymbol{\pi}^T \mathbf{P} = \boldsymbol{\pi}^T$) but are automatically satisfied for birth--death chains because transitions skip no states.

Solving recursively:

$$\pi_i = \pi_0 \prod_{k=0}^{i-1} \frac{\lambda_k}{\mu_{k+1}}, \quad i \geq 1,$$

where $\pi_0$ is determined by the normalisation $\sum_{i=0}^{\infty} \pi_i = 1$.

Birth--death processes are the backbone of queuing theory: the "births" are customer arrivals and the "deaths" are service completions.

The M/M/1 queue is the simplest and most important single-server queuing model:

• M (Markovian arrivals): packets arrive according to a Poisson process with rate $\lambda$ (hence exponential inter-arrival times with mean $1/\lambda$).
• M (Markovian service): service times are i.i.d. exponential with rate $\mu$ (mean service time $1/\mu$).
• 1: a single server.

The queue length $\{X(t)\}_{t \geq 0}$ forms a continuous-time birth--death process with constant rates $\lambda_i = \lambda$ and $\mu_i = \mu$ for all $i$. The discrete-time embedded chain at transition epochs is also a birth--death Markov chain.

Traffic intensity:

$$\rho = \frac{\lambda}{\mu}.$$

Stability condition: the queue has a stationary distribution if and only if $\rho < 1$ (the server must be faster than the arrival rate, on average).

Stationary distribution. From the birth--death recursion with $\lambda_i = \lambda$, $\mu_{i+1} = \mu$:

$$\pi_k = (1 - \rho)\,\rho^k, \quad k = 0, 1, 2, \ldots$$

This is a geometric distribution with parameter $\rho$. The probability that the queue is empty is $\pi_0 = 1 - \rho$, and the probability that the queue has $k$ or more customers is $P(X \geq k) = \rho^k$.