×

Hit-and-run algorithms for generating multivariate distributions. (English) Zbl 0771.60052

Summary: We introduce a general class of hit-and-run algorithms for generating essentially arbitrary absolutely continuous distributions on \(\mathbb{R}^ d\). They include the hypersphere directions algorithm and the coordinate directions algorithm that have been proposed for identifying nonredundant linear constraints and for generating uniform distributions over subsets of \(\mathbb{R}^ d\). Given a bounded open set \(S\) in \(\mathbb{R}^ d\), an absolutely continuous probability distribution \(\pi\) on \(S\) (the target distribution) and an arbitrary probability distribution \(\nu\) on the boundary of the \(d\)-dimensional unit sphere centered at the origin (the direction distribution), the \((\nu,\pi)\)-hit-and-run algorithm produces a sequence of iteration points as follows. Given the \(n\)th iteration point \(x\), choose a direction \(\theta\) according to the distribution \(\nu\) and then choose the \((n+1)\)st iteration point according to the conditionalization of the distribution \(\pi\) along the line defined by \(x\) and \(x+\theta\). Under mild conditions, we show that this sequence of points is a Harris recurrent reversible Markov chain converging in total variation to the target distribution \(\pi\).

MSC:

60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
62E20 Asymptotic distribution theory in statistics
65C05 Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI Link