Probability basics

Why you need this

Every generator in this cluster makes choices at random, and every choice is governed by a number: how likely a gap column is to follow a flat run, how likely a forest chunk is to sit beside a town chunk. Those numbers are probabilities. A Markov chain is a table of conditional probabilities, a hidden Markov model is two such tables, and Wave Function Collapse weights its tile choices with them. This page gives you the vocabulary and the handful of rules everything else relies on.

The idea

Sample space, outcomes, events

An experiment is anything with an uncertain result: rolling a die, picking the next column of a side-scroller level. The sample space $\Omega$ is the set of every result that could happen. An outcome is one element of that set. An event is a subset of outcomes, which is the same as a yes-or-no question about the result.

For one die, $\Omega = \{1, 2, 3, 4, 5, 6\}$. The outcome might be 4. The event "rolled an even number" is $E = \{2, 4, 6\}$.

For one column of a side-scroller, $\Omega = \{\text{flat}, \text{gap}, \text{climb}, \text{hazard}\}$. The event "the column is dangerous" is $D = \{\text{gap}, \text{hazard}\}$.

The probability of an event

$P(E)$ is the probability that event $E$ happens. It is always a number in $[0, 1]$: 0 means never, 1 means always, and $P(\Omega) = 1$ because something has to happen.

When every outcome is equally likely, $P(E)$ is the count of outcomes in $E$ divided by the count in $\Omega$. For the even die roll, $P(E) = 3/6 = 0.5$.

When outcomes are not equally likely, each outcome carries its own probability and $P(E)$ is the sum over the outcomes in $E$. Say a column is flat with probability 0.5, gap 0.2, climb 0.2, hazard 0.1. Then $P(D) = 0.2 + 0.1 = 0.3$.

Complement

The event "not $E$", written $E^c$, has $P(E^c) = 1 - P(E)$. The chance a column is safe is $1 - 0.3 = 0.7$.

"Or" for disjoint events

Two events are disjoint if they share no outcome. For disjoint $E$ and $F$, $P(E \text{ or } F) = P(E) + P(F)$. That is exactly why $P(D)$ above was a plain sum: "gap" and "hazard" cannot both be the same column.

If the events overlap, adding double-counts the overlap, so subtract it once: $P(E \cup F) = P(E) + P(F) - P(E \cap F)$. On a die, let $E = \{2, 4, 6\}$ and $F = \{5, 6\}$. Then $P(E \cup F) = 3/6 + 2/6 - 1/6 = 4/6$, and you can check by listing: $\{2, 4, 5, 6\}$ has four outcomes.

Conditional probability

$P(E \mid F)$ reads "the probability of $E$ given that $F$ happened". It is defined as a ratio:

$$P(E \mid F) = \frac{P(E \cap F)}{P(F)}, \quad P(F) > 0$$

In words: throw away every outcome outside $F$, then ask what fraction of what is left also lies in $E$.

Two dice. Let $F$ be "the sum is 8" and $E$ be "the first die shows 6". There are 36 equally likely pairs. Five of them sum to 8: (2,6), (3,5), (4,4), (5,3), (6,2). Only (6,2) also has a first die of 6. So

$$P(E \mid F) = \frac{1/36}{5/36} = \frac{1}{5}$$

Compare $P(E) = 1/6$. Learning that the sum is 8 raised the odds of a 6 on the first die from 0.167 to 0.2.

Rearranging the definition gives the multiplication rule: $P(E \cap F) = P(F)\,P(E \mid F)$.

Independence

$E$ and $F$ are independent when knowing $F$ tells you nothing about $E$: $P(E \mid F) = P(E)$, or equivalently $P(E \cap F) = P(E)\,P(F)$. Two separate dice both showing 6 has probability $\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{36}$. The sum-is-8 example was not independent, since the conditional probability moved.

The product rule for a sequence

Apply the multiplication rule twice and you get the probability of three events in order:

$$P(E_1 \cap E_2 \cap E_3) = P(E_1)\,P(E_2 \mid E_1)\,P(E_3 \mid E_1 \cap E_2)$$

Say the first column is flat with probability 0.5, a gap follows a flat with probability 0.3, and a flat follows the pair (flat, gap) with probability 0.6. Then $P(\text{flat}, \text{gap}, \text{flat}) = 0.5 \times 0.3 \times 0.6 = 0.09$. The pattern extends to any length: each new factor is conditioned on everything before it. A Markov chain is the special case where each factor is allowed to look only at the single previous event.

Law of total probability

If $F_1, \dots, F_n$ are disjoint and together cover all of $\Omega$, then

$$P(E) = \sum_{i=1}^{n} P(E \mid F_i)\,P(F_i)$$

You split the world into cases, find the probability of $E$ in each case, and weight the cases by how likely they are.

Bayes' rule

Writing $P(E \cap F)$ two ways, as $P(F)\,P(E \mid F)$ and as $P(E)\,P(F \mid E)$, and dividing gives

$$P(F \mid E) = \frac{P(E \mid F)\,P(F)}{P(E)}$$

This flips a conditional around. You know how likely an observation is under each hidden cause; Bayes tells you how likely each cause is given the observation.

Worked example

A top-down chunk is a 10 by 10 grid of 100 cells. Each cell has a biome, forest or grass, and may or may not carry a tree decoration. The counts:

	tree	no tree	total
forest	25	15	40
grass	5	55	60
total	30	70	100

Pick one cell uniformly at random. Each count divided by 100 is a probability.

Conditional probability. $P(\text{tree} \mid \text{forest}) = \frac{25/100}{40/100} = \frac{25}{40} = 0.625$. And $P(\text{tree} \mid \text{grass}) = \frac{5}{60} \approx 0.083$.

Independence check. $P(\text{tree}) = 0.30$ but $P(\text{tree} \mid \text{forest}) = 0.625$. Not equal, so biome and tree are dependent, which is what you want from decoration rules.

Total probability. Split on biome: $$P(\text{tree}) = 0.625 \times 0.40 + 0.083 \times 0.60 = 0.25 + 0.05 = 0.30$$ It matches the table's 30 out of 100.

Bayes' rule. You see a tree. How likely is the cell forest? $$P(\text{forest} \mid \text{tree}) = \frac{0.625 \times 0.40}{0.30} = \frac{0.25}{0.30} \approx 0.833$$ Check against the table directly: 25 of the 30 tree cells are forest, and $25/30 \approx 0.833$. Bayes' rule is just that column of the table, written so it still works when you only have the conditionals and not the raw counts.

In a map generator

• Catalog. Tile weights in a tileset are probabilities of one tile per cell. The "safe or dangerous" event over columns is a union of outcomes.
• Layout. The product rule scores a whole level: the probability of a column sequence is the first column's probability times each conditional in turn. Bayes' rule is what a hidden Markov model does when it looks at emitted tiles and asks which section type produced them.
• Fill. Wave Function Collapse's tile weights, restricted to the tiles still allowed in a cell, are conditional probabilities: $P(\text{tile} \mid \text{neighbors so far})$.
• Regime over time. The chance a calm region turns contested this tick is $P(\text{contested next} \mid \text{calm now})$.

Every one of those is a table with one row per "given" and one column per "next". A Markov chain is nothing but a set of $P(\text{next tile} \mid \text{this tile})$ tables, one row per current tile, each row summing to 1. See Markov chains.

Common mistakes

• Adding probabilities of overlapping events. The total comes out above 1. Symptom: a sampler that never reaches its last option, or a "probability" of 1.3 in a debug print.
• Swapping $P(E \mid F)$ for $P(F \mid E)$. $P(\text{tree} \mid \text{forest})$ is 0.625 but $P(\text{forest} \mid \text{tree})$ is 0.833; if forest were rare the two would differ wildly. Symptom: an inference step labels every tree cell "forest" even in a map that is 95 percent grass.
• Assuming independence that is not there. Estimating "two gaps in a row" as $P(\text{gap})^2$ ignores that gaps may cluster or repel. Symptom: the predicted frequency of double gaps disagrees with what the generator actually produces.
• Conditioning on an impossible event. $P(F) = 0$ means dividing by zero. Symptom: NaN in a transition row for a state that never appeared in the training data.
• Editing one entry and not renormalizing. A row that sums to 1.1 is not a distribution. Symptom: the chain drifts toward whichever state got the extra mass.
• Reading 0.1 per column as "one hazard every ten columns". Independent draws cluster. Three hazards in a row has probability 0.001 per triple, but a 300-column level has almost 300 triples. Symptom: a playtester reports "hazards come in clumps" and the numbers say that is expected.

Cost

Nothing here is an algorithm, so the cost is storage. A table of $P(\text{next} \mid \text{this})$ over $N$ states holds $N^2$ numbers. Conditioning on the two previous states instead of one needs $N^3$. With $N = 6$ section types that is 36 versus 216, both trivial; with $N = 40$ tiles and three steps of history it is 2.5 million entries, most of which no training example ever touches, so the estimates become noise. That is the practical reason the one-step Markov assumption is the default.

Going further

• Random variables and distributions, for turning a row of probabilities into an actual sample.
• Markov chains, where the conditional table becomes a generator.
• Hidden Markov models, where Bayes' rule does real work.
• The chapters on conditional probability and independence in any first-year probability text.