Posts Tagged Ising model
This Tuesday I’m starting off the talks for the Spring in the Algebra/Number Theory/Combinatorics Seminar here in Claremont. It will be at 12:15 on 24 Jan 2012 in Millikan 134. Complete details can be found here. The title is “A gadget for reducing the Ising model to matchings”, and it is joint work that I did with my first graduate student, Jenny Law.
Abstract: In my talk last semester in the seminar, I presented a classic result: the problem of counting the number of solutions to a logic formula can be turned into a problem of summing weighted perfect matchings in a graph. The key idea was the use of a combinatorial “gadget”. In this talk I’ll present a gadget developed with my first graduate student, Jenny Law, that allows for what is called a simulation reduction. The reduction works as follows: if you are able to sample randomly from a weighted distribution on perfect matchings in a graph, then you can also simulate from the Ising model, a classical model from statistical physics that has been heavily studied since its inception in the 1920’s. (http://arxiv.org/abs/0907.0477)
The talk that I gave at UMSL can now be downloaded here. This talk describes two different protocols for perfect simulation. The first, Partially Recursive Acceptance Rejection, gives an easy way to generate perfect samples from loosely coupled Markov random fields (such as the Ising model) in linear time without building a Markov chain at all for the problem.
The second part discusses Sequential Acceptance Rejection, a method that has proved useful for problems like approximating the permanent in dense problem instances.