Markov Chain Monte Carlo Sampling | Hacker News Reader

Markov Chain Monte Carlo Sampling

galeascience.wordpress.com

The intrinsic important of MCMC is clear. What kinds of applications would be of excitement to startup-oriented readers here on YCombinator?

Also why is this called Quantum MCMC rather than just normal Markov Chain Monte Carlo?

By coincidence there is a Coursera Cousrse that just started on Statistical Mechanics and Algorithms, and the first exercise is to approximate pi.

https://www.coursera.org/learn/statistical-mechanics

In Lattice QCD [1] we basically execute huge MCMC in order to sample the partition function [2] on a discretized spacetime.

[1] https://en.wikipedia.org/wiki/Lattice_QCD

[2] https://en.wikipedia.org/wiki/Path_integral_formulation#The_...

> Also why is this called Quantum MCMC rather than just normal Markov Chain Monte Carlo?

I had the same question, so I looked it up. From https://en.wikipedia.org/wiki/Quantum_Monte_Carlo :

"Quantum Monte Carlo encompasses a large family of computational methods whose common aim is the study of complex quantum systems. One of the major goals of these approaches is to provide a reliable solution (or an accurate approximation) of the quantum many-body problem."

Taking a quick look at the blog, I believe that the author is simply trying to lead up to quantum monte carlo. I'm not a theorist, but the basic idea is that we have a pretty good understanding of quantum mechanics. But in materials, we don't just have one or two electrons roaming around, but rather have HUGE numbers. So, we can try to make a number of approximations to get tractable calculations, BUT a number of those approximations actually neglect the strong interactions between individual electrons. Quantum monte carlo tries to apply monte carlo techniques to this problem. You might enjoy the summary at: http://people.physics.illinois.edu/Ceperley/papers/213.pdf

(though it's rather geared towards physicists).

As for the hacker news appeal...hmmm....There are two levels. One is the curiosity appeal of how things work. The applied level that I can think of would be quite down the line. I went to a talk at a conference awhile back (again, I'm not an expert on this) that talked a little about this. Searching for new materials is hard. If you remember some years back, there was a scare about China restricted exports of rare earth materials (which make up high power permanent magnets) and people began to search for replacements. Well, how do you search for materials with new properties? A lot of what we've done in the past has involved heuristics. If you are doing synthesis, you make some guesses, over time, you build up intuition, and then you try to start making materials--but you don't know if they will form, or if they'll even have the properties you want if you make them.

One approach that people have taken is to use a method called Density Functional theory (DFT)--or ab initio methods (parameter free)-- that only works at 0 temperature and neglects many of those interactions between electrons that I told you about. And despite this, it can get you some really nice directions to search in for some materials. Now, to better capture some of those interactions that you left out (which you need to understand to get things like magnetism correct) you can try to add back in by including a parameter called "U" that is a measure of how much energy it takes for an electron to move from one atom to another in your material. Within DFT, this is a "fudge" factor and people look at it over some range of values to see how it effects material properties (keep in mind that these calculations are computationally expensive!!!).

Now, it turns out that that recently some researchers from Rutgers have figured out how to calculate this U parameter using something called "Dynamical Mean Field Theory". And, it turns out that there is a stage in this calculation that can be mapped to a problem that Quantum monte carlo simulations can solve quickly.

So....Long story short (ok, maybe too late for that), it can help us when we try to calculate the properties of materials--without synthesizing them--which saves a lot of time and money. But, it's still early days...

I hope this helps a bit...

I highly recommend the coursera stat mech course. Professionally filmed against a green screen, clear explanations and a massive amount of python programs to illustrate it all.

The python stuff was just vanilla MCMC sampling with the Metropolis algorithm.

Quantum is popping up because this is in introductory series aimed at people who want to understand QMC.

>If you come from a math, statistics, or physics background you may have leaned that a Markov chain is a set of states that are sampled from a probability distribution.

That's a very weird way of putting it. A set of states sampled from a probability distribution is usually just called a 'sample' and has nothing to do with Markov or chains.

Really 'Markov chains' are called 'chains' because they represents an infinite sequence of states, which depend on each other.

And they're called 'Markov' because they have the 'Markov' property, which roughly states that the probability distribution for each state is completely determined by the previous state.

  > and if A < 1 we do the following:
  > Produce a random number \chi from 0 to 1
  > Calculate m=A + \chi
  > Accept the move if m >= 1, otherwise reject

I'm guessing people have their own ways of doing this step, but by doing the math here, seems to me the second move can be omitted and the third replaced with "Accept the move if A >= /chi, otherwise reject".

EDIT: I see in the actual code all of this is summarized as A + chi >= 1, i.e. not a big deal (but still an addition more than needed ;)

And instead of writing MCMC samplers yourself, with probabilistic programming languages you can define a model and the language figures out how to do the sampling for you.

Reply on news.ycombinator.com