Pattern Hit-and-Run for sampling efficiently on polytopes

Pattern Hit-and-Run (PHR) is a Markov chain Monte Carlo sampler for a target distribution that was originally designed for general sets embedded in a box. A specific set of interest to many applications is a polytope intersected with discrete or mixed continuous/discrete lattices. PHR requires an acceptance/rejection mechanism along a bidirectional walk to guarantee feasibility. We remove this inefficiency by utilizing the linearity of the constraints defining the polytope, so each iteration of PHR can be efficiently implemented even though the variables are allowed to be integer valued. Moreover, PHR converges to a uniform distribution in polynomial time for a class of discrete polytopes. (C) 2011 Elsevier B.V. All rights reserved.