Capacity of the Binary Deletion Channel

Capacity of the Binary Deletion Channel

Definitions and mathematical statement

For deletion probability $0<d<1$, a binary word $x^n$ is sent through independent deletions, and the output is the surviving subsequence in its original order. Neither terminal is told the deleted positions. A code has a uniform message $M$, an $n$-bit encoding, and a decoder acting on the variable-length output $Y$. Define \[ C_{\mathrm{del}}(d)=\sup\{R:\exists\text{ codes with }\liminf_n n^{-1}\log_2|\mathcal M_n|\ge R, \ \Pr(\widehat M\ne M)\to0\}. \] Determine this capacity exactly for every $d$. Rates are per input bit, not per surviving bit. A finite-precision numerical approximation, or substituting erasures whose positions are known, does not answer the exact deletion-channel question.

Formulation and concept references: [S1].

Short English statement

What is the exact reliable information rate when each transmitted bit independently disappears and the receiver sees only the surviving ordered subsequence?

Research attempt

Current frontier.

Dobrushin's synchronization-channel theorem identifies operational capacity with a limit of finite-block mutual-information maxima; it does not reduce the channel to a one-letter memoryless formula. [S1], Theorem 3 and the finite-block discussion. The September 2026 manuscript attached as the catalogue's status source is by Dimitris Papailiopoulos. Its Theorem 2.1 reports a uniform approximation within one hundredth of a bit using finite certificates and an explicit numerical arithmetic model. That is not an exact capacity formula; its full numerical certificate package has not been independently rerun here. [S2]; [E1], Sections 2 and 12--13. The attempt below uses the established information-limit theorem, and then derives its own boundary-loss and two-bit calculations.

Attack route.

An independent-bit input need not maximize information once positions are hidden. Finite-block optimization can be done exactly for small blocks, but its output is an upper bound unless boundary ambiguity is accounted for. A third route would optimize the asymptotic uncertainty of block boundaries rather than just their entropy. We pursue the second route, keeping the boundary term explicitly, and test whether one optimally correlated two-bit input could plausibly single-letterize the answer. The calculation gives an exact finite-block formula but leaves a nonzero synchronization gap.

Attempt.

1. A finite-block upper and lower enclosure. Write $q=1-d$ and \[ F_n(d)=\max_{P_{X^n}}I(X^n;Y),\qquad h_n(d)=H(\operatorname{Bin}(n,q)), \] where information and entropy are in bits. Compactness of the input simplex and continuity of mutual information give a maximum. Revealing the output boundary between input blocks of lengths $m,n$ produces two separate channel outputs and can only increase information. Conditional output entropy is additive given the two input blocks, while joint output entropy is at most the sum of the two marginal entropies. Hence $F_{m+n}\le F_m+F_n$. The information-limit theorem in [S1] then gives \[ C_{\mathrm{del}}(d)=\lim_{n\to\infty}\frac{F_n(d)}n =\inf_n\frac{F_n(d)}n. \] This is used as an established representation, not advertised as the requested exact evaluable solution.

For a lower comparison, use $k$ independent input blocks with an optimizing law for $F_n$. Let $L_i$ be the surviving length of block $i$, let $L=(L_1,\ldots,L_k)$, and let $Y$ be the unmarked concatenation. With $L$ revealed, the separate outputs can be parsed and have total mutual information $kF_n$. The lengths are independent of the input, so \[ I(X^{kn};Y)=kF_n-I(X^{kn};L\mid Y) \ge kF_n-H(L\mid Y). \] The total surviving length $S=\sum_iL_i$ is already a function of $Y$. Independence of the binomial lengths gives \[ H(L\mid Y)\le H(L\mid S)=kh_n-h_{kn}. \] Therefore $F_{kn}\ge kF_n-kh_n+h_{kn}$. Dividing by $kn$ and letting $k\to\infty$, using $0\le h_{kn}\le\log_2(kn+1)$, proves \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-38-3a-65-6e-63-6c-6f-73-75-72-65} \max\left\{0,\frac{F_n(d)-h_n(d)}n\right\} \le C_{\mathrm{del}}(d)\le\frac{F_n(d)}n. \end{equation} All boundaries in this argument are side information in a proof, not information supplied to a deletion-channel receiver. The enclosure width is at most $\log_2(n+1)/n$, but computing $F_n$ requires optimizing over $2^n$ inputs. A convergent approximation scheme is not a closed or otherwise new exact capacity characterization.

2. Solve the two-bit optimization exactly. Complementing every input and output bit, or reversing their orders, preserves the two-bit channel. Mutual information is concave in the input law. Averaging over these symmetries therefore permits an optimum of the form \[ P(00)=P(11)=a/2,\qquad P(01)=P(10)=(1-a)/2, \qquad0\le a\le1. \] Condition on the output length $K$, which is independent of the input. If $K=2$, the input is fully observed, giving $1+H_2(a)$ bits. If $K=1$, the observed bit is fair; conditional on a constant input it is deterministic, and conditional on a nonconstant input it is fair. The mutual information in this case is therefore $a$. If $K=0$, it is zero. Consequently \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-38-3a-74-77-6f-62-69-74} F_2(d)=\max_{0\le a\le1} \{q^2[1+H_2(a)]+2dq\,a\}. \end{equation} The derivative of $H_2$ is $\log_2((1-a)/a)$, so strict concavity gives \[ a_* =\frac1{1+2^{-2d/q}},\qquad F_2(d)=q^2\left[1+\log_2(1+2^{2d/q})\right]. \] An equivalent numerically stable expression is \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-38-3a-63-6c-6f-73-65-64} F_2(d)=q^2+2dq+q^2\log_2(1+2^{-2d/q}). \end{equation} For every $d>0$, $a_*>1/2$: constant adjacent bits are favored over the independent fair-bit law. At $d=1/2$ one gets $a_*=4/5$ and \[ \frac{F_2(1/2)}2=\frac{1+\log_2 5}{8} \approx0.4152410119, \] whereas the independent law gives $3/8$ bits per input bit on this two-bit channel. The exact formula, not the decimal, is the result. It is an upper bound on unrestricted asymptotic capacity, not an achievable rate established by this calculation.

3. The boundary penalty is real, not a proof artifact to discard. For fixed input $0101$, divided into blocks $01\mid01$, an observed output $01$ can arise with surviving block lengths $(2,0)$ or $(0,2)$; it can also arise with lengths $(1,1)$ for suitable deletion masks. Each event has positive probability for $0<d<1$. Thus the output does not determine the boundaries, even when the input happens to be known. Assuming that $Y$ automatically decomposes into independent optimized two-bit outputs is false.

More precisely the relevant information loss is $I(X^{kn};L\mid Y)$, not always the whole $H(L\mid Y)$. The entropy bound in (30006798:enclosure) deliberately overestimates it. An improvement could exploit correlations between input patterns and boundary ambiguity, but must do so uniformly for an actual chosen source and then match a converse for all sources. Merely choosing the two-bit optimizer independently at block boundaries does not make those boundaries recognizable to a decoder.

The single-bit case is the clearest limiting test. It gives $F_1=q$, the binary erasure rate, because a receiver knows whether that single input disappeared. Reusing $q$ as the capacity of a long deletion channel silently restores the missing positions. The two-bit formula already shows a stricter upper bound than $q$ for $0<d<1$, since \[ F_2=2q-q^2+q^2\log_2(1+2^{-2d/q})<2q. \] This strict inequality is exact, but it still does not determine the remaining capacity gap.

Stress test.

The output length is included in $Y$; no entropy for that already observed total length is charged twice. The subtraction $kh_n-h_{kn}$ uses independent blocks in the lower-bound construction, whereas the upper bound allows arbitrary correlated inputs. The finite-block maxima are information quantities, not finite codebook rates with equiprobable messages; their operational connection uses Dobrushin's theorem. No interchange of an optimization and an infinite-block limit has been assumed without that framework.

The 2026 approximation claim is identified as a manuscript result with numerical premises, not as an independently certified exact solution. The companion script enumerates the two-bit transition probabilities and checks the analytic formula numerically at selected parameters; it does not certify all numerical tables in [E1].

Outcome.

Outcome: Exploratory approach with unresolved gap.

The attempt derives a boundary-entropy enclosure and solves the two-bit input optimization exactly, including a strict finite-block improvement over the erasure upper bound. It identifies the unremoved boundary information loss and checks endpoint behavior through an expression valid for all $0<d<1$. No novelty claim is made for the finite-block method or its classical coding-theorem input.

A resolution would require matching asymptotic achievable and converse rates, or a genuinely evaluable exact formula beyond merely restating the multi-letter optimization. Neither is supplied here; the exact capacity function remains undetermined by this attempt.

Sources

• S1 Cheraghchi and Ribeiro, An Overview of Capacity Results for Synchronization Channels. https://arxiv.org/html/1910.07199v2. Catalogue formulation source.
• S2 Status source for Capacity of the Binary Deletion Channel. https://arxiv.org/abs/2609.19412. Catalogue research/status reference; not a proof endorsement.
• E1 D. Papailiopoulos, Binary Deletion Channel Capacity to Within One Hundredth of a Bit, arXiv:2609.19412v1, 16 September 2026, Theorem 2.1, Section 2.1 (capacity model) and Sections 12--13 (arithmetic assumptions and numerical checks). https://arxiv.org/html/2609.19412v1. Consulted 27 September 2026. This specifies the actual manuscript behind [S2]; its reported approximation is not an exact-capacity theorem, and its numerical package was not independently rerun here.