{"id":"b3da8aef-373f-4068-be01-89cab4a669b4","arxiv_id":"1908.06240","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Every stationary renewal process whose jump distribution is non-lattice and exponentially tailed is a finitary factor of an i.i.d. process with an exponentially tailed coding window; Markov chains with exponential return times are a corollary.","lead":"This paper proves that stationary Markov chains on countable state spaces with exponentially decaying return times can be generated from an independent random stream using only a finite window at each step. The construction is explicit and the required window has exponential tails, improving on earlier non-constructive results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"I read the paper as a self-contained proof of a precise statement: stationary ergodic (irreducible, aperiodic, positive recurrent) Markov chains with exponential return times are finitary factors of i.i.d. processes with exponential coding windows. The reader's verdict of ACCEPT with high confidence is justified. The weakest point is indeed the aperiodicity assumption: without it, the renewal process of visits to a state may be lattice, and Proposition 3 correctly shows that lattice renewal processes cannot be finitary factors. But the paper explicitly defines ergodic to include aperiodicity, so this is not a flaw in the stated theorem. I checked the three main reductions: Proposition 4's coupled chains coalesce on the events E_i, and the coding window is a genuine stopping time with exponential tail; Lemma 5's block-sampling reversal is conditionally correct and preserves exponential tails; Lemma 6's singularity analysis gives the required asymptotic form, from which the hazard-rate condition of Proposition 4 follows. The only non-supplied ingredient is the composition lemma cited from [2], which is standard and does not appear to introduce a hidden assumption. I therefore find no load-bearing concern and recommend no change to the reader's verdict.","tokens_in":6663,"tokens_out":31252,"duration_ms":325494,"concrete_test":"Verify that [2, Lemma 9] applies verbatim to two-sided finitary factors whose coding windows are stopping times in the symmetric filtration, since Theorem 1 and Lemma 5 rely on composing the renewal-process factor with the excursion-filling factor. If the lemma requires one-sidedness or independent coding windows, the composition step in Section 2.1 and Section 2.4 would need a short supplement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The chain of reductions is sound: Proposition 4 gives an explicit coupling-from-the-past construction for renewal processes with positive hazard; Lemma 5 correctly reverses independent thinning block-by-block; Lemma 6's generating-function argument yields T*_mu with a simple dominating pole, so Proposition 4 applies; Theorem 1 follows by coding the renewal process of visits to a state and filling in independent excursions. The only assumption that could invalidate the result if changed is aperiodicity, needed for the return-time distribution to be non-lattice, and Proposition 3 shows that non-lattice is necessary for a finitary-factor representation. Thus aperiodicity is an explicit hypothesis, not a gap. The proof of Proposition 3's exponential-tail claim is terse but valid: a positive-density 2m-dependent family of certified renewal times forces exponentially decaying gaps between renewals. The composition step is deferred to [2, Lemma 9], an external but standard result; I do not see a circularity or an omitted step that threatens the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that a stationary ergodic Markov chain on a countable state space with exponential return times is a finitary factor of an i.i.d. process with an exponentially decaying coding window (Theorem 1). The main technical result (Theorem 2) states that a stationary renewal process whose jump distribution is non-lattice and has exponential tails is such a finitary factor. The proof combines three ingredients: Proposition 4 constructs a finitary coding for renewal processes with positive asymptotic hazard via coupling from the past; Lemma 6 shows that a geometrically compounded jump distribution has regularly varying exponential tails with a single dominant singularity; and Lemma 5 reverses the independent thinning construction to transfer the finitary coding from the compounded process back to the original renewal process. Proposition 3 shows the assumptions in Theorem 2 are necessary.","tokens_in":6819,"tokens_out":12631,"duration_ms":115426,"significance":"The result is a significant improvement over Rudolph's earlier abstract finitary isomorphism theorem for such Markov chains: the construction is explicit, short, and yields strong quantitative control (exponential tails) on the coding window. The necessity part (Proposition 3) shows the hypotheses are natural. The proof is largely self-contained and uses only standard tools (coupling from the past, generating functions), which should make the result accessible and useful for further work on finitary codings.","major_comments":[],"minor_comments":[{"comment":"The reduction from the renewal process X to the Markov chain M is stated in two sentences; please expand the construction by specifying how the independent excursions are sampled from an auxiliary i.i.d. sequence, and justify the exponential tail bound for the combined coding window with a few more details or an explicit statement of the composition lemma from [2].","section":"Section 2.1 (Proof of Theorem 1)"},{"comment":"The reverse-thinning construction is described verbally; provide an explicit description of the block-coding rule (e.g., a deterministic function of an i.i.d. uniform sequence and the block length that samples the internal configuration) and justify carefully that the resulting coding window has exponential tails.","section":"Section 2.4 (Lemma 5)"},{"comment":"The exponential tail of the return time is concluded in one sentence via 2m-dependence; include the standard blocking argument (partition into separated blocks of length 2m+1) to make the proof self-contained.","section":"Section 2.2 (Proposition 3)"},{"comment":"There is a typo: 'Talyor expansion' should be 'Taylor expansion'.","section":"Section 2.5"},{"comment":"The statement that exponential return times for one state imply the same for every state is made without proof or reference; a short justification or citation would be helpful.","section":"Section 1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a well-written short note with a sound central argument. The only changes I request are expansions of the terse arguments listed in the minor comments; I have no concerns about novelty or correctness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main new result here is Theorem 2: a stationary renewal process with non-lattice, exponentially-tailing jump distribution is a finitary factor of an i.i.d. process with an exponential coding window. That is genuinely new, and Theorem 1 (the Markov chain corollary) improves on Rudolph's non-constructive isomorphism by giving an explicit construction and a quantitative tail bound. The paper does what it promises, and it does it in a short, readable way.\n\nThe proof strategy is well executed. The reduction to the positive-hazard case via independent thinning (Lemma 5) is elegant, and the generating-function argument in Lemma 6 is sound: it exhibits a simple dominant pole at the radius of convergence and extracts the exponential tail. Proposition 4's coupling-from-the-past construction is also correct, including the non-full-support case. I did not find any load-bearing gaps or circularities. The paper is self-contained except for the use of [2, Lemma 9] on composing finitary factors with exponential tails; that is an external but standard result, and citing it is fine.\n\nSoft spots are minor. The proof of Proposition 3's exponential-tail claim is terse; the step from a positive-density 2m-dependent family of certified renewal times to exponentially decaying gaps is correct but could use a line of explanation. The phrase \"and hence every state\" in the definition of exponential return times is a bit quick, though standard irreducibility plus exponential tails for one state does give it for all states. The aperiodicity assumption is explicit and necessary—Proposition 3 shows lattice jump distributions cannot be finitary. None of these affect the central claims.\n\nI also appreciate the honest framing: the authors state that their result and Rudolph's are incomparable (they get a tail bound, he gets an isomorphism), and they raise a clear open question about entropy. The citation pattern is appropriate.\n\nWho is this for? Ergodic theorists and probabilists working on finitary codings. It deserves serious referee attention. I would send it to a good journal and expect it to be accepted after minor revisions.","headline":"A clean, explicit construction showing renewal processes and Markov chains with exponential return times are finitary factors with exponential coding windows; the main theorems are new and the proofs hold up.","tokens_in":7283,"tokens_out":867,"would_cite":true,"duration_ms":9972,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","37A50","60G10","60K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A stationary ergodic Markov chain on a countable state space with exponential return times is a finitary factor of an i.i.d. process with a coding window that has exponential tails.","keywords":["stationary renewal process","finitary factor","i.i.d. process","Markov chain","exponential tails","coding window","coupling from the past","generating function"],"falsifier":"Exhibit a stationary renewal process whose jump distribution is supported on the even integers and show that it is a finitary factor of an i.i.d. process; this would contradict Proposition 3. Alternatively, prove that for some non-lattice exponential-tail renewal process every finitary coding window has heavier-than-exponential tail; this would contradict Theorem 2.","tokens_in":6494,"feed_emoji":"🎲","tokens_out":9881,"duration_ms":89686,"temperature":0.7,"pith_summary":"This paper proves that a stationary Markov chain on a countable state space, whose return times to a fixed state have exponentially small upper tails, can be reconstructed from an i.i.d. sequence of random inputs by a function that reads only finitely many inputs around each time coordinate. The coding window—the number of inputs needed to determine one output symbol—also has exponential tails, so the reconstruction is effectively local. The proof reduces the Markov chain to the renewal process of visits to one state and shows that every stationary renewal process with a non-lattice, exponentially tailed jump distribution is such a finitary factor. Because the construction is explicit and probabilistic, it yields concrete exponential bounds rather than an abstract existence statement.","feed_headline":"Exponential return times let Markov chains be rebuilt from coin flips","feed_subtitle":"Each output symbol needs only a finite block of coin flips, with exponential tail on its size.","key_machinery":"The proof rests on coupling from the past for the auxiliary Markov chain $Z_n$, which records the distance from $n$ to the nearest renewal on the left. A reset event $E_i$ forces every past-started copy of $Z$ to the same state at time $i$, so $Z_j$ is determined by the inputs between $I(j)$ and $j$, where $I(j)$ is the last reset before $j$. The remaining step replaces an arbitrary non-lattice exponential-tail jump distribution $T$ by the geometrically compounded distribution $T^*_\\mu=T_1+\\dots+T_N$ with $N\\sim\\mathrm{Geom}(\\mu)$; Lemma 6 shows $T^*_\\mu$ has probability mass $c\\nu^{-n}+O(\\kappa^{-n})$ for some $\\kappa>\\nu>1$, using the generating function $F(z)=\\mu G(z)/(1-(1-\\mu)G(z))$, whose only singularity is a simple pole at $z=\\nu$. Lemma 5 then reverses the compounding by filling missing renewals inside each block with fresh i.i.d. randomness, and the composition lemma for exponential-tail coding windows completes the reduction.","core_discovery":"The central claim is Theorem 2: if $X$ is a stationary renewal process whose jump distribution is non-lattice and has exponential tails, then $X$ is a finitary factor of an i.i.d. process with a coding window that has exponential tails. Theorem 1 follows by applying Theorem 2 to the renewal process of visits to a state of an ergodic Markov chain and then filling in the independent excursions between visits. The paper also proves a converse, Proposition 3: any stationary renewal process that is a finitary factor of an i.i.d. process must have a non-lattice jump distribution with exponential tails, so the hypotheses in Theorem 2 are necessary as well as sufficient.","pith_inferences":["The analytic compounding step is likely reusable: any stationary point process whose inter-arrival law has exponential tails could be dominated or approximated by such a renewal process, although the paper does not pursue this.","The explicit coding suggests a practical sampler: for each output coordinate one reads roughly a geometric number of inputs, so finite-window approximations of the factor map are computationally cheap; the paper does not discuss implementation.","If the compounding could be made entropy-preserving, it might answer Question 8 affirmatively and match the known entropy-optimal finite-state results; the paper leaves this open.","A separate treatment of periodic renewal processes would require a new idea, since Proposition 3 shows lattice jump distributions cannot be finitary factors directly."],"forward_implications":["The Markov chain itself, not just the visit process, is a finitary factor of an i.i.d. process with an exponential-tail coding window.","The exponential-tail window implies $X_0$ can be approximated by a function of a finite block $Y_{-r},\\dots,Y_r$ with approximation error decaying exponentially in $r$.","Renewal processes with lattice or heavy-tailed jump distributions are excluded: Proposition 3 makes the non-lattice and exponential-tail assumptions necessary.","The compounding step applies to every non-lattice exponential-tail renewal process, so the result covers much more than visit processes of Markov chains.","For unbounded renewal processes whose hazard $P(T=n\\mid T\\ge n)$ stays bounded below, Proposition 4 gives a direct coupling-from-the-past coding without the compounding reduction."],"supporting_citations":[{"why":"Establishes finite-state Markov chains as finitary factors of i.i.d. processes, the setting this paper extends to countable state spaces.","marker":"[1]"},{"why":"Supplies the composition lemma for finitary factors with exponential-tail coding windows used twice in the proof.","marker":"[2]"},{"why":"Provides exponential-tail coding windows for finite-state Markov chains, the bound this paper's construction mirrors in the countable-state setting.","marker":"[3]"},{"why":"Introduces coupling from the past, the sampling method adapted in Proposition 4.","marker":"[4]"},{"why":"Gives the prior finitary-isomorphism result for return-time Markov chains against which the present factor construction is compared.","marker":"[6]"}],"fun_headline_variants":["Exponential returns make Markov chains finitary from coin flips","Markov chains with exponential return times are finitary factors","Coin flips rebuild Markov chains when return times decay exponentially","Exponential return tails make Markov chains finitary from i.i.d.","Finitary coding for Markov chains with exponential return tails"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is aperiodicity: the return-time distribution must not be supported on a proper subgroup of $\\mathbb{Z}$; without it, the renewal process of visits is lattice, and the paper's Proposition 3 shows such a process cannot be a finitary factor of an i.i.d. process at all.","fun_headline_variants_meta":{"raw":{"variants":["Exponential returns make Markov chains finitary from coin flips","Markov chains with exponential return times are finitary factors","Coin flips rebuild Markov chains when return times decay exponentially","Exponential return tails make Markov chains finitary from i.i.d.","Finitary coding for Markov chains with exponential return tails"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000891,"raw_usage":{"total_tokens":3738,"prompt_tokens":735,"completion_tokens":3003,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":351,"completion_tokens_details":{"reasoning_tokens":2920}},"tokens_in":351,"tokens_out":3003,"duration_ms":22731,"temperature":1.0,"reasoning_tokens":2920,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:52:05.150388+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a stationary renewal process whose jump distribution is supported on the even integers and show that it is a finitary factor of an i.i.d. process; this would contradict Proposition 3. Alternatively, prove that for some non-lattice exponential-tail renewal process every finitary coding window has heavier-than-exponential tail; this would contradict Theorem 2.","supporting_citations":[{"cited_title":"Finitary codes between Markov processes","cited_arxiv_id":null,"evidence_quote":"Establishes finite-state Markov chains as finitary factors of i.i.d. processes, the setting this paper extends to countable state spaces."},{"cited_title":"Holroyd, Yuval Peres, and Dan Romik","cited_arxiv_id":null,"evidence_quote":"Provides exponential-tail coding windows for finite-state Markov chains, the bound this paper's construction mirrors in the countable-state setting."},{"cited_title":"Propp and David B","cited_arxiv_id":null,"evidence_quote":"Introduces coupling from the past, the sampling method adapted in Proposition 4."},{"cited_title":"A mixing Markov chain with exponentially decaying return times is finitarily Bernoulli","cited_arxiv_id":null,"evidence_quote":"Gives the prior finitary-isomorphism result for return-time Markov chains against which the present factor construction is compared."}],"review_version":1}