An entropic proof of cutoff on Ramanujan graphs

An entropic proof of cutoff on Ramanujan graphs

Narutaka Ozawa ( )

RIMS, Kyoto University

Wales MPPM Seminar 2020 October 20

Abstract: I will talk about a simple functional analysis proof of E. Lebetzky and Y. Peres’s theorem (2016) that the simple random walk on a Ramanujan graph exhibits cutoff phenomenon.

Based on my preprintarXiv:2009.00837.

Random walks 1/8

G a finited-regular conn. non-bipartite graph X^t: (Ω,P) → G simple random walk (SRW) onG

starting atX⁰ =x0∈G P[X^t =x] =∑

yP(x,y)P[X^t−1 =y] P(x,y) = 1/d if x∼y, = 0 otherwise µ^t(x) =P[X^t=x] the distribution of X^t µ^t →π the uniform distribution on G

Example (of the kind I’m most interested in)

Γ =SL(3,Z) res. finite grp with a sym. gen. subset S ={I ±Ei,j :i ̸=j}

G_n=SL(3,Z/nZ); x ∼xs for x∈G_nand s ∈S.

X^t =s₁· · ·s_t with s_i indep. uniformly distributed on S; µ^t= (µ_S)^∗t {Gn}n is an expanderfamily of |S|-regular transitivegraphs, |Gn| → ∞ Γ↠G_n is injective on the ball of radiusclogn (injectivity radius)

When do the random walkers X^t notice they live in a finite world?

Expander graphs 2/8

Throughout: G a finited-regular conn. non-bipartite graph, d fixed 1 is a simple eigenvalue ofP with the eigenvector 111.

ρ_G :=∥P|_{111}^⊥∩ℓ2G∥<1 thereduced spectral radius We say a family {G}of graphs is an expanderfamily if it has uniform spectral gap: sup_Gρ_G <1.

Expander property (Dodziuk ’84 and Alon–Milman ’85) For every A⊂G, |∂A| ≥(1−ρG)|A|(1− ^|A|_|G|).

⇝ If 1% of the population are infected by Disease X and they spread it, 99% will be infected shortly.

Randomd-regular graphs are expanders (Barzdin–Kolmogorov ’67).

Finite quotients of a property (T) group are expanders (Margulis ’74).

Finite quotients of an amenable group are never expanders.

A sample theorem on expanders (by Gillman ’98)

X^t SRW on G with the initial distributionX⁰ ∼π (NB!NOTX⁰ =x0).

Then for any f ∈ℓ_∞G with m= _|G¹_|∑

xf(x) and∥f∥_∞≤1, one has P[|_T¹ ∑_T

t=1f(X^t)−m|> ε]<2 exp(−¹₆₄^−ρε²T).

Cutoff phenomena 3/8

When do the random walkers X^t notice they live in a finite world?

dTV(η, ζ) = max{|η(A)−ζ(A)|:A⊂G}= ¹₂∥η−ζ∥1 ∈[0,1]

T_G^mix(α) := min{t :d_TV(µ^t, π)< α} total variation mixing time Do the random walkersX^t notice it simultaneously?

We say a family {G}of graphs exhibits cutoff(Aldous–Diaconis ’86) if

∀α, α^′ ∈(0,1) lim

|G|→∞

Tmix

G (α) Tmix

G (α^′) = 1.

Conjecture (Peres): Transitiveexpander graphs should exhibit cutoff.

Cutoff on Ramanujan graphs 4/8

Theorem (Lubetzky–Peres GAFA ’16)

Any family of asymptotically Ramanujan graphs exhibits cutoff.

Alternative proofs by Hermon ’17 and by Bordenave–Lacoin ’18.

Q. How good can expanders be?

A. TheAlon–Boppana bound for any graphs: lim inf

|G|→∞ρ_G ≥ ^2√d_d⁻¹ =:ρ_d. ρ_d is thespectral radius of the SRW on thed-regular tree (Kesten ’59).

We say a family {G}is asymptotically Ramanujanif lim

|G|→∞ρ_G =ρ_d. First examples were discovered by Lubotzky, Phillips, and Sarnak ’88.

Randomd-regular graphs are asymptotically Ramanujan (Friedman ’08).

Q. How fast can random walks mix?

A. Entropic bound: ∀α lim inf

|G|→∞

Tmix

G (α)

log|G| ≥ _h¹_d with h_d = ^d−_d²log(d −1).

hd is the asymptotic entropyof the SRW on thed-regular tree.

Cutoff at the entropic time 5/8

Q. How good can expanders be?

A. TheAlon–Boppana bound for any family: lim inf

|G|→∞ρG ≥ ^2√_d^d−1 =:ρd. ρ_d is the spectral radius of the SRW on thed-regular tree (Kesten ’59).

Q. How fast can random walks mix?

A. Entropic bound: ∀α lim inf

|G|→∞

Tmix

G (α)

log|G| ≥ _h¹_d with h_d = ^d−_d²log(d −1).

hd is the asymptotic entropy of the SRW on thed-regular tree.

∵ µ^t is concentrated on the ball of radius≈ ^d−_d²twhich has cardinality at mostd(d−1)^d−d2t−1which is proportional to|G|att =T_G^mix(α).

Theorem (Lubetzky–Peres GAFA ’16)

Asymptotically Ramanujan graphs satisfy ∀α lim

|G|→∞

Tmix

G (α) log|G| = _h¹

d.

Entropic interpretation of cutoff 6/8

Shannon entropy: H(ν) :=−∑

xν(x) logν(x) Entropy growth: H(t) :=H(µ^t) (↗log|G|if|G|<∞) Asymptotic entropy: h:= lim_t ¹_tH(t) (= 0 if |G|<∞) SRW on the d-regular tree: h=h_d = ^d−_d²log(d −1)

Shannon–McMillan–Breiman theorem (Derriennic, Kaimanovich–Vershik):

1

t |−logµ^t(X^t)−H(t)| →0 a.s.

Theorem (Entropic characterization of cutoff)

An expander family {G} exhibits cutoff iff ∀δ >0∀ε >0, one has H(T_G^mix(1−ε))>(1−δ) log|G| for G large enough.

∵∀ν ∀t≤T_G^mix(ε) H(Pν)−H(ν)≥ ¹₄(1−ρ_G)d_TV(ν, π)² >c Corollary (Quantitative SMB implies cutoff)

Suppose∀δ >0 ∀ε >0 ∃T₀ s.t. ∀G ∀t ≥T₀

µ^t(Nδlog|G|({x ∈G :−logµ^t(x)<H(t) +δt}))>1−ε.

Then {G} exhibits cutoff.

One page proof of the Lubetzky–Peres theorem 7/8

By Theorem and the entropic bound forT_G^mix, it suffices to show H(t)−H(t−1)≈h_d for t ≤T_G^mix(1−ε).

H(t) =−∑

xµ^t(x) log(µ^t(x)) =−E[ logµ^t(X^t) ] H(t)−H(t−1) =−E[ logf_t],f_t :=µ^t(X^t)/µ^t−1(X^t−1)

⟨P(µ^t−1)^1/2,(µ^t)^1/2⟩=∑

x,yP(y,x)µ^t−1(x)

( µ^t(y) µ^t−1(x)

)1/2

=E[f_t^1/2].

Hence E[f_t^1/2]≤ ∥P(µ^t−1)^1/2∥2≤ρ_G +δ(ε) fort ≤T_G^mix(1−ε).

X˜^t SRW on thed-regular tree that coversX^t: ft ≈E[ ˜ft |X^t−1,X^t] By concavity of the square root, E[ ˜f_t^1/2]≤E[f_t^1/2]≤ρd+δ(G, ε).

f˜t ≈ {

d−1 with prob 1/d (when the step ˜Xt is toward the origin) 1/(d −1) with prob (d−1)/d

−E[ log ˜f_t]≈ −_d¹ log(d −1) + ^d−_d¹log(d −1) = ^d−_d²log(d−1) =h_d E[ ˜f_t^1/2]≈ _d¹√

d −1 +^d−_d¹√¹ d−1 = ²

√d−1 d =ρ_d

⇝ E[f_t^1/2]≈E[ ˜f_t^1/2] ⇝ f_t≈˜f_t ⇝ −E[ logf_t]≈h_d.

Speculation 8/8

Kaimanovich and Vershik’s proof of the Shannon–McMillan–Breiman theorem for the SRW on a (infinite) transitive graph:

logµ^t(X^t) = log P^t(X^t,X⁰)

P^t−1(X^t,X¹) +· · ·+ log P^t−k(X^t,X^k)

P^t−k−1(X^t,X^k+1) +· · ·

= loggt +· · ·+ logS^k(g_t−k) +· · ·, where

gt:= P^t(X^t,X⁰)

P^t−1(X^t,X¹) = 1/d P[X¹|X^t] and S is the time (Bernoulli) shift operator on (Ω,P) =∏

N({1, . . . ,d}, µ_d).

By the MCT, gt →g_∞ and

∀ε >0 ∃m s.t.g_∞≈ε E[g_∞|X₁, . . . ,X_m].

Hence the CLT implies−¹_tlogµ^t(X^t)→ha.s.

(Naive) Conjecture: For any transitive expander graphG, one has gt ≈E[gt |X1, . . . ,Xm] withm=o(log|G|).