Kolmogorov complexity
Relation to entropy

For dynamical systems, entropy rate and algorithmic complexity of the trajectories are related by a theorem of Brudno, that the equality K (x; T) = h (T) {\displaystyle K(x;T)=h(T)} holds for almost all x {\displaystyle x}.

It can be shown that for the output of Markov information sources, Kolmogorov complexity is related to the entropy of the information source. More precisely, the Kolmogorov complexity of the output of a Markov information source, normalized by the length of the output, converges almost surely (as the length of the output goes to infinity) to the entropy of the source.

Theorem. (Theorem 14.2.5) The conditional Kolmogorov complexity of a binary string x 1: n {\displaystyle x_{1:n}} satisfies 1 n K (x 1: n | n) ≤ H b (1 n ∑ i x i) + log n 2 n + O (1 / n) {\displaystyle {\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)} where H b {\displaystyle H_{b}} is the binary entropy function (not to be confused with the entropy rate).
combination:two_responses