Running a random walk in a convex body $K\subseteq {\mathbb{R}}^{n}$ is a standard
approach to sample approximately uniformly from the body. The requirement is
that from a suitable initial distribution, the distribution of the walk comes
close to the uniform distribution ${\pi}_{K}$ on $K$ after a number of steps
polynomial in $n$ and the aspect ratio $R/r$ (i.e., when $r{B}_{2}\subseteq K\subseteq R{B}_{2}$ ).
Proofs of rapid mixing of such walks often require the probability density
${\eta}_{0}$ of the initial distribution with respect to ${\pi}_{K}$ to be at most
$\mathrm{poly}(n)$ : this is called a "warm start". Achieving a warm start often
requires non-trivial pre-processing before starting the random walk. This
motivates proving rapid mixing from a "cold start", wherein ${\eta}_{0}$ can be as
high as $\mathrm{exp}(\mathrm{poly}(n))$ . Unlike warm starts, a cold start is usually
trivial to achieve. However, a random walk need not mix rapidly from a cold
start: an example being the well-known "ball walk". On the other hand, Lov\'asz
and Vempala proved that the "hit-and-run" random walk mixes rapidly from a cold
start. For the related coordinate hit-and-run (CHR) walk, which has been found
to be promising in computational experiments, rapid mixing from a warm start
was proved only recently but the question of rapid mixing from a cold start
remained open.
We construct a family of random walks inspired by classical decompositions of
subsets of ${\mathbb{R}}^{n}$ into countably many axis-aligned dyadic cubes. We
show that even with a cold start, the mixing times of these walks are bounded
by a polynomial in $n$ and the aspect ratio. Our main technical ingredient is
an isoperimetric inequality for $K$ for a metric that magnifies distances
between points close to the boundary of $K$ . As a corollary, we show that the
CHR walk also mixes rapidly both from a cold start and from a point not too
close to the boundary of $K$ .

PREPRINT

# Sampling from convex sets with a cold start using multiscale decompositions

Hariharan Narayanan, Amit Rajaraman, Piyush Srivastava

Submitted on 8 November 2022, last revised on 30 November 2022

## Abstract

## Preprint

Comment: Changes from v1: Added a corollary on mixing of coordinate hit-and-run from a point. Also includes some minor corrections/simplifications and explanations

Subjects: Computer Science - Data Structures and Algorithms; Computer Science - Computational Geometry; Mathematics - Probability