it has the minimal expected word length for , then (Shannon 1948): Where denotes the expected value operator. Proof: Source coding theorem Given is an i.i.d. source, its time series is i.i.d. with entropy in the discrete-valued case and differential entropy in the continuous-valued case. The Source coding theorem states that for any , i.e. for any rate larger than the entropy of the source, there is large enough and an encoder that takes i.i.d. repetition of the source, , and maps it to binary bits such that the source symbols are recoverable from the binary bits with probability of at least . Proof of Achievability. Fix some , and let The typical set, , is defined as follows: The Asymptotic Equipartition Property (AEP) shows that for large enough , the probability that a sequence generated by the source lies in the typical set, , as defined approaches one. In particular, for sufficiently large , can be made arbitrarily close to 1, and specifically, greater than (See AEP for a proof). The definition of typical sets implies that those sequences that lie in the typical set satisfy: Note that: The probability of a sequence being drawn from is greater than . , which follows from the left hand side (lower bound) for . , which follows from upper bound for and the lower bound on the total probability of the whole set . Since bits are enough to point to any string in this set. The encoding algorithm: The encoder checks if the input sequence lies within the typical set; if yes, it outputs the index of the input sequence within the typical set; if not, the encoder outputs an arbitrary digit number. As long as the input sequence lies within the typical set (with probability at least ), the encoder doesn't make any error. So, the probability of error of the encoder is bounded above by . Proof of Converse. The converse is proved by showing that any set of size smaller than (in the sense of exponent) would cover a set of probability bounded away from . Proof: Source coding theorem for symbol codes For let denote the word length of each possible . Define , where is chosen so that . Then where the second line follows from Gibbs' inequality and the fifth line follows from Kraft's inequality: so . For the second inequality we may set