Technical Program

Paper Detail

Paper Title Large Deviations of Typical Random Codes
Paper IdentifierFR3.R8.1
Authors Ran Averbuch, Neri Merhav, Technion - Israel Institute of Technology, Israel; Albert Guillén i Fàbregas, ICREA & Universitat Pompeu Fabra, Spain and University of Cambridge, United Kingdom
Session Error Exponents II
Location Conseil, Level 5
Session Time Friday, 12 July, 14:30 - 16:10
Presentation Time Friday, 12 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract This work contains two main contributions concerning the large deviations behavior of randomly chosen fixed composition codes over a discrete memoryless channel (DMC). The first is an exponentially tight expression for the probability of randomly drawing a codebook that performs worse than the typical random coding (TRC) error exponent, which is proved to be exponentially small. The second is lower and upper bounds on the probability of randomly selecting a codebook that outperforms the TRC error exponent, which turn out to be double-exponentially small, suggesting that relatively good codebooks are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables.