Error exponent
In information theory, the error exponent of a channel code or source code over the block length of the code is the rate at which the error probability decays exponentially with the block length of the code. Formally, it is defined as the limiting ratio of the negative logarithm of the error probability to the block length of the code for large block lengths. For example, if the probability of error formula_1 of a decoder drops as formula_2, where formula_3 is the block length, the error exponent is formula_4. In this example, formula_5 approaches formula_4 for large formula_3 . Many of the information-theoretic theorems are of asymptotic nature, for example, the channel coding theorem states that for any rate less than the channel capacity, the probability of the error of the channel code can be made to go to zero as the block length goes to infinity. In practical situations, there are limitations to the delay of the communication and the block length must be finite. Therefore, it is important to study how the probability of error drops as the block length go to infinity. Error exponent in channel coding. For time-invariant DMC's. The channel coding  theorem states that for any ε > 0 and for any rate less than the channel capacity, there is an encoding and decoding scheme that can be used to ensure that the probability of block error is less than ε > 0 for sufficiently long message block "X". Also, for any rate greater than the channel capacity, the probability of block error at the receiver goes to one as the block length goes to infinity. Assuming a channel coding setup as follows: the channel can transmit any of formula_8 messages, by transmitting the corresponding codeword (which is of length "n ). Each component in the codebook is drawn i.i.d. according to some probability distribution with probability mass function Q". At the decoding end, maximum likelihood decoding is done. Let formula_9 be the formula_10th random codeword in the codebook, where formula_10 goes from formula_12 to formula_13. Suppose the first message is selected, so codeword formula_14 is transmitted. Given that formula_15 is received, the probability that the codeword is incorrectly detected as formula_16 is: The function formula_18 has upper bound for formula_20 Thus, Since there are a total of "M" messages, and the entries in the codebook are i.i.d., the probability that formula_14  is confused with any other message is formula_13 times the above expression. Using the union bound, the probability of confusing formula_14 with any message is bounded by: for any formula_26. Averaging over all combinations of formula_27: Choosing formula_29 and combining the two sums over formula_30 in the above formula: Using the independence nature of the elements of the codeword, and the discrete memoryless nature of the channel: Using the fact that each element of codeword is identically distributed and thus stationary: Replacing "M" by 2 and defining probability of error becomes "Q" and formula_36 should be chosen so that the  bound is tighest. Thus, the error exponent can be defined as Error exponent in source coding. For time invariant discrete memoryless sources. The source coding theorem states that for any formula_38 and any discrete-time i.i.d. source such as formula_39 and for any rate less than the entropy of the source, there is large enough formula_40 and an encoder that takes formula_40 i.i.d. repetition of the source, formula_42, and maps it to formula_43 binary bits such that the source symbols formula_42 are recoverable from the binary bits with probability at least formula_45. Let formula_46 be the total number of possible  messages. Next map each of the possible source output sequences to one of the messages randomly using a uniform distribution and independently from everything else. When a source is generated the corresponding message formula_47 is then transmitted to the destination. The message gets decoded to one of the possible source strings. In order to minimize the probability of error the decoder will decode to the source sequence formula_48 that maximizes formula_49, where formula_50 denotes the event that message formula_51 was transmitted. This rule is equivalent to finding the source sequence formula_48 among the set of source sequences that map to  message formula_51 that maximizes formula_54. This reduction follows from the fact that the messages were assigned randomly and independently of everything else. Thus, as an example of when an error occurs, supposed that the source sequence formula_55 was mapped to message formula_56 as was the source sequence formula_57. If formula_58 was generated at the source, but formula_59 then an error occurs. Let formula_60 denote the event that the source sequence formula_61 was generated at the source, so that formula_62 Then the probability of error can be broken down as formula_63 Thus, attention can be focused on finding an upper bound  to the formula_64. Let formula_65 denote the event that the source sequence formula_66 was mapped to the same message as the source sequence formula_61 and that formula_68. Thus, letting formula_69 denote the event that the two source sequences formula_70 and formula_71 map to the same message, we have that and using the fact that formula_73 and is independent of everything else have that A simple upper bound for the term on the left can be established as for some arbitrary real number formula_76 This upper bound can be verified by noting that formula_77 either equals formula_78 or formula_79 because the  probabilities of a given input sequence are completely deterministic. Thus, if formula_80 then formula_81 so that the inequality holds in that case. The inequality holds in the other case as well because for all possible source strings. Thus, combining everything and introducing some formula_83, have that Where the inequalities follow from a variation on the Union Bound. Finally applying this upper bound to the summation for formula_85 have that: Where the sum can now be taken over all formula_71 because that will only increase the bound. Ultimately yielding that Now for simplicity let formula_89 so that formula_90 Substituting this new  value of formula_91 into the above bound on the probability of error and using the fact that formula_71 is just a dummy variable in the sum gives the following as an upper bound on the probability of error: The term in the exponent should be maximized over formula_97 in order to achieve the highest upper bound on the probability of error. Letting formula_98 see that the error exponent for the source coding case is: References. R. Gallager, "Information Theory and Reliable Communication", Wiley 1968