Saddle Point in the Minimax Converse for Channel Coding

• Published in: IEEE transactions on information theory 2013-05, Vol.59 (5), p.2576-2595
• Main Author: Polyanskiy, Y.
• Format: Article
• Language: English
• Subjects: Applied sciences; Binary hypothesis testing; Channel coding; channel symmetries; Coding theory; Coding, codes; converse theorem; Decoding; error exponents; Exact sciences and technology; Extraterrestrial measurements; Information theory; Information, signal and communications theory; Memoryless systems; minimax; Optimization; Probability distribution; Shannon theory; Signal and communications theory; Telecommunications and information theory; Testing
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2012.2236382

A minimax metaconverse has recently been proposed as a simultaneous generalization of a number of classical results and a tool for the nonasymptotic analysis. In this paper, it is shown that the order of optimizing the input and output distributions can be interchanged without affecting the bound. In the course of the proof, a number of auxiliary results of separate interest are obtained. In particular, it is shown that the optimization problem is convex and can be solved in many cases by the symmetry considerations. As a consequence, it is demonstrated that in the latter cases, the (multiletter) input distribution in information-spectrum (Verdú-Han) converse bound can be taken to be a (memoryless) product of single-letter ones. A tight converse for the binary erasure channel is rederived by computing the optimal (nonproduct) output distribution. For discrete memoryless channels, a conjecture of Poor and Verdú regarding the tightness of the information spectrum bound on the error exponents is resolved in the negative. Concept of the channel symmetry group is established and relations with the definitions of symmetry by Gallager and Dobrushin are investigated.