A new proof of finitary isomorphism for Markov chains

Yinon Spinka

REVIEW 2 major objections 3 minor 1 cited by

A new proof of finitary isomorphism for Markov chains

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A short proof that exponential-return renewal processes are finitarily isomorphic to IID processes

desk verdict A genuinely new direct proof of Rudolph's finite-entropy theorem, but the infinite-entropy extension breaks on Proposition 2.1 as stated. read the letter →

arxiv 2506.04069 v1 pith:PHOARW6B submitted 2025-06-04 math.PR math.DS

Yinon Spinka This is my paper

classification math.PRmath.DS MSC 37A5037A3560J0560K05

keywords finitaryisomorphismrenewalprocessMarkovchainexponentialreturntimeinfiniteentropyBernoullimarkersetclassification

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that every countable-state mixing renewal process with a renewal state whose return time decays exponentially is finitarily isomorphic to a process of independent, identically distributed symbols. This is a classification result: such processes are, up to a local and invertible recoding, just i.i.d. noise, and the isomorphism works for infinite entropy as well as finite entropy. The significance is that finitary isomorphism is the strong, coding-friendly notion of sameness in ergodic theory, and the proof gives a direct construction that avoids the heavy characterization machinery used in earlier work.

What carries the argument

The load-bearing object is the marker set $b$ inside the $(k_0+1)$-stringing of the enriched process $(Y,Z,U,W)$. A point belongs to $b(k)$ exactly when the current age is $k$, the process returns to the renewal state after $k_0$ steps, the independent uniform variable is below $\alpha_k$, and the independent Bernoulli block is $(0,\dots,0,1)$; the probabilities $\alpha_k$ are chosen proportional to the inverse conditional return probability $P(Z_{k_0}=0 \mid Z_0=k)$. This proportionality makes the age $Z_0$ independent of the event $\{X_0\in b\}$, and hence gives the separation property (2.1): marker events are disjoint within $k_0$ steps and exactly independent beyond it. That property matches the law of the marker to the law of the string $0\cdots 01$ in the $(k_0+1)$-stringing of an IID process, which is the final identification step.

What would settle it

Compute, for a renewal process with hazard $f(1)=10^{-100}$ and $f(k)=1/2$ for $k\ge 2$, whether the marker events $\{X_0\in b\}$ and $\{X_n\in b\}$ are exactly independent for every $n>2$ under the stated choice of $\alpha_k$; failure for some $n$ would disprove the key separation property, and a countable-state mixing renewal process with exponential return time that is not finitarily isomorphic to an IID process would refute the theorem itself.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: if a countable-state mixing renewal process has a renewal state with exponential return time, then the process is finitarily isomorphic to an IID process. The argument proceeds in two propositions. Proposition 2.1 shows the original process can be finitarily reduced to a finite-state renewal process whose renewal return time has regular exponential tail, using independent splitting of a state and a geometric-sum lemma. Proposition 2.2 shows that any finite-state ergodic renewal process whose return time has semi-regular exponential tail is finitarily isomorphic to an IID process, via a marker set whose occurrences are disjoint on short scales and exactly independent on long scales. Because regular tail implies semi-regular tail, the two propositions combine to prove the theorem. The Markov-chain version follows by recording the history since the last renewal state.

Load-bearing premise

The construction of the marker probabilities requires a uniform lower bound on the probability of returning to the renewal state within $k_0$ steps from every starting age $k$, including the finitely many ages below $k_0$ where the tail hypothesis gives no control.

Editorial extensions

If this is right

Every countable-state mixing Markov chain with exponential return times is finitarily isomorphic to an IID process, including chains of infinite entropy.
The proof yields a direct, explicit coding in terms of stringings, marker sets, and independent splitting, so the isomorphism is accessible for quantitative coding questions.
The two-step reduction isolates what needs exponential tails: first to regularize the return-time distribution, then to build the long-range independence of markers.
The result places countable-state mixing Markov chains with exponential return times in the same finitary Bernoulli class as the finite-state chains already covered by the older finite-state theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The marker recipe is likely reusable: any regenerative process whose hazard function is bounded away from 0 and 1 on a tail and whose small-age hazards are handled by choosing $k_0$ and the normalization constants is a candidate for the same construction, not just Markov chains.
The small-$k$ dependence of $\alpha_k$ is the part of the proof most sensitive to the hypotheses; if the stated assumptions do not force the lower bound $P(Z_{k_0}=0\mid Z_0=k)\ge c^{k_0}$ for all $k$, a natural repair is to enlarge $k_0$ or shrink $c$ after recording the finitely many exceptional hazards, rather than to change the theorem.
A natural testbed for the method is a renewal process with an exceptionally rare early return, where computing the marker probabilities and checking (2.1) numerically would show precisely how the parameters must be chosen.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

Quick take: this is a real step forward for the finite-entropy case of Rudolph's theorem. The geometric-thinning lemma plus the block-marker construction is much more direct than Rudolph's heavy machinery, and the two-proposition structure is clean. If you work on finitary codings, this is worth your time.

The advertised extra — infinite entropy — does not hold as written. Proposition 2.1 says the output is a finite-state Y, but finitary isomorphism preserves entropy, and a finite-state process has finite entropy. So when X has infinite entropy, the proposition is false as stated. The proof actually produces a countable-state Y via independent splitting of the star state; that's fine, but then Proposition 2.2, which only handles finite-state Y, never applies. The paper quietly asserts 'Theorem 1.1 follows immediately,' but the chain breaks exactly at the case the abstract advertises. This is a load-bearing gap, not a matter of taste.

There is a second, smaller hole in Proposition 2.2. The marker probabilities alpha_k are set proportional to P(Z_{k0}=0 | Z0=k)^{-1}, and the justification requires a lower bound c^{k0} for all k, including k < k0. The semi-regular tail hypothesis only controls hazards for k >= k0; nothing prevents small-k hazards from being 0 or 1, making the bound fail. The independence argument depends on this proportionality for every k. This looks repairable — truncate the marker set to k >= k0 or adjust the blocking window — but as written the proof of (2.1) doesn't cover all cases.

The finite-entropy statement is already known, so the main theorem isn't new. What is new is the method: the use of the earlier lemma on geometric sums regularizing exponential tails, and the clean block-factor separation. That part tracks. The self-citations are to published work, not a problem.

Bottom line: this deserves a serious referee. The gaps are identifiable and at least the second is likely fixable. The infinite-entropy claim may be fixable by generalizing Prop 2.2 to countable-state renewal processes, but that requires real work. Send it out, and have the referee ask for a corrected Prop 2.1, a repaired small-k argument, and either a proof or a deletion of the infinite-entropy claim.

Referee Report

2 major / 3 minor

Summary. The paper proposes a new, short proof of Rudolph's theorem that a countable-state mixing Markov chain (or, more generally, a countable-state mixing renewal process) with exponential return times is finitarily isomorphic to an IID process. The proof is split into two propositions. Proposition 2.1 claims that such an X is finitarily isomorphic to a finite-state renewal process with regular exponential return times, and Proposition 2.2 claims that any finite-state ergodic renewal process with semi-regular exponential return times is finitarily isomorphic to an IID process. The argument uses geometric thinning to regularize return-time tails (Lemma 2.3), independent splitting of states to adjust entropy, and a blocking construction that produces a marker state whose occurrence process matches that of a state in an IID stringing. The abstract advertises that the proof works for both finite and infinite entropy, the latter being a case left open by Rudolph.

Significance. If the proof is correct, this would be a valuable contribution: it would give a direct and short proof of a known theorem for finite entropy, and would resolve the infinite-entropy case, which Rudolph left open. The two-step decomposition is conceptually clean and leverages prior results of the author and collaborators in a natural way, especially the use of Lemma 2.3 (Angel-Spinka) to convert exponential tails into regular exponential tails. The marker construction in Proposition 2.2 is an elegant adaptation of Keane-Smorodinsky ideas. However, the advertised infinite-entropy extension is not supported by the manuscript as written, and there is a gap in the proof of Proposition 2.2. These issues affect the central claims, so the paper needs substantial revision before it is publishable.

major comments (2)

Proposition 2.1 is false as stated for infinite-entropy X. Entropy is an isomorphism invariant, and a finite-state process has finite entropy, so no finite-state Y can be finitarily isomorphic to an infinite-entropy X. The proof itself reveals the problem: after constructing the three-state Y' with h(Y') < h(X), the step 'by independently splitting the state * in Y′, we obtain a process Y of equal entropy to X' requires countably many new symbols when h(X) = ∞, so Y is countable-state, not finite-state. Consequently, the proof of Theorem 1.1 cannot go through the stated chain 'Proposition 2.1 then Proposition 2.2', because Proposition 2.2 is stated only for finite-state Y. The paper needs a countable-state analogue of Proposition 2.2 and a corrected statement of Proposition 2.1 (e.g., 'finite-state when X has finite entropy, countable-state otherwise').
The claim that P(Z_{k0}=0 | Z_0=k) >= c^{k0} for every k>=0 is not justified. The semi-regular tail condition only gives f(k) in [c,1-c] for k>=k0. For k<k0, the path that avoids return until time k0 has probability product_{m=k+1}^{k+k0-1}(1-f(m)) * f(k+k0), which includes factors with m<k0 that are not controlled. These factors can be extremely small (e.g., if some f(m) is very close to 1), so the product can be much smaller than c^{k0}. Since the definition of alpha_k as c^{k0} * P(Z_{k0}=0 | Z_0=k)^{-1} <= 1 and the subsequent independence of Z_0 from {X_0 in b} depend on this lower bound, the proof of the key separation property (2.1) is incomplete. This gap is local and might be repairable by strengthening the tail assumption or handling the finitely many k<k0 separately, but as written it is a load-bearing error.

minor comments (3)

Line: 'Clearly, the process ( Y, Z) is clearly finitarily isomorphic to Y' contains a duplicated adverb; this is a typographical issue.
The sentence 'Since h(Y′) <= h(X′) + h(W) < h(X) provided that µ is small enough' is not quite precise when h(X)=∞, since h(W) is irrelevant then; the statement is still true, but the phrasing may confuse readers.
The notation for the state t is a bit ambiguous: the tuple ((a,1),...,(a,k0+1)) should be clarified as a state in the (k0+1)-stringing whose j-th coordinate is (a,j), and the reason this state has entropy less than h(Y,Z) is asserted without proof; adding a short justification would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the self-cited lemmas are independent technical results, and the constructed parameters are deliberate design choices rather than inputs disguised as conclusions.

full rationale

The proof's main load-bearing black boxes are Lemma 2.3 from Angel–Spinka [2] and Theorem 3.2 of Meyerovitch–Spinka [6]. Both are self-citations, but both are invoked as independent technical results whose stated assumptions do not include the conclusion of Theorem 1.1: Lemma 2.3 concerns geometric sums of variables with exponential tails, and Theorem 3.2 concerns finitary isomorphism between renewal processes with identically distributed renewal states. Under the review rule, such cited results are real evidence and do not raise the circularity score. The α_k proportionality in Proposition 2.2 is also not circular: α_k is explicitly defined from P(Z_{k0}=0 | Z_0=k)^{-1} so that the event {X_0 ∈ b(k)} has probability proportional to P(Z_0=k), and the subsequent independence statement is an algebraic consequence of that definition, not a fitted quantity being relabeled as a prediction. There are two genuine correctness concerns that are distinct from circularity: the claimed lower bound P(Z_{k0}=0 | Z_0=k) ≥ c^{k0} for k < k0 is not implied by the semi-regular tail assumption, since f(m) is uncontrolled for m < k0; and Proposition 2.1's asserted finite-state target is impossible when X has infinite entropy, because finitary isomorphisms preserve entropy and every finite-state process has finite entropy. These are mathematical gaps in the stated proof, not instances of the derivation reducing to its own inputs, so they do not change the circularity verdict.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The theorem itself introduces no new objects; all constructions (stringings, block factors, splittings, marker sets b(k)) are built from the given process. The load-bearing external inputs are two theorems from the author's own prior work (Lemma 2.3 from [2] and Theorem 3.2 from [6]), one assertion in the proof of Prop 2.2 not implied by the stated hypotheses, and standard ergodic-theory facts. No fitted data parameters appear; the free parameters are existence choices in the construction.

free parameters (5)

mu (Bernoulli thinning rate, Prop 2.1) = any sufficiently small mu > 0
W is IID Bernoulli(mu). mu must be small enough that the geometric sum T*_mu has regular exponential tail (Lemma 2.3) and that h(W) < h(X) - h(X'). The proof needs existence of such mu; no specific value is computed.
epsilon (Bernoulli rate for blocking process W, Prop 2.2) = any sufficiently small epsilon > 0
Controls P(X_0 in b) <= epsilon so the three-valued process X' has entropy below h(Y,Z). Existence asserted; the required smallness is not quantified.
k0 (marker window size) = any k0 >= 1 with f(k) in [c,1-c] for all k >= k0 and h_b(p_t) < h(Y,Z)
Window length in the stringing and marker construction. Needs to be large enough for the semi-regular tail bounds and for the state-t entropy to fall below h(Y,Z); the entropy condition is not stated in the paper.
alpha_k (marker probabilities) = c^{k0} * P(Z_{k0}=0 | Z_0=k)^{-1}, claimed to lie in [0,1]
Chosen proportional to the inverse hitting probability so that Z_0 is independent of the marker event. The claim alpha_k <= 1 for all k is not proven for k < k0.
independent splitting distributions for the '*' state = chosen to match the entropy of the target process
Used in both propositions to raise entropy to exactly h(X) or h(Y,Z). In the infinite-entropy case this requires a countable alphabet, which collides with the finite-state wording of Prop 2.1.

assumptions (5)

domain assumption Two renewal processes with renewal states having the same distribution are finitarily isomorphic (Keane-Smorodinsky [4] for finite state; Meyerovitch-Spinka [6, Thm 3.2] for countable state).
Invoked as the workhorse in both propositions ('We use this fact repeatedly in the proofs'). It is an external theorem from the author's own prior work [6] in the countable case; it does not assume Theorem 1.1.
domain assumption Lemma 2.3 [2]: if T has exponential tail and support not in a proper subgroup of Z, then the geometric sum T*_mu has regular exponential tail for small mu.
Black box from Angel-Spinka used in Prop 2.1 to produce a renewal state with regular exponential tail.
domain assumption Independent splitting of a state can raise entropy by any prescribed amount (finite or infinite) without changing renewal properties or other state distributions.
Used in both propositions to match entropies; the infinite-entropy case requires interpreting this as a countable-alphabet split, which collides with the 'finite-state' wording of Prop 2.1.
ad hoc to paper The lower bound P(Z_{k0}=0 | Z_0=k) >= c^{k0} holds for all k >= 0.
Asserted in the proof of Prop 2.2 in the paragraph introducing (alpha_k). Only derivable from the stated hypotheses for k >= k0; for smaller k the factors 1-f(m) with m < k0 are not controlled by semi-regular exponential tail.
standard math Standard facts: mixing implies the return-time distribution is not supported on a proper subgroup; exponential return time propagates to all renewal states and to k-stringings; entropy is an isomorphism invariant; entropy rate of a process is at most its one-symbol entropy.
Used throughout without proof; standard and correct.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A new proof of finitary isomorphism for Markov chains." pith.science (2026). https://pith.science/paper/PHOARW6B

@misc{pith2026250604069,
  author       = {Pith},
  title        = {Pith review of: A new proof of finitary isomorphism for Markov chains},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PHOARW6B}},
  note         = {Machine review of arXiv:2506.04069}
}

read the original abstract

We give a new proof of a result of Rudolph stating that a countable-state mixing Markov chain with exponential return times is finitarily isomorphic to an IID process. Besides being short and direct, our proof has the added benefit of working for processes of finite or infinite entropy.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Finitary codings and stochastic domination for Poisson representable processes
math.PR 2025-06 conditional novelty 7.0 of 10

Exponential moments of block-size probabilities decide when union-of-random-blocks processes on Z^d are finitary factors of IID and when they are stochastically dominated by non-trivial Bernoulli percolation.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · cited by 1 Pith paper

[1]

Finitary codes between Markov processes

M A Akcoglu, Andr´ es del Junco, and M Rahe. Finitary codes between Markov processes. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 47(3):305–314, 1979

work page 1979
[2]

Markov chains with exponential return times are finitary

Omer Angel and Yinon Spinka. Markov chains with exponential return times are finitary. Ergodic Theory and Dynamical Systems , 41(10):2918–2926, 2021

work page 2021
[3]

Bernoulli schemes of the same entropy are finitarily isomorphic

Michael Keane and Meir Smorodinsky. Bernoulli schemes of the same entropy are finitarily isomorphic. Annals of Mathematics , 109(2):397–406, 1979. 4

work page 1979
[4]

Finitary isomorphisms of irreducible Markov shifts

Michael Keane and Meir Smorodinsky. Finitary isomorphisms of irreducible Markov shifts. Israel Journal of Mathematics , 34(4):281–286, 1979

work page 1979
[5]

A case of isomorphism of Bernoulli schemes

LD Meshalkin. A case of isomorphism of Bernoulli schemes. DOKLADY AKADEMII NAUK SSSR , 128(1):41–44, 1959

work page 1959
[6]

Entropy-efficient finitary codings

Tom Meyerovitch and Yinon Spinka. Entropy-efficient finitary codings. Journal of Modern Dynamics , 20:1–49, 2024

work page 2024
[7]

Bernoulli shifts with the same entropy are isomorphic

Donald Ornstein. Bernoulli shifts with the same entropy are isomorphic. Advances in Mathematics , 4(3):337–352, 1970

work page 1970
[8]

Deux sch´ emas de bernoulli d’alphabet d´ enombrable et d’entropie infinie sont finitairement isomorphes

B Petit. Deux sch´ emas de bernoulli d’alphabet d´ enombrable et d’entropie infinie sont finitairement isomorphes. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 59(2):161–168, 1982

work page 1982

Show all 11 references

[9]

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

1981
[10]

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

1982
[11]

Finitary isomorphism of some renewal processes to Bernoulli schemes

Stephen M Shea. Finitary isomorphism of some renewal processes to Bernoulli schemes. Indagationes Mathematicae, 20(3):463–476, 2009. 5

2009

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Finitary codes between Markov processes

M A Akcoglu, Andr´ es del Junco, and M Rahe. Finitary codes between Markov processes. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 47(3):305–314, 1979

work page 1979

[2] [2]

Markov chains with exponential return times are finitary

Omer Angel and Yinon Spinka. Markov chains with exponential return times are finitary. Ergodic Theory and Dynamical Systems , 41(10):2918–2926, 2021

work page 2021

[3] [3]

Bernoulli schemes of the same entropy are finitarily isomorphic

Michael Keane and Meir Smorodinsky. Bernoulli schemes of the same entropy are finitarily isomorphic. Annals of Mathematics , 109(2):397–406, 1979. 4

work page 1979

[4] [4]

Finitary isomorphisms of irreducible Markov shifts

Michael Keane and Meir Smorodinsky. Finitary isomorphisms of irreducible Markov shifts. Israel Journal of Mathematics , 34(4):281–286, 1979

work page 1979

[5] [5]

A case of isomorphism of Bernoulli schemes

LD Meshalkin. A case of isomorphism of Bernoulli schemes. DOKLADY AKADEMII NAUK SSSR , 128(1):41–44, 1959

work page 1959

[6] [6]

Entropy-efficient finitary codings

Tom Meyerovitch and Yinon Spinka. Entropy-efficient finitary codings. Journal of Modern Dynamics , 20:1–49, 2024

work page 2024

[7] [7]

Bernoulli shifts with the same entropy are isomorphic

Donald Ornstein. Bernoulli shifts with the same entropy are isomorphic. Advances in Mathematics , 4(3):337–352, 1970

work page 1970

[8] [8]

Deux sch´ emas de bernoulli d’alphabet d´ enombrable et d’entropie infinie sont finitairement isomorphes

B Petit. Deux sch´ emas de bernoulli d’alphabet d´ enombrable et d’entropie infinie sont finitairement isomorphes. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 59(2):161–168, 1982

work page 1982