B09
Prediction, coding, and learning
When does shorter code length predict better classification on new examples?

I.07 / GNOSIS
How short a description will reproduce a sequence, and how does the choice of description language change that estimate?
Algorithmic information asks how briefly an individual object can be described by a program in a specified computational language. Vitányi's account makes the incomputability issue central: a compressor's output is a practical description, while the shortest possible description is a different mathematical object. This distinction lets compression remain useful without treating a file-size comparison as an exact measurement of intrinsic complexity.
Compare a thousand repeated characters, a repeated sentence, and a fixed pseudorandom sequence using the same compressor and settings. Record both input and output byte counts. Repeat with very short files, where headers can outweigh any saving; a larger compressed file can then reflect format overhead rather than deeper structure.
Reproduce one compression comparison with two algorithms and explain which conclusion survives the change in representation.
These models isolate a mechanism you can vary. Their assumptions define the part of this topic they can illuminate.
Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.
Compare symbol frequencies with the ordering that a code can exploit.
The first sweep changes the probability of A while drawing each symbol independently. The other three symbols share the remaining probability.
As one symbol dominates, the observed symbol entropy falls. Huffman codes use short words for frequent symbols; the comparison excludes headers and the codebook.
The second sweep gives all four new draws equal probability and increases repetition. Long runs reward run-length coding, even when a symbol histogram cannot describe the dependence.
Method. The histogram gives an order-zero Shannon entropy. Huffman coding repeatedly joins the two least frequent branches to build a prefix code. The run-length format stores a two-bit symbol and an eight-bit count; counts run from 1 to 255, and a longer run uses another packet.
Paul M. B. Vitányi / arXiv · Formal complexity and limits of computing shortest descriptions; practical compressors are distinct objects.
B09
When does shorter code length predict better classification on new examples?