# The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2015.

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

- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)
- [PolytopeWalk: Sparse MCMC Sampling over Polytopes](https://mlsanity.com/paper/2412.06629/) (2024)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

We study the mixing time of the Dikin walk in a polytope - a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing time are important for algorithms for sampling and optimization over polytopes. Here, we provide a simple proof of their result that this random walk mixes in time O(mn) for an n-dimensional polytope described using m inequalities.