REVIEW 5 minor 6 references
Markov chains with exponential return times are finitary
T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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.
minor comments (5)
- [Section 2.1 (Proof of Theorem 1)] 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 2.4 (Lemma 5)] 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 2.2 (Proposition 3)] 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 2.5] There is a typo: 'Talyor expansion' should be 'Taylor expansion'.
- [Section 1] 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.
Circularity Check
No significant circularity identified; the derivation is self-contained and does not reduce to its inputs.
full rationale
The central claim of the paper is proved by a direct chain of reductions that does not reintroduce its hypotheses as conclusions. Theorem 2 is built from Proposition 4, which gives an explicit coupling-from-the-past construction for renewal processes whose hazard function is bounded away from zero; Lemma 5, which reverses independent thinning block-by-block; and Lemma 6, which uses a generating-function argument to show that T*_mu has a simple dominating pole and hence satisfies the hazard condition of Proposition 4. The asymptotic formula P(T*_mu = n) = c nu^{-n} + O(kappa^{-n}) is derived from the analytic properties of the probability generating function, not assumed. Theorem 1 follows by applying Theorem 2 to the renewal process of visits to a state and filling in independent excursions; the only cited external ingredient is the standard composition fact for finitary factors with exponential coding windows, deferred to [2, Lemma 9]. That citation is to prior work by one of the authors, but it is not load-bearing in the sense of containing the substantive claim: it is a parameter-free, general fact about composing finitary maps, and the paper's own arguments establish the factors being composed. There are no fitted parameters renamed as predictions, no ansatz smuggled in through citation, and no uniqueness theorem imported from the authors. The aperiodicity assumption is explicitly needed to make the return-time distribution non-lattice, and Proposition 3 shows this condition is genuinely necessary, so it is a stated hypothesis rather than a hidden circular input. Overall, the paper is self-contained against external benchmarks and the main results do not reduce to their assumptions by construction.
Assumptions & free parameters
free parameters (1)
- mu (thinning parameter) =
sufficiently small (exists by Lemma 6)
assumptions (4)
- domain assumption If one state of an irreducible positive recurrent Markov chain has exponential return times, then every state does.
- domain assumption The composition of finitary factors whose coding windows have exponential tails is again such a factor ([2, Lemma 9]).
- standard math A size-biased version T' of the jump distribution has exponential tails iff T does.
- standard math The probability generating function G(z) has radius of convergence equal to the exponential tail rate and is strictly increasing on [0,a).
Cite this review
Pith. "Pith review of Markov chains with exponential return times are finitary." pith.science (2026). https://pith.science/paper/UGGTDOEY
@misc{pith2026190806240,
author = {Pith},
title = {Pith review of: Markov chains with exponential return times are finitary},
year = {2026},
howpublished = {\url{https://pith.science/paper/UGGTDOEY}},
note = {Machine review of arXiv:1908.06240}
}
abstract
Consider an ergodic Markov chain on a countable state space for which the return times have exponential tails. We show that the stationary version of any such chain is a finitary factor of an i.i.d. process. A key step is to show that any stationary renewal process whose jump distribution has exponential tails and is not supported on a proper subgroup of $\mathbb{Z}$ is a finitary factor of an i.i.d. process.
Figures
Reference graph
Works this paper leans on
-
[1]
Finitary codes between Markov processes
Mustafa A Akcoglu, Andr´ es del Junco, and Maurice Rahe. Finitary codes between Markov processes. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 47(3):305–314, 1979
work page 1979
-
[2]
Finitary codings for the random-cluster model and other infinite-range monotone models
Matan Harel and Yinon Spinka. Finitary codings for the random-cluster model and other infinite-range monotone models. arXiv preprint arXiv:1808.02333 , 2018
arXiv 2018
-
[3]
Holroyd, Yuval Peres, and Dan Romik
Nate Harvey, Alexander E. Holroyd, Yuval Peres, and Dan Romik. Universal finitary codes with exponential tails. Proceedings of the London Mathematical Society, 94(2):475–496, 2006
work page 2006
-
[4]
James G. Propp and David B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random structures and Algorithms, 9(1-2):223–252, 1996
work page 1996
-
[5]
A characterization of those processes finitarily isomorphic to a Bernoulli shift
Daniel J Rudolph. A characterization of those processes finitarily isomorphic to a Bernoulli shift. In Ergodic theory and dynamical systems i , pages 1–64. Springer, 1981
work page 1981
-
[6]
A mixing Markov chain with exponentially decaying return times is finitarily Bernoulli
Daniel J Rudolph. A mixing Markov chain with exponentially decaying return times is finitarily Bernoulli. Ergodic Theory and Dynamical Systems , 2(1):85–97, 1982. Omer Angel, Yinon Spinka Department of Mathematics, University of British Columbia Email: {angel,yinon}@math.ubc.ca 9
work page 1982
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.