📊 statistics

A Direct Route to Markov Chain Convergence via Asymptotic Equivalence with the Target

This paper presents a self-contained, necessary and sufficient criterion for Markov chain convergence based on asymptotic equivalence with the target measure, offering a streamlined proof that avoids traditional assumptions like irreducibility, aperiodicity, or coupling techniques while establishing the strong law of large numbers for various algorithms including Gibbs samplers and parallel tempering.

Original authors: Patrick Forré

Published 2026-08-05

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Patrick Forré

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the most popular spot in a giant, invisible city. You don't have a map, and you can't see the whole city at once. All you have is a very specific set of rules for taking steps. You start at a random house, follow your rules to jump to a new house, then jump again, and again. This is the heart of Markov Chain Monte Carlo (MCMC), a powerful tool used by scientists, statisticians, and machine learning engineers to solve problems that are too complex to calculate directly. Whether they are training an AI to recognize faces, simulating how atoms move in a new material, or figuring out the odds of a rare disease, they use these "random walkers" to explore a landscape.

The big question is: How do you know the walker has actually found the right place? If you keep walking long enough, does the walker eventually settle down and start visiting every neighborhood in proportion to how popular it is? In the world of math, this is called "convergence." For decades, proving that a walker will eventually settle down required a massive toolkit of heavy machinery: checking if the walker can reach every corner of the city (irreducibility), making sure it doesn't get stuck in a loop (aperiodicity), and finding special "small sets" that act as reset buttons. It was like trying to prove a car will reach its destination by checking the engine, the tires, the fuel, and the driver's license separately, even if you just wanted to know if the car would get there.

This paper, titled "A Direct Route to Markov Chain Convergence via Asymptotic Equivalence with the Target," by Patrick Forré, throws out the heavy toolkit and offers a much simpler, more direct path. The author proves that you don't need to check all those complicated conditions. Instead, you only need to watch the walker's relationship with the "target" (the true distribution of the city) over time. The paper shows that if two specific things happen as the walker takes more and more steps, the walker is guaranteed to converge. First, the walker must stop hiding in "invisible" places that the target doesn't care about. Second, the walker must eventually learn to see every part of the target that matters. If both happen, the walker has arrived. The paper doesn't just prove this for perfect, smooth cities; it proves it for messy, broken, or weirdly shaped ones, including famous algorithms like the Metropolis-Hastings and Gibbs samplers that were previously thought to need the heavy machinery to be understood.

The Story of the Two Ghosts

To understand what this paper actually does, let's imagine the "Target" (the true distribution $\pi$ ) as a Ghost City. This city has a specific shape and population density. Some neighborhoods are bustling (high probability), and some are empty (zero probability).

Now, imagine our Random Walker (the Markov chain) is a traveler trying to map this Ghost City. The traveler has a rulebook (the kernel $T$ ) that tells them how to jump from one spot to another. The goal is for the traveler's map, after many jumps, to look exactly like the Ghost City.

The paper argues that to prove the traveler has succeeded, we don't need to check if the traveler can visit every house or if they avoid loops. We only need to check for two specific "ghosts" that might be haunting the traveler's map:

1. The Ghost of the Invisible (Asymptotic Absolute Continuity)
Imagine the traveler starts in a part of the city that the Ghost City doesn't even know exists. Maybe they are standing on a bridge that the Ghost City considers "non-existent." As long as the traveler stays there, their map is wrong.

The Paper's Rule: The paper says, "We don't care if the traveler starts in the wrong place. We just need to know that as time goes on, the amount of time they spend in these 'invisible' places shrinks to zero."
The Metaphor: Think of the traveler wearing a heavy, invisible cloak. At first, the cloak covers them completely, hiding them from the Ghost City. The paper proves that if the cloak gets thinner and thinner with every step until it vanishes, the traveler is finally visible to the Ghost City. The traveler doesn't need to be perfectly visible immediately; they just need to become visible eventually.

2. The Ghost of the Blind Spot (Asymptotic Domination)
Now imagine the traveler is visible, but they are missing a huge chunk of the city. Maybe they can see the north side, but the south side is a "blind spot" they can't reach. The Ghost City exists there, but the traveler's map is empty.

The Paper's Rule: The paper says, "We need to make sure the traveler eventually learns to see the parts of the city they were ignoring."
The Metaphor: Imagine the traveler has a flashlight. At first, the flashlight beam is narrow, leaving the rest of the city in darkness. The paper proves that if the beam of the flashlight widens over time until it covers the entire Ghost City (even if it takes a long time), then the traveler has successfully mapped the target.

The "Direct Route" vs. The Old Way

Before this paper, mathematicians trying to prove a traveler would succeed had to use a very complicated method called the "Splitting Construction." It was like saying, "To prove the traveler will get to the Ghost City, we must first prove they can find a special 'reset button' (a small set) that lets them start over, and then prove they can reach every corner of the city without getting stuck in a loop."

This paper says: "Stop. You don't need the reset button. You don't need to check for loops. Just watch the two ghosts."

The author proves that if the "Invisible Ghost" fades away and the "Blind Spot Ghost" disappears, the traveler must converge. It's a "Direct Route" because it cuts out all the middlemen.

Why This Matters: The Messy Real World

The most exciting part of this paper is that it works for the algorithms we actually use in real life, which are often messy and imperfect.

The Metropolis-Hastings Algorithm: This is a famous method used in statistics. It often has a "stutter." Sometimes, the algorithm tries to move but gets rejected and stays exactly where it is. This creates a "clump" of probability at the starting point (an atom). In the old, complicated theory, this stutter made things hard to prove. In this paper's language, the "stutter" is just a heavy cloak that gets lighter and lighter with every step. The paper proves that even with the stutter, as long as the cloak eventually vanishes, the algorithm works.
The Gibbs Sampler: This is another popular method where you update one piece of data at a time. Sometimes, the math says the traveler is "singular" (completely invisible) to the target at every single step. The old theory struggled with this. This paper says, "So what? As long as the invisibility fades over time, you're good."

What the Paper Does Not Do

It is important to know what this paper leaves out, just as much as what it includes.

No Speed Limits: The paper proves the traveler will get there, but it doesn't tell you how fast. It's like proving a car will reach New York, but not saying if it takes 4 hours or 4 days. In fact, the paper explicitly shows examples where the car gets there, but the time it takes varies wildly depending on where you started, so there is no single "speed limit" for all travelers.
No New Algorithms: The paper doesn't invent a new way to walk. It just gives a new, simpler way to prove that existing walkers (like Gibbs and Metropolis-Hastings) are doing their job.
No "Magic" for Bad Walkers: If the traveler is stuck in a loop or can never reach a certain part of the city, the two ghosts won't disappear. The paper doesn't fix broken algorithms; it just gives a better way to test if they are broken or not.

The Big Picture

In simple terms, this paper is a shortcut to certainty.

Imagine you are a teacher grading a student's map of a city. The old way was to check every single street, every traffic light, and every building code to ensure the map was perfect. This new paper says, "Don't bother with all that. Just check two things: Did the student stop drawing things that don't exist? And did they eventually draw everything that does exist?" If the answer is yes to both, the map is correct.

By focusing on these two simple conditions—Asymptotic Absolute Continuity (stopping the invisible hiding) and Asymptotic Domination (filling the blind spots)—Patrick Forré has provided a clean, self-contained proof that works for almost any random walker, no matter how weird or broken their rules might be. It's a reminder that sometimes, the most direct route to the truth is to stop looking at the complicated machinery and just watch the destination.

Technical Summary: A Direct Route to Markov Chain Convergence via Asymptotic Equivalence with the Target

Problem Statement
Markov Chain Monte Carlo (MCMC) methods are widely used to sample from target probability measures $\pi$ on general state spaces, often defined only up to a normalizing constant. The standard justification for the convergence of these chains relies on the theory of $\psi$ -irreducible, aperiodic Harris chains. This classical framework requires establishing properties such as irreducibility, aperiodicity, recurrence, and the existence of "small sets" or "splitting constructions." These concepts are technically demanding and often designed to cover state spaces far more general than those encountered in practical applications (e.g., $\mathbb{R}^d$ or manifolds). Furthermore, many practical algorithms, such as the random scan Gibbs sampler or parallel tempering, possess transition kernels that are singular with respect to the target measure $\pi$ at every step, rendering standard density-based convergence criteria inapplicable.

The paper addresses the need for a self-contained, direct proof of Markov chain convergence in total variation that:

Avoids the machinery of irreducibility, aperiodicity, recurrence, couplings, and splitting constructions.
Works on arbitrary measurable spaces without topological assumptions.
Applies to kernels that are singular with respect to the target at every step.
Provides a criterion that is both necessary and sufficient for convergence.

Methodology
The author proposes a convergence criterion based on the Lebesgue decomposition of the law of the chain $T^n_x$ (the distribution after $n$ steps starting from $x$ ) with respect to the invariant measure $\pi$ . The decomposition is written as $T^n_x = T^n_{x,ac} + T^n_{x,sg}$ , where the first part is absolutely continuous with respect to $\pi$ and the second is singular.

The core of the methodology rests on two asymptotic conditions:

Asymptotic Absolute Continuity (S): The singular mass of the chain's law vanishes as $n \to \infty$ for every starting point $x$ . Formally, $\text{sing}(T^n_x \mid \pi) \to 0$ . This ensures that the chain eventually "forgets" any initial mass concentrated on sets of $\pi$ -measure zero.
Asymptotic Domination of the Target (L/P): The part of the target $\pi$ that the chain fails to "see" vanishes as $n \to \infty$ . Formally, $\text{sing}(\pi \mid T^n_x) \to 0$ for $\pi$ -almost every $x$ . This ensures the chain eventually explores the entire support of $\pi$ .

The proof strategy avoids the standard "Doeblin condition" (which requires a uniform lower bound on the transition density, $\epsilon_0 > 0$ ) because such a bound rarely exists on general spaces. Instead, the proof utilizes a renormalization argument:

It establishes that the total variation distance between two laws is non-increasing (contraction).
It shows that for laws dominated by a multiple of $\pi$ (i.e., $\mu \le M\pi$ ), the transition kernel creates a "common minorant" of positive mass after a finite number of steps, provided the target is asymptotically dominated.
By assuming the limit of the distance is non-zero, the author constructs a contradiction using the renormalized difference of two such laws, showing the distance must decay to zero.
The passage from arbitrary initial distributions to the dominated class is handled by the asymptotic absolute continuity condition, which allows truncating the singular part of the initial law.

Key Contributions and Results

The Main Convergence Theorem (Theorem A / Theorem 60):
On a countably generated measurable space, a Markov chain with invariant measure $\pi$ converges in total variation from every initial distribution if and only if:
- $\text{sing}(T^n_x \mid \pi) \to 0$ for every $x$ (Asymptotic Absolute Continuity).
- $\text{sing}(\pi \mid T^n_x) \to 0$ for $\pi$ -almost every $x$ (Asymptotic Domination).
  This criterion is shown to be necessary and sufficient.
Density-Free Formulation (Theorem 46):
To avoid the technical requirement of countable generation for the "if" direction, the paper introduces a stronger, density-based condition called (P): the existence of a jointly measurable minorant density after finitely many steps. Theorem 46 proves convergence under (P) and (S) without any topological assumptions on the state space.
Verification in Specific Settings:
The paper verifies the (P) and (S) conditions for four distinct scenarios, demonstrating the criterion's breadth:
- Strictly Positive Transition Density (Theorem B/70): The classical case where $T$ has a density $t(y|x) > 0$ everywhere.
- Metropolis–Hastings (Theorem C/77): Covers kernels with an atom at the starting point (due to rejection) plus an absolutely continuous part. This handles the generic case where the chain is not absolutely continuous at any finite step.
- Eventually Positive Density (Theorem D/87): Covers cases where the transition density becomes strictly positive only after a finite number of steps $n(x)$ that may depend on the starting point.
- Singular Kernels (Theorem E/98 & Corollary 103): Applies to the Random Scan Gibbs Sampler and Parallel Tempering. These algorithms are singular with respect to $\pi$ at every step (no iterate is absolutely continuous), yet the paper proves they satisfy (P) and (S) via specific minorant constructions.
Strong Law of Large Numbers (Corollary F/115):
The paper demonstrates that under these convergence conditions, Birkhoff's ergodic theorem applies, ensuring that time averages along a single trajectory converge almost surely to the integral against $\pi$ . A weak law of large numbers is also derived without invoking Birkhoff's theorem.

Significance and Claims
The paper explicitly states that none of the theorems proved are new in their conclusions; the convergence of these specific chains is well-established in the literature (e.g., by Doob, Tierney, Roberts & Smith).

The significance of the work lies in the route taken to these results:

Simplicity and Directness: It offers a "short route" to a single, widely applicable convergence criterion, bypassing the complex machinery of Harris recurrence, small sets, and splitting constructions.
Generality: It operates on bare measurable spaces, requiring no topology, metric, or countability assumptions (except where necessary to construct a jointly measurable density version).
Unified Framework: It treats algorithms with singular kernels (like Gibbs and Parallel Tempering) on the same footing as those with positive densities, using a unified criterion based on the Lebesgue decomposition.
Necessity and Sufficiency: Unlike many sufficient conditions in the literature, this criterion is proven to be necessary as well.
No Rates: The paper is modest about its limitations, noting that while it proves qualitative convergence, it does not provide convergence rates (geometric ergodicity), as the constants involved depend on the unknown limit of the distance.

In summary, the paper provides a self-contained, measure-theoretic proof that Markov chain convergence is equivalent to the mutual asymptotic absolute continuity of the chain's law and the target measure, offering a streamlined alternative to the general theory of Harris chains for a wide class of practical MCMC algorithms.