of the asymptotic equipartition property (AEP). Another style can be found in information theory texts using error exponents. Both types of proofs make use of a random coding argument where the codebook used across a channel is randomly constructed - this serves to make the analysis simpler while still proving the existence of a code satisfying a desired low probability of error at any data rate below the channel capacity. By an AEP-related argument, given a channel, length strings of source symbols , and length strings of channel outputs , we can define a jointly typical set by the following: We say that two sequences and are jointly typical if they lie in the jointly typical set defined above. Steps In the style of the random coding argument, we randomly generate codewords of length n from a probability distribution Q. This code is revealed to the sender and receiver. It is also assumed that one knows the transition matrix for the channel being used. A message W is chosen according to the uniform distribution on the set of codewords. That is, . The message W is sent across the channel. The receiver receives a sequence according to Sending these codewords across the channel, we receive , and decode to some source sequence if there exists exactly 1 codeword that is jointly typical with Y. If there are no jointly typical codewords, or if there are more than one, an error is declared. An error also occurs if a decoded codeword doesn't match the original codeword. This is called typical set decoding. The probability of error of this scheme is divided into two parts: First, error can occur if no jointly typical X sequences are found for a received Y sequence Second, error can occur if an incorrect X sequence is jointly typical with a received Y sequence. By the randomness of the code construction, we can assume that the average probability of error averaged over all codes does not depend on the index sent. Thus, without loss of generality, we can assume W = 1. From the joint AEP, we know that the probability that no jointly typical X exists goes to 0 as n grows large. We can bound this error probability by . Also from the joint AEP, we know the probability that a particular and the resulting from W = 1 are jointly typical is . Define: