Abstract.
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 2 R 2/r 2), 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 3), 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received January 26, 1998 / Revised version received October 26, 1998¶Published online July 19, 1999
Rights and permissions
About this article
Cite this article
Lovász, L. Hit-and-run mixes fast. Math. Program. 86, 443–461 (1999). https://doi.org/10.1007/s101070050099
Issue Date:
DOI: https://doi.org/10.1007/s101070050099