Capacity Convergence of Markov Approximations

11 concepts5 papers1 proposal

When transmitting data over a standard memoryless channel, calculating the maximum reliable transmission rate—the channel capacity—is straightforward. Because each transmitted symbol encounters independent noise, we can optimize the input distribution for a single channel use.

However, real-world physical systems often introduce memory and synchronization errors, such as symbol deletions or duplications. In a deletion channel, the receiver does not just receive corrupted bits; it receives a shortened sequence without knowing which bits were lost. This breaks the alignment between input and output indices, meaning the channel's behavior at any given moment depends on its entire history.

To calculate the capacity of these complex channels, researchers use Markov approximations. Instead of optimizing over all possible infinitely long input distributions, they restrict the input to an $m$-th order Markov chain. This limits the memory history to a manageable window, making the capacity numerically computable. But a critical question remains: as we increase the complexity of our approximation ($m \to \infty$), does this sequence of finite-memory capacities actually converge to the true capacity of the channel?

The Mechanics of Markov Approximations

To evaluate channels with both synchronization errors and state-dependent noise, Yonglong Li and Vincent Y. F. Tan investigated concatenated channels formed by a deletion channel and a finite-state channel. In On the Capacity of Deletion Channels with States and On the Capacity of Channels With Deletions and States, the authors established a vital theoretical bridge: the operational capacity (the highest actual rate of reliable communication) is mathematically equivalent to its stationary capacity.

To compute this stationary capacity, the authors validated the Markov approximation scheme. The core mechanism relies on optimizing over finite-memory inputs of an increasing order $m$. This creates a sequence of calculated capacities that behaves predictably:

$$\lim_{m \to \infty} C_m = C_{\text{true}}$$

As the order $m$ approaches infinity, the input process can capture increasingly long-range dependencies caused by the channel's memory. The authors proved that the sequence of capacities derived from these finite-order processes monotonically increases and converges directly to the true stationary capacity. This mathematical equivalence simplifies the analysis, allowing researchers to focus purely on stationary input processes to determine the fundamental limits of complex channels.

Establishing Information Stability

For an approximation scheme to converge to a meaningful limit, the underlying channel must be information stable. In simple terms, information stability guarantees that as a sequence grows longer, its sample mutual information rate concentrates tightly around its theoretical expectation. This is a manifestation of the Asymptotic Equipartition Property (AEP)—the information-theoretic equivalent of the Law of Large Numbers.

In channels with insertion and deletion errors, proving that the AEP holds is notoriously difficult because the asynchronous nature of the noise distorts the time index. Brendon McBain and Emanuele Viterbo tackled this challenge in the context of noisy duplication channels, which model the erratic readouts of DNA sequencers.

In On noisy duplication channels with Markov sources, the authors proved that when these channels are driven by an ergodic Markov source, the system remains information stable. The sample entropy of long sequences reliably approaches the theoretical entropy rate. This verification confirms that the Markov-constrained channel capacity is identical to the Markov-constrained Shannon capacity, validating the use of mutual information rates to compute real-world storage and transmission limits in asynchronous systems.

The Asymptotic Gap: From Theory to Practice

While proving that an approximation converges asymptotically ($\mathit{as } \ m \to \infty$) is a major theoretical triumph, it introduces a significant engineering bottleneck: the lack of an explicit convergence rate.

As Li et al. point out, knowing that a sequence converges does not tell you how fast it converges. Without an explicit rate or error bound, engineers cannot determine the exact Markov order $m$ required to achieve a target approximation accuracy. Computing higher-order Markov capacities becomes exponentially expensive, so running blind without knowing whether $m=3$ or $m=100$ is required limits the practical utility of the tool.

This tension between asymptotic convergence and practical implementation constants is a universal challenge across approximation theory, appearing prominently in neural network optimization as well:

Ultimately, whether optimizing the input distributions of a noisy DNA storage channel or sizing a deep neural network, the path forward requires moving past purely asymptotic proofs. Verifying that an approximation converges establishes that a problem is solvable; the next frontier is determining the explicit rates of convergence that allow us to solve it efficiently.

Key Foundational Work

On the Capacity of Deletion Channels with States (2020) — contributed 6 concept elements to this direction.
Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_markov_approximation_convergence_d1951f05,
  title = {Markov approximation convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-approximation-convergence/rdr_d1951f05f9054a918003453e3d86baa4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_markov_approximation_convergence_d1951f05_v1,
  title = {Markov approximation convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-approximation-convergence/rdr_d1951f05f9054a918003453e3d86baa4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake