Exact capacity of the binary deletion channel
Fix $d \in (0,1)$. The binary deletion channel takes an input word $x_1 \cdots x_N \in \{0,1\}^N$, deletes each bit independently with probability $d$, and outputs the surviving bits in their original order. The receiver is not told which positions were deleted, and there is no feedback. The capacity $C(d)$ is the supremum of the rates $R$ for which there are binary block codes of length $N$ with at least $2^{NR}$ codewords whose probability of decoding error, averaged over a uniformly chosen message and over the deletions, tends to zero as $N \to \infty$; rate is measured per input bit.
Dobrushin proved that $$C(d) = \lim_{N \to \infty} \frac{1}{N} \max_{X} I(X; Y),$$ the maximum taken over distributions of the input $X$ on $\{0,1\}^N$, with $Y$ the corresponding output. $C(d)$ is at most $1 - d$, the capacity of the binary erasure channel, and Mitzenmacher and Drinea proved $C(d) \ge (1-d)/9$ for every $d$. Kanoria and Montanari computed the three leading terms of an expansion of $C(d)$ for small $d$, and Pinto and Ribeiro, by a parallelized Blahut–Arimoto computation, obtained $C(d) \le 0.3578(1-d)$ for all $d \ge 0.64$.
Problem. Determine $C(d)$ for every $d \in (0,1)$.
Source: Classical: Dobrushin (1967) proved the coding theorem for channels with synchronization errors that defines the capacity as a limit; the exact value is posed as open in the surveys of Mitzenmacher (2009) and Cheraghchi and Ribeiro (2021).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- PR
- Keywords
- AIM Open Applied Problems, channel capacity, deletion channels, synchronization errors
References
@article{dobrushin1967,
author = {Dobrushin, R. L.},
title = {Shannon's theorems for channels with synchronization errors},
journal = {Problemy Peredachi Informatsii},
volume = {3},
number = {4},
year = {1967},
pages = {18--36},
}
@article{mitzenmacher2009,
author = {Mitzenmacher, Michael},
title = {A survey of results for deletion channels and related synchronization channels},
journal = {Probab. Surv.},
volume = {6},
year = {2009},
pages = {1--33},
doi = {10.1214/08-PS141},
}
@article{cheraghchi2021,
author = {Cheraghchi, Mahdi and Ribeiro, Jo{\~a}o},
title = {An overview of capacity results for synchronization channels},
journal = {IEEE Trans. Inform. Theory},
volume = {67},
number = {6},
year = {2021},
pages = {3207--3232},
doi = {10.1109/TIT.2020.2997329},
eprint = {1910.07199},
archivePrefix = {arXiv},
}
@article{mitzenmacher2006,
author = {Mitzenmacher, Michael and Drinea, Eleni},
title = {A simple lower bound for the capacity of the deletion channel},
journal = {IEEE Trans. Inform. Theory},
volume = {52},
number = {10},
year = {2006},
pages = {4657--4660},
doi = {10.1109/TIT.2006.881844},
}
@article{kanoria2013,
author = {Kanoria, Yashodhan and Montanari, Andrea},
title = {Optimal coding for the binary deletion channel with small deletion probability},
journal = {IEEE Trans. Inform. Theory},
volume = {59},
number = {10},
year = {2013},
pages = {6192--6219},
doi = {10.1109/TIT.2013.2262020},
eprint = {1104.5546},
archivePrefix = {arXiv},
}
@misc{pinto2026,
author = {Pinto, Martim and Ribeiro, Jo{\~a}o},
title = {Improved capacity upper bounds for the deletion channel using a parallelized {B}lahut--{A}rimoto algorithm},
year = {2026},
eprint = {2604.05867},
archivePrefix = {arXiv},
}
@misc{aim-binary-deletion-channel-capacity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Exact capacity of the binary deletion channel}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/137-binary-deletion-channel-capacity.md},
note = {Entry 137 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00502, "Exact capacity of the binary deletion channel", clopen.solutions.