Hit and Run is Fast and Fun

The hit-and-run algorithm is one of the fastest known methods to generate a random point in a high dimensional convex set. In this paper we study a natural extension of the hit-and-run algorithm to sampling from a logconcave distribution in n dimensions. After appropriate preprocessing, hit-and-run produces a point from approximately the right distribution in amortized time O* ( n 3 ).