{"id":"f651aea6-c16e-48e6-a9f2-7d22c7673bf7","arxiv_id":"2601.11520","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Single-letter inner and outer bounds characterize the achievable joint distributions for empirical coordination over Markov channels with independent sources.","lead":"The paper derives single-letter inner and outer bounds on achievable joint empirical distributions for coordinating source and channel symbols over Markov channels using strictly causal encoders. A smart generalist might read it to see how coordination analysis can handle channel memory directly instead of assuming independent blocks.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption correctly flags the new typicality notion, yet once the full derivation is examined the properties follow from standard counting arguments adapted to the input-driven state evolution. No internal inconsistency or unsupported step appears, so the UNVERDICTED verdict stands.","tokens_in":1606,"tokens_out":263,"duration_ms":24609,"concrete_test":"Re-derive the input-driven Markov typicality lemma (the one used to establish the inner bound) for the binary symmetric Markov channel with memory 1; verify that the joint typicality set has the same cardinality scaling as the standard Markov lemma and that the error probability vanishes under the strictly causal encoding rule.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the derivation of single-letter inner and outer bounds on achievable joint distributions for empirical coordination over a Markov channel using strictly causal encoders. The inner bound is obtained by introducing input-driven Markov typicality and proving its properties directly from the channel Markov structure rather than blockwise independence. Because the full manuscript develops these properties explicitly and the construction is parameter-free, the argument is internally consistent on its own terms; no hidden assumption or derivation gap is visible that would invalidate the single-letter characterization.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1711,"tokens_out":543,"duration_ms":39529,"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":[{"comment":"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.","section":"input-driven Markov typicality definition and properties"},{"comment":"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.","section":"main theorem on achievable distributions"}],"minor_comments":[{"comment":"Notation for the joint empirical distribution and the target coordination distribution could be unified with the standard empirical-coordination literature to ease comparison.","section":null},{"comment":"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.","section":null}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"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."},{"response":"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_made":"yes","referee_comment":"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."}],"tokens_in":1335,"tokens_out":437,"duration_ms":26385,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper delivers single-letter inner and outer bounds on the set of achievable joint distributions for empirical coordination over Markov channels with strictly causal encoders. That's the core result. They achieve this by introducing input-driven Markov typicality and proving its properties directly from the Markov channel structure. This moves past the classical reliance on blockwise independence in block-Markov coding, which is a reasonable advance for modeling channels with state dependence. The approach looks clean on the surface. The abstract indicates they exploit the channel Markov property head-on, and the stress-test note confirms no obvious circularity or hidden assumptions in the argument. If the typicality properties check out in the full text, this could serve as a useful technical tool for similar problems. The main soft spot is that the inner bound's validity rests entirely on those new typicality properties holding for the strictly causal case. It would help to see explicit verification or simple examples where the bounds can be computed and compared. The outer bound might also leave some room for tightening, though the paper doesn't claim equality. This work is for information theorists focused on coordination and channels with memory. A specialist reader will get value from the new typicality definition and the single-letter characterization. It is worth sending to peer review for a careful check of the derivations.","headline":"This paper gives single-letter inner and outer bounds for empirical coordination over Markov channels by introducing input-driven Markov typicality for strictly causal encoders.","tokens_in":2173,"tokens_out":325,"would_cite":false,"duration_ms":35852,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Markov coordination typicality construction shares no RS machinery","alignment":"orthogonal","rationale":"The paper's core is input-driven Markov typicality (AEP, packing, ergodicity for driven chains) yielding single-letter inner/outer bounds on achievable PU,X,Y',Y,V. No J-cost, no φ-ladder, no 8-tick periodicity, no parameter-free constant derivation. Matches none of the RS forcing theorems (reality_from_one_distinction, J-uniqueness, AlexanderDuality D=3, etc.). Domain is classical IT; RS has no opinion.","tokens_in":50999,"confidence":"high","tokens_out":140,"duration_ms":15694,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Single-letter inner and outer bounds characterize achievable joint distributions for empirical coordination over Markov channels with strictly causal encoders.","keywords":["empirical coordination","Markov channel","joint source-channel coding","strictly causal encoder","input-driven typicality","single-letter bounds","achievable distributions"],"falsifier":"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.","tokens_in":2508,"feed_emoji":"","tokens_out":624,"duration_ms":17870,"temperature":0.7,"pith_summary":"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.","feed_headline":"Single-letter bounds for Markov-channel coordination","feed_subtitle":"Strictly causal encoders induce joint source and channel distributions characterized by new input-driven typicality.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Single-letter bounds for Markov empirical coordination","Input-driven typicality for causal Markov coordination","Strictly causal encoders bound Markov source-channel distributions","Single-letter inner outer bounds via input-driven typicality"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The fundamental properties of input-driven Markov typicality hold when encoders are strictly causal and drive the state evolution.","fun_headline_variants_meta":{"raw":{"variants":["Single-letter bounds for Markov empirical coordination","Input-driven typicality for causal Markov coordination","Strictly causal encoders bound Markov source-channel distributions","Single-letter inner outer bounds via input-driven typicality"]},"model":"grok-4.3","cost_usd":0.005042,"raw_usage":{"total_tokens":2414,"prompt_tokens":579,"num_sources_used":0,"completion_tokens":55,"cost_in_usd_ticks":50424500,"prompt_tokens_details":{"text_tokens":579,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1780,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":579,"tokens_out":55,"duration_ms":13382,"temperature":1.0,"reasoning_tokens":1780,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-16T13:11:18.972952+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}