Metraipolis › archive › dc_9dcaacdf6019

Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs — arXiv:2609.24908

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.24908
License (as archived)
CC0-1.0
Archived
2026-10-09T21:57:30.096Z
SHA-256 of the archived text
96869189fff837972e5cda8aff6344b42b78c23181731046872d4527c963a54f
Stable URL of this page
https://metraipolis.com/documento/dc_9dcaacdf6019

How to cite

Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs — arXiv:2609.24908 — arXiv (en), https://arxiv.org/abs/2609.24908 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9dcaacdf6019 (Metraipolis archive dc_9dcaacdf6019, sha256 96869189fff837972e5cda8aff6344b42b78c23181731046872d4527c963a54f)
BibTeX
@misc{dc9dcaacdf6019,
  title = {Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs — arXiv:2609.24908},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24908},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9dcaacdf6019; sha256 96869189fff837972e5cda8aff6344b42b78c23181731046872d4527c963a54f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24908. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\times10^{-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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.24908 — 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-09T21:44:07.494Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).