• No results found

MLSI: Theory, Examples and Consequences Lecture 3

N/A
N/A
Protected

Academic year: 2024

Share "MLSI: Theory, Examples and Consequences Lecture 3"

Copied!
50
0
0

Loading.... (view fulltext now)

Full text

(1)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

MLSI: Theory, Examples and Consequences

Lecture 3

Prasad Tetali

Georgia Institute of Technology and Indian Institute of Science

ICTS, Bengaluru, August 5-17, 2019

(2)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

1 Discrete curvature and Conjectures

2 SLC and Matroid Bases Exchange

(3)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bochner-Bakry- ´ Emery Criterion

The following 2nd derivative criterion is also useful, and inspires a notion ofdiscrete curvature, mimicking the Ricci curvature.

Proposition (Bochner’46, Lichn´erowicz’58) inff

E(f,f)

Varπf =:λ= inf

f

E(−Lf,f)

E(f,f) =:µP =:µ . Proof. λµ: Use Cauchy-Schwartz. Indeed, w/Eπf = 0,

E(f,f) =E(f(−Lf))

Varπf1/2

E(−Lf)21/2

1

λ(E(f,f))1/2

E(−Lf)21/2

= 1

λ(E(f,f))1/2

E(−Lf,f)1/2

.

(4)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bochner-Bakry- ´ Emery Criterion (contd.)

Other direction,λµ: 2nd derivative and integration. Starting with d

dtVar(Htf) =−2E(Htf,Htf) and d

dtE(Htf,Htf) =−2E(Htf,−LHtf). Observe that ast→ ∞, Htf Eπf, and soE(Htf,Htf)0. Hence,

E(f,f) = Z

0

d

dtE(Htf,Htf)dt= 2 Z

0

E(Htf,−L(Htf))dt

= 2

Z

0

E(−L(Htf),Htf)dt P

Z

0

E(Htf,Htf)dt

= −µP

Z

0

d

dtVar(Htf)dt=µPVarf, implying thatλP =λPµP.

(5)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

MLSI and Bakry- ´ Emery Criterion

What about repeating the above for the entropy constant?

Proposition (Bakry- ´Emery’85) inf

f>0

E(f,logf)

Entπf =:αinf

f>0

u(f) E(f,logf), where u(f) =E(−Lf,logf) +E(f,(−Lf)/f).

Some relevant references include:

[Boudou, Caputo, Dai Pra, Posta, 2005]. “Spectral gap estimates for interacting particle systems via a Bochner type identity,” J. Funct.

Analysis.

[M. Erbar, J. Maas, P.T. 2015].“Discrete Curvature Bounds for

Bernoulli-Laplace and Random Transposition Models,” Annales Fac. Sci.

Toulouse.

(6)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bochner formula (iterated gradient Γ

2

criterion) :

application: discrete Buser ...

(7)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(DA)

Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V R, and∀x V,

∆Γ(f,f)(x)2Γ(f,∆f)(x)K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)f(x)). And givenf,g :V R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)f(y))(g(x)g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = 12P

y:(x,y)∈E(f(x)f(y))2=:|∇f(x)|2.

(8)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(DA) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V R, and∀x V,

∆Γ(f,f)(x)2Γ(f,∆f)(x)K Γ(f,f)(x),

where

∆f(x) = X

y:(x,y)∈E

(f(y)f(x)). And givenf,g :V R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)f(y))(g(x)g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = 12P

y:(x,y)∈E(f(x)f(y))2=:|∇f(x)|2.

(9)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(DA) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V R, and∀x V,

∆Γ(f,f)(x)2Γ(f,∆f)(x)K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)f(x)). And givenf,g :V R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)f(y))(g(x)g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = 12P

y:(x,y)∈E(f(x)f(y))2=:|∇f(x)|2.

(10)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(DA) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V R, and∀x V,

∆Γ(f,f)(x)2Γ(f,∆f)(x)K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)f(x)). And givenf,g :V R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)f(y))(g(x)g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = 12P

y:(x,y)∈E(f(x)f(y))2=:|∇f(x)|2.

(11)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f).

Basically, using the iterated gradient:

2(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

(12)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f).

Basically, using the iterated gradient:

2(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

(13)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f). Basically, using the iterated gradient:

2(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

(14)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus (contd.)

The iterated gamma can be written out:

2(f)(x) = ∆Γ(f)(x)2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)d(x)Γ(f)(x)X

v∼x

f(v) ∆f(v)∆f(x)

=X

v∼x

f(v)2

d(x) 2

X

v∼x

f2(v) + X

u∼v∼x

f2(u)4f(u)f(v) + 3f2(v) 2

=X

v∼x

f(v)2

X

v∼x

d(x) +d(v)

2 f2(v) +1 2

X

u∼v∼x

(f(u)2f(v)2

. (2.1) Ford-regular, further simplifies to:

2(f)(x) =dX

v∼x

f2(v) + X

v∼x

f(v)2

+X

v∼x

X

u∼v

f2(u)

2 2f(u)f(v) . (2.2)

(15)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus (contd.)

The iterated gamma can be written out:

2(f)(x) = ∆Γ(f)(x)2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)d(x)Γ(f)(x)X

v∼x

f(v) ∆f(v)∆f(x)

=X

v∼x

f(v)2

d(x) 2

X

v∼x

f2(v) + X

u∼v∼x

f2(u)4f(u)f(v) + 3f2(v) 2

=X

v∼x

f(v)2

X

v∼x

d(x) +d(v)

2 f2(v) +1 2

X

u∼v∼x

(f(u)2f(v)2

. (2.1)

Ford-regular, further simplifies to: 2(f)(x) =dX

v∼x

f2(v) + X

v∼x

f(v)2

+X

v∼x

X

u∼v

f2(u)

2 2f(u)f(v) . (2.2)

(16)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

2

Calculus (contd.)

The iterated gamma can be written out:

2(f)(x) = ∆Γ(f)(x)2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)d(x)Γ(f)(x)X

v∼x

f(v) ∆f(v)∆f(x)

=X

v∼x

f(v)2

d(x) 2

X

v∼x

f2(v) + X

u∼v∼x

f2(u)4f(u)f(v) + 3f2(v) 2

=X

v∼x

f(v)2

X

v∼x

d(x) +d(v)

2 f2(v) +1 2

X

u∼v∼x

(f(u)2f(v)2

. (2.1) Ford-regular, further simplifies to:

2(f)(x) =dX

v∼x

f2(v) + X

v∼x

f(v)2

+X

v∼x

X

u∼v

f2(u)

2 2f(u)f(v) . (2.2)

(17)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Cheeger is tight if curvature ≥ 0

h:=h(G) := minA⊂V|∂A|/|A|, the Cheeger const, ofG;λ >0: gap(G).

Theorem (A-M, L-S, J-S 80’s) h2

c1maxdeg(G) λc2h. Theorem (Klartag-Kozma-Ralli-T. ’14)

1. Bochner w/ parameter K implies: for any subset AV ,

|∂A| ≥ 1 2minn√

λ, λ

p2|K| o|A|

1 |A|

|V|

.

2. Bochner w/ parameter K 0impliesλK , and hence:

λ16h2.

(18)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

CD(K, ∞ ) with K ≥ 0 : Examples

1. Complete graph Kn: Curvature = 1 +n/2.

2. Discrete n-cube Qn: Curvature = 2.

3. Symmetric group S(n) with the transposition metric:

Curvature = 2

4. General Proposition. If T is the maximum number of triangles containing any edge, then K ≤2 +T/2.

5. Abelian necessary! OnSn, the (left) Cayley graph generated by (12),(12...n)±1, the Cheeger constant is c1n−2, while the spectral gap is c2n−3, with c1,c2>0, independent of n.

(19)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Cheeger, CD(K, ∞ ) with K ≥ 0

Qn. 1 Can we characterize the graphs or Markov kernels which satisfy non-negative curvature?

Qn. 2 Can we characterize the graphs for which the Cheeger inequality is tight?

Qn. 3 More examples? Non-crossing partition lattice NC(n)?

(20)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Ollivier-Villani

“ In positive curvature, balls are closer than their centers.”

Coarse Ricci: Take two small balls and compute the transportation distance between them. If it is smaller than the distance between the centers of the balls, then coarse Ricci ispositive.

W1x, µy) =: (1κ(x,y))d(x,y), Examples.

1. n-cube: µx uniform on the n+1 neighbors of x (including itself). For x,y, neighbors,κ(x,y) = 2/(n+ 1).

2. Snwith transpositions: Forσ, τ differing in a transposition, κ(x,y) = 1/ n2

.

(21)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

(Coarse) Ricci of Hypercube

Proposition (folklore)

The n-cube hascoarse Ricci=2/(n+ 1).

Proof sketch.

(i) Consider thelazyrandom walk on then-cube.

(ii) Use a simple (path) coupling argument to show that two copies of the chain started atneighboring verticesx,y ∈ {0,1}n can be “coupled”

with probability at least 2/(n+ 1) in one step.

(22)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

(Coarse) Ricci of Transposition Graph

Proposition

Snwith transpositions has coarse Ricci=1/ n2 .

Proof sketch.

Lower bound:

(i) Consider thelazyrandom transposition chain onSn.

(ii) Use a simple (path) coupling argument to show that two copies of the chain started atσ, τ Sn withd(σ, τ) = 1, can be coupled with probability at least 1/ n2

in one step.

Upper bound: Follows by showing that there is no better coupling – use (Kantorovich’s) dual formulation ofW1:

W1(ν, µ) = sup

f: 1−Lip

Eνf Eµf .

(23)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Peres-Tetali “Conjecture”!

Doescoarse Ricci at least κ >0 imply the MLSI constantα≥κ?

Something weaker is known: namely that aW1 transport-Entropy inequality follows, thanks to(Marton??, Eldan, Lehec, Lee’16)

(24)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

MLSI for Bases Exchange Walk

I am thankful to Heng Guo for letting me borrow some of his slides in this section.

(25)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Matroid

A matroidM= (E,I) consists of a finite ground setE and a collectionI of subsets ofE (independent sets) such that:

∅ ∈ I;

if S ∈ I,T ⊆S, then T ∈ I (downward closed);

if S,T ∈ I and |S|>|T|, then there exists an element i ∈S\T such thatT ∪ {i} ∈ I (augment axiom).

Maximum independent sets are thebases.

For any two bases, there is a sequence of exchanges of ground set elements that take one basis to the other.

Letn=|E|andr be the rank, namely the size of any basis.

(26)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bases-exchange walk

The following Markov chainPBX,π converges to a “homogeneous SLC”π:

1 remove an element uniformly at random from the current basis (call the resulting set S);

2 addi 6∈S with probability proportional to π(S∪ {i}).

The implementation of the second step may be non-trivial.

(27)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

MLSI for Matroid Basis Exchange

Theorem (Mary Cryan-Heng Guo-Giorgos Mousa) For any f : Ω→R≥0,

EPBX,π(f,logf)≥ 1

r ·Entπ(f), where r is the rank of the matroid.

(28)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Many open problems remain!

Sampling spanning trees ofG with no broken circuit- the same as evaluation TG(1,0) of the Tutte polynomial, leading coefficient |a1G(λ)]|of the chromatic polynomial (up to sign), number of maximumG-parking functions, sampling acyclic orientations with a unique sink...

Sampling all acyclic orientations of G Negative correlation for random forests ofG

(More generally) characterization of matroids with negative correlation for random bases.

(29)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Strongly log-concave polynomials

Log-concave polynomial

A polynomialp ∈R≥0[x1, . . . ,xn] is log-concave(atx) if the Hessian∇2logp(x) is negative semi-definite.

⇒ ∇2p(x) has at most one positive eigenvalue.

Strongly log-concave polynomial

A polynomialp ∈R≥0[x1, . . . ,xn] is strongly log-concaveif for any index setI ⊆[n],∂Ip is log-concave at 1.

Originally introduced byGurvits(2009), equivalent to:

Completely log-concave (Anari, Oveis Gharan, and Vinzant, 2018);

Lorentzian polynomials (Br¨and´en and Huh, 2019+).

(30)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Strongly log-concave distributions

A distributionπ: 2[n]→R≥0 is strongly log-concaveif so is its generating polynomial

gπ(x) = X

S⊆[n]

π(S)Y

i∈S

xi.

An important example of homogeneous strongly log-concave distributions is the uniform distribution over bases of a matroid (Anari, Oveis Gharan, and Vinzant 2018; Br¨and´en and Huh 2019+).

(31)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Alternative characterization for SLC

Br¨and´en and Huh(2019+): Anr-homogeneous multiaffine

polynomialp with non-negative coefficients isstrongly log-concave if and only if:

the support of p is the bases of some matroid;

after taking r−2 partial derivatives, the quadratic is real stableor 0.

Real stable: p(x)6= 0 if=(xi)>0 for alli.

Real stable polynomials (and strongly Rayleigh distributions) capture only “balanced” matroids, whereas SLC polynomials capture all matroids.

(32)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bases-exchange walk

The following Markov chainPBX,π converges to a homogeneous SLCπ:

1 remove an element uniformly at random from the current basis (call the resulting set S);

2 addi 6∈S with probability proportional to π(S∪ {i}).

The implementation of the second step may be non-trivial.

Recall the mixing time defn.

tmix(P, ε) := min

t

t | kPt(x0,·)−πkTV≤ε .

(33)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Theorem (Cryan-Guo-Mousa 2019)

For any r -homogeneous strongly log-concave distributionπ, tmix(PBX,π, ε)≤r

log log 1 πmin

+ log 1 2ε2

,

whereπmin= minx∈Ωπ(x).

Previously,Anari, Liu, Oveis Gharan, and Vinzant(2019):

tmix(PBX,π, ε)≤r

log 1 πmin

+ log1 ε

E.g. for the uniform distribution over bases of matroids (withn elements and rankr), the new bound is O(r(logr+ log logn)), whereas the previous bound isO(r2logn).

(34)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Levels of independent sets

The set of all independent sets of a matroidMisdownward closed.

LetM(k) be the set of independent sets of size k. Thus,M(r) is the set of all bases.

LetMi denote the matroid Mafter contractingi, which is another matroid itself.

(35)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Weights for independent sets

EquipMwith the following inductively defined weight function:

w(I) :=

(π(I)Zr if|I|=r, P

I0⊃I,|I0|=|I|+1w(I0) if|I|<r, for some normalization constantZr >0.

For example, we may choosew(B) = 1 for allB ∈ B andZr =|B|, which corresponds to the uniform distribution overB.

Letπk be the distribution such thatπk(I)∝w(I), and Zk be the corresponding normalizing constant.

(36)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Different views

Polynomial: ∂x∂p

i;settingxi = 0; (r−k)!∂x

Ip(1)

Matroid: contraction over i;deletion of i;w(I)

Distribution: conditioning on having i;conditioning on not having i; proportional toπk(I)

(37)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Random walk between levels

There are two natural random walks converging toπk. The “down-up” random walk Pk:

→ 1. remove an element of I ∈ M(k) uniformly at random to get I0 ∈ M(k−1);

2. move toJ such thatJ ∈ M(k),J ⊃I0 with probability w(Iw(J)0). The bases-exchange walkPBX,π=Pr.

The “up-down” walk Pk is defined similarly.

(38)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Random walk between levels

There are two natural random walks converging toπk. The “down-up” random walk Pk:

1. remove an element of I ∈ M(k) uniformly at random to get I0 ∈ M(k−1);

→ 2. move toJ such thatJ ∈ M(k),J ⊃I0 with probability w(Iw(J)0). The bases-exchange walkPBX,π=Pr.

The “up-down” walk Pk is defined similarly.

(39)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

LetAk be the matrix whose rows are indexed by M(k) and columns byM(k+ 1) such thatAk(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}I∈M(k), and Pk+1 := 1

k+ 1·ATk;

Pk := diag(wk)−1Akdiag(wk+1). We have

Pk+1=Pk+1 Pk; Pk =PkPk+1 .

(40)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

LetAk be the matrix whose rows are indexed by M(k) and columns byM(k+ 1) such thatAk(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}I∈M(k), and Pk+1 := 1

k+ 1·ATk;

Pk := diag(wk)−1Akdiag(wk+1).

We have

Pk+1=Pk+1 Pk; Pk =PkPk+1 .

(41)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

LetAk be the matrix whose rows are indexed by M(k) and columns byM(k+ 1) such thatAk(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}I∈M(k), and Pk+1 := 1

k+ 1·ATk;

Pk := diag(wk)−1Akdiag(wk+1).

We have

Pk+1=Pk+1 Pk; Pk =PkPk+1 .

(42)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

LetAk be the matrix whose rows are indexed by M(k) and columns byM(k+ 1) such thatAk(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}I∈M(k), and Pk+1 := 1

k+ 1·ATk;

Pk := diag(wk)−1Akdiag(wk+1).

We have

Pk+1=Pk+1 Pk; Pk =PkPk+1 .

(43)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Key lemma

Lemma

For any k≥2and f :M(k)→R≥0, Entπk(f)

k ≥ Entπk−1(Pk−1 f) k−1 .

ApplyingPk−1 to the left corresponds to the random walkPk. The lemma asserts that Pk contracts the relative entropy by at least (1−1/k):

Entπk−1(Pk−1 f)≤(1−1/k)Entπk(f).

(44)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Key lemma

Lemma

For any k≥2and f :M(k)→R≥0, Entπk(f)

k ≥ Entπk−1(Pk−1 f) k−1 .

ApplyingPk−1 to the left corresponds to the random walkPk. The lemma asserts that Pk contracts the relative entropy by at least (1−1/k):

Entπk−1(Pk−1 f)≤(1−1/k)Entπk(f).

(45)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Base case

For the base case, we want to show that

Entπ2(f)−2Entπ1(P1f)≥0.

Usingalogab ≥a−b for a,b>0, we can get Entπ2(f)−2Entπ1(P1f)≥1− 1

2Z2 ·hTWh, whereWij =w({i,j}) andh=P1f.

SinceW = (r−2)!Zr2gπ(1), it has at most one positive eigenvalue. The quadratic form is maximized ath =P1f =1, which helps prove the base case...

(46)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Base case

For the base case, we want to show that

Entπ2(f)−2Entπ1(P1f)≥0.

Usingalogab ≥a−b for a,b>0, we can get Entπ2(f)−2Entπ1(P1f)≥1− 1

2Z2 ·hTWh, whereWij =w({i,j}) andh=P1f.

SinceW = (r−2)!Zr2gπ(1), it has at most one positive eigenvalue. The quadratic form is maximized ath =P1f =1, which helps prove the base case...

(47)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Base case

For the base case, we want to show that

Entπ2(f)−2Entπ1(P1f)≥0.

Usingalogab ≥a−b for a,b>0, we can get Entπ2(f)−2Entπ1(P1f)≥1− 1

2Z2 ·hTWh, whereWij =w({i,j}) andh=P1f.

SinceW = (r−2)!Zr2gπ(1), it has at most one positive eigenvalue. The quadratic form is maximized ath=P1f =1, which helps prove the base case...

(48)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bound the mixing time directly

For a distributionτonM(k), the relative entropyD(τkπk) = Entπk(Dk−1τ) where Dk= diag(πk). Moreover, after one step ofPk, the distribution is

TPk)T= (Pk)Tτ. SincePkis reversible,Dk−1(Pk)T=PkDk−1. D (Pk)Tτkπk

= Entπk(Dk−1(Pk)Tτ)

= Entπk(PkD−1k τ)

= Entπk(PkPk−1 Dk−1τ)

Entπk−1(Pk−1 Dk−1τ) (Jensen’s inequality)

11 k

Entπk(Dk−1τ) (entropy contraction)

=

11 k

D kπk).

The mixing time bound follows from Pinsker’s inequality 2σk2TVD(τkσ).

(49)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Many open problems remain!

Sampling spanning trees ofG with no broken circuit- the same as evaluation TG(1,0) of the Tutte polynomial, leading coefficient |a1G(λ)]|of the chromatic polynomial (up to sign), number of maximumG-parking functions, sampling acyclic orientations with a unique sink...

Sampling all acyclic orientations of G Negative correlation for random forests ofG

(More generally) characterization of matroids with negative correlation for random bases.

(50)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Fin

Thank you!

References

Related documents