{"id":"8e919d76-a74b-4230-9036-efb16ee0e3cb","arxiv_id":"2504.14035","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For small insertion probability α, the capacity of the binary insertion channel is 1 + α log α + G1 α + O(α^(3/2-ε)), with G1 ≈ 0.49011, matching the rate of i.i.d. Bernoulli(1/2) inputs up to higher-order terms.","lead":"This paper derives the first two terms of the capacity expansion for binary insertion channels when the insertion probability is small, showing that using uniform random inputs is asymptotically optimal. The result matters because insertion errors are relevant to DNA storage and synchronization-error channels whose exact capacity is unresolved.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Converse depends on an unproved run-length concentration: Lemma 12 needs E[log L0] of arbitrary high-entropy inputs to match iid Bernoulli(1/2), and Lemma 8's constant is input-independent; neither is demonstrated in this paper.","rationale":"The reader identified the same load-bearing assumption: the converse requires a run-length concentration result for high-entropy stationary ergodic inputs, stated without proof and deferred to the companion paper [26]. In good faith, the paper's approach is plausible and follows the Kanoria–Montanari deletion-channel program, and the achievability side for Bernoulli(1/2) inputs is explicit and self-contained up to deferred algebra. However, the manuscript is a short version that repeatedly refers to [26] for the proofs of Lemmas 4 through 12, and the key converse ingredient—the closeness of E[log L0] and the input-independent A1 term to their iid Bernoulli values—is asserted rather than derived. This is a genuine soft spot, but it is not a demonstrated error; it is an omitted proof that may well check out in the full version. Therefore the appropriate verdict is CONDITIONAL, exactly as the reader stated, and my stress-test does not move the verdict. The concrete test would settle whether the concentration bound holds and whether the error terms in Lemma 12 and Lemma 11 are consistent with the claimed O(α^{3/2−ε}) error.","tokens_in":10391,"tokens_out":13160,"duration_ms":114560,"concrete_test":"Derive the concentration estimate from first principles: for binary stationary ergodic X ∈ S_{L*} with H(X) > 1 − α^{1−ε}, obtain a bound on |E_X[log L0] − E_{Ber(1/2)}[log L0]| (for example via Pinsker's inequality on the run-length distribution) and insert it into the proof of Lemma 12 to confirm the claimed o(α^{1/2−ε} log L*) error. As a concrete probe, evaluate the quantities in (45) for the Markov family with flip probability p = 1/2 + sqrt(α log(1/α)) and L* = α^{−1}; if the deviation exceeds o(α^{1/2−ε} log L*) or h(z,v) exceeds the stated bound, the converse is invalid and G1 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1's converse (Lemma 12, final paragraph) bounds I(X) by 1 + α log α + G1 α + α^{2−ε}(1 + α^{1/2} L*) only after asserting |E[log L0] − Σ 2^{−l−1} l log l| = o(α^{1/2−ε} log L*) and h(z,v) ≤ 0.5 α^{2−ε}(2 + 0.5 α^{1/2} L*) for every stationary ergodic S_{L*} input with H(X) > 1 + 2α log α, citing [22, Lemma IV.3]. This is the load-bearing step: Corollary 1's H(Y|X) bound and Lemma 8's input-independent double-sum A1 implicitly replace the input run-length distribution by the geometric 2^{−l} law. If the deviation is larger, the universal constant G1 is not certified and a different high-entropy process could shift the second-order term. The manuscript explicitly defers these proofs to [26], so the main theorem is currently unsupported at exactly this point. A secondary arithmetic concern is that Lemma 11's truncation loss α^{1/2−ε}(L*)^{-1} log(L*) only becomes O(α^{3/2−ε}) if L* is taken polynomially large in 1/α, and the interaction of that choice with the L*-dependent error in Lemma 12 is not discussed. This does not change the primary assessment: the run-length concentration is the weakest premise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":10616,"tokens_out":4392,"duration_ms":39168,"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":[{"comment":"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":"Section IV-F, Lemma 12"},{"comment":"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.","section":"Section IV-F, combination of Lemmas 11 and 12"},{"comment":"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.","section":"Sections IV-A through IV-D, Corollary 1"}],"minor_comments":[{"comment":"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":"Section IV-F, Lemma 12"},{"comment":"The heading 'Achiveability' contains a typo; it should read 'Achievability'.","section":"Section IV-E heading"},{"comment":"The phrase 'there exists there exists α0 = α0(ε)' contains a duplicated 'there exists'; it should be 'there exists α0 = α0(ε)'.","section":"Lemma 12 statement"},{"comment":"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)'.","section":"Section IV-B, after Eq. (21)"}],"recommendation":"major_revision","confidential_remarks":"The result is plausible and, if correct, would be a solid contribution to the information theory literature. However, the submitted manuscript is a short version that defers the proofs of most technical lemmas to an unreviewed companion preprint, and the key run-length concentration step in Lemma 12 is asserted rather than proved. These issues are load-bearing and cannot be resolved by copy-editing; the authors should be asked to supply the missing proofs and to make the choice of L* explicit. I would not recommend rejection at this stage, but the paper should not be accepted before the missing derivations are provided."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the Tegin-Duman insertion channel paper. Headline: they claim C(alpha) = 1 + alpha log alpha + G1 alpha + O(alpha^(3/2-epsilon)) with G1 ~ 0.49011 for the binary insertion channel. That would be the first analog of Kanoria-Montanari for insertions, extending the deletion-channel program. Novelty is real: no prior expansion exists for insertion channels with random inserted bits. The achievability side is straightforward and convincing: iid Bernoulli(1/2) inputs yield that rate, and H(Y) for iid input is n(1+alpha) plus O(log n). The constant G1 is derived cleanly from Corollary 1 when run lengths are geometric.\n\nThe soft spot is the converse. Lemma 12, the load-bearing step, asserts that for any stationary ergodic high-entropy input, the run-length distribution is close enough to iid Bernoulli(1/2) that |E[log L0] - sum 2^(-l-1) l log l| = o(alpha^(1/2-epsilon) log L*) and that h(z,v) <= 0.5 alpha^(2-epsilon)(2 + 0.5 alpha^(1/2) L*). The first assertion is stated with a reference to [22, Lemma IV.3], but that lemma is about deletion channels and does not obviously transfer. The second uses the PMF bound (21), which itself depends on E[L0] and on the modified process; the derivation is not in this manuscript. More troubling: Lemma 8's constant A1 is computed by replacing adjacent run-length probabilities with 2^(-rj) 2^(-rj+1), i.e., geometric. For arbitrary stationary ergodic X with H(X) > 1 - alpha^gamma, that substitution is not justified in the text. If the true run-length distribution deviates from geometric at order alpha^(1/2) or larger, the universal constant G1 is not certified. That is exactly the step the companion paper [26] needs to prove.\n\nThere is also a smaller arithmetic gap: Lemma 11's truncation loss alpha^(1/2-epsilon) (L*)^(-1) log L* only becomes O(alpha^(3/2-epsilon)) if L* grows polynomially in 1/alpha, but then the L* term in Lemma 12's error becomes non-negligible; the interaction is not discussed. Minor relative to the run-length issue.\n\nThe paper is honest about its structure: it says proofs are in [26]. For a short version that is acceptable; as a stand-alone journal manuscript it needs either the companion proofs or a substantial appendix. If [26] checks out, the result is likely correct and important. Citation pattern is fine; self-citation is expected.\n\nWho is this for? Researchers on synchronization-error channels, especially those extending the small-probability expansion program. It deserves a serious referee, but the referee should have the companion and should check Lemma 8 and Lemma 12 carefully.\n\nRecommendation: send to peer review with the companion; do not desk reject.","headline":"First small-insertion-probability expansion for insertion channel capacity, but the converse leans on deferred proofs and an unproved run-length concentration step.","tokens_in":11238,"tokens_out":2167,"would_cite":true,"duration_ms":19651,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A40","94A24"],"pacs":[],"model":"deepseek-v4-flash","headline":"For small insertion probability α, the capacity of the binary insertion channel is 1 + α log(α) + 0.49011α + o(α), and independent fair bits achieve it.","keywords":["binary insertion channel","channel capacity","small insertion probability","synchronization errors","run-length encoding","asymptotic expansion","Bernoulli(1/2) input","DNA storage"],"falsifier":"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.","tokens_in":10083,"feed_emoji":"🧬","tokens_out":11899,"duration_ms":95845,"temperature":0.7,"pith_summary":"This paper establishes the first two terms in the asymptotic expansion of the capacity of the binary insertion channel, in which a random fair bit is inserted after each transmitted bit with probability $\\alpha$. The main result, Theorem 1, states that for small $\\alpha$ and any $\\epsilon > 0$, $C(\\alpha) = 1 + \\alpha \\log(\\alpha) + G_1 \\alpha + O(\\alpha^{3/2-\\epsilon})$, with $G_1 \\approx 0.49011$ an explicit convergent-series constant. The paper proves that i.i.d. Bernoulli(1/2) inputs achieve this rate, and that no stationary ergodic input can beat it to this order. A sympathetic reader would care because insertion channels model DNA storage and other synchronization-error systems whose capacity has resisted exact computation; this gives a rigorous two-term approximation and shows that input shaping is unnecessary in the rare-insertion limit.","feed_headline":"Rare-insertion binary channel capacity resolved to two leading terms","feed_subtitle":"The formula gives a concrete rate target for DNA storage and other insertion-prone channels.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the capacity of synchronization-error channels as the limit of normalized mutual information and licenses the restriction to stationary ergodic inputs.","marker":"[7]"},{"why":"Supplies the small-error capacity expansion approach and the run-length bound (Lemma IV.3) used in the converse's entropy estimate.","marker":"[22]"},{"why":"Provides the version of Dobrushin's theorem used as Lemma 3 and the perturbed-process proof strategy mirrored in Lemma 9's bound.","marker":"[23]"},{"why":"Companion paper containing the full proofs of Lemmas 4–9 and the Gallager insertion-channel extension on which the main text relies.","marker":"[26]"}],"fun_headline_variants":["Capacity of rare insertion channels resolved to two leading terms","Binary insertion capacity: 1 + α log α + 0.49α","For tiny insertion rates, fair bits are asymptotically optimal","Insertion channel capacity matches i.i.d. input to leading order"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Capacity of rare insertion channels resolved to two leading terms","Binary insertion capacity: 1 + α log α + 0.49α","For tiny insertion rates, fair bits are asymptotically optimal","Insertion channel capacity matches i.i.d. input to leading order"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000739,"raw_usage":{"total_tokens":3235,"prompt_tokens":814,"completion_tokens":2421,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":2348}},"tokens_in":430,"tokens_out":2421,"duration_ms":15977,"temperature":1.0,"reasoning_tokens":2348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:58:03.310855+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Shannon’s theorems for channels with s ynchronization errors,","cited_arxiv_id":null,"evidence_quote":"Defines the capacity of synchronization-error channels as the limit of normalized mutual information and licenses the restriction to stationary ergodic inputs."},{"cited_title":"On the deletion channel wi th small deletion probability,","cited_arxiv_id":null,"evidence_quote":"Supplies the small-error capacity expansion approach and the run-length bound (Lemma IV.3) used in the converse's entropy estimate."},{"cited_title":"Optimal coding for the binary deletion channel wit h small deletion probability,","cited_arxiv_id":null,"evidence_quote":"Provides the version of Dobrushin's theorem used as Lemma 3 and the perturbed-process proof strategy mirrored in Lemma 9's bound."},{"cited_title":"Capacity approximations for i n- sertion channels with small insertion probabilities,","cited_arxiv_id":null,"evidence_quote":"Companion paper containing the full proofs of Lemmas 4–9 and the Gallager insertion-channel extension on which the main text relies."}],"review_version":1}