Binary deletion channel capacity

Suppose each bit of a message may disappear independently, without a marker showing where it was. How much information per sent bit can still be communicated reliably using very long messages? From 0101, keeping the first two bits gives 01; keeping the first and last bits gives the same 01. The receiver sees the survivors in order but cannot see which deletion happened.

A binary deletion channel deletes each bit with a fixed known probability d, between 0 and 1. Its capacity is the largest long-message information rate achievable as the chance of decoding the wrong message tends to zero. The unknown is the exact capacity for each deletion probability.[1] [2]

For a channel that independently removes bits without position markers, what is the exact best information per transmitted bit when block length grows and decoding error vanishes? A two-word codebook containing 000 and 111 has rate one-third, but an empty output leaves the message ambiguous; all three bits vanish with probability $d^3$. This is only a finite example of the tradeoff.

For fixed known $d\in(0,1)$, a length-n codebook has $M_n$ messages and rate $R_n=\log_2(M_n)/n$. Capacity $C(d)$ is the supremum of achievable asymptotic rates with error tending to zero. Inputs may have arbitrary dependence; the deletion events are independent. There is no efficient-decoding requirement in this information-theoretic target.[1] [2]

The repeated output 01 explains an ambiguity, but one short example does not determine the best long-message rate. The September 2026 preprint reports a numerical enclosure between lower and upper bounds. An enclosure of positive width improves approximation while leaving the exact capacity and its unrestricted input optimization unresolved.[1] [2]

The supremum allows arbitrary input dependence. Finite-block optimization, a selected input process or a nonzero-width enclosure does not establish the exact limiting rate.[2]

If a missing bit left a marker, the receiver would know the positions of every survivor. Deletion removes that alignment as well as the bit values: even a surviving 01 can have come from different positions. Capacity measures the information cost of having to recover a message despite both kinds of uncertainty.[1] [2]

The likelihood of an output depends on how many deletion patterns produce it, so hidden alignment connects the channel to the combinatorics of subsequences. Input dependence can change those output distributions, and the capacity optimization must include it. This explains why a best result for one chosen input process need not identify the unrestricted information limit.[1] [2]