abstract:
The hit-and-run algorithm provides a Markov chain which can be used to approximate distributions
which might be given by unnormalized densities. Assume that $\mu_\rho$ is such a distribution
given by $\rho$. Then we want to compute
\[
S(f,\rho) =\int_D f(y)\, \mu_\rho({\rm d}y)
=\frac{\int_D f(y) \rho(y)\, {\rm d}y}{\int_D \rho(y)\, {\rm d}y},
\]
for a function $f$ and $D\subset \mathbb{R}^d$. Under suitable assumptions on the densities one has
explicit estimates of the total variation distance of the hit-and-run distribution to $\mu_\rho$.
These estimates are used to get error bounds for Markov chain Monte Carlo methods
which depend polynomially on the dimension $d$. |