 limit of large n, the result in Eq. (7.33) yields: (7.34) This result means that for strings of sufficiently long length n, the average "per bit" complexity (K(x|n)) /n has the source entropy H(X) as an upper bound. This can be equivalently stated: the average complexity of a random bit string, (K(x)n)), is upper-bounded by the entropy n(((H)(X) of the source that generates it. Note that the same conclusion is reached concerning nonbinary sources having M-ary symbols. 26 24 Since all events are independent, the probability of obtaining the string X = is p(x) = II" p(x) The expectation value (K(x)) thus means Exp(x)K(x), or the statistical average over all possibilities of strings X. 25 Jensen's inequality applies to concave functions, which have the property that they always lie below any chord (such as x,-x2, or log(x)). 26 T.M. Cover and J.A. Thomas, Elements of information theory (New York: John Wiley & Sons, 1991). 7.6 Exercises Next, we try to find a lower bound to (K(x|n)) /n. To each string x corresponds a minimal-length program q, which is able to output x from a universal Turing machine U, i.e., U(q,n) = X. It will be shown in Chapter 8 that the average length L = (1(q)) of such programs cannot exceed the source entropy, nH(X). Equivalently stated, the source's entropy is a lower bound of the mean program length, i.e., H(X) < L. It is also shown there that if the program length for each q is chosen such that 1(q) = - log p(x), then the equality stands, i.e., L = nH(X). Here, I shall conveniently use this property to complete the demonstration. As we know, the conditional complexity K(x)n) is precisely the shortest program length that can compute X. Thus, we have (K(x)n) (1(q)) = and (7.35) Combining the results in Eqs. (7.34) and (7.35), we obtain the double inequality (7.36) It is seen from the final result in Eq. (7.36) that as the string length n increases, the two boundaries converge to H(X), and thus the per-bit complexity (K(x/n)) /n and the source entropy H(X) become identical. For the purpose of