# John's Walk

arXiv: https://arxiv.org/abs/1803.02032 · HTML: https://mlsanity.com/paper/1803.02032/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2018.

## Built on by (most cited first, 3 of 3)

- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)

## Abstract (arXiv)

We present an affine-invariant random walk for drawing uniform random samples from a convex body K subset ℝn that uses maximum volume inscribed ellipsoids, known as John's ellipsoids, for the proposal distribution. Our algorithm makes steps using uniform sampling from the John's ellipsoid of the symmetrization of K at the current point. We show that from a warm start, the random walk mixes in widetildeO(n7) steps where the log factors depend only on constants associated with the warm start and desired total variation distance to uniformity. We also prove polynomial mixing bounds starting from any fixed point x such that for any chord pq of K containing x, left|log frac|p-x||q-x|right| is bounded above by a polynomial in n.