The Space Too Big to Search

Counting asks one simple question: how many different things can happen? The answer explodes so fast that even a toy problem has more possibilities than there are atoms in the universe, far too many to ever try one by one. That explosion is the obstacle this whole class is about, and it is the reason a model learns by following a slope instead of testing every answer.

The answer you can’t reach by trying

Here is the most obvious idea in all of machine learning, and the first one to die. To find the best model, try every possible setting, score each one, and keep the best. It needs no calculus and no cleverness, and it cannot fail to find the best answer, because it looks at all of them. The only real question is how many settings there are to look at.

A model is a row of on/off switches, each switch one yes/no setting. A real model has billions of settings, each far finer than on/off, but a single switch is enough to find the pattern. One switch has two settings, off or on: two possibilities. Add a second switch and for each setting of the first the second can still be off or on, so the possibilities are off-off, off-on, on-off, on-on: four. Add a third and each of those four splits in two again, giving eight. Each switch added doubles the count.

That doubling is the whole engine, and it never lets up. After \(n\) switches the count is 2 multiplied by itself \(n\) times, written \(2^{n}\). Ten switches is already \(1{,}024\) combinations; twenty is more than a million. Each step doubles everything before it.

The number of settings is only half the story. For “try them all,” what matters is the time, and the time comes from one rule: each setting takes one check, the chip manages a billion checks (\(10^{9}\)) every second, so the time is the number of settings divided by a billion, read back in seconds, days, or years.

Every row is the same division; only the input grows. The last row is the one that should stop you: the \(1.3 \times 10^{21}\) seconds for 100 switches dwarf the age of the universe, about \(4 \times 10^{17}\) seconds, by a factor near 2,900. A faster chip does not rescue the plan either, because the rule is a division: doubling the checking speed halves the time, which removes a single switch from the wall, and the next switch added doubles the count straight back.

The most natural plan in the whole field is ruled out before we write a single line of training code, and the thing that rules it out is counting, the plain arithmetic of how many possibilities there are.

Before we can talk about the chance of an outcome, we have to answer something simpler and stranger: how many outcomes are there even?

Class 7 put probabilities on outcomes and multiplied them together, but it quietly assumed we already knew what the outcomes were and how many existed. Probability begins one step before that, with counting. This class builds the four tools that measure the size of a space of possibilities, each from first principles: the sample space, the multiplication principle, permutations, and combinations. Every one of them, the moment you push it, explodes.

The sample space: the set of everything that can happen

Counting measures the size of a space of possibilities, so before measuring one we have to name it. Flip a coin: exactly one of two things happens, heads or tails, and nothing else. That complete list, written as a set \(\{\text{heads}, \text{tails}\}\), is the sample space. Roll a die and it is \(\{1,2,3,4,5,6\}\). A set is a sample space when every possible outcome is in it and exactly one of them happens on any try, never none and never two at once. It is a set, the Class 6 object, and for counting the only thing we care about is its size, \(|S|\): a coin has \(|S| = 2\), a die \(|S| = 6\). Easy here; the whole class is about cases where the size is the hard part.

Now the hardware. When the ESP32 reads its light sensor, the voltage at the pin is a real number, a point on Unit 1’s infinite line, so you might expect infinitely many outcomes. But the real line does not fit in a machine. The analog-to-digital converter, the ADC, deals with that by quantizing: it keeps only a finite ladder of voltage levels and reports the nearest rung. The read is never a real number; it is always one rung of a finite ladder.

How many rungs? That is fixed by the bit count, and it is exactly the doubling from the opening. Each level is labelled by a pattern of bits, and with 12 bits, each off or on, there are \(2^{12} = 4096\) patterns, so 4096 levels. The 4096 is nothing special: an 8-bit ADC has \(2^{8} = 256\) levels, a 10-bit one \(2^{10} = 1024\), a 16-bit one \(2^{16} = 65{,}536\). The size of the sample space is just 2 raised to the bit count. For the 12-bit reads this series uses, that set is \(\{0, 1, 2, \ldots, 4095\}\), with \(|S| = 4096\).

This same 4096-element set is what the probability course will later spread sensor-noise probabilities across. We have done no probability yet, only counted the set it will live on.

In a real model that length is not an abstraction; it sets the model’s shape. An image classifier deciding among 1,000 categories has those 1,000 categories as its sample space, so the model ends in a layer of exactly 1,000 numbers, one probability per category. A language model is the same with a longer list: its sample space at every step is its whole vocabulary, so 50,000 possible next words means a final layer of 50,000 numbers, recomputed for every word it predicts. The size of the sample space is, quite literally, how many probabilities the model must produce and make add up to 1 at each step. It also sets how hard the task starts: with 50,000 possible next words and no knowledge yet, the fairest guess spreads probability evenly and gives each word \(1/50{,}000\), so the correct word begins with almost none, and learning is the slow work of moving probability off the 49,999 wrong words onto the right one. The size tells you two concrete things at once, how wide the output layer must be and how far it has to travel to become good, which is why you measure it first. From here the lists grow far too long to write out, and the rest of the class is the machinery for measuring their length without writing down a single entry.

The multiplication principle: counting in stages

One read has 4096 outcomes, but a single choice is rarely the whole story. Two sensor reads in a row, the thousands of settings inside a model, the many words of a sentence, each is several choices happening together, and what you want is the size of the whole combination.

When you put several choices together, how do their sizes combine into one?

The natural first guess is to add the sizes, and it is wrong. Suppose you own 3 shirts and 2 pairs of trousers. Adding would say \(3 + 2 = 5\) outfits. Count them directly instead: the red shirt pairs with either pair of trousers, 2 outfits; the blue shirt gives 2 more; the gray shirt gives 2 more; \(2 + 2 + 2 = 6\). You added the number 2 once for each of the 3 shirts, and adding the same number a fixed number of times is exactly multiplication, so the count is \(3 \times 2 = 6\), not 5. The sizes multiply.

When a thing is built from stages, and each stage has its own number of options, the size of the whole space is the options at each stage multiplied together.

This is the rule the opening used without naming it: each switch added was one more stage with 2 options, so the count multiplied by 2 every time. Two sensor reads work the same way: the first can be any of 4096 values, and for each one the second can again be any of 4096, which is \(4096 \times 4096 = 16{,}777{,}216\) possible pairs. It is the same multiplication that combined probabilities in Class 7, pointed at counts instead of chances: when the stages do not affect each other, the totals multiply.

Two conditions hide inside that word “multiply,” and each one decides what a later section looks like. The first is independence: each read still has all 4096 values open no matter what came before. The moment a choice removes options from the next stage, say you are dealt cards and cannot draw the same one twice, the clean product breaks into a product of shrinking numbers, which is the next section. The second is that this count is ordered: the pair \((12, 80)\) is counted separately from \((80, 12)\), because reading 12 then 80 is a different record from reading 80 then 12. Whether order should count is what separates the two sections after that, permutations and combinations. Here both conditions hold, so the plain product stands.

When the same choice repeats at every stage, the product becomes a power. Reading the sensor \(n\) times means 4096 options at each of \(n\) stages, which is \(4096^{n}\). In general, \(n\) independent stages with \(k\) options each give \(k^{n}\): a power is just the multiplication principle with one choice repeated. That one formula is behind everything so far. The opening’s switches were \(k = 2\) options over \(n\) stages, \(2^{n}\). The ADC was a single read of 12 bits, each with 2 options, \(2^{12} = 4096\).

This is very different from adding, and the difference is why the counts grow so fast. A hundred switches, counted one at a time, feel like a hundred small things. But each switch multiplies the running count instead of adding to it, so the total is \(2^{100}\), not 200. Addition accumulates; multiplication compounds, stacking a fresh factor on top of everything already counted. You can outrun a cost that adds up by buying a faster chip, but not one that keeps multiplying.

The same principle runs a routine chore in machine learning. Tuning a model means trying combinations of settings, and combinations multiply: 4 learning rates, 3 batch sizes, and 5 architectures is not 12 experiments but \(4 \times 3 \times 5 = 60\), and adding a single five-way knob makes it 300. A full grid search becomes impossible past a handful of knobs, which is why complete grids are rare and random or guided search is used instead. The repeated-power case is why a language model never lists its answers: a sentence of just 20 tokens drawn from a 50,000-word vocabulary is one of \(50000^{20}\) possibilities, about \(10^{94}\), more than the atoms in the universe. There is no table to pick from, so the model spreads a probability across that sample space and draws from it one token at a time. The size we just counted is the exact reason Class 7’s probabilities are unavoidable.

Permutations: when order matters

Every count so far let a stage reuse its options: both sensor reads could be 2731, both switches could be on. Now take the case the last section pointed at, where an option, once used, is gone. Line up \(n\) distinct things in a row, each used exactly once, and ask how many different orders are possible.

The multiplication principle still does the work; the one new feature is that the number of options shrinks by one at each stage, because each item placed is used up. The first slot can be filled by any of the \(n\) items. Once it is filled, the second slot has only \(n - 1\) left, the third \(n - 2\), and so on down to the final slot, where a single item remains. The stages still multiply, so the number of orders is \(n \times (n-1) \times (n-2) \times \cdots \times 1\). That product has its own name and symbol: \(n\) factorial, written \(n!\). For three letters A, B, C it is 3 choices for the first slot, 2 for the second, 1 for the last, so \(3 \times 2 \times 1 = 6\) orderings, and you can list every one.

If you fill only \(r\) of the slots instead of all \(n\), you stop the shrinking product after \(r\) factors, which is written \(n! / (n-r)!\) and called a permutation of \(r\) from \(n\). But the part that matters here is the full \(n!\), because it climbs faster than anything else in this course, fast enough to break the machine almost immediately. A factorial is a count, a whole number, so it lives in an integer type, and integer types have a ceiling (Class 4). A 32-bit unsigned integer tops out near \(4.3 \times 10^{9}\), and \(13!\) already sails past it. A 64-bit unsigned integer, the largest ordinary integer the chip has, tops out near \(1.8 \times 10^{19}\) and survives only to \(20!\). At \(21!\) the true answer is about \(5.1 \times 10^{19}\), the integer overflows, and the stored count is silently wrong.

The count of ways to arrange just 21 things does not fit in the widest integer the processor offers. Push to a shuffled deck of cards, \(52!\), and the number is about \(8 \times 10^{67}\): every properly shuffled deck in history has, with overwhelming probability, never appeared before and never will again.

Permutations are the count of orderings, and orderings show up wherever sequence matters: ranking a page of search results, ordering the words of an output, scheduling operations. The lesson is rarely that you should compute a permutation; it is that you must never try to enumerate one. The number of orderings of even a short list is past the machine’s largest integer, so any method that hopes to look at all the orders is dead on arrival, the same wall as the opening’s hundred switches.

Combinations: when order doesn’t matter

Permutations counted orderings, treating \(AB\) and \(BA\) as different. Often order carries no meaning. When you pick a mini-batch of \(k\) training examples from a dataset of \(N\), the batch \(\{3, 9, 40\}\) is the same batch as \(\{40, 3, 9\}\): you chose those same three either way. So the question becomes how many different groups there are, counting each once no matter which order you picked it in.

Begin with the ordered count, then correct it. Choosing \(r\) items from \(n\) with order is the permutation count, \(n! / (n-r)!\). The trouble is that this lists each real group more than once: the group \(\{A, B\}\) appears as both \(AB\) and \(BA\). How many times is each group counted? Exactly as many ways as its \(r\) members can be ordered, which is permutations applied to the group itself, \(r!\). So every group is counted \(r!\) times, the ordered count is \(r!\) times too large, and dividing by \(r!\) removes the duplication.

combinations = (the ordered count) ÷ (the orderings you double-counted) = n! / ( r! × (n-r)! )

Check it on small numbers. To choose 2 from \(\{A, B, C, D\}\) with order there are \(4 \times 3 = 12\) ordered pairs. Each unordered pair appears \(2! = 2\) times in that list (\(AB\) and \(BA\)), so the number of real pairs is \(12 / 2 = 6\).

This count is written \(C(n, r)\) and read “n choose r.” It grows just as wildly as the factorial it is built from. The number of 5-card poker hands is \(C(52, 5) = 2{,}598{,}960\), still countable. But the number of ways to choose 50 items from 1000 is about \(9 \times 10^{84}\), and the number of distinct 32-example mini-batches from a 60,000-image training set is around \(10^{117}\).

Combinations count the subsets, and machine learning is built on subsets: which examples land in a mini-batch, which neurons a dropout layer switches off this step, which rows go to training and which to test, which features a tree considers. The number of possible subsets is so enormous, that \(10^{117}\) of mini-batches, that no run could ever sweep through them. So training does not choose subsets by enumerating them; it draws them at random, trusting that a random sample stands in for a whole it can never list. The combination count is the proof that random sampling is not laziness but necessity.

Why the space is too big to search

Step back and put the four tools together. They all do the same thing: they measure the size of a space of possibilities, and that size, every time, is enormous beyond use. The opening’s hundred switches were \(2^{100}\). A model of just 40 bytes, each a value from 0 to 255, has \(256^{40} = 2^{320} \approx 2 \times 10^{96}\) possible settings, larger than the roughly \(10^{80}\) atoms in the observable universe. The space of a tiny model is bigger than the physical universe, and the number describing its size would itself overflow the machine, exactly as \(21!\) did.

Two consequences follow, and between them they shape almost everything the course does next.

The first: you cannot find the best model by trying every model. The space is not merely large, it is unsearchable, and no hardware closes that gap. So training does the opposite of enumeration. It starts at one setting, measures which direction lowers the loss, and steps to a better neighbor, over and over, never seeing more than a thread through the space. That is gradient descent, and the reason it exists at all is the counting in this class. It is also where Class 9 picks up: a search that cannot list its options can only move step by step and hope it settles, which is a question about sequences and limits.

The second: you cannot list every outcome in order to reason about it either. A 20-token sentence is one of \(10^{94}\); you will never tabulate them. So instead of a list you carry a probability spread over the sample space, the move from Class 7, which lets you say something about a whole space you can never walk through one element at a time. Counting is what tells you the walk is hopeless, and probability is the tool you reach for once you accept that.

Counting is not a side errand before the real mathematics; it is the proof that the two pillars of the field are necessary rather than optional. Because the space of models is unsearchable, learning must be an iterative climb instead of a search, which is optimization. Because the space of outcomes is unlistable, reasoning must be done with probabilities instead of enumeration, which is statistics. Every later class stands on the fact this one establishes: the things that can happen are too many to try.

What to carry out of Class 8

The sample space is the set of every outcome that can occur, and the first thing to know about it is its size. The multiplication principle says independent stages multiply, so \(n\) choices of \(k\) options give \(k^{n}\), the same multiply that combined Class 7’s probabilities. Permutations count orderings and equal \(n!\), which overflows a 64-bit integer at \(n = 21\). Combinations count subsets, \(n! / (r!\,(n-r)!)\), by dividing out the orderings you do not care about.

The next class takes up the consequence directly. If a model can only be found by stepping, setting by setting, never seeing the whole space, then the question becomes whether that stepping ever arrives. That is sequences, limits, and convergence, the mathematics of a process that moves one step at a time and the conditions under which it settles.

See if it stuck

Eight questions, all answerable from this post. Tap an answer for an immediate verdict and the reason.