Direction Choice for Accelerated Convergence in Hit-and-Run Sampling

David E. Kaufman and Robert L. Smith
Additional contact information
David E. Kaufman: AT & T Labs, Somerset, New Jersey
Robert L. Smith: University of Michigan, Ann Arbor, Michigan

Operations Research, 1998, vol. 46, issue 1, 84-95

Abstract: Hit-and-Run algorithms are Monte Carlo procedures for generating points that are asymptotically distributed according to general absolutely continuous target distributions G over open bounded regions S . Applications include nonredundant constraint identification, global optimization, and Monte Carlo integration. These algorithms are reversible random walks that commonly incorporate uniformly distributed step directions. We investigate nonuniform direction choice and show that, under regularity conditions on the region S and target distribution G , there exists a unique direction choice distribution, characterized by necessary and sufficient conditions depending on S and G , which optimizes the Doob bound on rate of convergence. We include computational results demonstrating greatly accelerated convergence for this optimizing direction choice as well as for more easily implemented adaptive heuristic rules.

Keywords: Simulation; random variable generation; Markov-chain Monte Carlo; Probability; random walk; direction choice (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.1.84 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:1:p:84-95

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().