CS294 Markov Chain Monte Carlo: Foundations & Applications Fall 2009Lecture 20: November 12Lecturer: Pro f. Alistair Sinclair Scribes: S. Negahban and D. OmidiranDisclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications.They may be distributed outside this class only with the permission of the Instructor.20.1 Glauber Dynamics for the 2-d Ising modelRecall the fundamental result quoted last time (see, e.g., [M98]):Theorem 20.1 The mixing time of the Glauber dynamics for the Ising model on a√n ×√n box in the2-dimensional square lattice is:O(n log n) if β < βc;eΩ(√n)if β > βc,where βcis the critical (inverse) temperature, βc=12ln (1 +√2).Last time we showed that the mixing time is eΩ(√n)for sufficiently large (but finite) β (though not all theway down to βc). Now we will show that the mixing time is O(n log n) for sufficiently small (but finite) β(again, not all the way up to βc). Getting both of these results to go all the way to βcis rather challengingand beyond the scope of this course.We also mention the following interesting conjecture:Conjecture: For the Ising model with the + (or −) boundary condition, the mixing time is poly(n) for allβ > 0. [Intuition: The obstacle to rapid mixing for β > βcis the bottleneck between the plus-phase and theminus-phase; but one of the phases disappears with such a boundary condition.]We now turn to the result claimed above, that the mixing time is O(n log n) for sufficiently small β.Let d(X, Y ) denote the number of disagreements between the configurations X, Y . We use path coupling,meaning that we need consider only pairs X, Y that have one disagreement.Consider Xt, Ytwith disagreement only at i0. Define the coupling in which Xtand Ytalways pick the samesite i and update it “optimally” (i.e., so as to maximize the probability of agreement).• Good moves: i = i0→ ∆d = −1 with probability 1.• Bad moves: i ∼ i0→ ∆d = +1 with probability at mostexp (2 β)−exp (−2 β)2+exp (2 β)−exp (−2 β), where i ∼ i0means thati is a neighbor of i0.To see this probability of a bad move, let α = α+− α−where α+denotes the number of + neighbors of iexcluding i0, and α−denotes the number of − neighbors excluding i0.20-120-2 Lecture 20: November 12Figure 20.1: Here, Xt, Ytdiffer only at node i0and are equal everywhere else. Node i is an arbitrary neighborof i0. In this example, α+= 2 and α−= 1.Letting Pr(Xt(i) = +) denote the probability that node i is set to + conditioned on its neighbors, then theprobability of creating an additional disagreement is |Pr(Xt(i) = +) − Pr(Yt(i) = +)|. A simple calculationshows that|Pr(Xt(i) = +) −Pr(Yt(i) = +)| =exp(2β) − exp(−2β)exp(2βα) + exp(−2β) + exp(2β) + exp(−2βα),which is maximized by letting α = 0. This gives the expression claimed above.Since all other moves leave d(Xt, Yt) unchanged, the expected change in distance in one move (bearing inmind that each no de i0has four neighbors), is at mostE[∆d] ≤1nh−1 + 4exp (2 β) − exp (−2 β)2 + exp (2 β) − exp (−2 β)i.Therefore, by our usual path coupling analysis, since the maximum distance is at most n, we will getO(n log n) mixing time if4exp (2 β) − exp (−2 β)2 + exp (2 β) − exp (−2 β)< 1.Setting z = exp(2 β) this becomes 4z − 4z−1< 2 + z + z−1. Multiplying out by z and factoring yields(3z − 5)(z + 1) < 0, so that we have O(n log n) mixing time for β <12ln(5/3). (Note that this is rathersmaller than the critical value βc=12ln (1 +√2).)20.2 Spatial and Temporal MixingIn this section we develop a relationship between “Spatial Mixing” and “Temporal Mixing.” That is, roughlyspeaking, we will prove that“Spatial Mixing” (decay of correlations) ⇐⇒ “Temporal Mixing” (fast mixing time)For simplicity we will focus on the 2-d Ising model in a√n ×√n box, but our results actually hold formuch more general spin systems on more general graphs. We will demonstrate each of the above twoimplications separately, beginning with the ⇐ direction. Let π+, π−denote the Gibbs measures (stationarydistributions) for the all-plus and all-minus boundary conditions, respectively. Let π+(σ0= +) denote theprobability under π+that the origin has spin +.Lecture 20: November 12 20-3Theorem 20.2 Suppose, τmix= O(n log n) for all boundary conditions. Then|π+[σ0= +] − π−[σ0= +]| → 0 as n → ∞.Exercise: With a bit more care in the argument, one can show exponential decay of correlations, i.e.,|π+[σ0= +] − π−[σ0= +]| ≤ exp (−c√n).(a) (b)Figure 20.2: (a) Markov chain (Xt) with boundary conditions set to all plus. (b) Markov chain (Yt) withboundary conditions set to all minus. The initial configurations X0, Y0are identical except on the boundary.The stationary distributions of (Xt), (Yt) are π+, π−respective ly.Proof: Set the initial condition X0= Y0(except on the boundary). Couple (Xt) and (Yt) such that:• They choose the same site i to be updated at all times t.• If the neighborhoods of the i are equal, then they both perform the same update, otherwise they updateindependently conditional on their neighbors.We then haveπ+[σ0= +] − π−[σ0= +]≤π+[σ0= +] − Xt[σ0= +]| {z }a+Xt[σ0= +] − Yt[σ0= +]| {z }b+Yt[σ0= +] − π−[σ0= +]| {z }cChoose t = Cn log2n > τmixlog n. Then, a ≤1n→ 0 and c ≤1n→ 0, by standard properties of the mixingtime. To analyze the remaining term b, note thatb ≤ Pr [∃ disagreement at 0 within t steps ] = Pr[∃ path of disagreement from boundary to 0].Here, a “path of disagreement” means a contiguous sequence of sites, starting at the boundary and leadingto the origin 0, that are chosen to be updated in sequence. Note that only if this happ ens is it possible forthe spins at the origin in Xt, Ytto differ, since they start out identical except on the boundary.Now, we may bound the latter term byPr[∃ path of disagreem ent from boundary to 0] ≤Xk≥12√n(4√n 4k)tk1nk,where (4√n 4k) is the numbe r of paths,tkcounts the numb e r of ways of choosing the sequence of updatetimes along the path, and (1n)kis the probability that this sequence of updates is actually chosen. The above20-4 Lecture 20: November 12quantity is then bounded by4√nXk≥12√n4etknk≤ 4√n|{z}“noise”Xk≥12√n4ec log2nkk→ 0 as n → ∞,We turn
View Full Document
Unlocking...