A repeating sequence can be described by a short instruction; a particular long sequence of fair coin flips usually cannot. Kolmogorov complexity captures this difference: it is the length of the shortest program that outputs a given object. It measures how compactly that particular object can be described, rather than how long the object looks. section 8.2
This is a different question from Shannon entropy, which concerns average uncertainty across outcomes from a source. Kolmogorov complexity concerns one specified outcome. In the same compression-based view, an algorithmically random sequence has no substantially shorter description than the sequence itself. Kolmogorov and Ray Solomonoff independently developed this central intuition. section 8.2
Algorithmic statistics extends the idea from describing data to explaining it. It seeks a simple model that captures structure without treating noise as structure. A useful explanation combines a concise model with data that look typical under that model; randomness deficiency describes how awkwardly the data fit. section 8.2.1
When an observation strains a model
A black swan is an awkward observation for the model “all swans are white,” giving it high randomness deficiency relative to that model. Under “swans can be black or white,” the observation is less surprising. A short explanation is not enough if it makes the observed data exceptional. section 8.2.1
