Markov Chain CLTs: Resolving Open Problems
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "Markov Chain CLTs: Resolving Open Problems".
Emmy: Here's the gist of the paper. Markov chain central limit theorems (CLTs) and their associated variances are very important for implementing Markov chain Monte Carlo algorithms among other applications The paper resolves seven open problems posed by Häggström and Rosenthal regarding the behavior of variance formulae (A, B, C) associated with additive functionals of stationary, ergodic, and reversible Markov chains Core Results on Variance Equivalence The authors prove that for stationary, ergodic, and reversible chains where the normalized partial sums satisfy a √n-CLT, the variance limit is finite if the function is square-integrable, otherwise undefined They establish that failure of the √n-CLT forces the normalized partial sums to be non-tight Specifically, for ergodic and reversible chains with centered h ∈ L1(π), the sequence (Sn/√n)n≥1 satisfies a dichotomy: either a √n-CLT holds, or the sequence (Sn/√n)n≥1 is not even tight When h ∈ L2(π), tightness forces A = B = C < ∞, which shows that A < ∞ is both necessary and sufficient for a √n-CLT Resolutions of Open Problems The paper provides solutions to the seven HR problems posed by Häggström and Rosenthal 1.
Ada: HR Problem 1 is resolved by developing a general Fourier-to-Markov covariance realization principle, showing that A = B can be infinite even when h ∈ L2(π) 2.
Emmy: HR Problem 2 is resolved by proving that if a √n-CLT exists for h /∈ L2(π), then A must be undefined 3.
Ada: HR Problem 3 is resolved by showing that Roberts’ condition cannot coexist with a √n-CLT, even without assuming reversibility or h ∈ L2(π) 4.
Paper summary: Emmy: So wrapping up this paper, we’re talking about Markov Chain CLTs: Resolving Open Problems by Austin Browna, Jeffrey S. Rosenthalb, and Quan Zhoua. It tackles those seven open problems Häggström and Rosenthal had posed concerning the equality of variance formulae A, B, and C.
Ada: The authors prove that for stationary ergodic reversible chains where the normalized partial sums satisfy a square root n central limit theorem, the variance limit is finite if you have square integrability for the function involved.
Kolya: And they also show that if that central limit theorem doesn't happen, then those normalized partial sums aren't tight at all.
Emmy: They also proved that Roberts’ holding-probability condition rules out a central limit theorem even without assuming reversibility or square integrability for the function.
Ada: The implications are that they’ve given us a sharp classification of the relationship between the square root n central limit theorem and those variance quantities A and B for ergodic reversible chains.
Kolya: For someone running simulations, it means you can use these conditions to predict whether your results will converge to a finite variance or if you should expect non-tight behavior instead.
Emmy: It’s about understanding the underlying structure of these Markov chains so we know what convergence to expect under different assumptions.
Conclusion: Ada: So, we’ve been diving into those seven open problems Häggström and Rosenthal had about variance formulae A, B, and C in Markov chains.
Emmy: Right, they're basically trying to figure out exactly when these formulas line up or when they diverge.
Ada: This paper just wraps up the resolution of those seven issues for stationary, ergodic reversible chains. It’s all about the behavior of partial sums and whether we get a square root n central limit theorem or not.
Kolya: So what this means is that we have a much clearer picture of how these chains behave when you’re looking at the variance limits.
Emmy: Exactly, it moves us past just guessing what the variance might be in different situations. It shows the necessary and sufficient conditions for things to hold together nicely.
Ada: The main thing is that they define sharp boundaries between when those limit variances are finite and when they aren't, based on properties like square integrability of a function.
Kolya: And the way they prove it, using martingale methods, it really connects the structure of the chain—like how we decompose things into forward and backward parts—to these asymptotic limits.
Emmy: It’s about seeing that underlying structure, you know? How those decompositions lead directly to those square root n central limit theorems.
Ada: The implication for us is that if you're running these Markov chain Monte Carlo algorithms, knowing these variance conditions helps you predict whether your estimates will settle down to a stable number or if they’ll keep bouncing around.
Kolya: Because the results show that without certain assumptions, like square integrability, we just run into undefined variances or non-tight behavior.
Emmy: It’s a lot of work to prove all those connections—from Fourier analysis to these specific bounds on sigma squared.
Ada: And it sets up the next big question about how these variance limits actually manifest in real-world applications.
Austin Browna, Jeffrey S. Rosenthalb, Quan Zhoua
Texas A&M University · University of Toronto
math.PR, math.ST, stat.CO, stat.TH
Submitted: 2026-09-07
Updated: 2026-11-02
Comments: 26 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 96/100
The gist: Markov chain central limit theorems (CLTs) and their associated variances are very important for implementing Markov chain Monte Carlo algorithms among other applications The paper resolves seven…
Key concepts
- Normalized Partial Sums (Sn/√n)
- These are the partial sums of a sequence related to additive functionals of a Markov chain, scaled by the square root of n. Analyzing their behavior (tightness or convergence) is central to determining if a Central Limit Theorem holds for the chain's properties.
- Square-Integrable Function (h ∈ L²(π))
- This condition means that the function h, which defines the additive functional, has a finite variance with respect to the stationary distribution of the Markov chain. The paper shows this is crucial: if h is square-integrable, it guarantees tightness and finite variance in certain scenarios.
- Fourier-to-Markov Covariance Realization Principle
- This advanced technique is used to solve open problem 1. It constructs a specific type of Markov chain whose lagged autocovariances match the Fourier coefficients of any continuous, even, periodic function. This helps understand complex covariance behaviors in nonreversible chains.
- Asymptotic Variance (σ²)
- This represents the limiting variance ($ ext{Var}(rac{S_n}{\sqrt{n}}) o ext{N}(0, \sigma^2)$) when the CLT holds. The paper characterizes this variance by relating it to the limits of various quantities (A, B, C) and shows its relationship with h ∈ L²(π).
Terminology
Summary
Markov chain central limit theorems (CLTs) and their associated variances are very important for implementing Markov chain Monte Carlo algorithms among other applications The paper resolves seven open problems posed by Häggström and Rosenthal regarding the behavior of variance formulae (A, B, C) associated with additive functionals of stationary, ergodic, and reversible Markov chains
Core Results on Variance Equivalence
The authors prove that for stationary, ergodic, and reversible chains where the normalized partial sums satisfy a √n-CLT, the variance limit is finite if the function is square-integrable, otherwise undefined They establish that failure of the √n-CLT forces the normalized partial sums to be non-tight Specifically, for ergodic and reversible chains with centered h ∈ L1(π), the sequence (Sn/√n)n≥1 satisfies a dichotomy: either a √n-CLT holds, or the sequence (Sn/√n)n≥1 is not even tight When h ∈ L2(π), tightness forces A = B = C < ∞, which shows that A < ∞ is both necessary and sufficient for a √n-CLT
Resolutions of Open Problems
The paper provides solutions to the seven HR problems posed by Häggström and Rosenthal
-
HR Problem 1 is resolved by developing a general Fourier-to-Markov covariance realization principle, showing that A = B can be infinite even when h ∈ L2(π)
-
HR Problem 2 is resolved by proving that if a √n-CLT exists for h /∈ L2(π), then A must be undefined
-
HR Problem 3 is resolved by showing that Roberts’ condition cannot coexist with a √n-CLT, even without assuming reversibility or h ∈ L2(π)
-
HR Problem 4 shows that h ∈ L2(π) is a necessary and sufficient condition for A < ∞ when the chain is reversible and ergodic
-
HR Problem 5 proves that if the chain is reversible, ergodic, and there is δ > 0 such that r(x) ≥ δ for all x ∈ X, then A < ∞
-
HR Problem 6 shows that if P is reversible and ergodic and h ∈ L2(π) satisfies a √n-CLT, then A < ∞
-
HR Problem 7 demonstrates that the condition π(h2) < ∞ cannot be dropped from Corollaries 6 and 7
Technical Methodology for Proofs
The proofs heavily rely on martingale-based methods, including forward-backward martingale decomposition and characteristic function analysis Proposition 3.2 constructs a function d ∈ L2(Γ) such that h(x) + h(y) = d(x, y) + d(y, x), which is central to proving the CLT for Sn/√n The proof of Theorem 3. p. 11 uses this decomposition to show that Varπ(S2n) ≤ 4n∥d∥2L2(Γ)
Asymptotic Variance Characterization
Theorem 3.1 establishes that if (Sn/√n)n≥1 is bounded in probability for a reversible and ergodic chain, then Sn/√n ⇒ N(0, σ2) for some 0 ≤ σ2 < ∞ The asymptotic variance σ2 is characterized by the limit of A2n as A2n → σ2, which is shown to be equal to C when h ∈ L2(π) Furthermore, Corollary 3. p. 25 shows that if h /∈ L2(π) but a √n-CLT holds, then lim inf n→∞ An = σ2, lim sup n→∞ An = ∞, and B is undefined
Advanced Construction Techniques
To solve HR Problem 1, the authors introduce a Fourier-to-Markov covariance realization principle that constructs a regenerative Markov chain whose lagged autocovariances coincide with the Fourier coefficients of any strictly positive, continuous, even, 2π-periodic function This construction allows for the realization of complex covariance behaviors in nonreversible Markov chains The proof for Proposition 5.3 uses a decomposition into sums of squared polynomial moduli derived from Fejér’s theorem
Sharpness and Bounds
The paper provides sharp bounds, such as in Proposition 3.4, showing that Varπ(S2) = 4δ while σ2 = δ/(1 − δ) for a specific chain Theorem 3. p. 910 further provides an upper bound on the asymptotic variance σ2 by relating it to the cycle-sum variance E[Z21] < ∞ The construction in Theorem 4. p. 65 yields a bound on σ2 ≤ βπ(D)E[Z21]<∞ This result is particularly useful for bounding the variance when Roberts’ condition holds The final result in Corollary 3. p. 07 shows that A < ∞ if and only if π(h2) < ∞ This is a key consequence derived from the combination of Theorem 4. p. 31 and Theorem 3. p. 01 The paper concludes by showing that for ergodic and reversible Markov chains, if h ∈ L2(π), then either a √n-CLT holds with σ2 = A = B = C < ∞, or (Sn/√n)n≥1 is not tight and A = B = C = ∞ The entire framework is built upon the GPT5. p. 6
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved variance estimation for Markov chain Monte Carlo algorithms by providing a general principle that expresses Fourier coefficients as autocovariances of an ergodic nonreversible Markov chain. This allows AI systems to estimate asymptotic variance sigma squared even when reversibility is not assumed, which is crucial for robust error bounds in MCMC methods.
-
Rigorous determination of the relationship between the square root n-CLT and variance quantities A, B, and C for stationary ergodic reversible chains by establishing a sharp classification based on whether h is in L 2(pi) or not. This enables AI systems to predict whether a CLT will hold with finite variance or if the normalized partial sums will be non-tight.
-
Development of a mathematical tool to construct countable-state, irreducible, and positive recurrent Markov chains whose lagged autocovariances coincide with the Fourier coefficients of any strictly positive, continuous, even 2 pi periodic function. This allows AI systems to realize complex correlation structures required for modeling specific physical or statistical processes in MCMC simulations.
-
A method to detect when Roberts’ holding-probability condition precludes a CLT even without assuming reversibility or square-integrability. This helps AI systems identify scenarios where standard CLT assumptions fail due to specific chain dynamics, leading to more targeted algorithm design.
-
A framework for proving that if the normalized partial sums satisfy a sqrt n-CLT, then the function h is in L 2(pi) if the chain is reversible and ergodic. This provides a necessary and sufficient condition for determining when an MCMC sampler's asymptotic behavior can be characterized by finite spectral variance C.
-
A method to detect if Roberts’ condition holds for reversible chains where a sqrt n-CLT exists, showing that this condition cannot coexist with the CLT unless h is in L 2(pi). This helps refine the search space for parameters in complex sampling algorithms.
-
A method to establish when a reversible chain with a sqrt n-CLT implies that A is finite, providing an upper bound on sigma squared derived from spectral and regenerative tools. This allows AI systems to verify if their simulations are converging to a well-behaved Gaussian limit by checking the convergence of A2n.
Sources
- On the central limit question for strictly stationary, reversible Markov chains
- Ergodic Central limit theorem for subgeometric Markov chains
- Early science acceleration experiments with GPT-5
- Hardy spaces and Szeg\H{o} projection on quotient domains
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests