🔢 mathematics

Empirical Coordination over Markov Channel with Independent Source

This paper establishes single-letter inner and outer bounds for the set of achievable joint source-channel distributions over Markov channels with strictly causal encoders by introducing a novel "input-driven Markov typicality" framework that directly exploits the channel's Markov structure, surpassing traditional independence-based block-Markov coding arguments.

Original authors: Mengyuan Zhao, Maël Le Treust, Tobias J. Oechtering

Published 2026-04-10

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Mengyuan Zhao, Maël Le Treust, Tobias J. Oechtering

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 organize a massive, synchronized dance performance between two groups of people: the Senders (who have a script) and the Receivers (who need to perform specific moves).

Usually, in a perfect world, the Senders shout instructions, and the Receivers hear them perfectly and dance in unison. But in this paper, the world is messy. The "shouting" happens over a Markov Channel.

The Problem: The "Echoing Room"

Think of the communication channel not as a clear phone line, but as a room with a strange echo.

The Twist: The echo you hear right now depends not just on what you shouted now, but also on what you shouted a moment ago. The room has a "memory."
The Constraint: The Senders are blind. They can hear the past echoes (the channel state history), but they cannot hear the current echo while they are shouting. They have to guess how their current shout will interact with the room's lingering memory.
The Goal: The Senders and Receivers aren't just trying to get a message across; they are trying to coordinate. They want the entire sequence of shouts and dance moves to look like a specific, pre-planned pattern (a "joint distribution").

The Solution: "Input-Driven" Coordination

The authors, Zhao, Le Treust, and Oechtering, figured out exactly how to pull this off. They didn't just use standard math; they invented a new way of thinking about "typical" behavior in these echoey rooms.

Here is the breakdown of their magic trick:

1. The "Block-Markov" Relay Race

Instead of trying to coordinate one single shout at a time, they break the performance into blocks (like chapters in a book).

The Encoder (Sender): They don't just pick a random shout. They look at the script from the previous block and pick a shout for the current block that fits perfectly with the previous one, creating a smooth transition.
The Decoder (Receiver): They wait until they hear the entire performance (non-causal decoding). Then, they look back at the whole sequence to figure out which "script" was actually used, ignoring the noise and focusing on the pattern.

2. The New Tool: "Input-Driven Markov Typicality"

This is the paper's biggest innovation.

Old Way: In normal, non-echoing rooms, we assume every shout is independent. We just check if the crowd is "typical" (statistically average).
New Way: Because the room has memory, the authors realized you can't just look at the crowd in isolation. You have to look at the relationship between the Input (the shout) and the Output (the echo).
The Metaphor: Imagine a drummer (the Input) and a bouncing ball (the Channel State). The ball bounces differently depending on how hard the drummer hits it right now and how it was bouncing a second ago.
- The authors created a new rule called "Input-Driven Typicality." It's a way of saying: "If the drummer hits the drum in this specific rhythm, the ball will bounce in this specific, predictable pattern, even though the ball has its own momentum."
- This allows them to prove that even with the echo, the Senders and Receivers can lock into a perfect rhythm without needing to talk to each other in real-time.

3. The "Secret Handshake" (The Auxiliary Variable $W$ )

To make the coordination work, the authors introduce a "ghost" variable called $W$ .

Think of $W$ as a secret handshake or a shared mental map.
The Sender doesn't just send the message; they send a compressed version of the "plan" ( $W$ ) that helps the Receiver understand why the Sender chose that specific shout.
This secret handshake ensures that even though the channel is noisy and has memory, the Receiver can reconstruct the Sender's intent perfectly.

The Big Result: The "Rulebook"

The paper gives us a Rulebook (mathematical bounds) that tells us:

What is possible: If the "information constraint" (a balance between how much the channel can carry and how much coordination is needed) is met, the dance can happen perfectly.
What is impossible: If the channel is too echoey or the coordination too complex, no amount of clever coding will save the performance.

Why This Matters

In the real world, many systems have "memory."

Wireless networks: Signal interference often depends on what happened a split-second ago.
Robot swarms: A robot's movement affects its neighbors, which affects the next movement.
Biological systems: Cells react to chemical signals that linger in the environment.

This paper provides the mathematical blueprint for how to get these complex, memory-filled systems to work together in perfect harmony, without needing a central boss to micromanage every single step. They proved that by understanding the "echo" (the Markov structure) rather than fighting it, you can achieve perfect coordination.

1. Problem Formulation

The paper investigates Joint Source-Channel Coding (JSCC) within the framework of Empirical Coordination over Markov Channels. The specific system model involves:

Source: An independent and identically distributed (i.i.d.) source sequence $U^n$ .
Encoder: A strictly causal encoder. It generates channel inputs $X_t$ based only on the past source symbols $U^{t-1}$ . Crucially, the encoder has no access to past channel states or outputs (no feedback).
Channel: A stationary Markov channel with one-step memory. The channel state $Y_t$ evolves based on the current input $X_t$ and the previous state $Y_{t-1}$ , governed by the transition kernel $W_{Y|X,Y'}$ . The initial state $Y_0$ is arbitrary.
Decoder: A non-causal decoder. It observes the entire channel output sequence $Y^n$ to generate an action sequence $V^n$ .
Objective: To determine the set of achievable joint empirical distributions $P_{U,X,Y',Y,V}$ that can be induced by a coding scheme. Unlike traditional capacity problems focusing on error rates, this framework aims to coordinate the behavior of all agents (source, encoder, channel, decoder) to match a target joint distribution.

2. Methodology

The authors employ a combination of information-theoretic bounds and a novel typicality analysis tailored to the Markov structure.

A. Input-Driven Markov Typicality

A core methodological contribution is the introduction of Input-Driven Markov Typicality.

Context: Standard block-Markov coding for Discrete Memoryless Channels (DMCs) relies on block-wise independence. However, Markov channels introduce memory where the current state depends on the previous state, breaking simple independence assumptions.
Definition: The authors define a set of typical sequences $(x^n, y^n)$ where the empirical distribution of adjacent triplets $(y_{t-1}, x_t, y_t)$ converges to a target stationary distribution $Q_{Y'XY} = \pi_{Y'} P_X W_{Y|X,Y'}$ .
Properties: They prove fundamental properties for this typicality set, including:
- Ergodicity: The empirical distribution converges almost surely to the stationary equilibrium regardless of the initial state.
- Asymptotic Equipartition Property (AEP): Characterizing the probability mass of typical sequences.
- Cardinality Bounds: Establishing the size of the typical set.
Significance: This allows the analysis to exploit the Markov structure directly rather than relying on independence arguments that would be suboptimal or inapplicable.

B. Coding Scheme (Achievability)

To prove the inner bound, the authors propose a Block-Markov Random Coding scheme extended to the coordination framework:

Codebook Generation: Generate codewords $X^n(m)$ and auxiliary codewords $W^n(m, \hat{m})$ based on the target distribution.
Encoding: The encoder uses a sliding window approach. In block $b$ , it observes the source $U^n_{b-1}$ and finds an index $m_b$ such that the tuple $(U^n_{b-1}, X^n(m_{b-1}), W^n(m_{b-1}, m_b))$ is jointly typical.
Transmission: The channel transmits $X^n(m_b)$ . Due to the Markov nature, the channel state at the start of block $b$ depends on the last symbol of block $b-1$ .
Decoding: The non-causal decoder observes $Y^n$ and finds the unique index $\tilde{m}$ such that the input-driven Markov typicality conditions hold for the current and previous blocks.
Action Generation: The decoder generates $V^n$ based on the recovered sequences.

C. Converse Proof

The outer bound is derived using information inequalities. The proof involves:

Expanding mutual information terms using the chain rule.
Utilizing the strictly causal constraint ( $X_t$ depends only on $U^{t-1}$ ) and the Markov channel property.
Introducing a time-sharing random variable $T$ to single-letterize the bounds.
Defining an auxiliary random variable $W$ to capture the necessary information flow.

3. Key Contributions

First Coordination Study on Markov Channels: This is the first work to apply the empirical coordination framework to JSCC over Markov channels with strictly causal encoders and no feedback.
Input-Driven Markov Typicality: The introduction of this new typicality notion is a significant theoretical advancement. It enables the handling of channel memory without resorting to block-independence approximations, allowing for tighter analysis that recovers known results for DMCs as a special case.
Single-Letter Characterization: The paper provides single-letter inner and outer bounds for the achievable region of joint distributions. This is a significant simplification compared to the multi-letter expressions often required for Markov channel capacity.
Unified Framework: The results unify source-channel separation and coordination. The paper shows that when the source and channel variables are independent, the result reduces to a form analogous to Shannon's separation theorem.

4. Main Results

The set of achievable joint distributions $P_{U,X,Y',Y,V}$ is characterized by the existence of an auxiliary random variable $W$ satisfying specific factorization and information constraints.

Theorem 1 (Main Result):
A joint distribution is achievable if there exists an auxiliary variable $W$ such that:

Factorization: The joint distribution decomposes as:
$P_{U,X,Y',Y,V} = P_U P_X P_{W|U,X} \pi_{Y'} W_{Y|X,Y'} P_{V|Y,X,W}$
(Note: The outer bound allows for a slightly more general decomposition involving $Y'$ in the conditioning of $W$ , but the inner bound uses the simpler form above).
Information Constraint:
$I(X; Y | Y') - I(U; W | X) \geq 0$
Where:
- $I(X; Y | Y')$ represents the channel capacity of the Markov channel (with feedback capability in the capacity definition, though the encoder here is strictly causal, the bound reflects the channel's inherent information flow).
- $I(U; W | X)$ represents the rate required to coordinate the source $U$ with the decoder's action $V$ given the channel input $X$ .

Interpretation:
The condition implies that the "information flow" available through the channel (the conditional mutual information of input and output given the past state) must be sufficient to support the "coordination rate" required to link the source and the decoder's actions.

5. Significance and Implications

Beyond Independence: The paper demonstrates that for Markov channels, one cannot simply treat blocks as independent. The new "Input-Driven Markov Typicality" provides the rigorous mathematical tool to handle the dependency between blocks caused by the channel state memory.
Control and Coordination: The results are highly relevant for networked control systems and distributed decision-making where agents must coordinate actions based on noisy, memory-dependent observations without full feedback.
Theoretical Bridge: It bridges the gap between classical JSCC (reliability) and empirical coordination (behavioral matching), showing that the fundamental limits of coordination over channels with memory can be captured by single-letter information inequalities.
Practicality: By providing single-letter bounds, the paper offers a computationally tractable way to evaluate the performance limits of such systems, which is essential for designing efficient coding schemes for applications like IoT, autonomous vehicle coordination, and smart grids where channel memory is prevalent.