Instituto de Ciencias y Tecnología de Materiales, University of Havana (IMRE), San Lazaro y L, CP 10400 La Habana, Cuba.
Chaos. 2013 Jun;23(2):023118. doi: 10.1063/1.4808251.
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.
随机序列具有最高的熵率。可以使用 Lempel-Ziv 复杂度来估计遍历源的熵率，但只有在无限极限下才能达到确切的熵率值。我们证明了与普遍看法相反，有限长度的典型随机序列无法达到最大的 Lempel-Ziv 复杂度。我们讨论了对于有限长度，可以使用定义明确的生成算法构建最大 Lempel-Ziv 序列，这使得它们的 Kolmogorov-Chaitin 复杂度较低，与随机性完全相反。我们将讨论到，在这种意义上，Lempel-Ziv 测度不如 Kolmogorov-Chaitin 复杂度通用，因为它可以被足够智能的代理所欺骗。事实证明，对于某些无理数的二进制展开就是这种情况。最大 Lempel-Ziv 序列诱导了一种归一化，对于多个源可以很好地估计熵率，同时对于所有序列长度保持有界的值，使其成为当前使用的其他归一化方案的替代方案。
