Second-Order Converses via Reverse Hypercontractivity
share
A strong converse shows that no procedure can beat the asymptotic (as blocklength n→∞) fundamental limit of a given information-theoretic problem for any fixed error probability. A second-order converse strengthens this conclusion by showing that the asymptotic fundamental limit cannot be exceeded by more than O(1√(n)). While strong converses are achieved in a broad range of information-theoretic problems by virtue of the `blowing-up method'---a powerful methodology due to Ahlswede, Gács and Körner (1976) based on concentration of measure---this method is fundamentally unable to attain second-order converses and is restricted to finite-alphabet settings. Capitalizing on reverse hypercontractivity of Markov semigroups and functional inequalities, this paper develops the `smothing-out' method, an alternative to the blowing-up approach that does not rely on finite alphabets and that leads to second-order converses in a variety of information-theoretic problems that were out of reach of previous methods.
READ FULL TEXT