it. Assume first that the string has k bits of value 1, thus n - k bits of value 0, with 0<k<n. We can then create a catalog of all possible strings containing k 1s, and index them in some arbitrary order. For instance, with n = 4 and k = 2, we have X1 = 1100, x2 = 1010, X3 = 1001, X4 = 0101, X5 = 0011, X6 = 0110. Having this catalog, we can simply define any string Xi according to some index i. Given n and k, the range of index values i is CK n!/[k!(n - k)!], which represents the number of ways to assign k 1s into n bit positions. The program q defining x must contain information on both k and i. As we have seen, it takes 2 log k + 2 bits to define k by repeating its bits, with a two-bit delimiter at the end (noting that fancier compression algorithms of shorter lengths also exist). The second number i can be defined after the delimiter, but without repeating bits, which occupies a size of log Ch bits. We must also include a generic program, which, given k, generates the catalog. Assume that its length is c, which is independent of k. The total length of the program q is, therefore, 1q(k,n)l =2logk+2+logChc=2logk+logC = (7.17) 7.4 Kolmogorov complexity The next task is to evaluate log CK. Using Stirling's formula,20 it is possible to show that for sufficiently large n:21 (7.18) where the function f is defined by f(u) = logu-(1-u)log(1-u) and, as usual, all logarithms are in base 2. The function f(k/n) is defined over the interval 0<k/n < 1. To include the special case where all bits are identical (k/n = 0 or k/n = =1) we can elongate the function by setting f(0)=f(1) =0,which represents the analytical limit of f(y) for real y. We note that f(u) is the same function as defined in Eq. (4.14) for the entropy of two complementary events. Its graph is plotted in Fig. 4.7, showing a maximum of f(1/2)= 1 for = 1/2. Substituting Eq. (7.18) into Eq. (7.17), we, thus, obtain: (7.19) where C" is a constant. Consistently, this program length represents an upper bound to the complexity of string X with k 1s, i.e., (7.20) In 