Discrete Hit-and-Run for Sampling Points from Arbitrary Distributions Over Subsets of Integer Hyperrectangles

We consider the problem of sampling a point from an arbitrary distribution (pi) over an arbitrary subset S of an integer hyperrectangle. Neither the distribution (pi) nor the support set S are assumed to be available as explicit mathematical equations, but may only be defined through oracles and, in particular, computer programs. This problem commonly occurs in black-box discrete optimization as well as counting and estimation problems. The generality of this setting and high dimensionality of S precludes the application of conventional random variable generation methods. As a result, we turn to Markov chain Monte Carlo (MCMC) sampling, where we execute an ergodic Markov chain that converges to (pi) so that the distribution of the point delivered after sufficiently many steps can be made arbitrarily close to (pi). Unfortunately, classical Markov chains, such as the nearest-neighbor random walk or the coordinate direction random walk, fail to converge to (pi) because they can get trapped in isolated regions of the support set. To surmount this difficulty, we propose discrete hit-and-run (DHR), a Markov chain motivated by the hit-and-run algorithm known to be the most efficient method for sampling from log-concave distributions over convex bodies in R n . We prove that the limiting distribution of DHR is (pi) as desired, thus enabling us to sample approximately from (pi) by delivering the last iterate of a sufficiently large number of iterations of DHR. In addition to this asymptotic analysis, we investigate finite-time behavior of DHR and present a variety of examples where DHR exhibits polynomial performance.