Binary deletion channel capacity approximated within one hundredth bit
Binary Deletion Channel Capacity to Within One Hundredth of a Bit
Information Theory
Summary
Communicating over a channel where some bits get randomly deleted is a hard problem, and exactly how much information you can send without errors is unknown. The authors provide a highly accurate estimate of this maximum reliable rate, called the capacity, with an error smaller than one hundredth of a bit per bit sent. They use computer-assisted proofs combining clever mathematical bounds and numerical checks over every possible deletion probability. Their approach also includes complete computational details and code so others can verify or build on their work.
What this means in practice
- •For network protocol designers: Design communication protocols that handle random bit deletions with nearly optimal information rates using certified bounds from this paper.
- •For data storage engineers: Improve coding strategies for storage systems where random deletions occur by applying close-to-optimal capacity estimates from this work.
Authors
Dimitris Papailiopoulos
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.