DOC PREVIEW
IPAM09talk

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A Proof of Aldous’ Spectral Gap ConjectureThomas M. Liggett, UCLAStirring ProcessesGiven a graph G = (V , E ), associate with each edge e ∈ E aPoisson process Πewith rate ce≥ 0.Labels are put on the vertices v ∈ V . At the event times of Πe,interchange the contents of the two vertices joined by e.Depending on the nature of the labels, one can define variouscontinuous time Markov chains:One particle MC Symmetric exclusion MC on permutationsLet Q be the rate matrix for a symmetric, irreducible n-stateMarkov chain, i.e., q(x, y ) = q(y , x) is the exponential rate atwhich the chain goes from state x to state y:pt(x, y) = q(x, y )t + o(t), t ↓ 0 for x 6= y.Then −Q has eigenvalues0 = λ0< λ1≤ λ2≤ ··· ≤ λn−1.The smallest positive eigenvalue λ1determines the rate ofconvergence to equilibrium:pt(x, y) =1n+ a(x, y )e−λ1t+ o(e−λ1t), t ↑ ∞.It is the largest value of λ for which12Xx,yq(x, y )[g(y ) − g(x)]2≥ λXxg(x)2,Xxg(x) = 0.Consider the stirring process on the complete graph G with nvertices. The one particle Markov chain has q(x, y ) = cxy. TheMarkov chain on permutations has q(π, πxy) = cxy, where πxyisthe permutation obtained from π by applying the transpositionthat interchanges x and y.Let0 = λ0< λ1≤ λ2≤ ··· ≤ λn−1.be the eigenvalues for the one particle Markov chain, and0 = λ∗0< λ∗1≤ λ∗2≤ ··· ≤ λ∗n!−1.be the eigenvalues for the Markov chain on permutations.Note: Each λi= some λ∗j, so λ∗1≤ λ1.In fact, any sum of the formλi1+ ··· + λikis an eigenvalue of the permutation chain. There are ∼ 4n−1/√πneigenvalues of this type, and all are ≥ λ1. How about the others?Aldous’ Conjecture (1992): λ∗1= λ1.Why guess this?1. True for ce≡ 1 on complete graph – Diaconis and Shahshahani(1981).2. True for ce≡ 1 on star graphs – Flatto, Odlyzko and Wales(1985).3. True for general ceon trees – Handjani and Jungreis (1996).4. True for ce≡ 1 on complete multipartite graphs – Cesi (2009).5. Other related results by Koma and Nachtergele (1997), Morris(2008), Starr and Conomos (2008), and Dieker (2009).Theorem.On a general finite graph with arbitrary rates,λ∗1= λ1.(Joint with P. Caputo (Rome) and T. Richthammer (UCLA).)Why should you care?1. It is MUCH easier to compute eigenvalues for an n × n matrixthan for an n! × n! matrix.2. “Intermediate” chains, such as symmetric exclusion have thesame smallest positive eigenvalue.z u y v xThe proof is by induction on the number of vertices:Construct Gxby removing vertex x and edges leading to it. Therates for the remaining edges are increased:New c{y,z}= c{y,z}+c{x,y}c{x,z}cx; cx=Xy6=xc{x,y}.Note:(a) If x is connected to only two vertices y, z, this corresponds toan electrical network series reduction from y ↔ x ↔ z to y ↔ z.(b) If x is connected to three vertices y, z, w , it corresponds to anelectrical network star-triangle reduction from the star with centerx to the triangle y, z, w .(c) The addition at the end corresponds to an electrical networkparallel reduction.Basic steps in the induction argument:1. λ1(Gx) ≥ λ1(G ). This is a consequence of the variationalcharacterization: Given a function on Gx, extend it to G by makingit harmonic at x.2. Let H = {f : E [f | position of ith particle] = 0 for each i},and µ∗1be the analogue of λ∗1for functions in H. Thenλ∗1= min{λ1, µ∗1}.Idea: eigenfunctions /∈ H generate eigenfunctions of the oneparticle chain.3. If the octopus inequality holds, thenµ∗1(G ) ≥ maxxλ∗1(Gx).This again uses the variational characterization.4. µ∗1(G ) ≥ maxxλ∗1(Gx) = maxxλ1(Gx) ≥ λ1(G ). Now use #2.The octopus inequality: For fixed x,Xy6=xcxyXπ[f (πxy)−f (π)]2≥Xy,z6=xc{x,y}c{x,z}cxXπ[f (πyz)−f (π)]2.This is equivalent to the positive semi-definiteness of a certainmatrix C . If n = 3, for example,C =c 0 0 −c1d −c2d c1c20 c 0 −c2d c1c2−c1d0 0 c c1c2−c1d −c2d−c1d −c2d c1c2c 0 0−c2d c1c2−c1d 0 c 0c1c2−c1d −c2d 0 0 c,where c = c21+ c1c2+ c22and d = c1+ c2. The eigenvalues of Cin this case are 0 and 2c, each with multiplicity 3.Ideas:1. Try to write C as the covariance matrix of Z = (X , Y ), whereX and Y are n!/2 random vectors. Choose X to have iidcomponents with variance c. How about Y ?2. Try Y = DX , where D is chosen so that cov (X , Y ) is right. Dis unique. Hope that the components of Y are uncorrelated andhave variance c. This works for n = 3, but fails for n = 4.However: If n = 4, it turns out that cov(Y ) ≤ cI , which is allthat is needed. Could this be true in general?To check this, write cI − cov(Y ) as a linear combination ofmatrices AJ; the coefficients (both positive and negative) involvethe rates, but the AJdo not. Here J ⊂ V with |J| = 4.The π, π0entry of AJis2 if π = π0or π−1π0= a product of 2 disjoint 2-cycles from J;−1 if π−1π is a 3-cycle from J;0 otherwise.Need to know that the AJ’s and certain linear combinations BKofthe AJ’s are positive semi-definite: For |K | = 5 and x ∈ K ,BK=XJ:x∈J⊂KAJ− AK \{x}.Example: For n = 4,A = 3E40 00 E400 0 E4− E12,where Ekis the k × k matrix with all entries =1. This A haseigenvalues 0 and 12 with multiplicities 10 and 2 respectively.Example: For n = 5, B is a 60 ×60 matrix with small integerentries.It turns out that B2= 24B, so its only eigenvalues are 0 and 24.In fact, the multiplicities are 45 and 15 respectively.But what about larger n? It turns out that the correspondingmatrices have a block form:A 0 0 ···0 A 0 ···0 0 A ···............B 0 0 ···0 B 0 ···0 0 B ···............Here A and B are the matrices from the n = 4 and n = 5 cases.The blocks correspond to:the n!/4! left cosets of the even permutations on 4 sites in theeven permutations on n sites for Aandthe n!/5! left cosets of the even permutations on 5 sites in theeven permutations on n sites for B.Why is n = 5 the main case?Each transposition affects two vertices, and we are looking at amatrix of the form DtD, so entries in the product involve at mostfour vertices. But then there is the special vertex x that wasremoved in the induction argument, for a total of 5.Not all Markov chains based on stirring have the same smallestpositive eigenvalue.Example: Perfect matchings – see e.g.,


IPAM09talk

Download IPAM09talk
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view IPAM09talk and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view IPAM09talk 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?