Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
Abstract
The best constructive lower bounds on the capacity of the binary deletion channel come from random codes with independent run lengths, yet the two strongest such bounds, due to Drinea and Mitzenmacher and to Venkataramanan, Tatikonda, and Ramchandran, have been evaluated mainly for geometric or low-parameter run-length laws. We let a learning algorithm choose the run-length law freely, which raises three challenges. First, the Drinea-Mitzenmacher functional is an infinite sum over the ways deletions merge runs; we show that it depends on the law only through its mean, its full-deletion probability, and bilinear forms in the law and its renewal weights, so that gradients of truncations are exact and every truncation can only lower the bound. Second, for non-Markov inputs the output is no longer Markov and the Venkataramanan-Tatikonda-Ramchandran analysis breaks down; we show that the residual length of the current input run turns the output into a hidden Markov chain, which extends the bound to every finite-support law. Third, its correction term counts only output runs formed from three input runs; we prove a larger correction that accounts for every output run formed by several input runs, which improves the published bound even for truncated geometric laws. Certified by interval arithmetic, the new bounds exceed all previously published deterministic lower bounds at every tabulated deletion probability, by up to 6.86×10−3 bits per channel use and 6.8%. At large deletion probability the learned laws concentrate on run-length clusters with survivor counts about two standard deviations apart, like a pulse-amplitude constellation.
Related
- A New Upper Bound on the Binary Deletion Channel Capacity
- 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 bound for the two-way-assisted quantum capacity of the bosonic thermal-loss channel
- An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version
BibTeX
@misc{khodaiemehr2026improved,
title = {{Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs}},
author = {Hassan Khodaiemehr and Chen Feng and Tolga M. Duman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24908},
eprint = {2609.24908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24908},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
AU - Hassan Khodaiemehr
AU - Chen Feng
AU - Tolga M. Duman
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.24908
UR - https://arxiv.org/abs/2609.24908
AB - The best constructive lower bounds on the capacity of the binary deletion channel come from random codes with independent run lengths, yet the two strongest such bounds, due to Drinea and Mitzenmacher and to Venkataramanan, Tatikonda, and Ramchandran, have been evaluated mainly for geometric or low-parameter run-length laws. We let a learning algorithm choose the run-length law freely, which raises three challenges. First, the Drinea-Mitzenmacher functional is an infinite sum over the ways deletions merge runs; we show that it depends on the law only through its mean, its full-deletion probability, and bilinear forms in the law and its renewal weights, so that gradients of truncations are exact and every truncation can only lower the bound. Second, for non-Markov inputs the output is no longer Markov and the Venkataramanan-Tatikonda-Ramchandran analysis breaks down; we show that the residual length of the current input run turns the output into a hidden Markov chain, which extends the bound to every finite-support law. Third, its correction term counts only output runs formed from three input runs; we prove a larger correction that accounts for every output run formed by several input runs, which improves the published bound even for truncated geometric laws. Certified by interval arithmetic, the new bounds exceed all previously published deterministic lower bounds at every tabulated deletion probability, by up to 6.86×10^−3 bits per channel use and 6.8%. At large deletion probability the learned laws concentrate on run-length clusters with survivor counts about two standard deviations apart, like a pulse-amplitude constellation.
ER -