Binary Deletion Channel Capacity to Within One Hundredth of a Bit
Abstract
The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.
Related
- A New Upper Bound on the Binary Deletion Channel Capacity
- Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
- Interference-Free Capacity of a Binary Interference Channel with Causal Observation
- Maximal input entropy for binary two-deletion and two-insertion channels
- The Capacity of the Relay Channel
BibTeX
@misc{papailiopoulos2026binary,
title = {{Binary Deletion Channel Capacity to Within One Hundredth of a Bit}},
author = {Dimitris Papailiopoulos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19412},
eprint = {2609.19412},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19412},
}
RIS
TY - UNPB
TI - Binary Deletion Channel Capacity to Within One Hundredth of a Bit
AU - Dimitris Papailiopoulos
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19412
UR - https://arxiv.org/abs/2609.19412
AB - The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.
ER -