A simulation has no randomness in it. It has a recurrence, a seed, and a table: xₙ₊₁ = (a·xₙ + c) mod m produces integers, U = x/m turns one into a fraction in [0, 1), and the sampled value is the first outcome whose cumulative probability reaches U. Both halves are exact, so a run is reproducible from its seed and every count in it is a ratio of whole numbers — and the period of the recurrence decides whether the table is being sampled at all.
Core ideas
Three ideas, and the third is the one that decides whether anything later on this course means anything: the sampler is the table, and a shortcut that does not read the probability column samples a different distribution.
xₙ₊₁ = (a·xₙ + c) mod m is a function, not a source of chance. Fix a, c, m and the seed and every draw in the run is determined — which is a feature, because it is what makes a simulation reproducible, debuggable, and comparable with a second simulation. Nothing on this course would work if the numbers were genuinely unrepeatable.
39022/65536 is 19511/32768 and it is not 0.5954. Every statistic taken of a run — a count, a frequency, a sample mean, a sample variance — is then a ratio of whole numbers, and the page can print it in full rather than in a form the reader has to take on trust.
Build F(k) = p₀ + ⋯ + p_k and return the first k with U < F(k). The band [F(k−1), F(k)) has width exactly p_k, so the outcome comes out with exactly its own probability. The tempting shortcut — ⌊k·U⌋ + 1 — never looks at the probability column at all, and therefore samples the uniform distribution on k values whatever table is on the page.
The material
Where the numbers come from, what turns them into outcomes, and the condition that decides whether the stream is long enough to be one.
A linear congruential generator is the recurrence xₙ₊₁ = (a·xₙ + c) mod m started from a seed x₀. The multiplier a, the increment c and the modulus m fix the whole sequence. Its period is the number of values before it returns to a state it has already been in, and it is at most m.
Discrete Mathematics built this object in “Hashing and Pseudorandom Numbers”, and the lab on this page lets you set all three parameters and watch what they do. What is new here is the use it is put to: this is the only supply of numbers a simulation has, and every figure on the eight pages after this one is a function of it.
Given a distribution on values v₀ < v₁ < ⋯ with probabilities p₀, p₁, …, build the cumulative table F(k) = p₀ + ⋯ + p_k. To sample: draw U = x/m and return the first v_k with U < F(k). The method is called inverse-transform because it is applying the inverse of the cumulative function to a uniform draw.
The correctness argument is one line and is worth having in front of you, because it is what the shortcut breaks. U is uniform on [0, 1), so the probability that it lands in the band [F(k−1), F(k)) is the width of that band, which is p_k by construction. Every outcome therefore comes out with its own probability, and the bands are read off the table rather than assumed.
Two properties of the method matter later and are easy to miss now. It consumes exactly one draw per sampled value, so two runs that sample the same number of things read the same number of draws — which is what makes “Common Random Numbers” possible. And it is monotone in U: a larger U never returns a smaller value. That is the condition “Antithetic Variates” stands on, and it is a property of this sampler rather than a lucky fact.
U < F(k) is x/m < n/d, which is x·d < n·m, and both sides are integers. Nothing in the sampler ever becomes a decimal, so there is no tie a rounding could decide wrongly. The modulus the rest of this course uses is odd, so U is never exactly 1/2 either, and no comparison on any of these pages has a boundary case at all.
A linear congruential generator has full period m from every seed if and only if gcd(c, m) = 1, every prime dividing m also divides a − 1, and a − 1 is divisible by 4 whenever m is. This course quotes the condition and checks it; the statement belongs to “Hashing and Pseudorandom Numbers”, which states it without proof, and so does this page.
The condition needs c ≠ 0, and the reason is worth a sentence because the generator the rest of this course uses has c = 0. Zero is a fixed point of x ↦ a·x mod m, so a purely multiplicative generator can never visit it and its best possible period is m − 1. Set the lab's generator to a = 16807, c = 0, m = 2147483647 and the first condition reads as a failure: gcd(0, m) = m. That is the theorem declining to apply, not the generator being bad.
Set a = 2, c = 4, m = 16. From seed 1 the stream is 6, 0, 4, 12, 12, 12, …: four values and then a constant forever. All three conditions fail — gcd(4, 16) = 4, and a − 1 = 1 is divisible neither by 2 nor by 4. A sampler fed that stream returns 2, 0, 1, 3, 3, 3, …, which is not a sample of any table; it is one cycle, repeated, with a frequency column that looks like data.
The fourth draw is the one to look at. 45005 is 51 short of 45056, so it lands in the third band rather than the fourth by a margin of fifty-one parts in sixty-five thousand. In whole numbers that is a settled question; in floating point it is a question about the last bit of a double, and the answer decides which outcome the reader is shown.
The gap of 11/200 between the empirical frequency of the value 2 and its probability 6/16 is not an error and not something to apologise for. It is what two hundred draws of this table look like. How large such a gap can honestly be is the subject of the two pages after this one, and the answer is the first thing on this path that arrives as an interval rather than as a number.
Interactive
An integer becomes a fraction, and the cumulative table decides which value it is
Method
Four steps, and the first is the one that is usually skipped.
Run the Hull-Dobell conditions on a, c and m, or, for a multiplicative generator, check that the modulus is prime and the multiplier is a primitive root. A short period is not a small inaccuracy: the run stops being a sample and becomes a cycle, and nothing downstream complains.
F(k) = p₀ + ⋯ + p_k, ending at exactly 1. If the last entry is not 1 the probabilities do not sum to one and the bug is in the model, not in the sampler.
U = x/m as a ratio of whole numbers. Every comparison after this is x·d < n·m in the integers, which has no rounding in it and no boundary case to guess at.
The first k with U < F(k). Keeping the band alongside the value is what makes a disputed draw checkable afterwards, and it costs nothing.
Empirical frequency against probability, as fractions, with the difference shown. That difference is the thing the next two pages put a bound on; looking at it now is what makes the bound mean something later.
The table has mean exactly 2 and variance exactly 1, which is why it is the one five of this course's nine panels open on: every theoretical standard error built on it is a fraction rather than a surd, and the halving of that standard error is a fact rather than a measurement.
Every entry in that table is exact. The counts are integers, the frequencies are those integers over two hundred, and the differences are fractions with denominators no larger than four hundred. Nothing here is a measurement of the generator; it is the generator's output, written down.
The sample mean is 413/200, which is 2.065, against a true mean of 2. That is a discrepancy of 13/200 on two hundred draws. Is it large? The honest answer at this point in the course is that nothing on this page can say, and the next page is about the smallest thing that can.
For a faded rehearsal, set the generator to a = 5, c = 3, m = 16 — small enough to walk by hand. The supplied first move is that all three conditions hold, so the period is the full 16 and the stream from seed 1 is 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, …. Work out the first four sampled values by comparing x against the band edges over m = 16 — they are 1, 5, 11, 15, 16 — and say why a modulus of sixteen cannot sample this table faithfully however long you run it, before the panel's frequency column tells you.
You should be able to run a linear congruential generator by hand for four steps, check the Hull-Dobell conditions on its parameters and say which fail, build a cumulative table and sample from it by comparing whole numbers, explain in one line why the band [F(k−1), F(k)) gives outcome k its own probability, and say what the index shortcut samples instead.
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.