Optimistic Estimation of Convergence inMarkov Chains with the Average MixingTime
Pierre AlquierSciCADE, July 15, 2024, Singapore

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Talk is based on the preprint :Wolfer, G. and Alquier, P. (2024).
Optimistic Estimation ofConvergence in Markov Chains withthe Average Mixing Time. Preprint
arXiv :2402.10506.
Geoffrey WOLFER
Waseda University, Tokyo

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing TimeIn this talk, (X1 , X2 , X3 . . . ) is an ergodic Markov chain on afinite or countable space X , with transition kernel P andinvariant probability π.
d(t) = sup ∥δx P t − π∥TV .
x∈XMixing timetmix (ξ) = min{t : d(t) ≤ ξ} ∈ {1, 2, . . . } ∪ {+∞}.
Multiplicative property
tmix (ξ) ≤ ⌈log2 (1/ξ)⌉tmix (1/4).
tmix := tmix (1/4).
Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Hsu, D., Kontorovich, A., Levin, D. A., Peres, Y., Szepesvári, C. & Wolfer, G. (2019). Mixing time
estimation in reversible Markov chains from a single sample path. Annals of Applied Probability.

Wolfer, G. & Kontorovich, A. (2024). Improved estimation of relaxation time in nonreversible
Markov chains. Annals of Applied Probability.

Based on a trajectory (X1 , . . . , Xn ) on a finite X we canestimate the spectral gap γ of P : with probability 1 − δ,v  uu log card(X ) log ntδπ∗ δ|γ̂ − γ| ≤ Cπ∗ γnwhere π∗ = minx π(x) ;estimate the relaxation time trel = 1/γ :finally,(trel − 1) log 2 ≤ tmix ≤ trel log
Pierre Alquier, ESSEC Business School4.
π∗Markov Chains & Average Mixing Time

The mixing time is a pessimistic notion :tmix (ξ) can be infinite,d(t) = supx∈X ∥δx P t − π∥TV .
This motivates :d ♯ (t) =Xπ(x)∥δx P t − π∥TV .

x∈X

Average mixing time
♯tmix(ξ) = min{t : d ♯ (t) ≤ ξ}.

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Proposition 1♯(ξ) < +∞.
tmix

Proposition 2
Assume card(X ) = 2. Then, for any M > 0, there exists atransition kernel P such thattmix (ξ)♯tmix(ξ)> M.

Remarks :no multiplicative property,♯
this talk : tmix(ξ) is still informative and can be estimated.

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing TimeA little detour to show that the average mixing time is a useful
notion : let us explore its connection to mixing coefficients.
Mixing coefficients are general tools developped to study
the convergence of general stochastic processes.
There are many notions : α-mixing, β-mixing andφ-mixing are the most popular.
Definition : β-mixing coefficients
For two σ-fields A and B,I XJX
1β(A, B) = sup|P(Ai ∩ Bj ) − P(Ai )P(Bj )|,2
i=1 j=1
sup over all partitions (Ai )Ii=1 and (Bj )Jj=1 of Ω by sets in A
and B respectively ;β(s) = sup β(σ(Xt , . . . , Xt+h ), σ(Xt+h+s , . . . , Xt+h+s+ℓ )).
t,h,ℓPierre Alquier, ESSEC Business School

Markov Chains & Average Mixing TimeLet f be a measurable function with Eπ (f ) = 0 and∥f ∥∞ ≤ 1. Let n, B, s be three integers with n = Bs.
Theorem (Yu, 1984)
P!
n1X
nε2f (Xi ) > ε ≤ 2 exp −+ 2(B − 1)β(s).
n i=14s

Theorem (Mohri and Rostmizadeh, 2008)!
n1X
P supf (Xi ) > ε + 2RadB (F)f ∈F ni=1
nε2≤ 2 exp −+ 2(B − 1)β(s)4swhere RadB (F) is the Rademacher complexity.
Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Many classical processes satisfy β(s) ≤ β0 exp(−β1 s b ) orβ(s) ≤ β1 /s b .
In theory, it is possible to estimate β(s) based on atrajectory (X1 , . . . , Xn ), see
Khaleghi, A. and Lugosi, G. (2023). Inferring the mixing properties of a stationary ergodic processfrom a single sample-path. IEEE Transactions on Information Theory.

However, their procedure is hardly feasible in practice, andthe convergence β̂(s) −−−→ β(s) can be arbitrarily slow...
n→∞Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Reminder
In this talk, (X1 , X2 , X3 . . . ) is an ergodic Markov chain withtransition kernel P and invariant probability π.
Theorem (Davydov, 1973)
Assume the chain has initial distribution µ.
Xβ(s) = supµP t (x)∥δx P s − µP t+s ∥TV ,tx∈Xφ(s) = sup sup ∥δx P s − µP t+s ∥TV .
tx∈XThus if the chain is stationary (µ = π),Xβ(s) =π(x)∥δx P s − π∥TV = d ♯ (s),xφ(s) = sup ∥δx P s − π∥TV = d(s).
xPierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Corollary
When the chain is stationary,♯(ξ) = min{t : β(t) ≤ ξ}.
tmix
Corollary
Assume β(s) ≤ β1 /s b . Thenlm1♯(ξ) ≤ (β1 /ξ) b .
tmix
For any ε, δ > 0, we have!
n1X
Pf (Xi ) > ε ≤ δn i=1as soon asn≥C

84log2εδ

Pierre Alquier, ESSEC Business School b+1b  1b

♯
(δ)
2tmix

.

Markov Chains & Average Mixing Time♯Estimation of β(t) and tmix(ξ) for stationary, erdogic Markovchains from (X1 , . . . , Xn ).

β(s) =Xπ(x)∥δx P s − π∥TVx1Xπ(x)|P s (x, y ) − π(y )|=2 x,ycs (x, y ).
Obvious empirical estimates for π̂(x) and P
Leads to an estimator β̂(s) of β(s) (see the paper for theexact formula).

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Theorem
For any p ≥ 1,sE|β̂(s) − β(s)| ≤ 4
Bp(s) =∞
X

1(s) (s)sBp Ip, wheren−s −1β(st) p and Ip(s) =X

1[π(x)P s (x, y )]1− p .

x,y ∈X

t=0(s)The term Bp is bounded explicitly and finite under thestandard assumptions β(s) ≤ β0 exp(−β1 s b ) orβ(s) ≤ β1 /s b , with conditions
on p and b.
P p(s)
Compare Ip to y P(x, y ) that already appears whenbounding ∥Pb − P∥∞ :Wolfer, G. (2024). Empirical and Instance-Dependent Estimation of Markov Chain and Mixing
Time. Scandinavian Journal of Statistics.
Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time(s)Study of Ip =1− p1s.
x,y ∈X [π(x)P (x, y )]P

Case s = 0 :Ip(0) =X

1[π(x)]1− p .

x∈Xs

When s → ∞, P (x, y ) → π(y ). Thus, at least when X
is finite, we expect :XX1
1[π(x)π(y )]1− p ≤Ip(s) −−−→[π(x)]2(1− p ) .
s→∞x,y ∈X

Pierre Alquier, ESSEC Business Schoolx∈X

Markov Chains & Average Mixing Time

Theorem
Assume :(s)X is finite, then Ip ≤ [card(X )]2/p .
the chain is V -geometrically ergodic, then, under suitable
moment conditions on 1/V and π, thensup Ip(s) < +∞.
s∈N(s)

various weak conditions : Ip sub-linear in s.

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time♯Estimation of β(t) and tmix(ξ) for stationary, uniformlyerdogic Markov chains from (X1 , . . . , Xn ).

Theorem
For any p ≥ 1,v
uu s + tmix p Ip(s)tlog(2)E|β̂(s) − β(s)| ≤ 8.
n−1
In this case, we can say more...

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Theorem(s)Let p > 1 and assume sups Ip = Ip < +∞. Putβ̃(s) = β̂(s)1{s≤S} for some S = S(n, ε, δ, p, Ip ). Then, assoon astmix p log 1εtmix p log 1εmax Ip , logn≳
ε2ε2
we have, with probability 1 − δ,sup |β̃(s) − β(s)| ≤ ε.
s♯
Put tˆmix(ξ) = min{s : β̃(s) ≤ ξ}. Then, for n (explicitly) large
enough,hi♯♯♯tˆmix(ξ) ∈ tmix
(ξ(1 + ε)), tmix
(ξ(1 − ε)) .
Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time

Thank you !

Pierre Alquier, ESSEC Business School

Markov Chains & Average Mixing Time