A Pairwise-Error-Probability Framework for One-Shot Information Theory

Abstract

We develop a one-shot (finite-blocklength) channel-coding framework based on the pairwise error probability (PEP) of a decoder with randomized tie-breaking. The tie-breaking rule yields a probability-integral-transform identity: the induced error spectrum describes both random-coding achievability and exact fixed-code converse statements, for an arbitrary decoding metric. We derive two variational identities for metric-weighted tail functionals of the PEP, one through the Neyman-Pearson $\beta$-functional and one through a reverse channel, valid for an arbitrary metric. Under matched maximum-likelihood decoding they specialize to representations of the spectrum itself, which is then jointly convex in the testing level and the input prior; combined with the reverse-channel representation, this gives a linear program for the prior-optimized minimax meta-converse -- finite-dimensional in general and, for memoryless channels with fixed alphabets, of size polynomial in the blocklength after a type reduction. Prior optimization of the random-coding bound is formulated as a concave program over input distributions with an explicit gradient, solved by a direct first-order method. The framework recovers several classical one-shot bounds, including the random-coding union bound and minimax meta-converse of Polyanskiy-Poor-Verdu, the information-spectrum bounds of Han-Verdu, and the linear-programming converse of Matthews. Numerical examples on the AWGN and binary Z-channels illustrate the achievability-converse comparison and the effect of prior optimization.