On the non-randomness of maximum Lempel Ziv complexity sequences of finite size

Abstract

Random sequences attain the highest entropy rate. The estimation of entropy rate for an ergodic source can be done using the Lempel Ziv complexity measure yet, the exact entropy rate value is only reached in the infinite limit. We prove that typical random sequences of finite length fall short of the maximum Lempel-Ziv complexity, contrary to common belief. We discuss that, for a finite length, maximum Lempel-Ziv sequences can be built from a well defined generating algorithm, which makes them of low Kolmogorov-Chaitin complexity, quite the opposite to randomness. It will be discussed that Lempel-Ziv measure is, in this sense, less general than Kolmogorov-Chaitin complexity, as it can be fooled by an intelligent enough agent. The latter will be shown to be the case for the binary expansion of certain irrational numbers. Maximum Lempel-Ziv sequences induce a normalization that gives good estimates of entropy rate for several sources, while keeping bounded values for all sequence length, making it an alternative to other normalization schemes in use.

References in corpus (1)

• Randomness, Information, and Complexity

Cited by in corpus (8)

• Deep learning generalizes because the parameter-function map is biased towards simple functions
• Transfer Entropy Rate Through Lempel-Ziv Complexity
• Phenomenology of coupled non linear oscillators
• Complexity-entropy analysis at different levels of organization in written language
• Two halves of a meaningful text are statistically different
• Quantifying Local Randomness in Human DNA and RNA Sequences Using Erdos Motifs
• Indistinguishability between quantum randomness and pseudo-randomness under efficiently calculable randomness measures
• Properties of maximum Lempel-Ziv complexity strings