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)