On the Gaussianity of Kolmogorov Complexity of Mixing Sequences

Let $K(X_1,\dots ,X_n)$ and $H(X_n\mathrm{\mid }{X}_{n-1},\dots ,X_1)$ denote the Kolmogorov complexity and Shannon’s entropy rate of a stationary and ergodic process $\{X_i{\}}_{i=-\mathrm{\infty }}^{\mathrm{\infty }}$. It has been proved that $$\frac{K(X_1,\dots ,X_n)}{n}-H(X_n\mathrm{\mid }{X}_{n-1},\dots ,X_1)\to 0,$$ almost surely. This paper studies the convergence rate of this asymptotic result. In particular, we show that if the process satisfies certain mixing conditions, then there exists $\sigma <\mathrm{\infty }$ such that $$\sqrt{n}(\frac{K(X_{1:n})}{n}-H(X_0\mathrm{\mid }{X}_1,\dots ,X_{-\mathrm{\infty }})){\to }_{d}N(0,{\sigma }^2)\mathrm{.}$$ Furthermore, we show that under slightly stronger mixing conditions one may obtain non-asymptotic concentration bounds for the Kolmogorov complexity.