On the Impossibility of Estimating the Average Mixing Time

Nathan A. Judd; Amedeo Roberto Esposito

Source-linked AI summary

On the Impossibility of Estimating the Average Mixing Time

Nathan A. Judd, Amedeo Roberto Esposito

arXiv:2610.10860v1Oct 7, 2026math.STcs.ITmath.ITstat.TH

TL;DR

Worst-case mixing can emphasize slowly mixing states that are rarely observed in a stationary trajectory, motivating estimation of average mixing time. The paper constructs converse bounds and shows that, in stated regimes, they recover key uniformly ergodic achievability dependencies up to logarithmic factors.

Problem
Worst-case mixing gives full weight to the slowest initial state, even when it has negligible stationary probability, motivating study of dependence averaged under stationary initialization.
Source: §1 · p. 2
Method
The paper constructs converse bounds, including a delayed-register chain that makes statistically close chains fall on opposite sides of the tolerance band.
Source: §1 · pp. 3–4, §4 · p. 5
Results
Within stated regimes, the converses recover uniformly ergodic achievability scaling and match its key dependencies up to logarithmic factors.
Source: §1 · p. 4
Takeaways & Limitations
The results match linear worst-case mixing-time, inverse-quadratic threshold-accuracy, effective-support, and confidence dependencies in the uniformly ergodic achievability bound, up to logarithmic factors.
Source: §1 · p. 4
The first converse does not capture the effective-support bottleneck, and open problems include non-stationary initialisations and whether the ergodic-chain (ξϵ)−2 gap is intrinsic.
Source: §4.1 · p. 6, §6 · p. 16

Abstract

from arXiv · show

We establish nearly-matching converse bounds on the sample complexity of estimating the average mixing time of a Markov chain from a single stationary trajectory. Unlike the worst-case mixing time, which maximises the total-variation distance to stationarity over all initial states, the average mixing time averages this distance under the stationary distribution and can therefore be substantially smaller. Our converse bounds establish when estimation is impossible, and match the key dependencies in existing achievability bounds, up to logarithmic factors. Together, these bounds provide nearly-tight PAC guarantees for estimating the average mixing time.

1 Introduction

Worst-case mixing emphasizes the slowest initial state, whereas average mixing measures dependence under stationary initialization and can be smaller when slow states have little stationary mass. The paper introduces converse bounds to test how difficult average-mixing-time estimation is and how closely it matches existing achievability guarantees.

1 Introduction

Worst-case mixing uses the slowest-converging initial state, which can overstate dependence along a stationary trajectory when that state has negligible stationary probability.Average mixing instead averages distance to stationarity over initial states according to their stationary probabilities and can be substantially smaller.Source: §1 · p. 2
Because β-mixing lacks the worst-case mixing-time submultiplicative property, average mixing requires an explicit threshold and a threshold-explicit loss.The loss is zero when the estimated mixing time lies within the tolerance interval.Source: §1 · pp. 2–3
Existing uniformly ergodic achievability guarantees motivate matching lower bounds to determine whether their sample-size dependencies reflect statistical difficulty.The cited result depends on effective support and confidence, and its tilde notation suppresses logarithmic factors.Source: §1 · p. 3
The first converse uses a constructed 2k-valued chain and rules out uniform estimation below its stated sample-complexity threshold.Below the bound, no estimator can guarantee failure probability at most δ for all admissible chains; this converse is uniform in ξ and ϵ.Source: §1 · pp. 3–4
The second converse uses a metastable D-state chain with checkerboard transitions and applies for a fixed threshold and narrow accuracy range.Together with the first converse, it contributes to bounds covering dependencies that neither converse captures alone.Source: §1 · p. 4
The converse bounds recover uniformly ergodic achievability scaling within stated threshold and accuracy regimes, matching key dependencies up to logarithmic factors.For ergodic chains, the cited achievability bound has a 1/(ξϵ)^4 threshold-accuracy scaling, a factor 1/(ξϵ)^2 larger than the uniformly ergodic achievability and impossibility bounds; whether this gap reflects looseness remains open.Source: §1 · p. 4

2 Related Work

Prior work studies estimation of worst-case mixing time and related quantities, while average mixing time and its estimation bounds are more recent topics. Related work also connects reversible-chain mixing-time estimation with spectral and stationary-mass estimation.

2 Related Work

Worst-case mixing-time estimation and related objects have been studied extensively (Hsu et al., 2019; Wolfer and Kontorovich, 2019, 2021).Source: §2 · p. 4
The average mixing time was introduced by M¨unch and Salez (2023), and estimation upper bounds appeared in Wolfer and Alquier (2026).Source: §2 · p. 4
For reversible chains, finite-sample worst-case mixing-time estimation is closely connected to estimating the absolute spectral gap and least stationary mass.Transition-kernel estimation and instance-dependent confidence intervals address the cost of learning conditional distributions from one dependent path (Wolfer and Kontorovich, 2019, 2021; Wolfer, 2024).Source: §2 · p. 4

3 Definitions and notation

The setup considers finite or countable state spaces and observes one stationary trajectory, with the estimator based on that trajectory. The section also introduces notation for the path law and a divergence used in the analysis.

3 Definitions and notation

The constructed chains have finite or countable state spaces.Source: §3 · p. 4
The data are one stationary trajectory of length m, containing m −1 transitions, and the estimator may be randomized and N-valued.Source: §3 · pp. 4–5
The setup names the path law of P and introduces the KL divergence between Rademacher variables with parameters in [−1, 1].Source: §3 · p. 5

4 Formal results

The formal results use delayed-register chains to expose estimation and confidence bottlenecks, and rare-refresh checkerboards to expose an effective-support bottleneck. Combining the checkerboard converses yields joint scaling across mixing time, relative accuracy, effective support, and confidence.

4.1 Delayed-register chain

The delayed-register construction creates statistically close chains whose β-mixing coefficients straddle the tolerance band at lags comparable to their mixing times, producing an inverse-quadratic ξϵ testing bottleneck.Source: §4 · p. 5
The delayed-register kernel shifts register coordinates and appends Z=x1E, where E is an independent Rademacher variable with mean a.Source: §4.1 · p. 5
Theorem 4.1 captures estimation and confidence bottlenecks uniformly in (ξ, ϵ), but does not capture the effective-support bottleneck.Source: §4.1 · p. 6

4.2 Rare-refresh checkerboard chain

The rare-refresh checkerboard has two metastable regions: most transitions hold, while refreshes switch regions with probability q=1/R.The information determining the β-mixing coefficient is spread across order D^2 possible left-to-right source-destination pairs.Source: §4.2 · p. 6
The common-coefficient checkerboard parametrisation yields the confidence term in its converse.Source: §4.2 · pp. 6–7
Combining the two checkerboard subclasses yields a converse with joint scaling across mixing time, relative accuracy, effective support, and confidence.The combined converse is stated under Assumption 2.Source: §4.2 · p. 7
The varying-coefficient checkerboard converse isolates an effective-support bottleneck, with dependence information spread over many state pairs observed at relevant lags.Source: §4 · p. 5, §4.2 · p. 7
The combined converse lower-bounds the trajectory length needed to estimate average mixing time within the stated threshold band; such estimates can inform MCMC effective-sample-size calculations.Source: §4.2 · p. 7

5 Overview of techniques

The section develops two converse constructions: a delayed register for the threshold–accuracy bottleneck and a rare-refresh checkerboard for confidence and effective-support bottlenecks. Together, their bounds match key uniformly ergodic achievability dependencies up to logarithmic factors.

5 Overview of techniques

The delayed register retains part of the initial state before k transitions, while weak binary dependence controls β-mixing at the first complete flush.The two chains are selected so their β-mixing heights lie on opposite sides of the threshold band.Source: §5.1 · p. 8

5.1 Proof of Theorem 4.1

m−1 ≥ k/[12L²(ξϵ)²] · log(1/(4δ)) is required for uniform risk at most δ in the delayed-register construction.The construction uses a weak binary dependence parameter to separate β-mixing coefficients after a k-transition delay.Source: §5.1 · pp. 8–9

5.2 Proof of Theorem 4.4

Rare refreshes enlarge the mixing scale while preserving checkerboard transition directions whose probabilities depend on unknown coefficients.Common coefficients yield a confidence problem; varying coefficients yield an effective-support bottleneck.Source: §5.2 · p. 9

5.2.1 Metastable regions

The rare-refresh checkerboard stays put with probability 1−q and switches regions at refreshes, giving each metastable region a geometric exit time with mean R.The constructed kernel is uniformly ergodic.Source: §5.2.1 · p. 10

5.2.2 General β-mixing coefficient

The general β-mixing calculation separates a coefficient-zero baseline from blockwise hinge contributions.The hinge contribution is positive when the exactly-one-refresh perturbation exceeds the regional imbalance.Source: §5.2.2 · p. 10

5.2.3 Common-coefficient checkerboard

Assigning one common coefficient to every block makes the checkerboard family statistically one-dimensional despite its order-D² transition-pair support.This specialization supplies the confidence bottleneck used in the combined converse.Source: §5.2.3 · pp. 11–12

5.2.4 Varying-coefficient checkerboard

When m−1 ≤ c_inf M/(qη^(2ℓ)), some chain has failure probability greater than 19/40, yielding the effective-support converse.The hidden coefficients spread information across many source–destination pairs, while moment matching cancels low-order terms in the likelihood comparison.Source: §5.2.4 · pp. 12, 15

5.3 Combining the two matched subclasses

The combined subclasses match the confidence and effective-support terms in the uniformly ergodic achievability scaling, within the stated threshold and accuracy regimes.The resulting converse dependencies are linear in worst-case mixing time and inverse-quadratic in threshold-accuracy, up to logarithmic factors.Source: §5.3 · p. 16

6 Discussion

The discussion identifies the constructions’ scope and several remaining gaps in the converse bounds.

6 Discussion

The effective-support bottleneck is not yet uniform over threshold and accuracy, non-stationary initialisations remain unaddressed, and logarithmic and ergodic-chain gaps remain open.The authors also leave open whether the ergodic-chain (ξϵ)^−2 gap is intrinsic or an upper-bound artefact.Source: §6 · p. 16

A Proofs of Lemmas and Propositions

The proofs establish mixing properties for delayed-register and rare-refresh checkerboard chains, and derive the checkerboard’s average-distance calculation from blockwise contributions.

Binomial total-variation bound

The binomial total-variation function is strictly increasing on the relevant interval, making its generalized inverse an ordinary inverse there.The proof establishes this for the interval [0, C/√k) and uses the result to control inverse increments.Source: A Proofs of Lemmas and Propositions · pp. 21–22

Delayed-register proof

Before k transitions, the delayed-register chain’s common distance from stationarity exceeds 1/2, so its worst-case mixing time is at least k.The distance is the same for every initial word.Source: A Proofs of Lemmas and Propositions · p. 22

Checkerboard proof

The rare-refresh checkerboard is doubly stochastic with a uniform stationary law and is uniformly ergodic.Positive self-loops and reachability across regions in one or two refreshes establish the stated properties.Source: A Proofs of Lemmas and Propositions · p. 22

Mixing-coefficient calculation

The checkerboard average-distance calculation sums blockwise increments, with stationary averaging and row-wise maximization using different factors.The coefficient-zero chain contributes the baseline distance; parameter-bearing blocks contribute hinge increments.Source: A Proofs of Lemmas and Propositions · p. 23

B Supporting Lemmas

The supporting lemmas establish useful properties of the threshold function h and express total variation between product laws as a difference of binomial upper-tail probabilities. They also give regularity for Bk and numerical bounds used in the appendix.

B Supporting Lemmas

For 0<a<1, h(a) obeys a/2 ≤ h(a) < a; moreover, h is continuous and strictly increasing on [0,1), with h(0)=0.Source: B Supporting Lemmas · p. 28
The likelihood ratio exceeds one exactly when S > kh(a), yielding the binomial event {X ≥ jk(a)} and a total-variation difference of binomial upper tails.Under Pa, X ∼ Bin(k, (1 + a)/2); under P0, X ∼ Bin(k, 1/2).Source: B Supporting Lemmas · p. 29
Bk is locally absolutely continuous on [0, 1), and its stated derivative identity holds almost everywhere despite finitely many threshold-change points.The threshold is piecewise constant, and Bk is continuous across its finitely many exceptional points.Source: B Supporting Lemmas · pp. 29–30
The bounds on r and 1 − 1/R ≥ 0.99 give 0.117 < w < 0.124; also, p/2 < r because 0 < 1 − 2/R < 1 − 1/R and 1 − 2/D ≥ 31/32.Source: B Supporting Lemmas · p. 33

C Constants for the rare-refresh checkerboard

The constants section defines a⋆ from the best uniform polynomial approximation error to |x| and uses a finite-degree Bernstein bound to show it is positive.

C Constants for the rare-refresh checkerboard

For γj := infdeg(p)≤j ∥|x| − p(x)∥∞,[−1,1] and a⋆ := infj≥1 jγj, the passage states that the finite-degree Bernstein bound gives a lower bound for a⋆.The displayed bound is truncated after “1/{4(1 +”, so its complete denominator cannot be reported.Source: C Constants for the rare-refresh… · p. 34