Counting, and the size of the spaces involved

Probability starts as division

The oldest definition of a probability is a fraction: the number of outcomes you care about, divided by the number of outcomes there are, when all outcomes are equally likely. Rolling a six on a fair die is 1/6. Drawing a heart from a shuffled pack is 13/52.

The definition is only useful if you can count both numbers, so counting comes first.

The three counting rules

Multiplication. If one choice has m options and an independent second choice has n, together they have m × n. A four-digit PIN has 10 × 10 × 10 × 10 = 10,000 possibilities. Add a fifth digit and it becomes 100,000; each extra position multiplies rather than adds, which is why password length beats password complexity.

Permutations — order matters. The number of ways to arrange k items chosen from n:

P(n, k) = n! / (n - k)!

The number of ways to rank the top 3 of 10 candidates is 10 × 9 × 8 = 720.

Combinations — order does not matter. The number of ways to choose k from n disregarding order:

C(n, k) = n! / (k! (n - k)!)

Choosing any 3 of 10 candidates is 720 / 6 = 120, because each set of three was counted 3! = 6 times in the permutation count.

Worked example with a use: how many ways can you pick 2 features from 20 to test for an interaction? C(20, 2) = 190. Test all of them at the usual 5 per cent significance level and you should expect about 9 or 10 to look significant purely by chance. That arithmetic is a whole lesson later in this course, and it starts here.

The number that should change how you think about language

Now apply multiplication to text. A model with a 50,000-token vocabulary generating a 20-token sentence has

50,000^20 = about 10^94

possible outputs. For scale, there are roughly 10^80 atoms in the observable universe.

Two consequences follow immediately, and both matter.

No model has memorised the space. It could not have. The training data contains perhaps 10^13 tokens, which is a vanishing fraction of 10^94. Whatever a language model is doing, exhaustive lookup is not available to it, and any explanation of the form "it just retrieves what it saw" fails on arithmetic alone. What it does instead is compress the structure of the space into weights, which is why it can produce fluent sentences nobody has ever written.

Exhaustive search is impossible for generation. You cannot score all continuations and choose the best. Decoding must be greedy or sampled, one token at a time, which is why the sequence a model produces is generally not the highest-probability sequence available. Beam search widens the search a little — keeping perhaps 4 or 8 candidates — and even that is a rounding error against 10^94.

The birthday problem, because your intuition is wrong

Twenty-three people in a room. What is the chance two share a birthday? Most people guess a few per cent. The answer is 50.7 per cent.

The mechanism is that you are not comparing one person against the others; you are comparing every pair. With 23 people there are C(23, 2) = 253 pairs, and 253 chances at 1-in-365 each adds up quickly. Compute it as the complement:

P(no match) = (365/365)(364/365)(363/365) ... (343/365) = 0.493
P(at least one match) = 1 - 0.493 = 0.507

This is not a party trick. It is the reason hash collisions appear far earlier than the hash space suggests — a 64-bit hash starts colliding around 2^32 items, not 2^64 — and the reason near-duplicate documents in a corpus are far more common than a per-document duplicate rate implies. Whenever your quantity of interest is about pairs, the count grows with the square.

Counting with the computer

The formulas are in the standard library, and you should not implement factorials yourself.

from math import comb, perm, factorial
print(comb(20, 2))            # 190
print(perm(10, 3))            # 720
print(comb(50, 25))           # 126,410,606,437,752

That last number is worth staring at. Choosing half of a set of 50 has more than 126 trillion possibilities, which is why "just try all the subsets of features" is never a plan.

The limit of the counting definition

Everything above assumes equally likely outcomes, and almost nothing in machine learning has them. The tokens a model might emit are not equally likely; the documents in a corpus are not equally likely queries. The counting definition is where probability starts historically and where it stops being sufficient almost immediately.

What replaces it is the idea already introduced in this course: a probability as a stated degree of belief, judged by calibration over many cases. Counting remains useful for sizing a space and for knowing when exhaustive anything is off the table. It is a tool for the denominators, not for the beliefs.

The rule to keep

Multiply for independent choices, use combinations when order does not matter, and check the size of the space before proposing to search it. When the count involves pairs, expect coincidences far sooner than the raw space size suggests.