Interactive Labs in Queuing Theory
Interactive labs I have built for my Cambridge course Computer Systems Modelling. Each one runs in the browser; no installation is needed. The cards below say what each lab shows, what to try, and which ideas from the course it illustrates.
Shows: how to generate samples from any distribution using the inverse-CDF method, X = F−1(U).
How it works: Sketch a density f with the mouse (or pick a preset: bimodal, piecewise constant, triangular, truncated exponential, uniform). The page computes the CDF F as you draw. Each sample picks u ~ U(0,1) on the vertical axis of F, runs across to the curve, and drops to x = F−1(u). A histogram of the samples builds up beneath, and converges to f.
Try this: Draw one sample at a time to follow the path, then switch off animation and draw batches. Note how steep parts of F catch many values of u while flat parts catch almost none.
Concepts: CDF and its inverse · inverse transform sampling · empirical distribution · sample mean vs. E[X]
Shows: how the sample mean, sample variance and 95% confidence interval behave, and why the central limit theorem makes intervals work for any population.
How it works: In three steps. (1) Sketch a population density; its true mean μ and variance σ² are computed exactly. (2) Draw one run of n samples and watch X̄n, Sn² and the t-interval settle as samples arrive, with the interval narrowing like 1/√n. (3) Repeat for hundreds or thousands of runs: the sample means pile up as N(μ, σ²/n), and about 95% of the intervals contain μ.
Try this: Use a skewed population with small n (say 5) and see coverage fall short of 95%; then increase n and watch it recover. Compare a bimodal population with a uniform one: the histogram of means looks normal either way.
Concepts: sample mean and variance · Student’s t interval · coverage · central limit theorem · standard error
Shows: sample paths of a birth–death Markov chain: a random walk that steps up with probability p and down with probability 1 − p, held at its boundaries.
How it works: Choose p, a starting state, the number of steps, and either a finite chain on 1 … N or a semi-infinite chain on 1, 2, 3, …. Each press of Run adds a new trajectory in a new colour, so runs can be compared side by side. For the semi-infinite chain, a dashed line shows the expected drift s0 + (2p − 1)t.
Try this: On the semi-infinite chain, compare p = 0.4, 0.5 and 0.6. For p > ½ the walk escapes and tracks the drift line (transient); for p ≤ ½ it keeps returning to state 1 and the line is misleading (recurrent). On a finite chain, watch where the walk spends its time as p moves away from ½.
Concepts: Markov chains · reflecting boundaries · drift and linearity of expectation · transience vs. recurrence · √t spread of trajectories
Shows: a refresher on eigenvalues and eigenvectors before they are used for Markov chains: what an eigenvector is, why every stochastic matrix has dominant eigenvalue 1, and how the power method finds the eigenvector that goes with it (§3.5–3.6).1
How it works: In three steps. (1) Drag a unit vector x around the circle and watch Ax: an eigenvector is a direction the matrix does not turn, and its eigenvalue is the stretch. The characteristic equation is solved alongside. (2) Edit a 3 × 3 stochastic matrix and check three facts: A1 = 1, Gerschgorin disks keep every eigenvalue inside the unit circle, and under mild assumptions 1 is the only eigenvalue on it. (3) Run the power method and watch the Rayleigh ratio converge to the dominant eigenvalue. Multiplying on the left gives the stationary distribution π.
Try this: Find both eigenvector directions of the book’s Example 3.15. Then try the rotation, which has none, and the deterministic 3-cycle, where three eigenvalues tie on the unit circle. Compare how fast the power method converges on Example 3.24 and on a chain where all states communicate. Each step has tasks with hidden answers.
Concepts: eigenvalues and eigenvectors · characteristic equation · stochastic matrices · spectral radius · Gerschgorin’s theorem · power method · Rayleigh ratio · left eigenvectors and the stationary distribution
Shows: a discrete-time Markov chain as a state graph and its stochastic matrix P, the difference between one random trajectory and the evolving distribution πt+1 = πtP, and two ways to find the stationary distribution.
How it works: In three steps. (1) Build a chain of 3–8 states from a preset or by editing P; the graph redraws as you type. (2) Step a single walker through the chain alongside the distribution πt, and compare both with 1,000 independent walkers and with the walker’s time average. (3) Find the stationary π as the dominant eigenvector of PT, by power iteration (with the Rayleigh quotient and the eigenvalues plotted in the complex plane) and by stepping through Gaussian elimination on (PT − I)πT = 0.
Try this: Load Two clusters, slow mixing and see how slowly power iteration converges when |λ2| is close to 1. Then try Period 2, where xk oscillates instead of converging, and Reducible, where the stationary distribution is not unique.
Concepts: stochastic matrices · trajectories vs. distributions · ensemble and time averages · stationary distribution · eigenvalues and power iteration · mixing rate · periodicity and reducibility
Shows: how a continuous-time Markov chain arises from coin flips, what the entries of the rate matrix Q mean, and how Q relates to the transition probability matrix P of a discrete-time chain.
How it works: It builds up in steps. A Bernoulli trial, repeated until the first success, gives the geometric distribution, drawn as a two-state chain. Running one trial every Δt with p = qΔt and shrinking Δt turns the geometric into the exponential. With several states, a discrete chain that ticks every Δt runs beside a continuous one that jumps at any instant. Racing exponential alarm clocks show what qjk and qjj mean, and the page derives P(Δt) ≈ I + QΔt. Probability then flows between states like fluid between tanks, which leads to Equations 6.12 and 6.13.2
Try this: Drag Δt towards zero and watch the geometric staircase close in on e−qt. Run 2,000 clock races and check that the holding time is Exp(−qjj) and that each clock wins a share qjk/(−qjj) of the races. Then edit Q and press Jump to π* to see every tank’s inflow balance its outflow.
Concepts: Bernoulli, geometric and exponential distributions · memorylessness · rate matrix Q · P(Δt) = eQΔt · holding times · embedded chain · Equations 6.12 and 6.13 · stationary distribution
Footnotes
Section numbers refer to Chapter 3 (Linear Algebra) of S. Keshav, Mathematical Foundations of Computer Networking, Addison-Wesley, 2012.↩︎
Equation numbers refer to Chapter 6 of S. Keshav, Mathematical Foundations of Computer Networking, Addison-Wesley, 2012.↩︎