Discrete Hit-and-Run for Sampling Points from Arbitrary Distributions Over Subsets of Integer Hyperrectangles
成果类型：
Article
署名作者：
Baumert, Stephen; Ghate, Archis; Kiatsupaibul, Seksan; Shen, Yanfang; Smith, Robert L.; Zabinsky, Zelda B.
署名单位：
University of Washington; University of Washington Seattle; Chulalongkorn University; University of Michigan System; University of Michigan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0600
发表日期：
2009
页码：
727-739
关键词：
摘要：
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.