Sampling and randomness

Intermediate

Introduction

Every time a generative model writes a word or paints a pixel, it makes a random choice. The randomness is what lets one model produce a thousand different stories from the same prompt. This lesson opens that box: how a computer makes random numbers at all, and how a random number becomes a choice among outcomes with given probabilities.

How it works

Computers are deterministic, so they make pseudo-random numbers with a formula. The oldest is the linear congruential generator (LCG):

x ← (a × x + c) mod m        r = x / m

Starting from a seed, each step gives a new whole number x between 0 and m − 1, and r = x / m is between 0 and 1. With good constants (the example uses the classic a = 1103515245, c = 12345, m = 2³¹), the numbers look random, yet the same seed always gives the same sequence. That is a feature: fixing the seed makes experiments and tests repeatable. Python's random module uses a stronger generator (the Mersenne Twister) on the same principle, and random.seed(42) fixes its sequence.

A categorical distribution gives each outcome a probability: sun 0.6, rain 0.3, snow 0.1. To sample it, take r and walk the outcomes, adding up their probabilities (the cumulative probability). The first outcome whose running total is greater than r is chosen: sun covers [0, 0.6), rain [0.6, 0.9) and snow [0.9, 1). Each outcome's slice is exactly as wide as its probability.

Samples only match their probabilities on average. The expected count of an outcome in n samples is n × p, but 20 samples might give 14 suns instead of 12. With thousands of samples, the shares settle close to the probabilities; this is the law of large numbers.

Example

labels = ["sun", "rain", "snow"]
probs = [0.6, 0.3, 0.1]
state = 42  # the seed


def next_random():
    """A linear congruential generator: the same seed always gives the same numbers."""
    global state
    state = (1103515245 * state + 12345) % 2**31
    return state / 2**31


def sample():
    r = next_random()
    running = 0.0
    for label, p in zip(labels, probs):
        running += p
        if r < running:
            return label
    return labels[-1]


days = [sample() for _ in range(20)]
print(" ".join(days))
for label, p in zip(labels, probs):
    print(f"{label}: {days.count(label)} of 20 (expected {p * 20:.0f})")
Open in compiler

Line by line

  1. labels and probs are the categorical distribution; state holds the seed.
  2. next_random updates the state with the LCG formula and divides by 2³¹ to get r in [0, 1).
  3. sample walks the running total of probabilities and returns the first outcome whose total passes r.
  4. Twenty samples are drawn and joined into one line.
  5. The counts are compared with the expected counts, 20 × p.

Expected result

sun sun sun rain sun sun sun rain rain rain sun sun sun sun snow sun rain sun sun rain
sun: 13 of 20 (expected 12)
rain: 6 of 20 (expected 6)
snow: 1 of 20 (expected 2)

In the real world

Language models choose every token by sampling from a distribution like this one, over a vocabulary of tens of thousands of tokens. Image generators start from random noise drawn from a generator with a seed, which is why image tools let you reuse a seed to recreate a picture. Simulations, games and statistics rely on the same generators. For security, such as passwords and keys, programs must use cryptographic generators (Python's secrets module), because an LCG's next number can be predicted.

Common mistakes

  • Using r <= running instead of r < running, which shifts the boundaries between outcomes.
  • Forgetting that probabilities must add up to 1, or normalizing them only sometimes.
  • Expecting exact counts from a small sample.
  • Using a predictable generator for security.

Best practices

  • Fix the seed in tests and experiments, and record it with the results.
  • Normalize weights by dividing by their sum before sampling.
  • Check a sampler by drawing many samples and comparing the shares with the probabilities.

Summary

Computers make pseudo-random numbers with formulas such as the linear congruential generator; a seed fixes the sequence. Sampling a categorical distribution walks the cumulative probabilities until the running total passes a random number in [0, 1), so each outcome is chosen as often as its probability on average. Small samples vary around the expected counts n × p.

Quick check

1. What does fixing the seed of a pseudo-random generator do?
2. Probabilities sun 0.6, rain 0.3, snow 0.1. Which outcome does r = 0.75 choose?
3. What is the expected count of an outcome with probability 0.25 in 40 samples?
4. Which generator should create passwords?

Key takeaways

  • Computers make "random" numbers with formulas; the same seed gives the same sequence.
  • To sample, walk the outcomes adding probabilities until the total passes a random number in [0, 1).
  • Small samples wander from their expected counts; large samples settle near them.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.