A New Upper Bound on the Binary Deletion Channel Capacity
Abstract
We prove that the capacity of the binary deletion channel satisfies C(d)≤ (1−d)/4 for every 13/20≤ d<1. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from d=13/20 to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit O(log n/n) corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.
Related
- Binary Deletion Channel Capacity to Within One Hundredth of a Bit
- An Improved Upper Bound on the Capacity of the Primitive Diamond Relay Channel
- Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
- Improved lower bound for the two-way-assisted quantum capacity of the bosonic thermal-loss channel
- Interference-Free Capacity of a Binary Interference Channel with Causal Observation
BibTeX
@misc{soysal2026upper,
title = {{A New Upper Bound on the Binary Deletion Channel Capacity}},
author = {Özgür Soysal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13351},
eprint = {2609.13351},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13351},
note = {CC0},
}
RIS
TY - UNPB
TI - A New Upper Bound on the Binary Deletion Channel Capacity
AU - Özgür Soysal
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.13351
UR - https://arxiv.org/abs/2609.13351
AB - We prove that the capacity of the binary deletion channel satisfies C(d)≤ (1−d)/4 for every 13/20≤ d<1. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from d=13/20 to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit O(log n/n) corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.
ER -