When two systems are being compared, the quantity estimated is the difference, and Var(A − B) = Var A + Var B − 2 Cov(A, B). Driving both systems from the same draws makes their outputs move together, which makes that covariance positive and takes twice it off the variance of the difference. Each system's own estimate is untouched; only the comparison improves, which is the whole of the technique and the whole of the misreading to avoid.
Core ideas
Three ideas. The first says what is being estimated, the second says what moves, and the third is the credit this technique must not be given.
“Is the faster server worth it?” is a question about A − B, not about A and B separately, and the variance of a difference has a covariance term in it. That term is the only place a comparison can be improved without buying draws, and it is free: it costs a decision about seeds and nothing else.
Run both configurations from the same seed and the same draws drive both: a run that happens to get a heavy burst of arrivals gets it in both systems, so both outputs are high together and the difference is stable. The covariance goes positive, 2 Cov comes off Var(A − B), and the interval on the comparison narrows.
The marginal distribution of each system's estimate is exactly what it was — sharing a stream changes which draws B sees, not the law of B's output. Reporting a smaller error bar on A alone because the runs were paired is the standard misreading, and it claims a precision that was never bought.
The material
Why a comparison has a covariance in it, how a shared stream makes that covariance positive, and what the technique does not buy.
A comparison of two configurations in which both are driven by the same stream of draws, so that replication j of system A and replication j of system B see the same randomness. The alternative — a fresh stream for each — is the independent scheme.
Var(A − B) = Var A + Var B − 2 Cov(A, B). Hence any scheme that makes Cov(A, B) positive reduces the variance of the estimated difference, and one that makes it negative increases it.
Expand: Var(A − B) = E[((A − B) − E[A − B])²], and write (A − B) − E[A − B] as (A − E[A]) − (B − E[B]).
Squaring gives (A − E[A])² − 2(A − E[A])(B − E[B]) + (B − E[B])², and taking expectations term by term gives Var A − 2 Cov(A, B) + Var B. Nothing about the two distributions was used, so the identity holds however A and B were generated.
□
That is the entire mechanism. Nothing about queues is involved and nothing is approximated: pairing does not make the estimator better in some vague sense, it moves one named term of an identity. If the covariance does not go positive, the technique has not worked, and the panel prints the covariance so that the question is answerable.
The two configurations on this page differ only in the service rate. The arrival test in slot t reads draw t, and the same draw against the same arrival probability gives the same answer, so both systems see exactly the same arrivals — verified, not assumed: the two runs produce identical arrival lists. A busy stretch is busy for both, a quiet one is quiet for both, and the difference between their occupancies is then driven by the service draws alone.
That is also why the kit takes the arrival draw for slot t from a fixed index and the service draw for the i-th customer from another fixed index, rather than consuming one stream in event order. Consuming in order would make the second system's arrival draws depend on how many service draws the first had taken, the two runs would silently decorrelate, and the mode built to measure the correlation would report a smaller one than the method actually achieves.
Read the two difference columns and not the two estimates. The estimates are 1.1329 and 1.0913, both aiming at 6/5 = 1.2, and neither is better than the other in any sense the method claims. The variance of the difference is 0.80789 against 2.10367, a factor of 2.604, and that factor is the only thing common random numbers bought.
The separate-stream covariance is −0.17812 rather than zero, which is worth a moment. Independent runs have covariance zero in expectation; a sample covariance over twenty-four replications is an estimate of zero and lands somewhere near it, on either side. Here it landed slightly negative, which pushed the independent variance up by 0.356 rather than leaving it at Var A + Var B.
Change the seed and the factor moves: 2.604 at seed 1, 5.770 at seed 0, 1.823 at seed 7, on the same twenty-four replications of two hundred slots. The covariance is reliably positive; its size is a measurement with a spread of its own. This is the course's own hazard arriving in the middle of a variance-reduction lesson: the number that says how much better the estimator got is an estimate, and quoting it to three figures from one seed is exactly the habit the first three pages were about.
The panel's second pair changes the arrival probability as well — 2/5 against 1/2 — so the two systems no longer see the same arrivals and their service draws line up against different customers. The coupling is still strong, and on this instance it is stronger: the arrival test is x < 0.4m in one system and x < 0.5m in the other, so every arrival in the first is an arrival in the second, and the two arrival streams are nested rather than merely similar. The measured factor is 5.001 against the first pair's 2.604.
The lesson of that second pair is not that more differences are better. It is that the size of the reduction is a property of how the two runs happen to couple, that coupling is a fact about the implementation as much as about the model, and that the only way to know what a pairing bought is to compute both variances and divide. Every claim on this page is of that form.
Interactive
Positive covariance shrinks the variance of the difference, which is the only thing being estimated
Method
Four steps, and the second is the one that makes the pairing real rather than nominal.
Form Dⱼ = Aⱼ − Bⱼ per replication and take the sample mean and sample variance of the Ds. An interval built from Var A and Var B separately throws the covariance away and is wider than the data supports.
Arrival draws at one set of indices, service draws at another. If both systems consume a single stream in event order, a difference anywhere makes every later draw land in a different place and the pairing evaporates without any warning.
Run the comparison paired and unpaired on the same replications. The ratio of the two variances is the only evidence that the pairing did anything, and it costs one extra set of runs on a question that is usually asked once.
Covariance positive and variance ratio above one is a working pairing. Covariance near zero means the synchronisation is nominal. Covariance negative means the pairing is actively hurting, which happens and is worth finding out before the result is published rather than after.
The two configurations are the slotted queue at q = 1/2 and at q = 3/5, arrivals at p = 2/5 in both. The exact long-run means are 12/5 and 6/5, so the true difference is 6/5 and every estimate below can be measured against it.
The first replication is the one that shows what pairing does. Under the shared stream the two systems gave 207/200 and 71/100, a difference of 13/40 = 0.325; under separate streams the second system happened to draw a busy run, gave 69/50 = 1.38, and the difference came out −69/200 = −0.345 — the wrong sign, on a comparison whose true answer is 6/5. Nothing is wrong with that replication; it is one draw of a quantity with a standard deviation of about 1.45.
Twenty-four such replications average to almost the same place under both schemes, which is the point: both estimators are unbiased for 6/5. What differs is that one of them has a variance of 0.81 and the other of 2.10, so an interval on the first is about 1.6 times narrower for the same compute.
For a faded rehearsal, drag the slots per replication from 200 to 800. The supplied first move is that both variances fall, because each replication is now a longer-run average of the same system. Say what you expect to happen to the ratio between them, and then check: it goes to 1.639, which is smaller, and the reason is that the two systems' long-run averages depend less on the particular burst of arrivals they shared.
You should be able to expand Var(A − B) and say which term the pairing moves, explain why synchronising by purpose rather than by order is what makes the pairing real, compute both variances and their ratio from the same replications, say what the technique does to a single system's own error bar, and treat the reduction factor as the estimate it is.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.