Universal Decoding via the Pairwise Error Probability
Abstract
We develop a theory of universal decoding built on the pairwise error probability (PEP) primitive of a companion paper. The PEP and its error spectrum are defined for an arbitrary decoding metric, and while raw metric values across a family share no common scale, the PEP supplies one. Universal decoding -- decoding well simultaneously against a whole family of metrics or channels -- becomes the problem of merging the per-metric spectra into a single rule, which we construct from a clipped inverse-PEP statistic. The construction rests on a Kraft-type inequality for decoding, valid for any input prior: per output, every metric canonicalizes into a conditional probability assignment on the codewords, and the merge is the normalized-maximum-likelihood envelope of the induced family. We prove the rule is random-coding universal (it loses only a vanishing rate relative to the best metric in the family, against every channel), show it is an asymptotic minimax/equalizer rule, and derandomize it: over a subexponential channel family a single deterministic code inherits the guarantee. For discrete memoryless channels the construction reduces to types and recovers the maximum-mutual-information decoder, its tilted variant for non-uniform memoryless input, and finite-state universal decoders. It extends to decoding with an erasure option (deterministically, uniformly over erasure margins) and, via a discretization of separable metric families, to continuous alphabets: for AWGN with deterministic interference it attains the matched-ML exponent up to an explicit typical-set cap, and for ISI channels the best exponent in a family of equalize-and-decode rules, under explicit assumptions on the equalizers and the channel spectrum and the same cap. Throughout, universality is a corollary of the PEP analysis rather than a separate theory.
Related
- Decoding Error Probability of the Random Code Ensemble over the Erasure Channel
- Universal Decoding for Unequal Error Protection
- Linking Error Estimation for Mean-Geometric Mean and Pairwise Haberman Linking Across Multiple Time Points in the 2PL Model
- Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
- An Upper Bound to the Undetected Error Exponent with Erasure Decoding at Positive Rates
BibTeX
@misc{elkayam2026universal,
title = {{Universal Decoding via the Pairwise Error Probability}},
author = {Nir Elkayam and Meir Feder},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27887},
eprint = {2609.27887},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27887},
}
RIS
TY - UNPB
TI - Universal Decoding via the Pairwise Error Probability
AU - Nir Elkayam
AU - Meir Feder
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.27887
UR - https://arxiv.org/abs/2609.27887
AB - We develop a theory of universal decoding built on the pairwise error probability (PEP) primitive of a companion paper. The PEP and its error spectrum are defined for an arbitrary decoding metric, and while raw metric values across a family share no common scale, the PEP supplies one. Universal decoding -- decoding well simultaneously against a whole family of metrics or channels -- becomes the problem of merging the per-metric spectra into a single rule, which we construct from a clipped inverse-PEP statistic. The construction rests on a Kraft-type inequality for decoding, valid for any input prior: per output, every metric canonicalizes into a conditional probability assignment on the codewords, and the merge is the normalized-maximum-likelihood envelope of the induced family. We prove the rule is random-coding universal (it loses only a vanishing rate relative to the best metric in the family, against every channel), show it is an asymptotic minimax/equalizer rule, and derandomize it: over a subexponential channel family a single deterministic code inherits the guarantee. For discrete memoryless channels the construction reduces to types and recovers the maximum-mutual-information decoder, its tilted variant for non-uniform memoryless input, and finite-state universal decoders. It extends to decoding with an erasure option (deterministically, uniformly over erasure margins) and, via a discretization of separable metric families, to continuous alphabets: for AWGN with deterministic interference it attains the matched-ML exponent up to an explicit typical-set cap, and for ISI channels the best exponent in a family of equalize-and-decode rules, under explicit assumptions on the equalizers and the channel spectrum and the same cap. Throughout, universality is a corollary of the PEP analysis rather than a separate theory.
ER -