Inequalities for Shannon Entropy and Kolmogorov Complexity

AbstractIt was mentioned by Kolmogorov (1968, IEEE Trans. Inform. Theory14, 662–664) that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropy and for Kolmogorov complexity. It turns out that (1) all linear inequalities that are valid for Kolmogorov complexity are also valid for Shannon entropy and vice versa; (2) all linear inequalities that are valid for Shannon entropy are valid for ranks of finite subsets of linear spaces; (3) the opposite statement is not true; Ingleton's inequality (1971, “Combinatorial Mathematics and Its Applications,” pp. 149–167. Academic Press, San Diego) is valid for ranks but not for Shannon entropy; (4) for some special cases all three classes of inequalities coincide and have simple description. We present an inequality for Kolmogorov complexity that implies Ingleton's inequality for ranks; another application of this inequality is a new simple proof of one of Gács–Körner's results on common information (1973, Problems Control Inform. Theory2, 149–162)