Convergence properties of hit–and–run samplers

Abstract

Abstract Hit–and–Run algorithms are probabilistic methods for generating points at random according to some prescribed distribution π on a subset A of R d . Given a current point, say , a direction vector, say , is chosen at random according to some prescribed random mechanism. The next point, is then chosen at random according to the conditionalization of π on the line defined by Xk and . Under appropriate conditions, the sequence will be a Markov chain converging in total variation to the target distribution π. This paper introduces a new class of Hit–and–Run algorithms. A general convergence theorem is obtained and the existence, within this class, of particular Hit–and–Run algorithms with desirable asymptotic properties is established Keywords: Monte Carlo methodsHit–and–Run algorithms