Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: An anti-inductive sequence, published by Viliam on August 14, 2024 on LessWrong.

I was thinking about what would it mean for a sequence of bits to be "anti-inductive". It probably is a concept that is already known (as a rule of thumb, if I can think about it, someone probably already wrote a paper on it 50 years ago), but I haven't heard about it.

*

Some sequences are predictable and can be compressed. These two concepts are deeply related, because if you can successfully predict the next part of the sequence, you don't need to actually write it down; hence compression. A completely random sequence of bits cannot be compressed or predicted.

There is a simple mathematical proof that some sequences cannot be compressed, although it doesn't say which ones. For any natural number N, there are more sequences of size exactly N, than sequences of size smaller than N. Therefore no program can generate a unique sequence shorter than N for any input sequence of size N.

*

Things get more complicated if we consider the caveat that although random sequences in general cannot be compressed, true randomness means that sometimes we accidentally get a sequence that can be compressed -- for example, with probability 1/2ᴺ we get a sequence of N zeroes, and it would sound silly to argue that we can't compress that!

The solution to this paradox is that if we decide to compress only some selected sequences, then we need to add an extra bit of information specifying whether this sequence was compressed or not. Otherwise, if we see a sequence of bits saying (in binary) "a sequence of thousand zeroes", we wouldn't know whether the intended value is this very sequence of bits taken literally, or the sequence of thousand zeroes.

One bit doesn't seem like much, but actually most sequences cannot be compressed, so the cost of adding one extra bit to each of them outweighs the occasional space we would save by compressing the ones we can.

But still, if I needed a random sequence of bits to use e.g. as a password for something important... and by a miracle I generated a sequence of N zeroes... I would probably feel quite uncomfortable to use it, and would simply generate a new one. Is this a good security practice, or not? Because from certain perspective, by removing the "insufficiently random" sequences from the pool of possible choices, I am reducing the size of the pool, which... kinda makes it easier to guess the password?

Something similar actually happened to me once. I used a mobile application that asked me to create a 4-digit PIN. So I typed 4 random digits, and the application said: "nope, you cannot use the same digit multiple times in the PIN, that is not secure". So I typed 4 random digits again, and the application said: "nope, you cannot use an ascending sequence of digits, that is not secure". So I typed 4 random digits yet again, and this time the application was finally satisfied.

But it felt funny that the more "security checks" the application uses, the more limited is the choice of possible PINs. There are only 10000 possible combinations of 4 digits to start with; I wonder how far an overzealous security department could reduce that number. In a hypothetical extreme case, we would be left with only one possible choice of PIN -- certainly the most secure one that no one could possibly guess! The holy grail of information security.

*

Okay, back to the sequences of bits. Imagine that we are trying to create not just any random sequence, but the single most random, most unpredictable sequence ever! Suppose the length of the sequence is not specified in advance, so we just keep generating bits one by one, for as long as necessary.

What we could do is create a predictor -- an algorithm that looks at the previously generated bits, tries to find all possible patterns in them and pr...