<< Chapter < Page Chapter >> Page >

A heat bath algorithm is simply a procedure of updating the vertices i one at a time based on the conditional probabilities given by π . All vertices must be chosen infinitely often so that there is no bias towards any assignments, σ . The following equation provided by Propp and Wilson [link] indicates how i will be updated:

f t ( σ , u t ) = σ i u t < π ( σ i ) π ( σ i ) + π ( σ i ) σ i u t π ( σ i ) π ( σ i ) + π ( σ i )

where t is time, and u t is a random real number in [ 0 , 1 ] chosen according to the uniform distribution. All u t 's are chosen independently of each other [link] .

We may order sets of configurations by the following definition: σ τ iff σ ( i ) τ ( i ) i V , where > . Two configurations are incomparable if one is not greater than the other. We also say that a probability distribution, π , is monotonic if and only if

π ( σ i ) π ( σ i ) π ( τ i ) π ( τ i ) for all σ τ

or equivalently, π ( σ i ) π ( τ i ) π ( σ i ) π ( τ i ). If the probability distribution is monotonic (or “attractive"), then the partial ordering of σ and τ is preserved after the heat bath algorithm is applied. To see why this is true, note that if the inequality in formula [link] holds, then π ( σ ) must be greater than or equal to π ( τ ). The proof is as follows:

π ( σ i ) π ( τ i ) π ( σ i ) π ( τ i )
π ( σ i ) π ( τ i ) + π ( σ i ) π ( τ i ) π ( σ i ) π ( τ i ) + π ( σ i ) π ( τ i )
π ( σ i ) ( π ( τ i ) + π ( τ i ) ) π ( τ i ) ( π ( τ i ) + π ( τ i ) )
π ( σ i ) π ( τ i ) .

If we choose the same u t for both σ and τ , it is impossible for σ i and τ i to occur simultaneously. Therefore after any amount of time, t , whatever configuration τ becomes after t updates must remain greater than or equal to whatever configuration σ becomes after t updates. This preservation of partial ordering leads to the theorem proved by Propp and Wilson:

Theorem: If one runs the heat bath for an attractive spin system under the coupling-from-the-past protocol, one will generate states of the system that are exactly governed by the target distribution, π [link] .

Exact sampling of yd's in an a × B box

Expanding the Monotone Monte Carlo Algorithm to YD's is fairly simple, if we treat each YD as a configuration set, σ , in a spin system. The unit squares are vertices i in the vertex set of all i in the a × b box, where i spins up if i is in the YD σ and i spins down otherwise. The configurations are selected according to the probability distribution

π ( σ ) q | σ | , 0 < q 1

where | σ | denotes how many vertices in σ spin up. The vertices are updated according to the conditional probabilities given by π . There are three equations to update by: 1) if σ ( i ) = is improbable, f t ( σ , u t ) = σ i ; 2) if σ ( i ) = is improbable f t ( σ , u t ) = σ i ; 3) if both σ ( i ) = and σ ( i ) = have positive probability, update i according to the equation

f t ( σ , u t ) = σ i u t < 1 1 + q σ i u t 1 1 + q

where t is time, and u t is a random real number in [ 0 , 1 ] chosen according to the uniform distribution where all u t 's are chosen independently of each other.

It is easy to demonstrate using the three equations that for all possible σ , τ , and i , formula [link] holds given σ τ . Essentially, we have 5 possible cases:

1.) If i is chosen to be a box in σ such that σ i is not a valid YD, then τ i is not a valid YD either, since σ τ . Therefore π ( σ i ) = 0 and π ( τ i ) = 0 . Formula [link] becomes 0 = 0 .

2.) If i is chosen to be a box such that both σ i and σ i are YD's, but τ i is not a valid YD, then

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask