[35] Let x be a finite binary sequence of length n with fj =

x1 + x2 + ··· + xj for 1 ≤ j ≤ n. Show that there exists a constant c > 0 such that for all m ∈ N , all  > 0, and all x, C(x|n, fn) > log n fn

− log(m4) + c implies max m≤j≤n 



fj j − fn n 



< .
Comments. This result is called Fine’s theorem. This is an instance of the general principle that high probability of a computable property translates into the fact that high complexity implies that property. (For infinite sequences this principle is put in a precise and rigorous form in Theorem 2.5.6.) Fine’s theorem shows that for finite binary sequences with high Kolmogorov complexity, given the length and the number of ones, the fluctuations of the relative frequencies in the initial segments is small. Since we deal with finite sequences, this is called apparent convergence. Since virtually all finite binary strings have high complexity (Theorem 2.1.3), this explains why in a typical sequence produced by random coin throws the relative frequencies appear to converge or stabilize. Apparent convergence occurs because of, and not in spite of, the high irregularity (randomness or complexity) of a data sequence. Conversely, the failure of convergence forces the complexity to be less than maximal. Source: [T.L. Fine, IEEE Trans. Inform. Theory, IT-16(1970), 251–257]; also [R. Heim, IEEE Trans. Inform. Theory, IT-25(1979), 557–
566].