skip to content

Under Kolmogorov complexity, is a gigabyte grown from a 200-byte seed random, given that no coder shrinks it?

level: seniorimportance: should knowfreq 34%

answer

  1. randomness as a property of the object
  2. the seed is the description
  3. coders search a narrow family
  4. close to its own length means random
  5. no short description found is not none exists

basics

~20 s

No. Its Kolmogorov complexity is at most the seed plus the generator, a few hundred bytes, so a very short description exists. The coders tried failed to find it, which is not the same as no description existing.

solid answer

~50 s

Randomness in this sense is a property of the string, and it means **incompressibility**: `s` is random when `K(s)` is close to `|s|`, that is, when no program much shorter than the string itself prints it. The generated fixture fails that test by construction - the seed plus the generator's code is a program that prints all of it, so `K` is a few hundred bytes against a gigabyte of output. That the byte distribution looks flat and general-purpose coders make no headway says only that those coders search a narrow family of descriptions - repeats, back-references, symbol frequencies - and the generator's description is not in that family. A gigabyte of captured physical noise is the opposite case: no short description is believed to exist, so it is plausibly random, but the coder failures are evidence for that, never proof.

code

pseudocode · 7 lines
pseudocode
# a complete description of the fixture, in a few hundred bytes
state = SEED                  # 200 bytes of constants
count = 1000000000            # one gigabyte of output
while count > 0:
    state = mix(state)        # fixed, published mixing step
    emit(low_byte(state))
    count = count - 1

go deeper

for a junior

Hold on to one fact: a huge file made by a small program has a small description, no matter how scrambled it looks. Looks and description length are different things.

for a middle

Explain why a general-purpose coder misses the generator: it searches repeats and symbol frequencies, and a generator is built to leave none. Then state the definition of randomness as complexity close to the string's own length.

for a senior

Draw the practical conclusion in a review: a generated fixture corpus carries one seed's worth of content, so argue from provenance rather than from an incompressibility observation, and refuse benchmark claims measured on generated noise.

for a principal

The judgement is what evidence your organisation accepts for a data-quality claim. Since the property is untestable, require a documented production path for anything labelled random, and treat compression results as a hint, not a certificate.

## Two gigabytes that look the same Put two files side by side. One is emitted by a published generator from a 200-byte seed. One is a capture of physical noise. Byte histograms match, every general-purpose coder makes no headway on either, and a viewer shows the same grey confetti. Under Kolmogorov complexity they are opposites, because the measure asks a question no inspection of the bytes answers: **how short is the shortest program that prints this?** | Property | Seeded gigabyte | Captured-noise gigabyte | |---|---|---| | Shortest known description | seed plus generator, a few hundred bytes | none shorter than the file | | `K(s)` | tiny relative to `|s|` | believed close to `|s|` | | Random in this sense | no | plausibly yes | | Coders shrink it | no | no | | Reproducible from a note | yes, from the seed | no | The last two rows are the whole lesson: what a coder does is the same on both, and what the measure says is completely different. ## Incompressibility as the definition of randomness The usual notion of randomness is about a **process** - a fair coin, an unbiased source. That definition cannot be applied to a file sitting on disk, because any fixed string is a possible output of a fair process. Descriptive complexity gives a definition for **a single object**: call `s` *k-incompressible* when `K(s) >= |s| - k`, and call it random when no program meaningfully shorter than the string itself produces it. This definition has the properties you want from one: - It is a statement about the object, so you can apply it to the file in front of you rather than to the story of where it came from. - Almost every string satisfies it. Because there are fewer than `2^(n-k)` descriptions shorter than `n - k` bits and `2^n` strings of length `n`, fewer than one string in `2^k` can be compressed by `k` bits at all - fewer than one in 1024 by ten bits. - It matches the intuitions: a string of a million zeros is not random under it, because 'print a million zeros' is a very short program, no matter how improbable that particular string is under a fair coin. And it has one property you must respect: it is **not testable**. You cannot run a procedure on a file and have it certify incompressibility. ## Why the generated file defeats the coders anyway A general-purpose coder does not search programs. It searches a restricted family of descriptions: repeated substrings within a window, symbol frequencies, runs, simple residuals after a transform. A good generator is built precisely so that its output has none of those surface regularities - that is what 'looks random' means operationally. So the short description exists, is even public, and lies entirely outside the space the coder explores. That is the general shape of the trap. The observable is 'my tools found nothing'. The claim people make is 'nothing is there'. The gap between them is unbounded, and a seeded generator is the cheapest way to make that gap a gigabyte wide. ## What this changes in practice 1. **A fixture corpus grown from one seed carries one seed's worth of content.** However many gigabytes you generate, the set of behaviours it can exercise is the generator's, and the tests it can possibly distinguish are limited accordingly. Volume is not variety. 2. **'It is incompressible, so it is good random data' is not an argument.** The right argument is provenance: say how the bytes were produced, because that is the fact the measure cannot recover from the bytes. 3. **Benchmarking a coder on generated 'random' data measures almost nothing.** You have handed it a file you know it cannot shrink, and the only result is that it did not shrink it. 4. **Storage decisions still work on the practical side.** If nothing you have shrinks the file, it costs a gigabyte, whatever its complexity. The measure changes what you may *claim*, not what the disk holds. ## The claim you are allowed to make For the generated file you can make a positive claim and back it: a short program exists, here it is, its complexity is at most a few hundred bytes plus a constant. For the captured file you can make only a negative observation - nothing found a shorter description - and the honest phrasing keeps the possibility open. Interviewers ask this leaf almost entirely to see whether the candidate says 'looks random', 'passes the tests' and 'no coder shrinks it' as if the three were one claim.

  • If the seed were captured from physical noise instead of chosen, would the output become random in this sense?
    Only up to the seed's own size. The description is still generator plus seed, so the complexity of a gigabyte of output is bounded by roughly 200 bytes plus a constant. A random seed makes the file unpredictable to someone who lacks it; it does not make the file hard to describe.
  • Does a statistical test suite passing on the output tell you anything about its complexity?
    No. Such suites check surface properties - bit balance, run lengths, correlations - and a good generator is designed to satisfy them. Passing every one of them is consistent with the file having a few hundred bytes of descriptive complexity.
  • Can a string be highly compressible and still look structureless to every human reading it?
    Routinely. The digits of a computable constant, or the output of a short arithmetic recurrence, show no pattern a reader can name, yet each has a description of a few dozen characters. Human perception of pattern is another narrow search, and it misses the same descriptions coders do.

A dealing machine that always starts from the same stacked deck deals a hand every player at the table calls shuffled, while the dealer can reproduce the whole evening from one starting note. How random it looks to the room says nothing about how short the note is.

saying these in an interview costs you the question

  • Calls a file random because coders cannot shrink it
  • Treats passing statistical tests as evidence about descriptive complexity
  • Says complexity depends on how the bytes look
  • Assumes a large generated corpus covers more behaviour than its seed
  • Confuses unpredictable-without-the-seed with hard-to-describe