id: 00617057 dt: j an: 00617057 au: Li, Ming; Vitányi, Paul M.B. ti: Statistical properties of finite sequences with high Kolmogorov complexity. so: Math. Syst. Theory 27, No.4, 365-376 (1994). py: 1994 pu: Springer-Verlag, New York la: EN cc: ut: Kolmogorov complexity; Martin Löf randomness ci: li: doi:10.1007/BF01192146 ab: Kolmogorov complexity provides us with the means to assign randomness to an individual binary sequence, whereas this notion doesn’t make sense in a standard probabilistic interpretation. Random sequences are those sequences whose descriptive complexity is about as large as possible (i.e. not much shorter than their length). Martin Löf randomness characterizes the random sequences as being those sequences which pass all known or still to be discovered statistical tests. The two notions are known to be equivalent in the sense that the Martin Löf random sequences are precisely those whose prefixes have about maximal Kolmogorov complexity. Consequently, the Kolmogorov random sequences can be shown to obey all standard statistical properties like having a frequence of zeros and ones converging to 1/2 and normality with respect to larger block sizes. In this paper, the authors obtain sharp bounds measuring the degree to which these statistical properties must hold for an individual Kolmogorov random sequence. Results obtained indicate that the frequency of zeros and ones indeed converges to 1/2 but not too fast (since otherwise the sequence can’t be random). Also the block size up to which normality holds is determined. Random sequences are shown to have constant runs of zeros or ones which are larger than humans consider to be “random”. The proofs are based on a simple technique: if some property is “easy” to describe, and not “too many” sequences have this property, an individual sequence can be described by a code describing its length, the property, and its index in the lexicographical ordering of all strings of that length sharing the property. This code must exceed in length the required lower bound for the Kolmogorov complexity since otherwise the string is in fact not random. rv: P.van Emde Boas (Amsterdam)