1. David Rachel

    Nice article! I’d not heard of Metropolis-Hastings, but it’s awesome.

    Since the limit behaviour is independent of the jump width, does that mean that the transition function T (jump width) can be arbitrarily altered mid-algorithm without undermining the result?

    If so, is there any potential benefit in this? Something like annealing, or even fancy and adaptive things – e.g. target desired acceptance/rejection rate, or transition function determined by variance (scalar or matrix) of existing selection?

    • Changing the transition function mid-algorithm can affect the asymptotic result if you’re not careful. For example, making jumps smaller or when the current position is in a specific region could lead to that region being over-represented.

      However, there are benefits to tuning the acceptance rate or reducing the autocorrelation of the sampling process, such as reducing the variance of the integral estimate or making sure that you adequately explore all local maxima. To do this without damaging the convergence of the algorithm, one can specify a “burn-in” segment at the beginning in which parameters of the algorithm are tuned, and then throw out those samples. This has the added advantage of making the final result less dependent on the starting point.

  2. Interesting stuff Michael, have you ever encounter stochastic evolutionary game dynamics?

    It’s a way you can take these methods and merge them with some pretty interesting frameworks coming out of game theory. Basically a way to connect the world of analyzing dynamic, stochastic systems to the world of human behavior. Where does the ‘system’ end up, when the system is a complex world of players, beliefs, actions, and payoff functions.

    Link below is a pretty good paper on the topic from my thesis advisors at Oxford. Think you would enjoy it.


  3. Thanks Michael for the great article. It’s such an amazing thing to see when we can take previously unsolvable problems and transform them into nothing more than a tedious calculation. Probability FTW!

  4. Kshitij Lauria

    @David Rachel
    If you change transition probabilities mid-algorithm, you must be very careful that you have not made your Markov chain irreversible.

    An intuitive way to understand detailed balance is that it means your state transitions are reversible: the likelihood of a path is the same in either direction.

    Simulated annealing makes use of the idea of Metropolis-Hastings by constructing a FAMILY of reversible Markov chains (each temperature). http://www.mit.edu/~dbertsim/papers/Optimization/Simulated%20annealing.pdf is a survey paper.

Leave a Reply

Your email address will not be published. Required fields are marked *