Math Conjectures

Capacity of the binary deletion channel

OPENMajorExact constant problemProposed c. 1961 · Standard version

Canonical statement

Fix d∈(0,1)d\in(0,1). On input x=(x1,…,xn)∈{0,1}nx=(x_1,\ldots,x_n)\in\{0,1\}^n, independently delete each coordinate with probability dd and output the undeleted bits in their original order, without deletion markers. Let Mn(d,ε)M_n(d,\varepsilon) be the largest cardinality of a code C⊆{0,1}n\mathcal C\subseteq\{0,1\}^n for which some decoder has average error at most ε\varepsilon under a uniformly selected codeword. Determine, for every d∈(0,1)d\in(0,1),
Cdel(d)=lim⁡ε↓0lim sup⁡n→∞1nlog⁡2Mn(d,ε). C_{\mathrm{del}}(d)=\lim_{\varepsilon\downarrow0}\limsup_{n\to\infty}\frac1n\log_2 M_n(d,\varepsilon).
View source LaTeX
Fix \(d\in(0,1)\). On input \(x=(x_1,\ldots,x_n)\in\{0,1\}^n\), independently delete each coordinate with probability \(d\) and output the undeleted bits in their original order, without deletion markers. Let \(M_n(d,\varepsilon)\) be the largest cardinality of a code \(\mathcal C\subseteq\{0,1\}^n\) for which some decoder has average error at most \(\varepsilon\) under a uniformly selected codeword. Determine, for every \(d\in(0,1)\),
\[
C_{\mathrm{del}}(d)=\lim_{\varepsilon\downarrow0}\limsup_{n\to\infty}\frac1n\log_2 M_n(d,\varepsilon).
\]
INFO-002:[Dobrushin1967Sync][Mitzenmacher2009Deletion][RubinsteinCon2024Deletion]
Information theoryProbability theory

Notes

In the binary deletion channel with parameter d∈(0,1)d\in(0,1), each transmitted bit is deleted independently with probability dd, and the surviving bits arrive in their original order with no indication of where deletions occurred. This loss of synchronization makes the channel far harder to analyze than the erasure channel, where the positions of lost symbols are known. The problem, which took shape with the first systematic study of channels with synchronization errors around 1961, asks for the exact capacity Cdel(d)C_{\mathrm{del}}(d) at every deletion probability. Dobrushin proved Shannon-type coding theorems for such channels, so the capacity is well defined [Dobrushin1967Sync].

Decades of work have produced analytic and computer-assisted upper and lower bounds, together with asymptotics in the small-deletion regime; Mitzenmacher's survey collects the state of the field as of 2009 [Mitzenmacher2009Deletion], and the bounds have since been sharpened on both sides [RubinsteinCon2024Deletion]. No closed-form or otherwise exact expression is known at a general fixed deletion probability.

The problem remains open: unlike memoryless channels without synchronization errors, whose capacities follow from Shannon's single-letter formula, the deletion channel still awaits an exact characterization of its capacity.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.