💻 computer science

Channels with Markov Synchronization Errors: Information Stability and Capacity Bounds

Motivated by DNA storage, this paper proves that channels with synchronization errors (insertions, deletions, and substitutions) governed by a stationary and ergodic Markov chain are information-stable, thereby establishing the existence of their Shannon capacity and demonstrating that such memory increases capacity compared to memoryless counterparts.

Original authors: Ruslan Morozov, Tolga M. Duman

Published 2026-04-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruslan Morozov, Tolga M. Duman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message written on a long strip of paper to a friend. But, the delivery system is a bit glitchy. Sometimes, the paper gets torn (a deletion), sometimes extra scraps of paper get stuck in the middle (an insertion), and occasionally, a letter gets smudged and looks like a different letter (a substitution).

In the world of computer science, this is called a channel with synchronization errors. The receiver doesn't know where the message starts or ends because the paper strip has changed length.

For a long time, scientists assumed these glitches happened randomly and independently, like rolling a die for every single letter. If you roll a die, the result of the next roll doesn't care about the previous one. This is called "memoryless."

The Big Discovery
This paper, written by Ruslan Morozov and Tolga Duman, tackles a more realistic scenario: What if the glitches have "memory"?

Think of it like a stormy day. If it's raining heavily right now, it's very likely it will be raining heavily in the next minute too. The errors aren't random; they come in bursts. If the channel is in a "bad mood," it deletes a whole chunk of your message. If it's in a "good mood," it lets everything through. This is modeled using something called a Markov Chain—a fancy way of saying the system has states (like "Good" or "Bad") that it switches between, and the next state depends on the current one.

The Core Questions

The authors asked two big questions:

Does a limit exist? Even with these messy, memory-driven errors, is there a maximum speed (capacity) at which we can send information perfectly?
Does memory help or hurt? Does having these "bursty" errors make the channel worse, or does the predictability of the bursts actually help us send more data?

The "Magic" Proof

Proving that a limit exists for these messy channels is incredibly hard. It's like trying to measure the speed of a car that keeps changing its engine while driving.

The authors used a clever mathematical trick. They imagined adding "guard rails" or "filler bits" to the message. Think of these as special markers inserted between chunks of your message.

The Analogy: Imagine you are sending a long letter, but you insert a unique stamp every 100 words. Even if the delivery service deletes some words, the receiver knows, "Ah, the next 100 words belong to this section."
By using these markers, they could break the complex, memory-filled channel into smaller, independent pieces. They proved that even though the errors are connected (they have memory), the overall system is stable enough that a maximum speed (Shannon Capacity) definitely exists.

The Surprising Result: Memory is Good!

Here is the most exciting part. The authors ran computer simulations to compare two scenarios:

Random Errors: Deletions happen completely randomly (like static on a radio).
Memory Errors: Deletions happen in bursts (like a storm).

They found that having memory actually increases the channel's capacity.

Why?
Think of it like driving in traffic.

Random Errors (No Memory): It's like a car randomly swerving left or right every second. You can't predict it, so you have to drive very slowly to stay safe.
Memory Errors (Bursts): It's like a car that swerves wildly for 10 seconds, then drives perfectly straight for 10 minutes. Because the "bad" behavior is predictable (it's a burst), you can speed up during the "good" periods and just slow down or pause during the "bad" bursts.

Because the errors are clumped together, the "good" times are longer and more reliable. The receiver can anticipate the bad times and adjust, allowing for a higher overall data rate.

Real-World Application: DNA Storage

The paper was inspired by DNA storage. Scientists are trying to store digital data inside DNA molecules. However, when reading DNA, the machines often make mistakes where they skip letters or add extra ones.

The authors showed that these DNA errors aren't random; they follow patterns (memory).
By understanding this memory, we can design better coding schemes to store more data in DNA than we thought possible.

Summary

The Problem: Communication channels often mess up by deleting or adding data.
The Old View: We assumed these mess-ups were random.
The New View: These mess-ups often come in predictable bursts (memory).
The Result: We proved that even with these messy, bursty errors, there is a clear maximum speed for sending data.
The Twist: Surprisingly, the "bursty" nature of the errors makes the channel better than random errors because the predictability allows us to send data faster during the quiet periods.

In short: If your communication channel is a bit crazy, but its craziness is predictable, you can actually talk faster than if it were just randomly chaotic.

1. Problem Statement

The paper addresses the fundamental information-theoretic problem of determining the Shannon capacity for communication channels subject to synchronization errors (insertions, deletions, and substitutions), specifically when these errors exhibit memory.

Context: While synchronization errors are common in systems like DNA storage, magnetic recording, and wireless communications, the capacity of such channels is notoriously difficult to compute.
The Gap: Previous seminal work by Dobrushin established the existence of capacity for channels with independent and identically distributed (i.i.d.) synchronization errors. However, recent experimental evidence (particularly in DNA storage) suggests that insertion/deletion processes often possess memory (i.e., the occurrence of an error depends on previous states or errors).
The Challenge: It was an open question whether the Shannon capacity exists for channels where synchronization errors are governed by a Markov chain (Markov-IDS channels). Standard coding theorems for memoryless channels do not directly apply because the error process is non-stationary in the i.i.d. sense and the channel output length varies stochastically based on the state.

2. Methodology

The authors employ a rigorous information-theoretic approach to prove the existence of capacity and derive bounds. Their methodology involves three main pillars:

A. Generalization of Dobrushin's Framework

The authors extend Dobrushin's capacity theorem (which applies to i.i.d. errors) to the Markovian case. They decompose the proof of the capacity theorem into modular propositions regarding the properties of functions applied to channel sequences.

Function Transformation: They define a class of functions applied to channel outputs that preserve the mutual information capacity (i-capacity) and coding capacity (c-capacity).
Key Conditions: A function sequence preserves capacity if:
1. The size of its inverse image (pre-image) grows sub-linearly ( $o(n)$ ).
2. The probability of the function altering the output (non-bijective behavior) vanishes asymptotically.
Application: These propositions allow the authors to transform the complex Markov-IDS channel into a simpler, analyzable form (e.g., by inserting "guard" symbols or erasing specific blocks) without changing the fundamental capacity limits.

B. Proof of Information Stability

To prove the existence of Shannon capacity, the authors must demonstrate Information Stability.

Definition: A channel sequence is information-stable if the mutual information density converges in probability to the mutual information capacity as the block length $n \to \infty$ .
Technique: They utilize Fekete's Lemma (specifically a quasi-subadditive version) to prove the existence of the limit of mutual information.
Handling Markov States: They analyze the convergence of the Markov chain's state distribution to its stationary distribution ( $\pi$ ). By inserting sufficiently long "guard intervals" (blocks of filler bits) between transmission blocks, they effectively "reset" the Markov state, allowing the channel to be treated as a sequence of nearly independent components.

C. Variance Analysis

A critical step in proving information stability is bounding the variance of the mutual information density.

The authors derive a proposition showing that the variance of mutual information grows at a rate related to the square of the logarithm of the inverse of the smallest non-zero transition probability ( $\phi_n$ ).
They prove that for the Markov-IDS channel, this variance grows slowly enough ( $O(n^2)$ or sub-quadratic relative to the block length) to satisfy the conditions for information stability.

3. Key Contributions

Existence of Shannon Capacity for Markov-IDS Channels:
The primary theoretical contribution is the proof that channels where synchronization errors are governed by a stationary and ergodic finite-state Markov chain are information-stable. This implies that the Shannon capacity exists and is equal to the limit of the mutual information rate ( $C = \lim_{n\to\infty} \max I(X^n; Y^n)/n$ ).
Modular Proof Framework:
The paper introduces a set of reusable propositions (Propositions 3–6) regarding the perturbation of channel sequences. These tools allow researchers to prove capacity theorems for complex, non-trivial channel sequences by transforming them into simpler equivalents without altering capacity.
Numerical Capacity Bounds for Markov Deletion Channels:
The authors provide a specific numerical analysis for a two-state Markov deletion channel (a "bursty" deletion model).
- They derive upper bounds on capacity using a "genie-aided" approach where both transmitter and receiver are given side information about the block boundaries and the Markov states.
- They compare these bounds against the capacity of i.i.d. deletion channels with the same average deletion probability.

4. Key Results

Theoretical Result: For any Markov-IDS channel with an aperiodic and irreducible state transition matrix, the i-capacity exists and is independent of the initial state distribution. Furthermore, the c-capacity (coding capacity) equals the i-capacity.
Numerical Finding (Memory Increases Capacity):
- The numerical evaluation of the upper bounds reveals a counter-intuitive but significant result: Having memory in the deletion process increases the channel capacity compared to an i.i.d. deletion channel with the same average deletion probability.
- Reasoning: When deletions are bursty (correlated), the "bad" states (high deletion probability) and "good" states (low deletion probability) are more predictable. This predictability allows coding schemes to adapt better (e.g., by avoiding transmission during predicted bursty periods or utilizing the structure of the bursts), leading to a higher achievable rate.
- Data: The paper presents graphs (Figs. 2–4) showing that as the correlation strength increases (larger $1/\alpha$ , meaning longer stays in a specific state), the capacity upper bound rises significantly above the i.i.d. baseline.

5. Significance

Theoretical Advancement: This work resolves a long-standing open problem regarding the existence of capacity for synchronization error channels with memory, moving beyond the restrictive i.i.d. assumption.
Practical Implications for DNA Storage: Since DNA storage channels exhibit bursty insertion/deletion errors due to synthesis and sequencing processes, this paper provides the theoretical justification for designing high-rate codes specifically for these memory-dependent channels. It suggests that leveraging the memory structure (rather than treating errors as random noise) can yield higher storage densities.
Methodological Impact: The modular propositions developed in the paper serve as a toolkit for future research. They can be applied to other complex channel models, such as those with intersymbol interference (ISI) combined with synchronization errors, or nanopore sequencing models where state transitions depend on input sequences.

In summary, the paper bridges the gap between classical information theory and modern physical channel models by proving that synchronization error channels with Markovian memory are information-stable and, crucially, that this memory can be exploited to achieve higher transmission rates than memoryless models.