# Hit and run MCMC

I'm trying to implement the hit and run MCMC algorithm, but I'm having a bit of trouble understanding how to go about it. The general idea, is as follows:

To generate a proposal jump in MH, we:

• Generate a direction $d$ from a distribution on the surface of the unit sphere $\mathcal{O}$
• Generate a signed distance $\lambda$ along the constrained space.

However, I have no idea of how I should go about implementing this in R (or any other language).

Does anyone have a snippet of code that would point me in the right direction?

BTW, I not that interested in a library that does this method, I want to try and code it up myself.

Many thanks.

• Never heard of this algorithm before, but it sounds pretty interesting. Could you provide a link to a explanatory source ? Thank you ! – steffen Dec 2 '10 at 10:35
• @steffen Here's a link to the original paper - well actually the technical report. I've never used this procedure either. – csgillespie Dec 2 '10 at 11:20
• What is the advantage of the hit and run MCMC over other methods? Speed of convergence? – RockScience Dec 6 '10 at 5:14
• @fRed: That's why I offered the bounty. I've read about Hit and run, but don't know under what circumstances it would be useful. – csgillespie Dec 6 '10 at 18:46
• Link is now broken. – daknowles Feb 1 '17 at 23:54

I didn't look at the paper you supplied, but let me have a go anyway:

If you have a $p$-dimensional parameter space you can generate a random direction $d$ uniformly distributed on the surface of the unit sphere with

x <- rnorm(p)
d <- x/sqrt(sum(x^2))


(c.f. Wiki).

Then, use this to generate proposals for $d$ for rejection sampling (assuming you can actually evaluate the distribution for $d$).

Assuming you start in position $x$ and have accepted a $d$, generate a proposal $y$ with

 lambda <- r<SOMEDISTRIBUTION>(foo, bar)
y <- x + lambda * d


and do a Metropolis-Hastings-Step to decide whether to move to $y$ or not.

Of course, how well this can work will depend on the distribution of $d$ and how expensive it is to (repeatedly) evaluate its density in the rejection sampling step, but since generating proposals for $d$ is cheap you may get away with it.

Added for @csgillespie's benefit:

From what I was able to gather by some googling, hit-and-run MCMC is useful primarily for fast mixing if you have a (multivariate) target that has arbitrary bounded but not necessarily connected support, because it enables you to move from any point in the support to any other in one step. More here and here.

• If this answer is not satisfactory, could you explain why? – John Salvatier Dec 8 '10 at 22:11
• I'm not sure about @fred, but when I offered the bounty I suppose I was wanting a bit more insight into hit-and-run MCMC. For example, what types of problems would it be best suited for. Of course, if there are no other answers, then this question would win the bounty. – csgillespie Dec 9 '10 at 9:49
• @csgillespie: I edited my answer to better accomodate your interest. Let it not be said that I was undeserving of the bounty. ;) – fabians Dec 9 '10 at 11:50
• Many thanks for the link. One of the reasons I placed the bounty was that my google searches turned up a few mathematical discussions of the method, but little in the way of practical applications. Please don't take it as a slight if I wait another 48 hours before awarding the bounty (it is a particularly generous bounty!) – csgillespie Dec 9 '10 at 18:03

I came across your question when I was looking for the original reference for Hit-and-Run. Thanks for that! I just put together a proof-of-concept implementation of hit-and-run for PyMC at the end of this recent blog.