REVIEW 3 major objections 4 minor 26 references
On the Capacity of Insertion Channels for Small Insertion Probabilities
T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read For small insertion probability α, the capacity of the binary insertion channel is 1 + α log(α) + 0.49011α + o(α), and independent fair bits achieve it.
desk verdict First small-insertion-probability expansion for insertion channel capacity, but the converse leans on deferred proofs and an unproved run-length concentration step. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the run-length decomposition of the input together with a modified insertion process that allows at most one insertion per extended run. The mutual information rate is split as $H(Y) - H(A_n,B_n) + H(A_n,B_n|X^n,Y,K) + H(K|X^n,Y)$, and each summand is expanded in powers of $\alpha$. Two identities do the heavy lifting: $H(A_n,B_n)/n = h(\alpha)+\alpha$, and the run-length term $E[\log L_0]$, where $L_0$ is the length of the input run containing a typical position—equal to $\sum_{l \geq 1} 2^{-l-1} l \log l$ for Bernoulli(1/2) input. The constant $G_1$ assembles these leading coefficients, and the gap between original and perturbed insertion processes is controlled by typical insertion spacing, contributing only higher-order terms.
What would settle it
Run a finite-block dynamic program for the insertion channel with $n$ up to a few tens and $\alpha \in \{0.001, 0.005, 0.01\}$, and compare the exact $C_n$ with $1+\alpha\log\alpha+0.49011\alpha$; a persistent gap of order $\alpha^{3/2}$ or larger would contradict Theorem 1. Alternatively, construct a stationary ergodic binary process with entropy rate just above $1+2\alpha\log\alpha$ whose run-length expectation $E[\log L_0]$ differs from $\sum_{l \geq 1} 2^{-l-1} l \log l$ by an amount that is not $o(\alpha^{1/2-\epsilon}\log(1/\alpha))$; if such a process exists, Lemma 12's bound fails and the converse is false.
Extended reading notes
Core claim
The central claim is that the binary insertion channel capacity satisfies $C(\alpha) = 1 + \alpha \log(\alpha) + G_1 \alpha + O(\alpha^{3/2-\epsilon})$ as $\alpha \to 0$, where $G_1 \approx 0.49011$. This means that sending independent fair bits is asymptotically optimal: the rate achieved by i.i.d. Bernoulli(1/2) input matches capacity through the $\alpha \log(1/\alpha)$ and linear terms, and the difference is confined to higher-order terms. The proof decomposes the mutual information rate into entropy components organized by run lengths, approximates the insertion-pattern ambiguity and the output-run-length entropy with modified insertion processes, and establishes a converse over stationary ergodic inputs. The result places the insertion channel next to the deletion channel as a synchronization-error channel whose small-error asymptotics are now known.
Load-bearing premise
The load-bearing premise is the deferred assertion that every stationary ergodic binary input with entropy rate above $1+2\alpha\log\alpha$ has run lengths so close to i.i.d. Bernoulli(1/2) that $|E[\log L_0] - \sum_{l \geq 1} 2^{-l-1} l \log l| = o(\alpha^{1/2-\epsilon}\log(1/\alpha))$; the converse also assumes without proof that inputs with entropy at or below $1+2\alpha\log\alpha$ can be neglected in the capacity supremum.
Editorial extensions
If this is right
- For small insertion probabilities, the capacity of the binary insertion channel is $1 + \alpha \log(\alpha) + 0.49011\,\alpha + o(\alpha)$, giving an explicit numeric target for code design and simulation benchmarks.
- Independent fair-bit inputs achieve this rate to leading order, so coding schemes for rare insertions do not need to shape the input distribution; effort can concentrate on error correction.
- The run-length decomposition and perturbed-process bounds transfer to related channels such as the Gallager insertion channel, as the companion paper shows, promising similar expansions there.
- The result parallels the known deletion-channel expansion, supporting the view that i.i.d. Bernoulli(1/2) input is asymptotically optimal across synchronization-error channels in the small-error regime.
- In DNA-storage applications with low insertion rates, the expansion provides a quantitative capacity estimate that can inform the maximum coding rate.
Reading between the lines
- If the deferred run-length concentration is proven, the same argument should provide a self-contained technique for any i.i.d. insertion process with finite mean run length, not only Bernoulli(1/2) inserted bits.
- The run-length machinery likely carries over to nonbinary alphabets: for a $q$-ary alphabet, a similar constant $G_1(q)$ would emerge while the leading term $1+\alpha \log(1/\alpha)$ should be unchanged, giving a testable prediction for DNA storage with four nucleotides.
- Until the companion-paper lemma is proven in the main text, the converse's validity rests on an external result; a direct proof would make the two-term expansion fully self-contained.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the binary insertion channel in which, after each transmitted bit, a fair Bernoulli(1/2) bit is inserted with probability α. The central result, Theorem 1 (Eqs. (1)–(2)), asserts that for small α the capacity is C(α) = 1 + α log α + G1 α + O(α^{3/2−ε}) for any ε > 0, with an explicit constant G1 ≈ 0.49011 defined by a convergent series. Achievability is claimed via i.i.d. Bernoulli(1/2) inputs, and the converse is developed by decomposing the mutual information in terms of run lengths and by bounding the relevant entropy terms for stationary ergodic inputs. The paper is explicitly a condensed version: the proofs of Lemmas 4–9 and 11, and the detailed steps of Lemma 12, are deferred to the companion manuscript [26].
Significance. If Theorem 1 is correct, it provides the first two terms of the capacity expansion for the binary insertion channel and shows that i.i.d. Bernoulli(1/2) inputs are asymptotically optimal up to the second order. This is a natural and meaningful analogue of the Kanoria–Montanari results for the deletion channel, and it has potential relevance for DNA storage and other synchronization-error models. The explicit, parameter-free definition of G1 is a strength, as is the use of information-stability and stationary-ergodic inputs in the converse. However, the manuscript as submitted does not contain the proofs of several load-bearing lemmas, and Lemma 12 rests on a nontrivial concentration assertion that is not derived or referenced in sufficient detail; the main theorem is therefore currently unsupported at a key point.
major comments (3)
- [Section IV-F, Lemma 12] The converse proof depends on two unproved assertions: (i) |E[log L0] − Σ_{l≥1} 2^{-l−1} l log l| = o(α^{1/2−ε} log L*) for every stationary ergodic input with H(X) > 1 + 2α log α, and (ii) h(z,v) ≤ 0.5 α^{2−ε}(2 + 0.5 α^{1/2} L*). The paper cites [22, Lemma IV.3] only for an upper bound on E[L0]; this does not by itself control E[log L0] or the joint PMF of (Z,V). Since the constant G1 in Eq. (2) is computed from the i.i.d. Bernoulli(1/2) run-length law, assertion (i) is exactly what certifies that G1 is universal. Without a derivation of these estimates, the upper bound (44) and hence Theorem 1 are not established.
- [Section IV-F, combination of Lemmas 11 and 12] The proof of the converse does not state how the truncation parameter L* is chosen when Lemma 11 and Lemma 12 are combined. Lemma 11 gives an error α^{1/2−ε}(L*)^{-1} log(L*), while Lemma 12's bound grows with L* as α^{2−ε}(1 + α^{1/2} L*). A choice such as L* = α^{-1} makes both errors O(α^{3/2−ε'}) for any ε' > ε, but the manuscript never discusses this trade-off; without it, the claimed O(α^{3/2−ε}) remainder in Theorem 1 is not justified.
- [Sections IV-A through IV-D, Corollary 1] The main entropy decomposition leading to Corollary 1 (Eq. (39)) rests on Lemmas 4, 5, 6, 7, 8, and 9, whose proofs are all deferred to the companion paper [26]. The manuscript states 'we exclude detailed proofs of the lemmas and theorems' and 'For details, please refer to the extended version.' Because these lemmas are load-bearing for the central claim, the paper as submitted is not self-contained: a journal referee cannot verify the capacity theorem without consulting an external preprint. The authors should either include the full proofs in an appendix or clearly indicate that the companion paper is under review and provide a version of the proof for the record.
minor comments (4)
- [Section IV-F, Lemma 12] In the sentence 'Hence Corollary 1 with α = 1 − ε applies,' the parameter α is already used for the insertion probability; the intended quantity is γ = 1 − ε. This should be corrected.
- [Section IV-E heading] The heading 'Achiveability' contains a typo; it should read 'Achievability'.
- [Lemma 12 statement] The phrase 'there exists there exists α0 = α0(ε)' contains a duplicated 'there exists'; it should be 'there exists α0 = α0(ε)'.
- [Section IV-B, after Eq. (21)] The sentence 'To compute the entropy, one can evaluate the PMF of P(z,v)' is redundant: the PMF is the object P(z,v), not a separate 'PMF of P(z,v)'. This should be rephrased, e.g., 'one can evaluate the PMF P(z,v)'.
Circularity Check
No significant circularity: the capacity expansion is derived from the channel model with G1 as a convergent series, not a fitted parameter, and the converse attempts a genuine bound over stationary ergodic inputs.
full rationale
The paper's derivation chain is not circular. Theorem 1's expansion (1) is obtained by decomposing I(X^n;Y) via the entropy chain rule in Eq. (14) and estimating the four resulting terms (H(A^n,B^n), H(A^n,B^n|X^n,Y,K), H(K|X^n,Y), and H(Y)) for small insertion probability α. The constant G1 in Eq. (2) is defined by an absolutely convergent infinite series with a numerical approximation and a truncation bound given in the footnote; it is not fitted to the channel output. Achievability (Lemma 10) is a genuine lower bound: it computes the mutual information for i.i.d. Bernoulli(1/2) inputs, which is a legitimate admissible input distribution, and the resulting expression matches the claimed expansion. The converse (Lemma 12) attempts to upper-bound I(X) for every stationary ergodic input, using the decomposition of Corollary 1 and the external bound from [22, Lemma IV.3] on E[L0]. The step involving |E[log L0] - sum 2^{-l-1} l log l| = o(alpha^{1/2-epsilon} log L*) is asserted rather than proved in this manuscript, and the full proofs of several lemmas are deferred to the authors' companion paper [26]. This is a serious completeness/verifiability gap and a correctness risk, but it is not circularity: the assertions are not equivalent to the theorem's conclusion by definition, and the companion is cited as containing derivations rather than as a source of the target result itself. The paper explicitly states 'we exclude detailed proofs of the lemmas and theorems, offering instead discussions on the approaches employed' and refers to [26]; this is an omitted-proof issue, not a self-referential reduction. No equation or fitted parameter is renamed as a prediction, and G1 is not calibrated from the data whose capacity is being predicted. Accordingly, no circular step is identified.
Assumptions & free parameters
assumptions (4)
- standard math Dobrushin's coding theorem: the capacity of a memoryless synchronization-error channel equals the limit of normalized mutual information (Theorem 2, from [7]).
- standard math Stationary ergodic inputs achieve capacity (Lemma 3, from [23]).
- domain assumption For any stationary ergodic input with H(X)>1+2α log α, the run-length distribution is sufficiently close to i.i.d. Bernoulli(1/2) so that |E[log L0] - Σ 2^(-l-1) l log l| = o(α^(1/2-ε) log L*); this relies on [22, Lemma IV.3].
- standard math The entropy decomposition (14) with the chain rule for the run-length marker K is valid.
Cite this review
Pith. "Pith review of On the Capacity of Insertion Channels for Small Insertion Probabilities." pith.science (2026). https://pith.science/paper/ERAKP7F6
@misc{pith2026250414035,
author = {Pith},
title = {Pith review of: On the Capacity of Insertion Channels for Small Insertion Probabilities},
year = {2026},
howpublished = {\url{https://pith.science/paper/ERAKP7F6}},
note = {Machine review of arXiv:2504.14035}
}
read the original abstract
Channels with synchronization errors, such as deletion and insertion errors, are crucial in DNA storage, data reconstruction, and other applications. These errors introduce memory to the channel, complicating its capacity analysis. This paper analyzes binary insertion channels for small insertion probabilities, identifying dominant terms in the capacity expansion and establishing capacity in this regime. Using Bernoulli(1/2) inputs for achievability and a converse based on the use of stationary and ergodic processes, we demonstrate that capacity closely aligns with achievable rates using independent and identically distributed (i.i.d.) inputs, differing only in higher-order terms.
Reference graph
Works this paper leans on
-
[26]
Capacity approximations for i n- sertion channels with small insertion probabilities,
B. Tegin and T. M. Duman, “Capacity approximations for i n- sertion channels with small insertion probabilities,” arXiv preprint arXiv:2411.14771, 2024
-
[1]
Coding for deletion channels with multiple traces,
M. Abroshan, R. V enkataramanan, L. Dolecek, and A. Guill én i Fàbre- gas, “Coding for deletion channels with multiple traces,” i n IEEE International Symposium on Information Theory (ISIT) , Paris, France, Jul. 2019, pp. 1372–1376
work page 2019
-
[2]
On the embedding capacity of DNA strands unde r substitu- tion, insertion, and deletion mutations,
F. Balado, “On the embedding capacity of DNA strands unde r substitu- tion, insertion, and deletion mutations,” in Media F orensics and Security II, vol. 7541. San Jose, CA, USA: SPIE, Jan. 2010, pp. 411–422
work page 2010
-
[3]
A characterizati on of the DNA data storage channel,
R. Heckel, G. Mikutis, and R. N. Grass, “A characterizati on of the DNA data storage channel,” Scientific reports , vol. 9, no. 1, p. 9663, Nov. 2019
work page 2019
-
[4]
Co ding over sets for DNA storage,
A. Lenz, P . H. Siegel, A. Wachter-Zeh, and E. Y aakobi, “Co ding over sets for DNA storage,” IEEE Transactions on Information Theory , vol. 66, no. 4, pp. 2331–2351, Apr. 2019
work page 2019
-
[5]
Coding and signal processing for ultra-high density magne tic recording channels,
Y . L. Guan, G. Han, L. Kong, K. S. Chan, K. Cai, and J. Zheng, “Coding and signal processing for ultra-high density magne tic recording channels,” in 2014 International Conference on Computing, Networking and Communications (ICNC) , Honolulu, HI, USA, Feb. 2014, pp. 194– 199
work page 2014
-
[6]
Efficient reconstruction of sequenc es,
V . I. Levenshtein, “Efficient reconstruction of sequenc es,” IEEE Trans- actions on Information Theory , vol. 47, no. 1, pp. 2–22, Jan. 2001
work page 2001
-
[7]
Shannon’s theorems for channels with s ynchronization errors,
R. L. Dobrushin, “Shannon’s theorems for channels with s ynchronization errors,” Problemy Peredachi Informatsii, vol. 3, no. 4, pp. 18–36, 1967
work page 1967
Show all 26 references
-
[8]
A mathematical theory of communication,
C. E. Shannon, “A mathematical theory of communication, ” The Bell System Technical Journal , vol. 27, no. 3, pp. 379–423, Jul. 1948
1948
-
[9]
On the capacity of channels wi th Markov insertions, deletions and substitutions,
R. Morozov and T. M. Duman, “On the capacity of channels wi th Markov insertions, deletions and substitutions,” in IEEE International Symposium on Information Theory (ISIT) , Athens, Greece, Jul. 2024, pp. 3444–3449
2024
-
[10]
Shannon capacity of channels with Markov insertio ns, deletions and substitutions,
——, “Shannon capacity of channels with Markov insertio ns, deletions and substitutions,” arXiv preprint arXiv:2401.16063 , 2024
2024 arXiv
-
[11]
R. G. Gallager, Sequential decoding for binary channels with noise and synchronization errors. British Library, Reports & Microfilms, 2000
2000
-
[12]
Sequential decoding for a binary chann el with drop- outs and insertions,
K. Zigangirov, “Sequential decoding for a binary chann el with drop- outs and insertions,” Problemy Peredachi Informatsii, vol. 5, no. 2, pp. 23–30, 1969
1969
-
[13]
A simple lower bound for the capacity of the deletion channel,
M. Mitzenmacher and E. Drinea, “A simple lower bound for the capacity of the deletion channel,” IEEE Transactions on Information Theory , vol. 52, no. 10, pp. 4657–4660, Oct. 2006
2006
-
[14]
Directly lower bounding the in formation capacity for channels with iid deletions and duplications,
A. Kirsch and E. Drinea, “Directly lower bounding the in formation capacity for channels with iid deletions and duplications, ” IEEE Trans- actions on Information Theory , vol. 56, no. 1, pp. 86–102, Jan. 2009
2009
-
[15]
Capacit y upper bounds for the deletion channel,
S. Diggavi, M. Mitzenmacher, and H. D. Pfister, “Capacit y upper bounds for the deletion channel,” in IEEE International Symposium on Information Theory , Nice, France, Jun. 2007, pp. 1716–1720
2007
-
[16]
Novel bounds on the capaci ty of the binary deletion channel,
D. Fertonani and T. M. Duman, “Novel bounds on the capaci ty of the binary deletion channel,” IEEE Transactions on Information Theory , vol. 56, no. 6, pp. 2753–2765, Jun. 2010
2010
-
[17]
An upper bound on the capacit y of non-binary deletion channels,
M. Rahmati and T. M. Duman, “An upper bound on the capacit y of non-binary deletion channels,” in IEEE International Symposium on Information Theory , Istanbul, Turkey, Jul. 2013, pp. 2940–2944
2013
-
[18]
Bounds on the capacity of channels with insertions, deletions and substitutions,
D. Fertonani, T. M. Duman, and M. F. Erden, “Bounds on the capacity of channels with insertions, deletions and substitutions,” IEEE Transactions on Communications , vol. 59, no. 1, pp. 2–6, Jan. 2010
2010
-
[19]
Capacity upper bounds for deletion-ty pe channels,
M. Cheraghchi, “Capacity upper bounds for deletion-ty pe channels,” Journal of the ACM (JACM) , vol. 66, no. 2, pp. 1–79, Mar. 2019
2019
-
[20]
An overview of capacity r esults for synchronization channels,
M. Cheraghchi and J. Ribeiro, “An overview of capacity r esults for synchronization channels,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3207–3232, Jun. 2020
2020
-
[21]
Tight asympto tic bounds for the deletion channel with small deletion probabilities ,
A. Kalai, M. Mitzenmacher, and M. Sudan, “Tight asympto tic bounds for the deletion channel with small deletion probabilities ,” in IEEE International Symposium on Information Theory , Jun. 2010, pp. 997– 1001
2010
-
[22]
On the deletion channel wi th small deletion probability,
Y . Kanoria and A. Montanari, “On the deletion channel wi th small deletion probability,” in IEEE International Symposium on Information Theory, Austin, TX, USA, Jun. 2010, pp. 1002–1006
2010
-
[23]
Optimal coding for the binary deletion channel wit h small deletion probability,
——, “Optimal coding for the binary deletion channel wit h small deletion probability,” IEEE Transactions on Information Theory , vol. 59, no. 10, pp. 6192–6219, Oct. 2013
2013
-
[24]
On the capacity of duplica tion chan- nels,
M. Ramezani and M. Ardakani, “On the capacity of duplica tion chan- nels,” IEEE Transactions on Communications , vol. 61, no. 3, pp. 1020– 1027, Mar. 2013
2013
-
[25]
Capacity bounds for sticky channels ,
M. Mitzenmacher, “Capacity bounds for sticky channels ,” IEEE Trans- actions on Information Theory , vol. 54, no. 1, pp. 72–77, Jan. 2008
2008
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.