Empirical Coordination over Markov Channel with Independent Source
Mengyuan Zhao 1 , Maël Le Treust 2 , Tobias J. Oechtering 1 · 2026
Read Empirical Coordination over Markov Channel with Independent Source by Mengyuan Zhao 1 , Maël Le Treust 2 , Tobias J. Oechtering 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11520.txt.
Introduction
Mengyuan Zhao, Mael Le Treust, and Tobias Oechtering study coordination over Markov channels. Their 2026 preprint uses the empirical coordination framework. Joint source-channel coding sends data while shaping joint statistics. The channel here is a Markov channel, with memory in its state.
The source is independent, which sets a clean test case. The team asks which joint distributions can be induced. Source and channel symbol statistics are the quantities in play. Encoders are strictly causal and see no past channel states. Each output still drives how the Markov state evolves. The results mark the limits of coding under those rules. Such limits guide code design for channels with memory.
Catalog record
| CREATOR | Mengyuan Zhao 1 , Maël Le Treust 2 , Tobias J. Oechtering 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11520
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Empirical Coordination over Markov Channel with Independent Source Thanks: This work is supported by Swedish Research Council (VR) under grant 2020-03884. The work of M. Le Treust is supported by the French National Agency for Research (ANR) via the project n°ANR-22-PEFT-0010 of the France 2030 program PEPR Futur Networks. Mengyuan Zhao 1 , Maël Le Treust 2 , Tobias J. Oechtering 1 Abstract We study joint source–channel coding over Markov channels through the empirical coordination framework. More specifically, we aim at determining the empirical distributions of source and channel symbols that can be induced by a coding scheme. We consider strictly causal encoders that generate channel inputs, without access to the past channel states, henceforth driving the current Markov state evolution. Our main result is the single-letter inner and outer bounds of the set of achievable joint distributions, coordinating all the symbols in the network. To establish the inner bound, we introduce a new notion of typicality, the input-driven Markov typicality, and develop its fundamental properties. Contrary to the classical block-Markov coding schemes that rely on blockwise independence for discrete memoryless channels, our analysis directly exploits the Markov channel structure and improves beyond the independence-based arguments. I Introduction Markov chains, as canonical models of stochastic recursion, are often represented as being driven by exogenous independent randomness [ 1 ] . This perspective casts the evolution as a state update rule acted on by fresh external randomness at each step, unifying formulations across random dynamical systems and stochastic algorithms. When combined with structural conditions such as monotonicity or contractivity, it leads to tractable analyses of stationarity and convergence [ 2 , 3 ] . From a control perspective, such exogenous inputs correspond to the classical open-loop operation [ 4 , 5 , 6 ] . In information theory literature, Markov channels, sometimes known as finite state channels (FSC), have been studied extensively through the lens of channel capacity and control mechanisms [ 7 , 8 , 9 , 10 , 11 ] . When feedback is available, the encoder observes the channel state and can adapt its inputs accordingly, leading to a rich body of results on FSCs with feedback [ 12 , 13 , 14 , 15 , 16 , 17 ] . These capacity characterizations, however, are complicated and typically involve multi-letter expressions. Recently, under the assumption of unichain and ergodicity, a single-letter capacity representation was obtained for Markov channels with feedback [ 18 ] . In this work, we study the Markov evolution structure from a joint source–channel coding (JSCC) perspective [ 19 , 20 ] . Specifically, the source sequence is generated independently at each time, and the channel input is generated by strictly causal encoders based solely on the past source sequence, and does not adapt to the latent channel state history. The channel input, together with the previous state, updates the current channel state. The decoder operates noncausally, observing the entire state sequence to produce its action sequence. Empirical coordination coding framework, introduced in [ 21 , 22 , 23 ] , characterizes cooperative behavior among agents by requiring the empirical distribution of symbol sequences to converge to a prescribed target distribution. In this framework, encoders and decoders select their actions based on local observations not only to ensure reliable communication, but also to induce a desired joint behavior. Coordination results for JSCC with (strictly) causal decision-makers over dmc ( dmc ) were established in [ 24 , 25 ] . Extensions to point-to-point settings with channel state or feedback were developed in [ 26 , 27 ] , and recently have been further applied to distributed decision-making [ 28 , 29 , 30 ] etc.. To the best of our knowledge, this work is the first to study JSCC over Markov channels through the lens of coordination coding. Under our Markov channel model assumption, we derive single-letter inner and outer bounds that characterize the set of achievable joint distributions that can be arbitrarily well approximated by suitable coding schemes. To establish the inner bound, we introduce a new notion of typicality, the input-driven Markov typicality, and develop its fundamental properties, such as asymptotic equipartition property (AEP) and a packing lemma, etc.. In contrast to the standard random-coding arguments for dmc that rely on block independence in the block-Markov coding constructions, such as in [ 27 , 31 ] , this notion of typicality enables us to exploit the Markov channel structure directly, allowing the analysis to go beyond independence-based arguments while still recovering the results. The outer bound shares the same information constraint expression as the inner bound, but is defined over a generally larger set of distributions. Enc. X_{t} \mathcal{W}(Y_{t}|X_{t},Y_{t-1}) Y^{n} Dec. V^{n} U^{t-1} Fig. 1 : Joint source-channel coding with strictly causal encoder and noncausal decoder over Markov channel This paper is structured as follows: Our problem is formulated in Section II . Section III presents our main results, which comprise the inner and outer bounds for the achievable distribution region. In the Appendices, we introduce the input-driven Markov typicality and prove the main results. II System Model We study the problem depicted in Fig. 1 . Capital letters, like U , denote random variables, calligraphic fonts, like \mathcal{U} , denote alphabets, and lowercase letters, like u\in\mathcal{U} , denote the realizations of random variables. We assume all the alphabets considered here \mathcal{U},\mathcal{X},\mathcal{Y},\mathcal{V} are finite. The \ell_{1} distance between two probability distributions \mathcal{Q} and \mathcal{P} is denoted by \lVert\mathcal{Q}-\mathcal{P}\lVert_{1}=\sum_{u}\left\lvert\mathcal{Q}(u)-\mathcal{P}(u)\right\rvert . The probability is denoted by \mathbb{P}(\cdot) . We assume the source is drawn i.i.d. \sim\mathcal{P}_{U} , and the channel is stationary Markov with one step memory of the latent state, with conditional distribution \mathcal{W}_{Y|X,Y^{\prime}} . Moreover, the statistics of the source and channel are known by both agents. Definition 1 . A code with strictly causal encoder and noncausal decoder is a tuple of (deterministic) functions c=(\{f^{(t)}_{X_{t}|U^{t-1}}\}_{t=1}^{n},g_{V^{n}|Y^{n}}) defined by f^{(t)}_{X_{t}|U^{t-1}}:\mathcal{U}^{t-1}\longrightarrow\mathcal{X},\quad g_{V^{n}|Y^{n}}:\mathcal{Y}^{n}\longrightarrow\mathcal{V}^{n}, (1) where U_{0}\triangleq\varnothing . We denote by \mathcal{C}(n) the set of codes with strictly causal encoder and non-causal decoder. We assume the initial channel state Y_{0} is arbitrary. Then, a code c\in\mathcal{C}(n) induces a joint distribution on sequences (U^{n},X^{n},Y^{n},V^{n}) given by \displaystyle\mathcal{P}_{U}^{\otimes n}\prod_{t=1}^{n}\left[f^{(t)}_{X_{t}|U^{t-1}}\cdot\mathcal{W}_{Y_{t}|X_{t},Y_{t-1}}\right]g_{V^{n}|Y^{n}}, (2) from which we have the following: \displaystyle U_{t}\perp\!\!\!\perp(X_{t},Y_{t}), (3) \displaystyle X_{t}-\!\!\!\!\minuso\!\!\!\!-U^{t-1}-\!\!\!\!\minuso\!\!\!\!-Y^{t-1}, (4) \displaystyle Y_{t}-\!\!\!\!\minuso\!\!\!\!-(X_{t},Y_{t-1})-\!\!\!\!\minuso\!\!\!\!-(U^{t-1},X^{t-1},Y^{t-2}), (5) where ( 3 ) comes from the independent source and strictly causal encoding, ( 4 ) is our strictly causal encoder, and ( 5 ) is the Markov channel. We denote the empirical distribution Q^{n}\in\Delta(\mathcal{U}\times\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}\times\mathcal{V}) of sequences (u^{n},x^{n},y^{n},v^{n}) by \displaystyle Q^{n}(u,x,y^{\prime},y,v) (6) \displaystyle=\frac{1}{n}\sum_{t=1}^{n}\mathbf{1}\{u_{t}=u,x_{t}=x,y_{t-1}=y^{\prime},y_{t}=y,v_{t}=v\}, \displaystyle\qquad\qquad\qquad\forall(u,x,y^{\prime},y,v)\in\mathcal{U}\times\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}\times\mathcal{V}. Note here, we take into account the adjacent pairs (y_{t-1},y_{t}) in the Markov sequence y^{n} . Definition 2 . We define a joint distribution \mathcal{P}_{U,X,Y^{\prime},Y,V}\in\Delta(\mathcal{U}\times\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}\times\mathcal{V}) to be achievable, if for all \varepsilon\geq 0 , there exists N_{0}\in\mathbb{N} , such that for all n\geq N_{0} , we can find a sequence of codes c\in\mathcal{C}(n) , such that the joint empirical distribution given by ( 6 ) satisfying that \displaystyle\mathbb{P}(||Q^{n}-\mathcal{P}_{U,X,Y^{\prime},Y,V}||_{1}\geq\varepsilon)\leq\varepsilon. (7) We impose the following assumption: Assumption A . For every stationary channel input distribution \mathcal{P}_{X} on \mathcal{X} , the induced Markov chain Y^{n}=\{Y_{1},\ldots,Y_{n}\} admits a unique recurrent class \mathcal{R}_{Y}\subseteq\mathcal{Y} that is irreducible and aperiodic. The above assumption is standard, see [ 32 , 33 , 18 ] , [ 34