Ergodicity
Property of a stochastic process: the long-run time average of one trajectory equals the expected value across the ensemble. For an ergodic process, “watching one system for a long time” gives the same answer as “looking at many systems at one moment.”
Why it matters for queueing: performance formulas give ensemble averages. You measure time averages from a running system. Those match only if the system is ergodic.
For Markov chains (and most well-behaved queues like M/M/1 below saturation):
- Irreducible: every state reachable from every other.
- Positive recurrent: expected return time to each state is finite.
Together these imply a unique stationary distribution, and the chain is ergodic.
Practical consequences:
- An M/M/1 queue with is ergodic; queue-length statistics converge as you run it longer.
- At , it’s not ergodic: queue length diverges, time averages never stabilize.
- Warm-up period before sampling exists because early behaviour still depends on initial conditions.
Non-ergodic cousin: a process with absorbing states, or phase transitions. Financial models that assume ergodicity have blown up spectacularly by ignoring this.
From ECE459 L32
Three-part definition [HB13]: irreducible + positive recurrent + aperiodic.
- Irreducible: any state reachable from any other. Initial state doesn’t matter; queue can get from 0 jobs to 27 jobs.
- Positive recurrent: every state is revisited infinitely often, with finite expected return time. Pick “queue empty” as a natural restart marker.
- Aperiodic: state isn’t tied to time parity. Otherwise sampling at vs gives different answers.
Tim vs Enzo [HB13]
FCFS queue, arrival prob /sec, completion prob /sec. Goal: average jobs in system.
- Tim: one very long simulation, 1M samples, time-average.
- Enzo: 1 000 independent short runs, sample at , ensemble-average.
Both correct iff the system is ergodic. Ensemble-average wins in practice: embarrassingly parallel, gives confidence intervals, less sensitive to initial-condition bleed-through. Tim must ensure startup costs attenuate; Enzo must sample past them.
Positive recurrence is what makes Tim’s one long run equivalent to Enzo’s 1 000 runs: every “queue empty” is a renewal, and the long run decomposes into a chain of restarts.