Information Theory Beyond Memoryless Sources

44 concepts43 papers1 proposal

In classical information theory, the memoryless source assumption is a powerful mathematical convenience. By treating a data stream as a sequence of independent and identically distributed (i.i.d.) random variables, the joint entropy of a sequence decomposes into a simple sum of individual entropies: $H(X_1, X_2, \dots, X_n) = nH(X_1)$. This assumption underpins foundational results in data compression, channel capacity, and network coding, allowing researchers to derive clean, single-letter asymptotic bounds.

However, real-world data streams—such as video frames, speech signals, sensor networks, and biometric identifiers—are rarely memoryless. What happens at time $t$ is deeply correlated with what happened at time $t-1$. When we force memoryless models onto sources that possess memory, our theoretical guarantees diverge from practical performance.

A major research direction focuses on dismantling the memoryless source assumption, uncovering how temporal and spatial dependencies fundamentally alter the limits of compression, security, and coordination.

The Cost of Assuming Independence

When a system assumes a source is memoryless, it treats every incoming symbol as a complete surprise. In reality, if a source has memory, the past contains a footprint of the future. Ignoring this footprint leads to systemic inefficiencies and vulnerabilities across several domains.

Rate-Distortion and Perception

In lossy compression, we trade off the transmission rate against the reconstruction distortion. Modern applications also demand high perceptual quality—ensuring the reconstructed data looks or sounds realistic.

Sadaf Salehkalaibar et al. demonstrate in Rate-Distortion-Perception Tradeoff Based on the Conditional-Distribution Perception Measure that evaluating perception requires shifting from marginal distributions to conditional distributions. However, they note that existing frameworks still heavily rely on memoryless assumptions, failing to capture the complex spatial and temporal correlations inherent in video or high-resolution imagery.

Similarly, Jiakun Liu et al. point out in An Indirect Rate-Distortion Characterization for Semantic Sources: General Model and the Case of Gaussian Observation that semantic source coding—where the goal is to preserve the "meaning" of a signal—cannot rely on i.i.d. models if it hopes to accurately represent real-world data streams like speech.

Security and Secrecy

In secure source coding, an encoder must compress data such that a legitimate decoder can reconstruct it, while an eavesdropper learns as little as possible. If the encoder designs its secrecy bounds around a memoryless assumption, it leaves a massive blind spot.

Joffrey Villard et al. show in Secure Lossy Source Coding with Side Information at the Decoders that ignoring temporal correlations prevents the direct application of theoretical secrecy regions to practical distributed sensing tasks. An adversary can exploit the unmodeled temporal dependencies to predict hidden states.

This vulnerability is echoed by Neri Merhav in A large deviations approach to secure lossy compression, who notes that real-world data like video or text requires moving toward Markovian structures to prevent information leakage.

Distributed Coordination

When multiple isolated nodes must generate coordinated random variables without communicating—a task known as non-interactive source simulation—the presence of memory changes the capacity of the system.

Deniz Gunduz et al. demonstrate in Remote Channel Synthesis that when data sources and noise channels are assumed to be memoryless, the resulting models significantly underperform when deployed on highly correlated real-world data streams.

Why Memory Changes the Intuition

To understand why memory changes the mathematics so deeply, consider the difference between symbol-by-symbol communication and block coding.

As Bixio Rimoldi et al. show in To Code, Or Not To Code: On the Optimality of Symbol-by-Symbol Communication, zero-delay, uncoded transmission is only optimal under highly specific cost functions that align with memoryless conditions. Once a source possesses memory, the optimal strategy must look across time.

The presence of memory introduces a fundamental tension:

  1. Predictability Saves Bandwidth: Because past states inform future states, the encoder can achieve much higher compression ratios or tracking accuracy by only transmitting the innovations (the unpredictable changes).
  2. State Space Explosion: Because the current state depends on the past, the encoder and decoder must maintain synchronized state representations, or the algorithm must adaptively learn the source's temporal structure on the fly.

This tension is clearly visible in distributed tracking. Victoria Kostina explores this in Fundamental limits of distributed tracking, analyzing a scenario where isolated sensors track a moving target. If the target's motion is modeled as a source with memory (a Gauss-Markov process), the sensors can drastically reduce their communication rate by exploiting the predictable trajectory of the target. A memoryless model would treat each position as a completely independent surprise, wasting precious communication bandwidth.

Memoryless Source (i.i.d.):
[X_1] -> Independent -> [X_2] -> Independent -> [X_3]
(Encoder must transmit the full entropy of every symbol)

Source with Memory (e.g., Markov):
[X_1] --Predicts--> [X_2] --Predicts--> [X_3]
(Encoder only needs to transmit the "innovation" or error signal)

Mathematical Frameworks for Modeling Memory

To capture these temporal dependencies without making the mathematics intractable, researchers employ several advanced structural models.

Stationary Mixing Sources

Instead of assuming complete independence, we can assume a source is stationary (its statistical properties do not change over time) and mixing (events that occur far apart in time become asymptotically independent).

Maxim Raginsky addresses this in Joint universal lossy coding and identification of stationary mixing sources with general alphabets. By leveraging Vapnik–Chervonenkis (VC) dimension theory, the author proves that it is possible to design a universal system that simultaneously compresses data and identifies the source's underlying statistical parameters, even when dealing with continuous alphabets and complex memory structures.

Adaptive and MCMC-Based Coding

When the exact memory structure of a source is unknown, compression algorithms must learn the dependencies dynamically.

Shirin Jalali et al. tackle this in Multiple Description Coding of Discrete Ergodic Sources by using a stationary coding framework combined with simulated annealing. This mechanism allows the system to adapt to the unknown, time-dependent statistics of ergodic sources.

Similarly, Dror Baron et al. introduce a Markov Chain Monte Carlo (MCMC) approach in An MCMC Approach to Universal Lossy Compression of Analog Sources, demonstrating that scalar quantization is highly suboptimal for analog signals unless the algorithm explicitly accounts for the correlations between current and past values.

Information Dimension

To quantify the complexity of continuous-valued signals that possess memory, researchers look to fractal geometry. Farideh Ebrahim Rezagah et al. prove in Rate-distortion dimension of stochastic processes that the Rate-Distortion Dimension (RDD) of an analog stationary process is equivalent to its Information Dimension (ID). This equivalence provides an operational bridge, linking a signal's internal temporal structure directly to its compressed-sensing recovery limits.

The Non-Asymptotic Frontier

While information theory has found success characterizing the asymptotic limits (infinite block lengths) of sources with memory, the non-asymptotic regime—where we must compress finite sequences—remains an open frontier.

The mathematical tools used to analyze finite block lengths often break down when independence is lost:

Integrating temporal dependencies into large-alphabet, finite-length frameworks represents the next major step in closing the gap between information-theoretic elegance and real-world engineering reality.

Key Foundational Work

To Code, Or Not To Code: On the Optimality of Symbol-by-Symbol Communication (2001) — contributed 1 concept elements to this direction.
Implementation and Experimental Evaluation of Flexible Parsing for Dynamic Dictionary Based Data Compression (1998) — 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_memoryless_source_assumption_ff9fc008,
  title = {memoryless source assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memoryless-source-assumption/rdr_ff9fc008822a46c3a0debd0f0d23d9e8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_memoryless_source_assumption_ff9fc008_v1,
  title = {memoryless source assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memoryless-source-assumption/rdr_ff9fc008822a46c3a0debd0f0d23d9e8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake