Chapter 3 Markov Chain Monte Carlo: Metropolis and Glauber Chains Yael Harel Contents Reminders from previous weeks Definitions Theorems Motivation Metropolis Chains What is it? Construction over symmetric matrices Example Construction over asymmetric matrices Example Glauber Dynamics What is it?

Examples Metropolis Chains VS Glauber Dynamics Summary Reminders from previous weeks Definitions finite state space (configurations) P transition matrix the probability to be in each on time t (row vector) Moving to state y at time t+1: Chain P is irreducible if: Stationary distribution: Detailed balance equations: Reversible chain satisfying the detailed balance equations Regular graph each vertex has the same degree Simple random walk on graph: if x~y (0 otherwise) Reminders from previous weeks

Theorems Irreducible chain there exists a unique stationary distribution satisfied detailed balance equations stationary P symmetric, uniform distribution reversible chain Motivation The problem in most of the book Given probability distribution Assume a Markov chain can be constructed s.t stationary. How large should t be in order that will be close enough to ? The problem in this chapter Given probability distribution Can we construct a Markov chain s.t is its stationary? Example q-coloring The goal given a graph random sample a proper q-coloring. e

asy ult c diffi Why do we want to do it? Size of can be estimated. Characteristics of colorings can be studied. Markov chain Monte Carlo Sampling from a given probability distribution Metropolis Chains Given: state space, symmetric matrix distribution The goal: modify to P s.t = * P The new chain construction In order that will be stationary, detailed balanced should be satisfied: ( x, y ) = ( y , x)

a ( y , x ) , a( x, y)1 We would like P(x,x)~0 Maximize Maximize Metropolis Chains Example uniform distribution over the global maximum Given: vertex set of regular graph, f function defined on The goal: find Hill climb The algorithm: move from x to neighbor y if f(y) > f(x) The problem: we can stuck in local maximum Building a metropolis chain For simplicity the algorithm (): a simple random walk. P(x,y) =

Metropolis Chains Given: state space, matrix distribution The goal: modify to P s.t = * P a ( y , x ) , a( x, y)1 The new chain construction In order that will be stationary, detailed balanced should be satisfied: We would like P(x,x)~0 Maximize Maximize a(x,y) Metropolis Chains Example uniform distribution for irregular graph Irregular graph. Each vertex is familiar only with its neighbors. matrix of simple random walk.

uniform distribution over |V|. The goal: modify to P s.t is its stationary distribution. a (x According to what we saw: , y )= 1 ( y ) (x ( ) y , x ) (x , y)

Although we dont know how all of the graph looks like, from each vertex, we can go to the next one! Glauber Dynamics (Gibbes sampler) Given: V vertex set of a graph S finite set SV functions from V to S (proper configurations) probability distribution The goal: construct P s.t = * P The new chain construction Let: Define: Move to other configuration: Select vV at random Move to y with probability P(x,y)= The detailed balance equations are satisfied:

=the same blob sta tion ary o fP Glauber Dynamics (Gibbes sampler) Example q-coloring Given: G = (V,E), S = {1,2,,q}, = uniform over proper configurations The goal: construct Markov chain on the set of proper q-coloring x proper configuration, vV jS is allowable if j{x(w) : w~v} Av(x) {jS : j is allowable} Moving from proper configuration x to other proper configuration: Select vV at random P(x,y)= Select jAv(x) at random

0 0 Av(x) = Av(y) 1 1 4 3 1 1 4 3 1 1 4 3 P(x,y) = P(y,x) 1 1

4 2 1 1 4 2 stationary Glauber Dynamics (Gibbes sampler) 1 1 5 2 1 1 1 5= 5 2 2

4 1 1 1 + =1 5 5 2 10 Example particle configuration Given: G = (V,E), S = {0,1}, = uniform over proper configurations x configuration: x(v)=1 v occupied x(v)=0 v vacant Proper configuration if Moving from proper configuration x to other proper configuration: Select vV at random v is vacant If s.t w is occupied stay in configuration x Else y(v) = 1 with probability If x(v)=1 y=x 1 1

5 2 1 1 5 2 P(x,y) = P(y,x) stationary 1 1 5 2 1 1 5 2 Metropolis Chains VS Glauber Dynamics Given: G = (V,E) S finite set

probability distribution over SV chain with the following rule: Select vV at random Select sS at random and update v Metropolis construction Glauber construction P(x,y)= stationary of P but Will the Glauber and the Metropolis chains be equal? similar? Metropolis Chains VS Glauber Dynamics Example q-coloring Metropolis Chain original matrix: (x,y) = maybe not a proper configuration! P s.t uniform over proper q-coloring configurations is stationary:

If y proper configuration (: P(x,y) = Else: P(x,y) = 0 Galuber Chain x, y proper configurations: If x, y are different in 1vertex: P(x,y) = Else: P(x,y) = 0 The chains are different! vV was selected the probability of remaining at the configuration: In Metropolis: Choose a non allowable color/the color of v In Glauber: Choose the color of v Metropolis Chains VS Glauber Dynamics Example particle configuration Metropolis Chain original matrix: (x,y) = maybe not a proper configuration! P s.t uniform over proper particles configurations is stationary: If y proper configuration (: P(x,y) = Else: P(x,y) = 0

Galuber Chain x, y proper configurations: If x, y are different in 1vertex: P(x,y) = The chains are equal! Else: P(x,y) = 0 Summary Chain construction with a given stationary distribution Metropolis given a transition matrix. Glauber without any transition matrix. Can be equal or similar Example q-coloring NP-complete problem #proper configurations unknown.proper configurations unknown. Construct a chain with the uniform stationary distribution. Simulation: After T iterations For i=1 to N same probability Run the chain T iterations for each configuration

Save the result Learn how does the configurations distribute In the next weeks: How to find T? Thank you