Hit-and-run mixes fast

It is shown that the ‘hit-and-run’ algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O*(n²R²/r²), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O*(n³), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R, r and n.