Metraipolis › archive › dc_bbe22e81019a
Universal Decoding via the Pairwise Error Probability — arXiv:2609.27887
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.27887
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:12:00.665Z
- SHA-256 of the archived text
1878cf91e5ba7678f81777b72bcf05ff3ecee9c724b2eddeaf86d69d16e95262- Stable URL of this page
https://metraipolis.com/documento/dc_bbe22e81019a
How to cite
Universal Decoding via the Pairwise Error Probability — arXiv:2609.27887 — arXiv (en), https://arxiv.org/abs/2609.27887 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bbe22e81019a (Metraipolis archive dc_bbe22e81019a, sha256 1878cf91e5ba7678f81777b72bcf05ff3ecee9c724b2eddeaf86d69d16e95262)
BibTeX
@misc{dcbbe22e81019a,
title = {Universal Decoding via the Pairwise Error Probability — arXiv:2609.27887},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.27887},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bbe22e81019a; sha256 1878cf91e5ba7678f81777b72bcf05ff3ecee9c724b2eddeaf86d69d16e95262},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.27887. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-24 in math.IT). Categorie arXiv: Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2609.27887 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T12:10:03.931Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).