Where to Start a Geometric Random Walk?

Consider a random walk in Rn. It starts somewhere, and at each step moves to a randomly chosen “neighboring” point (which could be the current point). By a suitable choice of the “neighbor” relation, the steady state distribution of such a walk can be the uniform distribution over a convex body, or indeed any reasonable distribution in Rn.

These walks have several nice properties. For example, they are easy to implement as algorithms. Further, they seem to approach their steady state distribution quite rapidly when the target distribution is logconcave. There has been much work in this direction, showing that the conductance of natural random walks (lattice walk, ball walk, speedy walk, and hit-and-run) is large enough that the rate of convergence is polynomial in n.