Maximal input entropy for binary two-deletion and two-insertion channels
Abstract
Under uniform transmission, we determine the received binary words that maximize input entropy for two-deletion and two-insertion channels. For two deletions the maximizers are exactly the two alternating words at every positive received length. For two insertions the same conclusion holds from received length five onward; we give all smaller cases and exact maximal values. The proof combines an embedding-count identity organized by runs with strict convexity estimates, and a grouping of two-position deletion masks. For every insertion radius we give the complete positive embedding histogram of an alternating received word. We also determine its three-deletion histogram for every length, and certify all three-deletion maximizers through received length twelve and all three-insertion maximizers through length eighteen by exact integer comparison. These computations give precise three-error conjectures with their small-length exceptions.
Related
- Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels
- A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
- Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
- A New Upper Bound on the Binary Deletion Channel Capacity
- Binary Deletion Channel Capacity to Within One Hundredth of a Bit
BibTeX
@misc{ma2026maximal,
title = {{Maximal input entropy for binary two-deletion and two-insertion channels}},
author = {Haobo Ma and Wenlin Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01064},
eprint = {2611.01064},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01064},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Maximal input entropy for binary two-deletion and two-insertion channels
AU - Haobo Ma
AU - Wenlin Zhang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01064
UR - https://arxiv.org/abs/2611.01064
AB - Under uniform transmission, we determine the received binary words that maximize input entropy for two-deletion and two-insertion channels. For two deletions the maximizers are exactly the two alternating words at every positive received length. For two insertions the same conclusion holds from received length five onward; we give all smaller cases and exact maximal values. The proof combines an embedding-count identity organized by runs with strict convexity estimates, and a grouping of two-position deletion masks. For every insertion radius we give the complete positive embedding histogram of an alternating received word. We also determine its three-deletion histogram for every length, and certify all three-deletion maximizers through received length twelve and all three-insertion maximizers through length eighteen by exact integer comparison. These computations give precise three-error conjectures with their small-length exceptions.
ER -