Chapter 3 Markov Chain Monte Carlo: Metropolis and

Chapter 3 Markov Chain Monte Carlo: Metropolis and

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

Recently Viewed Presentations

  • Designing a DSL in KOTLIN - static.rainfocus.com

    Designing a DSL in KOTLIN - static.rainfocus.com

    A DSL? "A Domain-Specific Language is a computer language specialized to a particular application domain.This is in contrast to a General-Purpose Language, which is broadly applicable across domains."-- Wikipedia. @nicolas_frankel #kotlin #dsl #kaadin
  • The Problem of the Deadly Embrace

    The Problem of the Deadly Embrace

    An example of priority rule. Previous Section: ... "Banker" software which manages the use of a magnetic tape deck, "loaning a florin" could mean the permission to use one of the tape decks. The "banker" first calculates what happens if...
  • A S E I C N E O

    A S E I C N E O

    Zygotic Mortality. Mating and fertilization are possible, but zygote doesn't develop properly. ... Polyploidy is the result of the failure to nuclei to separate during meiosis. Formation of Polyploidy. In plants, polyploidy is much more common than in animals.
  • Compass

    Compass

    First we crawl news articles and run topic modeling on it. We look for the class that can be marked as politics .. We call these keywords as seeds. On a different segment we create a word2vec model from general...
  • Canadas National Laboratory for Particle and Nuclear Physics

    Canadas National Laboratory for Particle and Nuclear Physics

    Canadians are involved in nuclear physics programs (theory and experiment) in Europe and the Canadian NSERC LRplan support opportunities for participation and leadership in these efforts. The TRIUMF 5 year plan process is starting and community consultation is on-going (ARIEL...
  • Diapositiva 1 - doc.santuariosancalogero.org

    Diapositiva 1 - doc.santuariosancalogero.org

    Sapat nang isipin ang ilang katangian ng pag-ibig tulad ng pagpaparaya, pang-unawa, pagtanggap sa isa't isa, pagpapasensya, bukas-loob na paglilingkod, habag sa anumang pagkukulang ng kapwa, pagbabahaginan ng mga materyal na bagay, atbp... Makikita natin ang maraming pagkakataong maisabuhay ito.
  • Meditation - Dublin Diocese

    Meditation - Dublin Diocese

    Meditation is now a mainstream practice worldwide millions people practicing on a regular basis. Meditation is the absence of thinking and it is the process of concentrating the mind. We meditate every day without knowing!!!!!
  • Running Your Services On Docker An experience report

    Running Your Services On Docker An experience report

    We use Consul, Nginx and Consul Template to implement a "Service Proxy" for inter and intra-host container communication. We built a utility container called "Service Proxy" that uses Consul's service directory to locate a container's ip address and port