Suppose I have a binary function $f$, with a million input bits and one output bit. The function is uniformly randomly chosen from all such functions - i.e. for each of the $2^{1000000}$ possible inputs $x$, we flipped a coin to determine the output $f\left(x\right)$ for that particular input.

Now, suppose I know $f$, and I know all but 50 of the input bits - i.e. I know 999950 of the input bits. How much information do I have about the output?

Answer: almost none. For almost all such functions, knowing 999950 input bits gives us $\sim \frac{1}{2^{50}}$  bits of information about the output. More generally, If the function has $n$ input bits and we know all but $k$, then we have $o\left(\frac{1}{2^k}\right)$ bits of information about the output. (That’s “little $o$” notation; it’s like big $O$ notation, but for things which are small rather than things which are large.) Our information drops off exponentially with the number of unknown bits.

Proof Sketch

With $k$ input bits unknown, there are $2^k$ possible inputs. The output corresponding to each of those inputs is an independent coin flip, so we have $2^k$ independent coin flips. If $m$ of those flips are 1, then we assign a probability of $\frac{m}{2^k}$ that the output will be 1.

As long as $2^k$ is large, Law of Large Numbers will kick in, and very close to half of those flips will be 1 almost surely - i.e. $m\approx$ $\frac{2^k}{2}$. The error in this approximation will (very quickly) converge to a normal distribution, and our probability that the output will be 1 converges to a normal distribution with mean $\frac{1}{2}$ and standard deviation $\frac{1}{2^{k/2}}$. So, the probability that the output will be 1 is roughly $\frac{1}{2}\pm \frac{1}{2^{k/2}}$.

We can then plug that into Shannon’s entropy formula. Our prior probability that the output bit is 1 is $\frac{1}{2}$, so we’re just interested in how much that $\pm \frac{1}{2^{k/2}}$ adjustment reduces the entropy. This works out to $o\left(\frac{1}{2^k}\right)$ bits.

Why Is This Interesting?

One core idea of my work on abstraction is that noise very quickly wipes out almost all information; only some very-low-dimensional summary is relevant “far away”. This example shows that this sort of thing is not unusual, but rather “the default”: for almost all random functions, information drops off exponentially with the number of unknown bits. In a large system (i.e. a function with many inputs), ignorance of even just a few bits is enough to wipe out essentially-all information. That’s true even if we know the vast majority of the bits.

A good intuitive example of this is the “butterfly effect”: the flap of a butterfly’s wings could change the course of a future hurricane, because chaos. But there’s an awful lot of butterflies in the world, and the hurricane’s path is some complicated function of all of their wing-flaps (and many other variables too). If we’re ignorant of even just a handful of these flaps, then almost all of our information about the hurricane’s path is probably wiped out. And in practice, we’re ignorant of almost all the flaps. This actually makes it much easier to perform Bayesian reasoning about the path of the hurricane: the vast majority of information we have is basically-irrelevant; we wouldn’t actually gain anything from accounting for the butterfly-wing-flaps which we do know.