Capacity Atlas Channel-capacity problems
Channels with memory

Binary deletion channel

Each input bit is independently deleted without an erasure marker. The exact capacity is unknown for every nontrivial deletion probability.

Open Lean: not started BDC
01 · Model

Channel specification

Input

\(X^n\in\{0,1\}^n\)

Output

\(A random subsequence of the input, with no markers indicating deleted positions.\)

Law

Each input bit is independently retained with probability 1-d and the surviving bits keep their order.

Parameters

SymbolMeaningRange
\(d\) Independent deletion probability. \(0<d<1\)

Assumptions

  • Neither encoder nor decoder observes the deletion pattern.
  • Average probability of error vanishes with blocklength.
02 · Capacity

Shannon capacity

bits per input bit bounds
\[0.1221(1-d)<C_{\mathrm{del}}(d)\le 0.3578(1-d)\]

Conditions. The displayed pair is valid in the high-deletion regime d at least 0.64; stronger pointwise bounds may apply at individual d.

The site records simple uniform high-deletion bounds here. A future data extension should store the full pointwise numerical envelopes.

Best lower boundOpen gapBest upper bound
\(0.1221(1-d)\)\(0.3578(1-d)\)
Symbol
\(C_{\mathrm{del}}(d)\)
Error criterion
Average-error operational capacity.
03 · Evidence

Known bounds and characterizations

TypeClaimMethodSource
lower \(C_{\mathrm{del}}(d)>0.1221(1-d)\) Optimized run-length input distributions in the Mitzenmacher-Drinea construction. 2023 [1]
upper \(C_{\mathrm{del}}(d)\le 0.3578(1-d)\)d\ge 0.64 Finite-block deletion-channel upper bounds computed by a parallelized Blahut-Arimoto algorithm. 2026 [1]
04 · History

Bound timeline

  1. 2023

    Rubinstein and Con improved both the high-deletion lower and upper constants.

    Reference
  2. 2026

    Pinto and Ribeiro improved the uniform high-deletion upper constant to 0.3578.

    Reference
05 · Frontier

What remains open?

Central question

Determine C_del(d), even at a single benchmark value such as d=1/2, or substantially narrow the pointwise gap.

Why the gap remains

Deletions destroy symbol alignment, so finite-letter mutual-information optimizations grow exponentially and do not single-letterize.

What would count as progress

  • Improve a certified pointwise lower or upper bound at a specified deletion probability.
  • Prove structural properties of capacity-achieving stationary input processes.
  • Replace large numerical optimizations by compact certificates that can ultimately be checked in Lean.

Concrete subproblems

open

Formalize the operational deletion-channel model and existence of capacity.

open

Store machine-readable pointwise upper and lower envelopes with provenance.

06 · Lean

Formalization status

Lean: not started

Not started

The finite-channel core does not yet model variable-length outputs or synchronization errors.

  1. Definitions
  2. Statement
  3. Partial proof
  4. Complete proof

No Lean file is linked yet. A contribution should begin by reusing the shared definitions under lean/CapacityAtlas.

References

Primary sources

  1. Ittai Rubinstein and Roni Con (2023). Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel. arXiv preprint. arXiv:2305.07156
  2. Martim Pinto and João Ribeiro (2026). Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm. arXiv preprint; presented at ISIT 2026. arXiv:2604.05867
Keep exploring

Related entries

Point-to-point Updated 2026-08-09

Binary symmetric channel

Solved Lean: definitions

Each bit is independently flipped with probability p. This is the canonical finite noisy channel.

\(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
2 bounds Open entry
Multi-user Updated 2026-08-09

General discrete memoryless relay channel

Open Lean: not started

A relay assists communication from a source to a destination. Decode-forward and the cut-set bound do not coincide in general.

\(R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\)
2 bounds Open entry