Ferkans — Interactive Telecom Tutor

Markov Chains in the Wireless World

Markov chains are not merely an elegant mathematical construct — they are the workhorse model for many phenomena in communications systems. Channel fading, protocol state machines, error propagation, and network access contention all admit natural Markov chain formulations. In this section we study three canonical applications: the Gilbert-Elliott burst error channel, ARQ retransmission protocols, and slotted ALOHA random access.

Definition:
Gilbert-Elliott Channel Model

The Gilbert-Elliott (GE) channel is a two-state DTMC $\{S_n\} \in \{\text{G}, \text{B}\}$ (Good, Bad) with transition matrix

$\mathbf{P}_{\text{GE}} = \begin{pmatrix} 1 - b & b \\ g & 1 - g \end{pmatrix},$

where $b = \mathbb{P}(\text{G} \to \text{B})$ and $g = \mathbb{P}(\text{B} \to \text{G})$ .

In state G, bits are received correctly (error probability $\epsilon_G \approx 0$ ). In state B, bits are corrupted with high probability ( $\epsilon_B \gg \epsilon_G$ ).

The channel state is hidden — only the received bits are observed — making this a hidden Markov model (HMM). The GE channel captures the bursty nature of errors on fading channels: errors tend to cluster in "bad" intervals.

E. N. Gilbert (1960) proposed the original two-state model; E. O. Elliott (1963) extended it by allowing errors in the good state. The model remains widely used in protocol simulation and link-level abstraction for LTE/5G.

,

Example: Steady-State Error Rate of the Gilbert-Elliott Channel

For the Gilbert-Elliott channel with parameters $b = 0.1$ , $g = 0.4$ , $\epsilon_G = 0.001$ , $\epsilon_B = 0.3$ , find the steady-state bit error rate.

Solution

Find the stationary distribution

Using the two-state formula: $\pi_G = \frac{g}{b + g} = \frac{0.4}{0.5} = 0.8, \quad \pi_B = \frac{b}{b + g} = \frac{0.1}{0.5} = 0.2.$

Compute steady-state BER

$\text{BER} = \pi_G \epsilon_G + \pi_B \epsilon_B = (0.8)(0.001) + (0.2)(0.3) = 0.0008 + 0.06 = 0.0608.$ $

So the steady-state BER is about 6.1%. Despite spending 80% of the time in the good state, the high error rate during bad intervals dominates.

Burst length

The expected duration of a bad burst is $1/g = 1/0.4 = 2.5$ slots. The expected duration of a good interval is $1/b = 1/0.1 = 10$ slots. Errors are clustered in bursts of average length 2.5, separated by error-free runs of average length 10.

,

Gilbert-Elliott Channel: Burst Errors and BER

Simulate the Gilbert-Elliott channel and observe burst error patterns. Adjust the transition probabilities and error rates to see their effect on BER and burst length.

Parameters

b (G to B transition)0.1

g (B to G transition)0.4

Error rate in Good state0.001

Error rate in Bad state0.3

Number of bits500

Example: Stop-and-Wait ARQ as a Markov Chain

In stop-and-wait ARQ, a transmitter sends a packet and waits for an ACK. If the packet is received correctly (probability $1 - p$ ), an ACK is sent and the transmitter moves to the next packet. If the packet is lost (probability $p$ ), a timeout triggers retransmission. Model the number of transmissions per packet as a Markov chain and find the expected number of transmissions.

Solution

Model as a geometric random variable

Let $N$ = number of transmissions until success. Each transmission succeeds independently with probability $1 - p$ . So $N \sim \text{Geometric}(1 - p)$ and $\mathbb{E}[N] = 1/(1 - p)$ .

Throughput

The throughput (fraction of time spent sending new packets) is:

$\eta = \frac{1}{\mathbb{E}[N]} = 1 - p.$

For $p = 0.1$ : $\eta = 0.9$ (90% efficiency). For $p = 0.5$ : $\eta = 0.5$ .

Over a Gilbert-Elliott channel

If the channel is Gilbert-Elliott rather than i.i.d., successive transmissions are not independent. The number of retransmissions depends on the channel state, and the analysis requires the full Markov chain machinery. The effective throughput is lower than $1 - \bar{p}$ because errors cluster in bursts.

Example: Slotted ALOHA Backlog as a Markov Chain

In slotted ALOHA with $N$ users, each backlogged user transmits in a slot with probability $q$ . New packets arrive according to a Poisson process with rate $\lambda$ per slot. Let $X_n$ be the number of backlogged users at the start of slot $n$ . Show this is a DTMC and discuss stability.

Solution

Markov property

The number of backlogged users $X_{n+1}$ depends on $X_n$ (how many users may transmit), the number of new arrivals (Poisson, independent of history given $X_n$ ), and whether a success occurs (depends only on how many transmit in this slot). Since all randomness in slot $n$ depends only on $X_n$ , this is a DTMC.

Transition structure

Success occurs when exactly one user transmits. Given $X_n = k$ backlogged users, the probability of exactly one transmission among the $k$ backlogged users is $k q (1-q)^{k-1}$ .

If success: one user leaves the backlog, new arrivals join. If no success: all remain, new arrivals join.

$X_{n+1} = X_n - \mathbf{1}_{\text{success}} + A_n,$

where $A_n \sim \text{Poisson}(\lambda)$ is the number of new arrivals.

Stability condition

The system is stable (positive recurrent) when the arrival rate $\lambda$ is less than the maximum throughput. For large $N$ with $q = 1/N$ , the maximum throughput of slotted ALOHA is $1/e \approx 0.368$ packets per slot. Stability requires $\lambda < 1/e$ .

Why This Matters: Markov Chains in Channel Modeling and Link Adaptation

The Gilbert-Elliott model is the simplest example of finite-state Markov channel (FSMC) models, where the channel quality is quantized into a finite number of states. Modern link adaptation in LTE/5G partitions the SNR range into intervals and models transitions between intervals as a DTMC. The stationary distribution determines the long-run fraction of time at each modulation/coding rate, enabling throughput prediction. HARQ (Hybrid ARQ) protocols are naturally modeled as Markov chains, where states track the number of retransmissions and the decoder state.

Why This Matters: MCMC in Wireless System Design

MCMC methods appear in several wireless contexts: Bayesian channel estimation (sampling posterior distributions over channel parameters), MIMO detection via Gibbs sampling (approaching ML performance without exhaustive search), and network optimization (simulated annealing for resource allocation). The convergence theory of this chapter — particularly mixing time analysis — determines how many iterations these algorithms need before their outputs are reliable.

🎓CommIT Contribution(2021)

Age of Information in Status Update Systems

Y. Sun, E. Uysal-Biyikoglu, G. Caire — IEEE Trans. Inf. Theory

The CommIT group has contributed to analyzing status update systems where the sampling and transmission protocol is modeled as a discrete-time Markov chain. The age of information (AoI) — the time elapsed since the freshest received update was generated — is a key metric for cyber-physical systems, autonomous driving, and IoT. Sun, Uysal-Biyikoglu, and Caire showed that when the update process follows a DTMC, the stationary distribution of the chain directly determines the average AoI. By optimizing the transition probabilities (i.e., the sampling policy), one can minimize AoI subject to energy or throughput constraints. The Markov chain framework unifies results previously obtained for specific queueing models.

age of informationMarkov chainstatus update

Gilbert-Elliott channel

A two-state hidden Markov model for bursty error channels. State G (good) has low error probability; state B (bad) has high error probability. Transitions between states capture temporal correlation in channel quality.

Related: Gilbert-Elliott Channel Model

Age of information

The time elapsed since the generation of the most recently received status update. Measures the freshness of information at a receiver.

Key Takeaway

Markov chains model burst error channels (Gilbert-Elliott), retransmission protocols (ARQ), and random access (ALOHA). The stationary distribution yields steady-state performance metrics — BER, throughput, average delay, age of information — directly from the transition matrix.

Applications in Communications

Markov Chains in the Wireless World

Definition: Gilbert-Elliott Channel Model

Example: Steady-State Error Rate of the Gilbert-Elliott Channel

Find the stationary distribution

Compute steady-state BER

Burst length

Gilbert-Elliott Channel: Burst Errors and BER

Parameters

Example: Stop-and-Wait ARQ as a Markov Chain

Model as a geometric random variable

Throughput

Over a Gilbert-Elliott channel

Example: Slotted ALOHA Backlog as a Markov Chain

Markov property

Transition structure

Stability condition

Why This Matters: Markov Chains in Channel Modeling and Link Adaptation

Why This Matters: MCMC in Wireless System Design

Age of Information in Status Update Systems

Gilbert-Elliott channel

Age of information

Key Takeaway

Definition:
Gilbert-Elliott Channel Model