pith. sign in

arxiv: 2601.11520 · v3 · submitted 2026-01-16 · 💻 cs.IT · math.IT

Empirical Coordination over Markov Channel with Independent Source

Mengyuan Zhao , Ma\"el Le Treust , Tobias J. Oechtering This is my paper

Pith reviewed 2026-05-16 13:11 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords empirical coordinationMarkov channeljoint source-channel codingstrictly causal encoderinput-driven typicalitysingle-letter boundsachievable distributions
0
0 comments X

The pith

Single-letter inner and outer bounds characterize achievable joint distributions for empirical coordination over Markov channels with strictly causal encoders.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies joint source-channel coding over Markov channels and determines which empirical distributions of source and channel symbols can be induced by a coding scheme. It focuses on strictly causal encoders that generate channel inputs without access to past states, thereby driving the channel's Markov evolution. The central result is a pair of single-letter inner and outer bounds on the set of achievable joint distributions that coordinate all symbols in the network. The inner bound is proved by introducing input-driven Markov typicality, whose properties allow direct exploitation of the channel memory rather than blockwise independence arguments. A reader would care because the result gives explicit, computable descriptions of inducible distributions for channels that retain memory across time slots.

Core claim

The set of achievable joint distributions for empirical coordination of an independent source with a Markov channel admits single-letter inner and outer bounds when encoders are strictly causal. The inner bound is obtained by introducing input-driven Markov typicality and establishing its fundamental properties for sequences generated by encoders that drive the state process without observing past states. This approach replaces classical block-Markov arguments that rely on blockwise independence and directly uses the Markov structure of the channel.

What carries the argument

Input-driven Markov typicality, a new notion of typicality for sequences produced when strictly causal encoders drive the Markov state evolution without access to past states.

If this is right

  • Achievable coordination distributions are described by single-letter expressions without requiring blockwise independence.
  • All symbols in the network, including channel states, can be coordinated under the derived bounds.
  • Classical block-Markov coding schemes can be replaced by direct Markov-structure arguments.
  • The framework applies to joint source-channel coding problems where encoders lack access to past channel states.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bounds may be used to design coding schemes for specific Markov channels such as Gilbert-Elliott or finite-state fading models.
  • The typicality notion could extend to channels with feedback or to coordination problems with common randomness.
  • Numerical evaluation of the bounds for binary symmetric Markov channels would reveal how much coordination gain memory provides compared with memoryless approximations.

Load-bearing premise

The fundamental properties of input-driven Markov typicality hold when encoders are strictly causal and drive the state evolution.

What would settle it

A concrete joint distribution that lies inside the outer bound but cannot be achieved by any sequence of strictly causal encoders, or that lies outside the inner bound yet is achieved by some coding scheme, for a fixed Markov channel and independent source.

Figures

Figures reproduced from arXiv: 2601.11520 by Ma\"el Le Treust, Mengyuan Zhao, Tobias J. Oechtering.

Figure 1
Figure 1. Figure 1: Joint source-channel coding with strictly causal encoder [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
read the original 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 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 the blockwise independence for discrete memoryless channels, our analysis directly exploits the Markov channel structure and improves beyond the independence-based arguments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies empirical coordination over a Markov channel with an independent source, where the encoders are strictly causal (driving the channel state evolution without access to past states). The central claim is a single-letter characterization consisting of inner and outer bounds on the set of achievable joint distributions over all source and channel symbols. The inner bound is obtained by introducing and analyzing a new notion of input-driven Markov typicality whose properties are derived directly from the channel's Markov structure, rather than from blockwise independence assumptions used in classical block-Markov schemes for memoryless channels.

Significance. If the single-letter bounds are valid, the result meaningfully extends the empirical coordination framework from discrete memoryless channels to channels with memory. The parameter-free nature of the characterization and the direct exploitation of the Markov structure (instead of imposed independence) are strengths. The new input-driven Markov typicality may prove useful in other settings involving driven Markov processes. The work supplies a concrete, falsifiable description of achievable coordination distributions that can be checked against the channel transition kernel.

major comments (2)
  1. [input-driven Markov typicality definition and properties] The section defining input-driven Markov typicality: the stated properties (e.g., that the typical set probability tends to 1 and that the induced marginals match the target joint distribution) are asserted to follow from the Markov chain structure, but the explicit verification that these properties survive when the input sequence is generated by a strictly causal encoder (which itself depends on the evolving state) is not fully expanded; this step is load-bearing for the inner-bound achievability argument.
  2. [main theorem on achievable distributions] Theorem stating the inner and outer bounds: the outer bound is derived via standard single-letter mutual-information arguments, yet it is not immediately clear whether the strictly causal constraint and the resulting state dependence are fully accounted for in the converse; a short auxiliary lemma showing that any achievable joint distribution must satisfy the outer-bound inequalities would close this gap.
minor comments (2)
  1. Notation for the joint empirical distribution and the target coordination distribution could be unified with the standard empirical-coordination literature to ease comparison.
  2. The network diagram (or its textual description) should explicitly label the independent source, the strictly causal encoder, the Markov channel, and the decoder outputs to clarify which symbols are being coordinated.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the significance, and constructive suggestions. We address each major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: The section defining input-driven Markov typicality: the stated properties (e.g., that the typical set probability tends to 1 and that the induced marginals match the target joint distribution) are asserted to follow from the Markov chain structure, but the explicit verification that these properties survive when the input sequence is generated by a strictly causal encoder (which itself depends on the evolving state) is not fully expanded; this step is load-bearing for the inner-bound achievability argument.

    Authors: We agree that an expanded verification is warranted for clarity. The properties are derived directly from the Markov structure of the channel and the definition of input-driven typicality, which accounts for the causal dependence of the input on the evolving state. In the revised manuscript we will add a detailed appendix subsection that explicitly verifies the probability tending to 1 and the marginal consistency under strictly causal encoding, using the Markov property to bound the deviation terms without relying on blockwise independence. revision: yes

  2. Referee: Theorem stating the inner and outer bounds: the outer bound is derived via standard single-letter mutual-information arguments, yet it is not immediately clear whether the strictly causal constraint and the resulting state dependence are fully accounted for in the converse; a short auxiliary lemma showing that any achievable joint distribution must satisfy the outer-bound inequalities would close this gap.

    Authors: The converse derivation already incorporates the strictly causal constraint by single-letterizing the mutual information terms while respecting the causal information flow and the resulting state dependence induced by the Markov channel. To make this explicit and close the gap noted by the referee, we will insert a short auxiliary lemma immediately preceding the main theorem that shows any achievable joint distribution must satisfy the outer-bound inequalities under the strictly causal encoder constraint. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives single-letter inner and outer bounds on achievable joint distributions by introducing input-driven Markov typicality and proving its fundamental properties directly from the Markov channel structure and strictly causal encoder constraints. No step reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation; the construction is parameter-free and exploits the channel Markov property without blockwise independence assumptions. This matches the provided reader's assessment of internal consistency with no hidden reduction to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on standard information-theoretic modeling of independent sources and Markov channels plus the newly defined typicality concept; no explicit free parameters or invented physical entities are mentioned.

axioms (2)
  • domain assumption The source is independent and the channel is Markovian with strictly causal encoding
    Stated directly in the title and abstract as the setup for the coordination problem.
  • ad hoc to paper Input-driven Markov typicality satisfies the required properties for bounding achievable distributions
    The abstract says the inner bound is established by developing fundamental properties of this new typicality notion.
invented entities (1)
  • input-driven Markov typicality no independent evidence
    purpose: To prove the inner bound by directly exploiting the Markov channel structure without blockwise independence
    Explicitly introduced in the abstract as a new notion to establish the inner bound.

pith-pipeline@v0.9.0 · 5430 in / 1335 out tokens · 28127 ms · 2026-05-16T13:11:18.972952+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Iterated random functions,

    P. Diaconis and D. Freedman, “Iterated random functions,” SIAM review, vol. 41, no. 1, pp. 45–76, 1999

    work page 1999

  2. [2]

    Rates of convergence for chains of expansive markov operators,

    N. Hermer, D. R. Luke, and A. Sturm, “Rates of convergence for chains of expansive markov operators,” Transactions of Mathematics and Its Applications, vol. 7, no. 1, p. tnad001, 2023

    work page 2023

  3. [3]

    Probabilistic contraction analysis of iterated random operators,

    A. Gupta, R. Jain, and P. Glynn, “Probabilistic contraction analysis of iterated random operators,” IEEE Transactions on Automatic Control , vol. 69, no. 9, pp. 5947–5962, 2024

    work page 2024

  4. [4]

    K. J. ˚Astr¨om, Introduction to stochastic control theory . Courier Corpo- ration, 2012

    work page 2012

  5. [5]

    Bertsekas, Dynamic programming and optimal control: Volume I , vol

    D. Bertsekas, Dynamic programming and optimal control: Volume I , vol. 4. Athena scientific, 2012

    work page 2012

  6. [6]

    A dynamic pivot mechanism with application to real time pricing in power systems,

    T. Tanaka, A. Z. W. Cheng, and C. Langbort, “A dynamic pivot mechanism with application to real time pricing in power systems,” in 2012 American Control Conference (ACC), pp. 3705–3711, IEEE, 2012

    work page 2012

  7. [7]

    Proof of shannon’s transmission theorem for finite-state indecomposable channels,

    D. Blackwell, L. Breiman, and A. J. Thomasian, “Proof of shannon’s transmission theorem for finite-state indecomposable channels,” The Annals of Mathematical Statistics , pp. 1209–1220, 1958

    work page 1958

  8. [8]

    R. G. Gallager, Information theory and reliable communication, vol. 588. Springer, 1968

    work page 1968

  9. [9]

    Ergodicity of markov channels,

    R. Gray, M. Dunham, and R. Gobbi, “Ergodicity of markov channels,” IEEE transactions on information theory , vol. 33, no. 5, pp. 656–664, 1987

    work page 1987

  10. [10]

    A general formula for channel capacity,

    S. Verd ´u et al., “A general formula for channel capacity,” IEEE Trans- actions on Information Theory , vol. 40, no. 4, pp. 1147–1157, 1994

    work page 1994

  11. [11]

    Capacity, mutual information, and coding for finite-state markov channels,

    A. J. Goldsmith and P. P. Varaiya, “Capacity, mutual information, and coding for finite-state markov channels,” IEEE transactions on Information Theory, vol. 42, no. 3, pp. 868–886, 2002

    work page 2002

  12. [12]

    Causality, feedback and directed information,

    J. Massey et al., “Causality, feedback and directed information,” inProc. Int. Symp. Inf. Theory Applic.(ISITA-90) , vol. 2, p. 1, 1990

    work page 1990

  13. [13]

    Finite state channels with time-invariant deterministic feedback,

    H. H. Permuter, T. Weissman, and A. J. Goldsmith, “Finite state channels with time-invariant deterministic feedback,”IEEE Transactions on Information Theory , vol. 55, no. 2, pp. 644–662, 2009

    work page 2009

  14. [14]

    The capacity of finite-state markov channels with feedback,

    J. Chen and T. Berger, “The capacity of finite-state markov channels with feedback,” IEEE Transactions on Information Theory , vol. 51, no. 3, pp. 780–798, 2005

    work page 2005

  15. [15]

    The capacity of channels with feedback,

    S. Tatikonda and S. Mitter, “The capacity of channels with feedback,” IEEE Transactions on Information Theory , vol. 55, no. 1, pp. 323–349, 2008

    work page 2008

  16. [16]

    Capacity of a post channel with and without feedback,

    H. H. Permuter, H. Asnani, and T. Weissman, “Capacity of a post channel with and without feedback,” IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 6041–6057, 2014

    work page 2014

  17. [17]

    Capacity of finite state channels with feedback: Algorithmic and optimization theoretic properties,

    A. Grigorescu, H. Boche, R. F. Schaefer, and H. V . Poor, “Capacity of finite state channels with feedback: Algorithmic and optimization theoretic properties,” IEEE Transactions on Information Theory, vol. 70, no. 8, pp. 5413–5426, 2024

    work page 2024

  18. [18]

    Actions speak louder than words: Rate-reward trade-off in markov decision processes,

    H. Wu, G. Chen, and D. G ¨und¨uz, “Actions speak louder than words: Rate-reward trade-off in markov decision processes,” arXiv preprint arXiv:2502.03335, 2025

    work page arXiv 2025

  19. [19]

    A mathematical theory of communication,

    C. E. Shannon, “A mathematical theory of communication,” The Bell system technical journal , vol. 27, no. 3, pp. 379–423, 1948

    work page 1948

  20. [20]

    Joint source–channel coding: Fundamentals and recent progress in practical designs,

    D. G ¨und¨uz, M. A. Wigger, T.-Y . Tung, P. Zhang, and Y . Xiao, “Joint source–channel coding: Fundamentals and recent progress in practical designs,” Proceedings of the IEEE , 2024

    work page 2024

  21. [21]

    Coordination using implicit communication,

    P. Cuff and L. Zhao, “Coordination using implicit communication,” in 2011 IEEE Information Theory Workshop , pp. 467–471, IEEE, 2011

    work page 2011

  22. [22]

    Empirical processes, typical sequences, and coordinated actions in standard borel spaces,

    M. Raginsky, “Empirical processes, typical sequences, and coordinated actions in standard borel spaces,” IEEE Transactions on Information Theory, vol. 59, no. 3, pp. 1288–1301, 2012

    work page 2012

  23. [23]

    Coordination capacity,

    P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” IEEE Transactions on Information Theory , vol. 56, no. 9, pp. 4181– 4206, 2010

    work page 2010

  24. [24]

    Hybrid codes needed for coordination over the point-to-point channel,

    P. Cuff and C. Schieler, “Hybrid codes needed for coordination over the point-to-point channel,” in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pp. 235–239, IEEE, 2011

    work page 2011

  25. [25]

    Empirical coordination with channel feedback and strictly causal or causal encoding,

    M. Le Treust, “Empirical coordination with channel feedback and strictly causal or causal encoding,” in 2015 IEEE International Symposium on Information Theory (ISIT) , 2015

    work page 2015

  26. [26]

    Joint empirical coordination of source and channel,

    M. Le Treust, “Joint empirical coordination of source and channel,” IEEE Transactions on Information Theory , vol. 63, no. 8, pp. 5087– 5114, 2017

    work page 2017

  27. [27]

    Empirical coordination with two-sided state information and correlated source and state,

    M. Le Treust, “Empirical coordination with two-sided state information and correlated source and state,” in 2015 IEEE International Symposium on Information Theory (ISIT) , pp. 466–470, IEEE, 2015

    work page 2015

  28. [28]

    Power-estimation trade-off of vector-valued Witsenhausen counterexample with causal decoder,

    M. Le Treust and T. J. Oechtering, “Power-estimation trade-off of vector-valued Witsenhausen counterexample with causal decoder,”IEEE Transactions on Information Theory , vol. 70, no. 3, pp. 1588–1609, 2024

    work page 2024

  29. [29]

    Coordination coding with causal encoder for vector-valued Witsenhausen counterexample,

    M. Zhao, M. Le Treust, and T. J. Oechtering, “Coordination coding with causal encoder for vector-valued Witsenhausen counterexample,” in 2024 IEEE International Symposium on Information Theory (ISIT) , pp. 3255–3260, IEEE, 2024

    work page 2024

  30. [30]

    Causal vector-valued Wit- senhausen counterexamples with feedback,

    M. Zhao, M. Le Treust, and T. J. Oechtering, “Causal vector-valued Wit- senhausen counterexamples with feedback,” in 2024 IEEE Information Theory Workshop (ITW), pp. 687–692, IEEE, 2024

    work page 2024

  31. [31]

    Causal state communication,

    C. Choudhuri, Y .-H. Kim, and U. Mitra, “Causal state communication,” IEEE Transactions on Information Theory , vol. 59, no. 6, pp. 3709– 3719, 2013

    work page 2013

  32. [32]

    J. R. Norris, Markov chains. No. 2, Cambridge university press, 1998

    work page 1998

  33. [33]

    Breuer and D

    L. Breuer and D. Baum, An introduction to queueing theory and matrix- analytic methods. Springer, 2005

    work page 2005

  34. [34]

    Huang, Linear Coding, Applications and Supremus Typicality

    S. Huang, Linear Coding, Applications and Supremus Typicality . PhD thesis, KTH Royal Institute of Technology, 2015

    work page 2015

  35. [35]

    The method of types [information theory],

    I. Csisz ´ar, “The method of types [information theory],” IEEE Transac- tions on Information Theory , vol. 44, no. 6, pp. 2505–2523, 2002

    work page 2002

  36. [36]

    The error exponent for the noiseless encoding of finite ergodic markov sources,

    L. Davisson, G. Longo, and A. Sgarro, “The error exponent for the noiseless encoding of finite ergodic markov sources,”IEEE Transactions on Information Theory , vol. 27, no. 4, pp. 431–438, 2003

    work page 2003

  37. [37]

    T. M. Cover and J. A. Thomas, Elements of information theory . John Wiley & Sons, 1999. APPENDIX D PROPERTY OF THE INPUT-DRIVEN MARKOV TYPICALITY Under Assumption A, the induced transition matrix TY |Y ′ = [Ti,j]i,j∈Y of the Markov chain Y n does not depend on time t ∈ [1 : n], where Ti,j = P(Yk = j|Yk−1 = i) = X x∈X PX(x)WY |X,Y ′(Yk = j|Xk = x, Yk−1 = i...

    work page 1999

  38. [38]

    If (xn, yn) ∈ T (n) ε (QY ′XY ), then xn ∈ T (n) ε (PX), yn ∈ T (n) ε (πY ′ · TY |Y ′), yn ∈ T (n) 2ε (QY ′XY |xn) conditional typical, where T is the marginalized transition matrix of Markov sequence Y n given in (16)

    work page

  39. [39]

    If xn ∈ T (n) ε (PX), yn ∈ T (n) 2ε (QY ′XY |xn), then (xn, yn) ∈ T (n) 2ε (QY ′XY ) Proof. 1) Proof of item 1: If (xn, yn) ∈ T (n) ε (QY ′XY ), then ε ≥ ∥Qn Y ′XY − QY ′XY ∥1 = X x∈X ,i,j∈Y Qn Y ′XY (i, x, j) − πY ′(i)PX(x)WY |X,Y ′(j|x, i) ≥ X x X i,j Qn Y ′XY (i, x, j) − πY ′(i)PX(x)WY |X,Y ′(j|x, i) = X x |Qn X(x) − PX(x)| = ∥Qn X − PX ∥1 Similarly, ε...

    work page

  40. [40]

    APPENDIX E PROOF FOR THEOREM 2 Define the stochastic process for t ≥ 1: St = (Yt−1, Xt, Yt) (16) It is obviously a Markov chain

    Proof of item 2: ∥Qn Y ′XY − πY ′PX WY |X,Y ′∥1 = ∥Qn Y ′XY − πY ′Qn X WY |X,Y ′ + πY ′Qn X WY |X,Y ′ − πY ′PX WY |X,Y ′∥1 ≤ ∥Qn Y ′XY − πY ′Qn X WY |X,Y ′∥1+∥πY ′Qn X WY |X,Y ′ − πY ′PX WY |X,Y ′∥1 ≤ 2ε. APPENDIX E PROOF FOR THEOREM 2 Define the stochastic process for t ≥ 1: St = (Yt−1, Xt, Yt) (16) It is obviously a Markov chain. We show first, that {St...

    work page