o random events or sequences: the average size of a minimal-length program describing random events or sequences x from a source X is, indeed, approximately equal to the source entropy, or (K(x)) X 2 H(X). The conceptual convergence between algorithmic entropy and Shannon entropy is formalized in the next section. Kolmogorov complexity VS. Shannon's entropy As we have seen, complexity can be viewed as a measure of information, just like Shannon's entropy. The key difference is that complexity K(x) measures the information from an individual event x, while entropy H(X) measures the average information from an event source X. Despite this important conceptual difference, I have shown in the previous section the remarkable similarity existing between chain rules governing the two information measures. In this section, I shall formally establish the actual (however approximate) relation between Shannon's entropy and Kolmogorov complexity. Consider a source X of random events Xi with associated probabilities p(xi). For simplicity, we will first assume that the source is binary, i.e., the only two possible events are X1 = 0 or x2 = 1, thus p(x2) = 1 - p(x1). We can record the succession of n such events under the form of a binary string of length n, which we define as x(n) with i = 1,2. Algorithmic entropy and Kolmogorov complexity We can then estimate the upper bound of the conditional complexity of K(x)n) according to Eq. (7.21), which I repeat here with the new notations: (7.32) where (to recall) f(u) = -ulog2u-(1-u)log2(1- u). Next, we take the expectation value²4 of both sides in Eq. (7.32) to obtain: (K(x|n)) (7.33) = 2logn + c - nf (q) = 2logn + c + nH(X). To get the above result, we have made use of three properties. First, we have applied Jensen's inequality, which states that for any concave25 function F, we have (F(u)) < F((u)); Second, we made the substitution = q; Third, we have used the property F (q) = H(X), which is the definition of the entropy of a binary, random-event source X, see Eq. (4.13). In the