ies, therefore, differ by u with respect to H(X), and the absolute difference in Eq. (13.24) is equal to u/k. For long sequences (k >> U > 1), the result can be made arbitrarily small. The above analysis leads us to a most general definition of a typical sequence: given a message source X with entropy H(X) = f(q) and an arbitrary small number E, any sequence x of length k, which satisfies (13.25) is said to be "typical, within the error E. Such typical sequences are roughly equiproba- ble with probability 2-kH(X) and their number is roughly 2kH(X) The property of typical sequences, as defined in Eq. (13.25), is satisfied with arbitrary precision as the sequence length k becomes large.10 Alternatively, we can rewrite Eq. (13.25) in the form (13.26) which shows the convergence between the upper and lower bounds of the probability p(x) as k increases. Note that the typical set does not include the high-probability sequences (such as, in our example, the sequences with high numbers of 0 bits). However, any sequence x selected at random is likely to belong to the typical set, since the typical set (roughly) has 2kH(X) members out of (exactly) 2k sequence possibilities. The probability p that x belongs to the typical set is, thus, (roughly): (13.27) which increases as H(X) becomes closer to unity 0.5).11 Shannon's channel coding theorem In this section, I describe probably the most famous theorem in information theory, which is referred to as the channel coding theorem (CCT), or Shannon's second theorem. 12 The 10 This property is also known as the asymptotic equipartition principle (AEP). This principle states that given a source X of entropy H(X), any outcome x of the extended source Xk is most likely to fall into the typical set roughly defined by a uniform probability p(x) = 2-kH(X) 11 In the limiting case H(X) = 1, q = 0.5, p = 1, all possible sequences belong to the typical set; they are all strictly equiprobable, but generally they do not have the same number kq = k/2 of 1 and 0 bits. Such a case corresponds to 