pith. sign in

arxiv: 2401.16063 · v6 · submitted 2024-01-29 · 💻 cs.IT · math.IT

Channels with Markov Synchronization Errors: Information Stability and Capacity Bounds

Ruslan Morozov , Tolga M. Duman This is my paper

Pith reviewed 2026-05-24 04:51 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords synchronization errorsMarkov chaininformation stabilityShannon capacitydeletion channelsDNA storageinsertions and deletions
0
0 comments X

The pith

Channels with synchronization errors driven by a stationary ergodic finite-state Markov chain are information-stable and thus have a Shannon capacity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that synchronization errors modeled as insertions, deletions, and substitutions governed by a stationary and ergodic finite-state Markov chain yield an information-stable channel. Information stability means the Shannon capacity exists and equals the limit of the normalized mutual information. The result applies to a wide class of channels with memory in error processes, including those modeling DNA storage. For concrete deletion channels, numerical bounds show that Markov memory increases capacity relative to memoryless channels at identical deletion probability.

Core claim

We assume that the synchronization errors are governed by a stationary and ergodic finite state Markov chain and prove that such a channel is information-stable, which implies the existence of the Shannon capacity for a wide range of channels with synchronization errors, with different applications, including DNA storage. We also provide specific examples of deletion channels with Markov memory and numerically evaluate their capacity bounds.

What carries the argument

Information stability of the channel, established via the stationary ergodic finite-state Markov chain governing the synchronization error process.

If this is right

  • The Shannon capacity exists and equals the limit of mutual information for these channels.
  • Coding schemes exist that achieve this capacity limit.
  • The result covers channels relevant to DNA storage and similar applications.
  • For Markov deletion channels, capacity is strictly higher than for memoryless deletions at the same probability.
  • Capacity bounds can be numerically evaluated for finite-state Markov error models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The stability proof may extend to other dependent error processes beyond finite-state Markov chains.
  • Design of practical codes could exploit the memory to achieve higher rates than memoryless designs.
  • Numerical capacity comparisons suggest that real-world channels with bursty or correlated errors may outperform independent-error models.

Load-bearing premise

The synchronization error process is a stationary and ergodic finite-state Markov chain.

What would settle it

A specific stationary ergodic Markov deletion channel where the normalized mutual information fails to converge to a limit would falsify the stability claim.

Figures

Figures reproduced from arXiv: 2401.16063 by Ruslan Morozov, Tolga M. Duman.

Figure 1
Figure 1. Figure 1: Exemplary synchronization error channel with memor [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The upper bound on capacity for δ = 0.01, BDC capacity ≤ 0.945. 0.715 0.72 0.725 0.73 0.735 0.74 0.745 0.75 2 4 8 16 capacity UB 1/α D=d (BDC) α=2β, D=2d α=2β, D=4d α=2β, D=8d α=β, D=2d α=β, D=4d α=β, D=8d α=β/2, D=2d α=β/2, D=4d α=β/2, D=8d δ = 0.1, α=2β [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
read the original abstract

Particularly motivated by DNA storage channels, we consider channels with synchronization errors modeled as insertions and deletions, along with substitutions. We focus on the case where the synchronization error process has memory and investigate the information stability of these channels, hence the existence of their Shannon capacity. We assume that the synchronization errors are governed by a stationary and ergodic finite state Markov chain and prove that such a channel is information-stable, which implies the existence of a coding scheme that achieves the limit of mutual information. This result implies the existence of the Shannon capacity for a wide range of channels with synchronization errors, with different applications, including DNA storage. We also provide specific examples of deletion channels with Markov memory and numerically evaluate their capacity bounds, thereby allowing us to quantify the capacity difference between memoryless deletion channels and those with memory with the same deletion probability and reveal that having memory increases the channel capacity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper models synchronization-error channels (insertions, deletions, and substitutions) whose error process is a stationary ergodic finite-state Markov chain. It proves that such channels are information-stable, which implies that the Shannon capacity exists and equals the limit of the normalized mutual information. The result is applied to DNA-storage channels and illustrated with explicit capacity bounds for Markov deletion channels; numerical comparisons show that memory increases capacity relative to the memoryless deletion channel with the same deletion probability.

Significance. If the information-stability proof holds, the work supplies a general sufficient condition for the existence of capacity in a broad class of synchronization-error channels with memory. The numerical evaluation quantifies the capacity gain due to Markov memory, which is directly relevant to applications such as DNA storage. The manuscript ships an explicit proof under the stated modeling assumptions together with reproducible numerical bounds.

minor comments (3)
  1. §4 (numerical evaluation): the state-space size of the Markov chain used for the capacity-bound computation and the truncation length for the mutual-information estimator should be stated explicitly so that the reported numbers can be reproduced from the given deletion probability and transition matrix.
  2. Notation: the definition of the output process Y^n in the presence of variable-length synchronization errors should be accompanied by a short diagram or explicit recursion showing how the Markov state evolves with each input symbol.
  3. References: the citation list omits the classic Dobrushin information-stability criterion and the recent works on deletion channels with memory; adding these would clarify the precise technical advance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the report, so we have no specific points requiring point-by-point rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper states an explicit modeling assumption (synchronization errors form a stationary ergodic finite-state Markov chain) and proves information stability as a consequence. No step reduces a claimed prediction or theorem to a fitted parameter, self-citation chain, or definitional tautology; the argument is a standard information-theoretic proof under the given hypothesis and is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Markov modeling assumption; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The synchronization error process is a stationary and ergodic finite-state Markov chain.
    This modeling choice is invoked to prove information stability.

pith-pipeline@v0.9.0 · 5676 in / 1024 out tokens · 23676 ms · 2026-05-24T04:51:31.980559+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Channels with Input-Correlated Synchronization Errors

    cs.IT 2025-04 unverdicted novelty 7.0

    Derives general capacity theorems for input-correlated synchronization error channels and explicit capacity-achieving codes for multi-trace runlength-dependent deletion channels.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bit patte rned media with written-in errors: Modelling, detection and theoreti cal limits,

    J. Hu, T. M. Duman, E. M. Kurtas, and M. F. Erden, “Bit patte rned media with written-in errors: Modelling, detection and theoreti cal limits,” IEEE Transactions on Magnetics , vol. 43, pp. 3517–3524, 2007

    work page 2007

  2. [2]

    DNA-based storage: Models a nd funda- mental limits,

    I. Shomorony and R. Heckel, “DNA-based storage: Models a nd funda- mental limits,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3675–3689, 2021

    work page 2021

  3. [3]

    On optimal k-deletion correcting c odes,

    J. Sima and J. Bruck, “On optimal k-deletion correcting c odes,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3360–3375, 2021

    work page 2021

  4. [4]

    Systematic cod es correcting multiple-deletion and multiple-substitution errors,

    W. Song, N. Polyanskii, K. Cai, and X. He, “Systematic cod es correcting multiple-deletion and multiple-substitution errors,” IEEE Transactions on Information Theory , vol. 68, no. 10, pp. 6402–6416, 2022

    work page 2022

  5. [5]

    Non-binary two-deletion correcting codes and burst-deletion correcting codes,

    W. Song and K. Cai, “Non-binary two-deletion correcting codes and burst-deletion correcting codes,” IEEE Transactions on Information Theory, vol. 69, no. 10, pp. 6470–6484, 2023

    work page 2023

  6. [6]

    Codes for channels with inserti ons, deletions and substitutions,

    E. Ratzer and D. Mackay, “Codes for channels with inserti ons, deletions and substitutions,” in 2nd International Symposium of Turbo Codes and Related Topics, 2000

    work page 2000

  7. [7]

    Reliable communication over cha nnels with insertions, deletions, and substitutions,

    M. Davey and D. Mackay, “Reliable communication over cha nnels with insertions, deletions, and substitutions,” IEEE Transactions on Information Theory , vol. 47, no. 2, pp. 687–698, 2001

    work page 2001

  8. [8]

    Symbol-level syn chronization and LDPC code design for insertion/deletion channels,

    F. Wang, D. Fertonani, and T. M. Duman, “Symbol-level syn chronization and LDPC code design for insertion/deletion channels,” IEEE Transac- tions on Communications , vol. 59, no. 5, pp. 1287–1297, 2011

    work page 2011

  9. [9]

    Shannon’s theorems for channels with s ynchronization errors,

    R. L. Dobrushin, “Shannon’s theorems for channels with s ynchronization errors,” Prob. of Information Trans. , vol. 3, no. 4, pp. 18–36, 1967

    work page 1967

  10. [10]

    On lower bounds for the c apacity of deletion channels,

    E. Drinea and M. Mitzenmacher, “On lower bounds for the c apacity of deletion channels,” IEEE Transactions on Information Theory , vol. 52, no. 10, pp. 4648–4657, 2006

    work page 2006

  11. [11]

    simple lower bound for t he capacity of the deletion channel,

    M. Mitzenmacher and E. Drinea, “simple lower bound for t he capacity of the deletion channel,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4657–4660, 2006

    work page 2006

  12. [12]

    Directly lower bounding the in formation capacity for channels with i.i.d. deletions and duplicatio ns,

    E. Drinea and A. Kirsch, “Directly lower bounding the in formation capacity for channels with i.i.d. deletions and duplicatio ns,” in 2007 IEEE International Symposium on Information Theory , 2007, pp. 1731– 1735

    work page 2007

  13. [13]

    Capacity u pper bounds for deletion channels,

    S. Diggavi, M. Mitzenmacher, and H. Pfister, “Capacity u pper bounds for deletion channels,” in 2007 IEEE International Symposium on Information Theory , 2007

    work page 2007

  14. [14]

    Novel bounds on the capaci ty of binary deletion channels,

    D. Fertonani and T. M. Duman, “Novel bounds on the capaci ty of binary deletion channels,” IEEE Transactions on Information Theory , vol. 56, no. 6, pp. 2753–2765, 2010

    work page 2010

  15. [15]

    Upper bounds on the capacity of deletion channels using channel fragmentation,

    M. Rahmati and T. M. Duman, “Upper bounds on the capacity of deletion channels using channel fragmentation,” IEEE Transactions on Information Theory , vol. 61, no. 1, pp. 146–156, 2015

    work page 2015

  16. [16]

    Optimal coding for the bin ary deletion channel with small deletion probability,

    Y . Kanoria and A. Montanari, “Optimal coding for the bin ary deletion channel with small deletion probability,” IEEE Transactions on Infor- mation Theory , vol. 59, no. 10, pp. 6192–6219, 2013

    work page 2013

  17. [17]

    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 2010 IEEE International Symposium on Information Theory , 2010, pp. 997–1001

    work page 2010

  18. [18]

    A survey of results for deletion chan nels and related synchronization channels,

    M. Mitzenmacher, “A survey of results for deletion chan nels and related synchronization channels,” Probability Surveys, vol. 6, pp. 1–33, 2009

    work page 2009

  19. [19]

    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, 2021

    work page 2021

  20. [20]

    Channel model and decoder with memory for DNA data storage with nanopore sequencing,

    B. Hamoum and E. Dupraz, “Channel model and decoder with memory for DNA data storage with nanopore sequencing,” IEEE Access, vol. 11, pp. 52 075–52 087, 2023

    work page 2023

  21. [21]

    Optimized code design for constrained DNA dat a storage with asymmetric errors,

    L. Deng, Y . Wang, M. Noor-A-Rahim, Y . L. Guan, Z. Shi, E. G unawan, and C. L. Poh, “Optimized code design for constrained DNA dat a storage with asymmetric errors,” IEEE Access , vol. 7, pp. 84 107–84 121, 2019

    work page 2019

  22. [22]

    Models and informa tion- theoretic bounds for nanopore sequencing,

    W. Mao, S. N. Diggavi, and S. Kannan, “Models and informa tion- theoretic bounds for nanopore sequencing,” IEEE Transactions on Information Theory , vol. 64, no. 4, pp. 3216–3236, 2018

    work page 2018

  23. [23]

    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, 2011

    work page 2011

  24. [24]

    A mathematical theory of communication,

    C. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, July, October 1948

    work page 1948

  25. [25]

    On Shannon theorem and its converse for sequen ces of communication schemes in the case of abstract random variab les,

    G. D. Hu, “On Shannon theorem and its converse for sequen ces of communication schemes in the case of abstract random variab les,” in Transactions of the Third Prague Conference on Information Theory, Statistical Decision Functions, Random Processes , 1962, pp. 285–332

    work page 1962

  26. [26]

    A general formula for channel cap acity,

    S. V erdu and T. S. Han, “A general formula for channel cap acity,” IEEE Trans. on Information Theory , vol. 40, no. 4, pp. 1147–1157, 1994

    work page 1994

  27. [27]

    A general formulation of the fundamen tal theorem of Shannon in the theory of information,

    R. L. Dobrushin, “A general formulation of the fundamen tal theorem of Shannon in the theory of information,” Uspekhi Mat. Nauk , vol. 14, no. 6, pp. 3–104, 1959

    work page 1959

  28. [28]

    Memoryless channels with synchroniza tion errors: the general case,

    S. Z. Stambler, “Memoryless channels with synchroniza tion errors: the general case,” Probl. Peredachi Inf., vol. 6, no. 3, pp. 43–49, 1970

    work page 1970

  29. [29]

    R. G. Gallager, Information Theory and Reliable Communication . Wi- ley, 1968

    work page 1968

  30. [30]

    Capacity and coding for th e Gilbert- Elliott channels,

    M. Mushkin and I. Bar-David, “Capacity and coding for th e Gilbert- Elliott channels,” IEEE Transactions on Information Theory , vol. 35, no. 6, pp. 1277–1290, 1989

    work page 1989

  31. [31]

    On the capacity of channels with de letions and states,

    Y . Li and V . Y . F. Tan, “On the capacity of channels with de letions and states,” IEEE Transactions on Information Theory , vol. 67, no. 5, pp. 2663–2679, 2021

    work page 2021

  32. [32]

    Billingsley, Probability and Measure , ser

    P . Billingsley, Probability and Measure , ser. Wiley Series in Probability and Statistics. Wiley, 2012

    work page 2012

  33. [33]

    Some linear and some quadra tic recursion formulas. II,

    N. Bruijn, de and P . Erd¨ os, “Some linear and some quadra tic recursion formulas. II,” Proceedings of the Koninklijke Nederlandse Akademie van W etenschappen: Series A: Mathematical Sciences, vol. 14, pp. 152–163, 1952

    work page 1952