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

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.