Random variables and distributions

Why you need this

A generator's whole job reduces to one move: given a list of probabilities, pick one option. "Pick the next column type", "pick a tile for this cell", "pick the next regime for this region" are all the same move. This page names the object being picked from, a categorical distribution, shows how a row of a transition table is one, and gives the ten-line function that draws from it.

The idea

Discrete random variable

A random variable is a quantity whose value depends on the result of a random experiment. It is discrete when its possible values form a list you can count. Write a capital letter, $X$, for the variable and a lowercase letter or a label for a particular value. In this cluster the values are usually labels: section types, tile ids, or states numbered $1, 2, \dots, N$. The state at time $t$ is written $X_t$.

Probability mass function

The probability mass function (pmf) of $X$ assigns each possible value $k$ its probability: $p(k) = P(X = k)$. Two constraints make a list of numbers a pmf:

• every $p(k) \ge 0$, and
• $\sum_k p(k) = 1$, the sum-to-one constraint.

For a fair die, $p(k) = 1/6$ for each of $k = 1, \dots, 6$, and six sixths is 1.

Categorical distribution

A categorical distribution is a random variable over $N$ labelled outcomes, described completely by $N$ numbers $p_1, \dots, p_N$ that are non-negative and sum to 1. It is the only distribution this cluster really needs. A die is categorical with $N = 6$. A column type is categorical with $N = 4$.

A row of a transition matrix $A$ is exactly a categorical distribution. Row $i$ holds $A_{i1}, \dots, A_{iN}$, where $A_{ij} = P(X_{t+1} = j \mid X_t = i)$, and those $N$ numbers are non-negative and sum to 1. "Take a step from state $i$" means "sample from row $i$".

Weights versus probabilities

Designers rarely write probabilities. They write weights: grass 10, dirt 3, rock 1. Weights are non-negative but need not sum to 1. To turn weights into probabilities, divide each by their sum. Here the sum is 14, so grass is $10/14 \approx 0.714$, dirt $3/14 \approx 0.214$, rock $1/14 \approx 0.071$. Only the ratios matter: doubling every weight changes nothing.

Expectation

When the outcomes are numbers, the expectation is the probability-weighted average:

$$E[X] = \sum_k k \cdot p(k)$$

For a die, $E[X] = (1 + 2 + 3 + 4 + 5 + 6)/6 = 3.5$. Suppose a platform column is 0 tiles high with probability 0.5, 1 tile with probability 0.3, and 2 tiles with probability 0.2. Then $E[\text{height}] = 0 \times 0.5 + 1 \times 0.3 + 2 \times 0.2 = 0.7$ tiles. No single column is 0.7 tiles high; that is the long-run average. Expectations add: if each of 100 columns is a hazard with probability 0.1, the expected hazard count is $100 \times 0.1 = 10$.

Sampling with one uniform draw

Draw $u \sim \mathrm{Uniform}(0, 1)$ from a seeded generator. Build the cumulative sums $c_1 = p_1$, $c_2 = p_1 + p_2$, and so on up to $c_N = 1$. Return the first $k$ with $u < c_k$.

Picture a roulette wheel whose wedges have widths $p_1, \dots, p_N$. The cumulative sums are the wedge boundaries. Spinning the wheel is choosing $u$; the pointer lands in wedge $k$ when $c_{k-1} \le u < c_k$. Because $u$ is uniform, the probability of landing in an interval equals its length, and that length is $c_k - c_{k-1} = p_k$. So outcome $k$ is chosen with probability exactly $p_k$, which is what you wanted.

Worked example

Four column types with probabilities flat 0.5, gap 0.2, climb 0.2, hazard 0.1.

$k$	outcome	$p_k$	$c_k$	chosen when $u$ is in
1	flat	0.5	0.5	$[0, 0.5)$
2	gap	0.2	0.7	$[0.5, 0.7)$
3	climb	0.2	0.9	$[0.7, 0.9)$
4	hazard	0.1	1.0	$[0.9, 1)$

Four draws: $u = 0.63$ gives gap, $u = 0.07$ gives flat, $u = 0.95$ gives hazard, and $u = 0.90$ gives hazard too, since the test is strict: $0.90 < 0.9$ is false, so the walk moves past climb.

The same walk in code. The generator is mulberry32, the one the demos use; the sampler accepts raw weights and normalizes on the fly by scaling $u$ instead of the weights.

function mulberry32(seed) {
  return function () {
    seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function sampleCategorical(weights, rand) {
  const total = weights.reduce((s, w) => s + w, 0); // weights need not sum to 1
  const u = rand() * total;                          // u in [0, total)
  let acc = 0;
  for (let k = 0; k < weights.length; k++) {
    acc += weights[k];
    if (u < acc) return k;
  }
  return weights.length - 1;                         // guard against rounding
}

const rand = mulberry32(42);
const names = ["flat", "gap", "climb", "hazard"];
const counts = [0, 0, 0, 0];
for (let i = 0; i < 10000; i++) counts[sampleCategorical([0.5, 0.2, 0.2, 0.1], rand)]++;
console.log(names.map((n, k) => `${n}: ${counts[k]}`).join(", "));
// seed 42 prints: flat: 5022, gap: 2038, climb: 1918, hazard: 1022

The expected counts are 5000, 2000, 2000, 1000. The observed counts wobble around them by a percent or two, which is normal for 10,000 draws. Change the seed and the wobble changes; keep the seed and the output is identical every run.

In a map generator

• Catalog. Each biome's tile weights are an unnormalized categorical distribution. The sampler above eats them as they are.
• Layout. A Markov chain step is sampleCategorical(A[i], rand). The first state comes from the initial distribution $\pi$, another categorical.
• Fill. In Wave Function Collapse every undecided cell holds a categorical over the tiles still allowed there. Collapsing the cell is one call to the sampler.
• Regime over time. Each region advances by sampling its current row once per tick.
• Export. Expectations are your sanity checks. If hazards are 0.1 per column, a 300-column level should average about 30, and a run that averages 60 has a bug upstream.

Common mistakes

• Treating weights as probabilities. Walking cumulative weights that sum to 14 against $u$ in $[0, 1)$ picks the first option almost every time. Symptom: a map that is nearly all grass no matter what the weights say.
• Using Math.random(). The same seed then produces different maps. Symptom: "reload with the same seed" shows a different level.
• Mixing < and <=, or a cumulative sum that tops out at 0.9999999. The last outcome is never chosen, or the loop falls off the end and returns undefined. Symptom: a missing tile id, or a tile that exists in the weights but never appears.
• A negative weight from a subtraction upstream. The total shrinks and the walk misbehaves. Symptom: the sampler returns an index that should have had probability zero.
• Confusing the expectation with the typical value. A mean height of 0.7 tiles does not mean most columns are near 0.7; here most are 0. Symptom: you tune the mean while players notice the mode.
• Sharing one random stream across systems. Adding a decoration pass shifts every later draw. Symptom: a change to trees moves the platforms too. See Pseudo-random numbers.

Cost

One sample from $N$ outcomes takes $O(N)$ time to walk the cumulative sums and $O(1)$ extra memory. With a precomputed cumulative array, $O(N)$ memory per distribution, a binary search brings each draw to $O(\log N)$. For the $N$ in this cluster, a few to a few dozen, the linear walk is fine. It begins to matter in Wave Function Collapse with hundreds of tiles and tens of thousands of cells, where the alias method gives $O(1)$ per draw after $O(N)$ setup.

Going further

• Matrices and vectors: a row-stochastic matrix is a stack of these distributions.
• Pseudo-random numbers: where $u$ comes from and why the seed matters.
• Markov chains: sampling a whole sequence, one row at a time.
• Entropy: a single number for how spread out a distribution is.
• Walker's alias method, for constant-time sampling.