2. Preliminaries

Notation. We will denote positive universal constants that are less than 1 by c and positive universal constants that are greater than 1 by C.

2.1. The CHR walk

Let $K\subseteq {\mathbb R}^n$ be a convex body. Let $e_1, \dots, e_n$ denote the canonical basis of ${\mathbb R}^n$ . The law of the CHR walk can then be expressed as follows. Fix v belonging to the interior of K. To implement one step of the CHR walk, do the following. First, choose $i \in [n]$ uniformly at random, and let $\ell$ be the cord $K \cap (v + e_i {\mathbb R}).$ Then, choose u uniformly at random from $\ell$ (with respect to the $1-$ dimensional Lebesgue measure $\lambda_1$ on ${\mathbb R}$ ). Thus, the transition probability densities (with respect to $\lambda_1$ ) are given by

\begin{equation*} \mathcal P_{vu} = \begin{cases} \frac{1}{n|K \cap (v + e_i {\mathbb R})|} & \text{$u \in K \cap (v + e_i {\mathbb R})$ for some $i \in [n]$,}\\ 0 & \text{ otherwise.} \end{cases}\end{equation*}

2.2. Markov schemes and isoperimetry

In this section, we collect some definitions and results about Markov chains that will be used in our proofs. We mostly follow the terminology and notation of Lovász and Simonovits [Reference Lovász and Simonovits15].

For any measurable $S \subseteq {\mathbb R}^n$ , we denote by ${\mathrm{vol}\left({S}\right)}$ its Lebesgue volume, and by $\pi_S$ the uniform probability distribution on S. Thus, $\pi_{S}(A)=\mathrm{vol}(S\cap A)/\mathrm{vol}(S)$ for any measurable A. Fix a measurable set $S \subseteq {\mathbb R}^n$ of finite volume and let $\mathcal{S}$ denote the set of measurable subsets of S. A Markov scheme on S is a map $P\;:\;S \times \mathcal{S} \rightarrow [0,1]$ such that (i) for every $u \in S$ , $P(u, \cdot)$ is a probability measure on S, and (ii) for every $A \in \mathcal{S}$ , the function $P(\cdot, A) : S \rightarrow [0,1]$ is measurable. Given a Markov scheme P and a probability distribution $\mu_0$ on S, A Markov chain $M = M(\mu, P)$ is a sequence $X_0, X_1, \dots, X_k,\dots$ of random points in S such that $X_0 \sim \mu_0$ and for $i \geq 1$ , $X_i \sim P(X_{i-1}, \cdot)$ . We denote by $\mu_{k, P}$ the probability distribution of the random variable $X_k$ .

A probability measure Q on S is said to be stationary with respect to a Markov scheme P on S if for all measurable $A\subseteq S$ ,

$$\int_S P (u,A)\;Q(du) = Q(A).$$

Such a Q is said to be reversible with respect to P if for all measurable $A, B \subseteq S$ ,

$$\int_A P (u,B)\;Q(du) = \int_B P (u,A)\;Q(du).$$

Note that if Q is reversible with respect to P, then it is also stationary with respect to Q.

The ergodic flow $\Phi_{P,Q}$ of a Markov scheme P on S with respect to a probability distribution Q on S is defined as

$${\Phi _{P,Q}}(A){\mkern 1mu} : = {\mkern 1mu} \int_A P (u,S - A)Q(du),{\rm{for \, all \, measurable \, A}} \subseteq {\rm{S}}.$$

Note that when Q is stationary with respect to P, one can easily check that [Reference Lovász and Simonovits15, p. 366]

(2.1) \begin{equation} \Phi_{P, Q}(A) = \Phi_{P, Q}(S - A).\end{equation}

By abuse of notation, we extend the definition of ergodic flow to pairs of measurable sets:

$${\Phi _{P,Q}}(A,B){\mkern 1mu} : = {\mkern 1mu} \int_A P (u,B)Q(du),{\rm{for \, all \, measurable \, A}},{\rm{B}} \subseteq {\rm{S}}.$$

The s-conductance [Reference Lovász and Simonovits15, p. 367] $\Phi_s$ , where $0 \leq s < 1/2$ , of a Markov scheme P on S with respect to a probability distribution Q on S is defined as

(2.2) \begin{equation} \Phi_s \,:\!=\, \inf_{A {\;\textbf{:}\;} s < Q(A) \leq 1/2} \frac{\Phi_{P,Q}(A)}{Q(A) - s}.\end{equation}

Quantitative estimates involving the conductance of Markov chains have been an important ingredient of various results proving mixing time upper bounds for Markov chains. In our proof, we will use the following estimate, stated in this form by Lovász and Simonovits [Reference Lovász and Simonovits15].

Theorem 2.1 ([ Reference Lovász and Simonovits15 , Corollary 1.6]). Let S be a measurable subset of ${\mathbb R}^n$ of finite volume. Let P be a Markov scheme on S, and let $\mu_0$ and Q be probability distributions on S such that Q is stationary with respect to P. Assume that Q is atom-free, that is, $Q(\left\{{u}\right\}) = 0$ for all $u \in S$ . Fix $0 < s < 1/2$ , and define

$${H_s}{\mkern 1mu} : = {\mkern 1mu} \mathop {\sup }\limits_{A \subseteq S\;:\;Q(A) \le s} \left| {{\mu _0}(A) - Q(A)} \right|.$$

For each $k \geq 0$ , let $\mu_{k, P}$ denote the distribution of the kth element in the Markov chain $(\mu_0, P)$ . Then, for all non-negative integers k,

$${d_{TV}}({\mu _{k,P}},Q) \le \left( {1 + {{{{(1 - \Phi _s^2/2)}^k}} \over s}} \right)\cdot{H_s},$$

where $\Phi_s$ is the s-conductance of P with respect to Q.

We will also need the following isoperimetric inequality.

Theorem 2.2 ([ Reference Lovász and Simonovits15 , Corollary 2.7]). Let $\delta > 0$ be arbitrary. Fix any norm ${\Vert {\cdot} \Vert_{\ell}}$ on ${\mathbb R}^n$ . Let $K \subseteq {\mathbb R}^n$ be a convex body and let $K_1$ and $K_2$ be disjoint measurable subsets of K such that for all $u \in K_1$ and $v \in K_2$ , one has ${\Vert {u - v} \Vert_{\ell}} \geq \delta$ . Suppose that the diameter of K in the ${\Vert {\cdot} \Vert_{\ell}}$ -norm is at most D (i.e., ${\Vert {x - y} \Vert_{\ell}} \leq D$ for all $x, y \in K$ ). Then,

$${\rm{vol}}\left( {K - \left( {{K_1} \cup {K_2}} \right)} \right) \ge {{2\delta } \over {D - \delta }}\cdot\min \left\{ {{\rm{vol}}\left( {{K_1}} \right),{\rm{vol}}\left( {{K_2}} \right)} \right\}.$$

2.3. Volume of the robust interior

Given a closed convex body K, we define, for $r > 0$ ,

$${K_r}{\mkern 1mu} : = {\mkern 1mu} \left\{ {x \in K\;:\;\forall v,v{_\infty } \le r \Rightarrow x + v \in K} \right\}.$$

The following proposition follows directly from [Reference Dyer, Frieze and Kannan4, Proposition 2].

Proposition 2.3. Suppose that $\epsilon \in (0, 1/\sqrt{n})$ and $K \subset {\mathbb R}^n$ is a closed convex body such that $B = B_2 \subseteq K$ . Then $(1-\epsilon\sqrt{n})K \subseteq K_{\epsilon}$ . In particular, ${\mathrm{vol}\left({{K_\epsilon}}\right)} \geq (1-\epsilon\sqrt{n})^n{\mathrm{vol}\left({{K}}\right)}$ .

In our setting, we will need the following proposition which improves upon Proposition 2.3 in the case when K is guaranteed to contain the ${\Vert {\cdot} \Vert_{\infty}}$ -ball $B_\infty$ instead of just the ${\Vert {\cdot} \Vert_{2}}$ -ball $B_2$ . The proof follows in an essentially identical fashion to that of [Reference Dyer, Frieze and Kannan4, Proposition 2], but we include it for completeness.

Proposition 2.4. Suppose that $\epsilon \in (0, 1)$ and $K \subset {\mathbb R}^n$ is a closed convex body such that $B_\infty \subseteq K$ . Then $(1-\epsilon)K \subseteq K_{\epsilon}$ . In particular, ${\mathrm{vol}\left({{K_\epsilon}}\right)} \geq (1-\epsilon)^n {\mathrm{vol}\left({{K}}\right)}$ .

Proof. We only need to show that ${\Vert {z - x} \Vert_{\infty}} > \epsilon$ for all $x \in (1-\epsilon)K$ and $z \in K^c$ . Fix any $z \in K^c$ . Now, by the separating hyperplane theorem, there exists a non-zero vector v such that $v^Tz > 1$ and $v^Ty \leq 1$ for all $y\in K$ . Since $B_\infty \subseteq K$ , the latter inequality implies that ${\Vert {v} \Vert_{1}} \leq 1$ . Further, for any $x \in (1-\epsilon)K$ , the same inequality gives $v^T{x} \leq (1-\epsilon)$ . But then we have

$$\epsilon < v^T(z - x) \leq {\Vert {v} \Vert_{1}}\cdot{\Vert {z - x} \Vert_{\infty}} \leq {\Vert {z - x} \Vert_{\infty}}. $$

3. Overlaps and conductance

The next definition and the results following it in this section are based on a method proposed by Lovász [Reference Lovász14, Section 5].

Definition 3.1 ( $(\epsilon, \delta, \nu)$ -overlap property) Let K be a convex body in ${\mathbb R}^n$ . A Markov scheme P on K is said to have the $(\epsilon, \delta, \nu)$ -overlap property with respect to K ^′, where K ^′ is a convex subset of K, if (i) ${\mathrm{vol}\left({{K'}}\right)} \geq {\mathrm{vol}\left({{K}}\right)}(1 - \epsilon)$ and (ii) for all $u, v \in K'$ satisfying ${\Vert {u - v} \Vert_{2}} \leq \delta$ , we have

$${d_{TV}}(P(u,\cdot),P(v,\cdot)) \le 1 - \nu .$$

Lemma 3.2 Let $\epsilon, \delta, \nu \in (0, 1/2)$ . Let K be a convex body in ${\mathbb R}^n$ of ${\Vert {\cdot} \Vert_{2}}$ -diameter at most $D \geq 2\delta$ and let P be a Markov scheme on K which is reversible with respect to the uniform distribution $\pi_K$ on K. Suppose also that P has the $(\epsilon, \delta, \nu)$ -overlap property with respect to K’. Then, the $\epsilon$ -conductance of P with respect to $\pi_K$ is at least $\frac{\nu\delta}{4(D-\delta)}$ . In fact, if $S_1, S_2$ is any arbitrary partition of K into disjoint measurable subsets, and we denote $K'\cap S_1$ by $T_1$ and $K'\cap S_2$ by $T_2$ , then we have

\begin{align*} \Phi_{P, \pi_K}(S_1) \geq \max \left\{{\Phi_{P, \pi_K}(S_1, T_2), \Phi_{P, \pi_K}(S_2, T_1) }\right\} & \geq \left(\frac{\nu\delta}{4(D-\delta)}\right)\min\left\{{\pi_K(T_1), \pi_K(T_2)}\right\}\!,\\ & \geq \left(\frac{\nu\delta}{4(D-\delta)}\right)\min\left\{{\pi_K(S_1) - \epsilon, \pi_K(S_2) - \epsilon}\right\}\!. \end{align*}

Proof. The proof follows the same method as that of Lovász [Reference Lovász14, Sections 5 and 6]. Let $S_1, S_2$ be any arbitrary partition of K into disjoint measurable subsets, and let the convex subset $K' \subseteq K$ be as in the definition of the $(\epsilon, \delta, \nu)$ -overlap property, with $T_1 \,:\!=\, S_1 \cap K'$ , $T_2 \,:\!=\, S_2 \cap K'$ . Note that since $\pi_K(K') \geq 1 - \epsilon$ , one has

(3.1) \begin{equation} \begin{aligned} \pi_K(T_1) = \pi_K(S_1 \cap K') &\geq \pi_K(S_1) - \epsilon\text{, and}\\ \pi_K(T_2) = \pi_K(S_2 \cap K') &\geq \pi_K(S_2) - \epsilon. \end{aligned} \end{equation}

Now, consider the following subsets of $T_1$ and $T_2$ :

(3.2) \begin{equation} \begin{aligned} S^{\prime}_1 &\,:\!=\, \left\{{x \in T_1 {\;\textbf{:}\;} P(x, S_2) < \nu/2}\right\}\!\text{, and}\\ S^{\prime}_2 &\,:\!=\, \left\{{x \in T_2 {\;\textbf{:}\;} P(x, S_1) < \nu/2}\right\}\!. \end{aligned} \end{equation}

It then follows from the definition of the overlap property that

(3.3) \begin{equation} x \in S^{\prime}_1, y \in S^{\prime}_2 \implies {\Vert {x - y} \Vert_{2}} > \delta, \end{equation}

for if not, then for such x and y satisfying ${\Vert {x-y} \Vert_{2}} \leq \delta$ , we would have

\begin{align*} 1 - \nu \geq d_{TV}(P(x, \cdot), P(y, \cdot)) \geq P(x, S_1) - P(y, S_1) = 1 - P(x, S_2) - P(y, S_1) > 1 - \nu, \end{align*}

which is a contradiction. We can therefore apply the isoperimetric inequality of Theorem 2.2 to the subsets $S^{\prime}_1$ and $S^{\prime}_2$ of the convex body K ^′ to get

(3.4) \begin{equation} \pi_K(K' - (S^{\prime}_1 \cup S^{\prime}_2)) \geq \frac{2\delta}{D - \delta}\min\left\{{\pi_K(S^{\prime}_1), \pi_K(S^{\prime}_2)}\right\}. \end{equation}

Note that since P is reversible with respect to $\pi_K$ , we have $\Phi_{P, \pi_K}(S_1, T_2) = \Phi_{P, \pi_K}(T_2, S_1)$ . We thus have

(3.5) \begin{equation} \Phi_{P, \pi_K}(S_1, T_2) = \int\limits_{T_2}P(u, S_1) \pi_K(du) \geq \int\limits_{T_2 - S^{\prime}_2}P(u, S_1) \pi_K(du) \geq \frac{\nu}{2}\pi_K(T_2-S^{\prime}_2). \end{equation}

Similarly, we get

(3.6) \begin{equation} \Phi_{P, \pi_K}(S_2, T_1) = \int\limits_{T_1}P(u, S_2) \pi_K(du) \geq \int\limits_{T_1 - S^{\prime}_1}P(u, S_2) \pi_K(du) \geq \frac{\nu}{2}\pi_K(T_1-S^{\prime}_1). \end{equation}

Consider now the condition:

(3.7) \begin{equation} \pi_K(S^{\prime}_1) > \frac{1}{2}\pi_K(T_1)\text{ and } \pi_K(S^{\prime}_2) > \frac{1}{2}\pi_K(T_2). \end{equation}

The rest of the proof is divided into two cases:

Case 1 : The condition in equation(3.7)is false. In this case, we must have $\pi_K(S^{\prime}_1 ) \leq \frac{1}{2} \pi_K(T_1)$ or $\pi_K(S^{\prime}_2) \leq \frac{1}{2}\pi_K(T_2)$ . Using equation (3.5) or equation (3.6) in the respective cases, we immediately get

(3.8) \begin{align} & \max\left\{{\Phi_{P, \pi_K}(S_1, T_2), \Phi_{P, \pi_K}(S_2, T_1)}\right\} \nonumber \\ & \quad \geq \frac{\nu}{4}\min\left\{{\pi_K(T_1), \pi_K(T_2)}\right\} \stackrel{\text{equation (3.1)}}{\geq} \frac{\nu}{4}\min\left\{{\pi_K(S_1) - \epsilon, \pi_K(S_2) -\epsilon}\right\}, \end{align}

and the required inequality follows because of the assumption $D \geq 2\delta$ .

Case 2 : The condition in equation(3.7)is true. By adding the inequalities in equations (3.5) and (3.6), and using the fact that the sets $T_1$ and $T_2$ form a disjoint partition of K $^{\prime}$ , we have

(3.9) \begin{equation} \max\left\{{\Phi_{P, \pi_K}(S_1, T_2), \Phi_{P, \pi_K}(S_2, T_1)}\right\} \geq \frac{\nu}{4}\pi_K((T_1 - S^{\prime}_1) \cup (T_2 - S^{\prime}_2)) = \frac{\nu}{4}\pi_K(K' - (S^{\prime}_1 \cup S^{\prime}_2)). \end{equation}

Now, using equation (3.7) followed by equation (3.1) in the isoperimetric inequality in equation (3.4), we get

\begin{align*} \pi_K(K' - (S^{\prime}_1 \cup S^{\prime}_2)) & \geq \frac{\delta}{D - \delta}\min\left\{{\pi_K(T_1), \pi_K(T_2)}\right\}\\ & \geq \frac{\delta}{D - \delta}\min\left\{{\pi_K(S_1) - \epsilon, \pi_K(S_2) - \epsilon}\right\}. \end{align*}

Substituting this into equation (3.9), we again obtain the required inequality.

4. The Gaussian walk

In this section, we analyse an auxiliary Markov chain with Gaussian steps. In the next section, this chain will be compared with the CHR chain to establish lower bounds on the s-conductance of the latter.

Let $N(0, \sigma^2)$ denote the Gaussian distribution on ${\mathbb R}$ with mean 0 and variance $\sigma^2$ , and let $\gamma$ denote its density with respect to the Lebesgue measure. The Gaussian walk on a convex body K is then defined as follows. For some $t \in \mathbb{N}$ , suppose that we are given $x_t = v \in K$ . To generate $x_{t+1}$ , do the following. Choose $i \in [n]$ uniformly at random, and $\kappa \sim N(0, \sigma^2)$ . Let $u = v + \kappa e_i$ . If $u \in K$ , accept the proposed transition and set $x_{t+1} = u$ . Else, the proposal is rejected and $x_{t+1} = v$ .

Thus, the transition probability densities $\mathcal{G}_{vu}$ (with respect to the one-dimensional Lebesgue measure) are given by

\begin{equation*} \mathcal{G}_{vu} = \begin{cases} \frac{\gamma(|u - v|)}{n} & \text{ if $u \neq v$ and $u \in K \cap (v + e_i {\mathbb R})$ for some $i \in [n]$,}\\ 0 & \text{ otherwise.} \end{cases}\end{equation*}

In addition, the rejection probability, that is, the probability that $x_{t+1} = v$ , conditional on $x_t = v$ , is given by

\begin{equation*} \mathbb{P}[x_{t+1} = v|x_t = v] = 1- \mathbb{P}[v + \kappa e_i \in K|x_t = v].\end{equation*}

Note that like the CHR chain, the Gaussian chain is also reversible with respect to the uniform probability measure $\pi_K$ on K.

Given a positive integer $\tau$ , let $\mathcal{G}_v^{(\tau)}$ denote the probability distribution of $x_\tau$ given that $x_0 = v,$ and where, for $0 \leq t \leq \tau - 1$ , $x_{t+1}$ is generated from $x_t$ according to the Gaussian chain $\mathcal{G}_{x_t}$ .

We now set up some notation. Given a multi-index $\mathbb{I}=(i_1, \dots, i_n) \in \mathbb{N}^{n}$ , we define $\mathcal{G}_{v,\mathbb{I}}$ to be the unique Gaussian distribution centered at $v \in {\mathbb R}^n$ , whose covariance matrix $\Sigma_\mathbb{I}$ with respect to the canonical basis is the diagonal matrix with $i_j \sigma^2$ as the $j^{th}$ diagonal entry. We define $\mathcal M_{n,\tau}$ to be the set of all such multi-indices $\mathbb{I} = (i_1, i_2, \dots, i_n) \in \mathbb{N}^n$ for which $\sum_j i_j = \tau$ . We say that such an $\mathbb{I}$ is of full rank if the covariance matrix $\Sigma_I$ has full rank, that is, if all of the $i_k$ are at least 1. Further, for $\mathbb{I} \in \mathcal M_{n,\tau}$ , we define $\lambda_\mathbb{I} \,:\!=\, {\binom{\tau}{\mathbb{I}}}n^{-\tau},$ where ${\binom{\tau}{\mathbb{I}}}$ is the multinomial coefficient $\frac{\tau!}{\prod_k i_k!}.$ Observe that

(4.1) \begin{equation}\sum_{\mathbb{I} \in \mathcal M_{n,\tau}} \lambda_\mathbb{I}= 1.\end{equation}

We then have the following lemma.

Lemma 4.1 Fix $\sigma > 0$ , $n \geq 2$ and $\tau = \tau(n) \,:\!=\, \lceil 20 n \ln n\rceil$ . Let $K \in {\mathbb R}^n$ be a convex body and let $v \in K$ be a point such that $\inf_{z \in \partial K} \|v - z\|_{\infty} > 100 \sigma \ln n.$ Define the measures $\mathcal{G}_v^{\tau}$ and $\mathcal{G}_{v, \mathbb{I}}$ as above, in terms of $N(0, \sigma^2)$ . Then,

$$d_{TV}\left({\mathcal{G}_v^{(\tau)}, \sum_{\substack{\mathbb{I} \in \mathcal M_{n,\tau}\\\mathbb{I}\text{ of full rank}}} \lambda_\mathbb{I} \mathcal{G}_{v,\mathbb{I}}}\right) \leq 2 n^{-5}.$$

Proof. Let $\mathcal{H}$ denote the probability measure $\left(\sum_{\mathbb{I} \in \mathcal M_{n,\tau}} \lambda_\mathbb{I} \mathcal{G}_{v,\mathbb{I}}\right)$ , and $\mathcal{H}'$ the measure $(\!\sum_{\substack{\mathbb{I} \in \mathcal M_{n,\tau}\\\mathbb{I}\text{ of full rank}}} \lambda_\mathbb{I} \mathcal{G}_{v,\mathbb{I}})$ . Consider the following natural coupling between $\mathcal{G}_{v}^{(\tau)}$ and $\mathcal{H}$ , for $0 \leq t \leq \tau$ . Set $x_0 = x^{\prime}_0 = v$ . For $0 \leq t \leq \tau - 1$ , the pair $(x_{t+1}, x^{\prime}_{t+1})$ , given the pair $(x_t, x^{\prime}_t)$ , is generated as follows. Pick $i \in [n]$ u.a.r. and $\kappa \sim N(0, \sigma^2)$ , and set $x^{\prime}_{t+1} = x^{\prime}_{t} + \kappa e_i$ . Further $x_{t+1} = x_t + \kappa e_i$ if that point is in K, otherwise $x_{t+1} = x_{t}$ . As before, in the latter case we say that the update at time $t + 1$ was rejected. Let E be the event that none of the updates at times $1\leq t \leq \tau$ are rejected.

By definition, we have $x_\tau \sim \mathcal{G}_v^{(\tau)}$ and $x^{\prime}_\tau \sim \mathcal{H}$ . Further, when the event E occurs, we also have $x_\tau = x^{\prime}_\tau$ . It therefore follows from standard coupling arguments that

(4.2) \begin{equation} d_{TV}(\mathcal{G}_v^{(\tau)}, \mathcal{H}) \leq {\mathbb{P}}[\lnot E] = 1 - {\mathbb{P}}[E]. \end{equation}

We now lower bound ${\mathbb{P}}[E]$ . For $1 \leq i \leq n$ , let $A_i$ denote the number of times an update along the coordinate direction i is proposed in the above coupling. Then, by a standard Chernoff bound (see Fact A.1), and recalling that $\tau = {\left\lceil{20 n \ln n}\right\rceil}$ , we have

(4.3) \begin{equation} {\mathbb{P}}\left[{\exists i, 1\leq i \leq n, \text{ s.t. } A_i \geq 50\ln n}\right] \leq n \cdot \exp\!\left({-\tau/(3n)}\right)\leq n^{-5}. \end{equation}

We now recall that $x_0 = x^{\prime}_0 = v$ satisfies $\inf_{z \in \partial K} \|v - z\|_{\infty} > 100 \sigma \ln n$ . Thus, conditioned on the event that each $A_i$ is at most $50\ln n$ , standard Gaussian tail bounds imply that with high probability, each of the $x^{\prime}_j$ , $0 \leq j \leq \tau$ , is actually contained in K, so that the event E occurs. To establish this claim formally, let $A_{i,t}$ , where $1 \leq i \leq n$ and $1 \leq t \leq \tau$ , denote the number of times, up to time t, that an update along the coordinate direction i is performed in the above coupling (thus, $A_i = A_{i, \tau}$ ). Note that conditioned on the $A_{i,t}$ , the jth coordinate $x^{\prime}_{s,j}$ of $x^{\prime}_s$ has the distribution $N(v_j, A_{j,s}\sigma^2)$ . Further, if we have $\vert x^{\prime}_{s,j} - v_j\vert \leq 100 \sigma \ln n$ for all $1 \leq s \leq \tau$ and $1 \leq j \leq n$ , then the event E occurs. Using a union bound, we thus have

\begin{multline*} {\mathbb{P}}[\lnot E\, \big\vert\, A_{i,t}, \text{ where } 1\leq i \leq n, 1 \leq t \leq \tau]\\ \begin{aligned} &\leq \sum_{j = 1}^n\sum_{s = 1}^\tau {\mathbb{P}}[\vert x^{\prime}_{s,j} - v_j\vert > 100 \sigma \ln n\, \big\vert\, A_{i,t}, \text{ where } 1\leq i \leq n, 1 \leq t \leq \tau]\\ &= \sum_{j = 1}^n\sum_{s = 1}^\tau {\mathbb{P}}_{Z \sim N(v_j, A_{j,s}\sigma^2)}[\vert Z - v_j\vert > 100 \sigma \ln n]. \end{aligned} \end{multline*}

Now, using the fact that $A_{j,s} \leq A_j$ for all $1 \leq j \leq n$ and $1 \leq s \leq \tau$ , and then applying Fact A.2 to bound each term in the sum above, we get

(4.4) \begin{equation} {\mathbb{P}}[\lnot E\, \big\vert\, \forall 1\leq i \leq n, A_i \leq 50\ln n] \leq n\cdot\tau \cdot \exp\!\left({-\frac{100^2\,\sigma^2(\ln n)^2}{100 \, \sigma^2 \ln n}}\right) \leq n^{-90}. \end{equation}

Together, equations (4.2), (4.3) and (4.4) imply that

(4.5) \begin{equation} d_{TV}(\mathcal{G}_v^{(\tau)}, \mathcal{H}) \leq {\mathbb{P}}[\lnot E] \leq 1.5\, n^{-5}. \end{equation}

Finally, we note that

(4.6) \begin{equation} d_{TV}({\mathcal{H'}, \mathcal{H}}) \;\;\leq \sum_{\substack{\mathbb{I} \in \mathcal M_{n,\tau}\\\mathbb{I}\text{ not of full rank}}} \lambda_\mathbb{I} \;\; \leq \;\; n\cdot\left({1- \frac{1}{n}}\right)^\tau \leq n^{-19}. \end{equation}

The claim now follows from equations (4.5) and (4.6) and the triangle inequality for $d_{TV}$ .

• • $\|v - u\|_2 \leq \sigma,$

• • $\inf_{z \in \partial K} \|v - z\|_{\infty} > 100 \sigma \ln n,$ and

• • $\inf_{z \in \partial K} \|u - z\|_{\infty} > 100 \sigma \ln n.$

Define the measures $\mathcal{G}_u^{(\tau)}, \mathcal{G}_v^{(\tau)}$ and $\mathcal{G}_{u, \mathbb{I}},\mathcal{G}_{v, \mathbb{I}}$ as above, in terms of $N(0, \sigma^2)$ . Then,

$${d_{TV}}({\cal G}_v^{(\tau )},{\cal G}_u^{(\tau )}) \le {1 \over 2} + 4{n^{ - 5}} \le 3/4.$$

Proof. Let us fix an $\mathbb{I} \in \mathcal M_{n,\tau}$ such that $\mathbb{I}$ has full rank. As $\mathbb{I}$ has full rank, it follows that $\sigma^2I \preccurlyeq \Sigma_\mathbb{I}$ and $\Sigma_\mathbb{I}^{-1} \preccurlyeq \sigma^{-2}I$ . We then have

(4.7) \begin{equation} d_{TV}\left({\mathcal{G}_{v, \mathbb{I}}, \mathcal{G}_{u, \mathbb{I}}}\right) \leq \sqrt{\frac{1}{2}D_{KL}(\mathcal{G}_{v, \mathbb{I}}\Vert\mathcal{G}_{u, \mathbb{I}})} = \frac{1}{2}\sqrt{(v-u)^T\Sigma_{\mathbb{I}}^{-1}(v-u)} \leq \frac{1}{2\sigma}{\Vert {v-u} \Vert_{2}} \leq \frac{1}{2}. \end{equation}

Here, the first inequality is Pinsker’s inequality (see Fact A.3), the equality is a direct calculation of the Kullback–Leibler divergence between two Gaussian distributions with the same covariance matrix, and the second inequality is from the observation above that $\Sigma_\mathbb{I}^{-1} \preccurlyeq \sigma^{-2}I$ . On the other hand, from Lemma 4.1(applied separately to $\mathcal{G}_{u, \mathbb{I}}$ and $\mathcal{G}_{v, \mathbb{I}}$ ) and the triangle inequality for $d_{TV}$ , we have

$$d_{TV}\!\left({\mathcal{G}_{v, \mathbb{I}}, \mathcal{G}_{u, \mathbb{I}}}\right) \leq 4\, n^{-5} + \sum_{\substack{\mathbb{I} \in \mathcal M_{n,\tau}\\\mathbb{I}\text{ of full rank}}} \lambda_\mathbb{I} d_{TV}\left({\mathcal{G}_{u,\mathbb{I}}, \mathcal{G}_{v,\mathbb{I}}}\right).$$

The claim now follows from equation (4.7) since the sum of the $\lambda_\mathbb{I}$ over all $\mathbb{I}\in \mathcal M_{n,\tau}$ of full rank is at most 1.

It follows quite easily from Lemma 4.2 that the multi-step Gaussian chain has the overlap property discussed in Section 3. In the next section, we discuss this in more detail, and compare the Gaussian chain with the CHR chain to obtain a lower bound on the s-conductance of the latter.

5. The s-conductance of CHR

Our goal in this section is to the give a lower bound on the s-conductance of the CHR chain, by comparing it with the Gaussian chain studied in the previous section.

Let the Markov scheme corresponding to CHR be denoted by $\mathcal{C}$ . We also carry forward the notation $\mathcal{G}$ and $\mathcal{G}^{(\tau)}$ for the Gaussian scheme and its iterates, respectively, introduced in the previous section.

Lemma 5.1 There are universal constants $C> 1$ and $0 < c < 1$ such that the following is true. Let $\sigma > 0, n \geq 2, \tau = \tau(n) = {\left\lceil{20n\ln n}\right\rceil}$ be as in the statement of Lemma 4.1, and let $K \in {\mathbb R}^n$ be a convex body such that for some $R \geq 1$ , it is the case that $B_\infty \subseteq K \subseteq R\cdot B_\infty$ . Set ${\epsilon} \,:\!=\, Cn\sigma\ln n$ , and assume that $\sigma$ is chosen so that $\epsilon, \sigma < 1/2$ . Define the chain $\mathcal{G}^{(\tau)}$ as in Section 4, in terms of $N(0, \sigma^2)$ . Then, for any measurable set S contained in K, such that ${\epsilon} < \pi_K(S)$ we have

$${\Phi _{{{\cal G}^{(\tau )}},{\pi _K}}}(S,K - S) \ge \left( {{{c\sigma } \over {R\sqrt n }}} \right)\left( {\min \left\{ {{\pi _K}(S),{\pi _K}(K - S)} \right\} - } {\epsilon} \right).$$

Proof. Recall from Definition 3.1 that a Markov scheme $\mathcal P$ on K is said to have the $(\epsilon, \delta, \nu)$ -overlap property with respect to K $^{\prime}$ if K $^{\prime}$ is a measurable convex subset of K such that (i) ${\mathrm{vol}\left({{K'}}\right)} \geq {\mathrm{vol}\left({{K}}\right)}(1 - \epsilon)$ , and further, (ii) for all $u, v \in K'$ satisfying ${\Vert {u - v} \Vert_{2}} \leq \delta$ , we have

$${d_{TV}}({\cal P}(u,\cdot),{\cal P}(v,\cdot)) \le 1 - \nu .$$

Set $C = 100$ . Now, from Proposition 2.4, we see that ${\mathrm{vol}\left({{K_{C\sigma\ln n}}}\right)} \geq (1-C\sigma\ln n)^n{\mathrm{vol}\left({{K}}\right)} \geq (1-\epsilon){\mathrm{vol}\left({{K}}\right)}$ . On the other hand, Lemma 4.2 implies that for any $u, v \in K_{C\sigma\ln n}$ such that ${\Vert {u - v} \Vert_{2}} \leq \sigma$ , we have $d_{TV}\left({\mathcal{G}^{(\tau)}(u, \cdot), \mathcal{G}^{(\tau)}(v, \cdot)}\right) \leq 3/4$ . It follows that $\mathcal{G}^{(\tau)}$ has the $({\epsilon} , \sigma, 1/4)-$ overlap property with respect to $K_{C\sigma \ln n}$ .

Now, we apply Lemma 3.2 to the Markov scheme $G^{(\tau)}$ to see that (note that the ${\Vert {\cdot} \Vert_{2}}$ -diameter of K is at most $2R\sqrt{n}$ )

$${\Phi _{{{\cal G}^{(\tau )}},{\pi _K}}}(S,K - S) \ge \left( {{\sigma \over {32R\sqrt n }}} \right)\left( {\min \left\{ {{\pi _K}(S),{\pi _K}(K - S)} \right\} - } {\epsilon} \right).$$

Setting $c = 1/32$ gives us the lemma.

To use the above result for obtaining a lower bound on the s-conductance of the CHR chain, we need the following simple observation comparing the ergodic flows of the single step CHR chain and the single step Gaussian chain (note that what was analysed in the previous lemma was an iterate of the latter).

Observation 5.2 Let $\sigma > 0, n \geq 2, \tau = \tau(n) = {\left\lceil{20 n \ln n}\right\rceil}\!, R \geq 1$ and the convex body $K \in {\mathbb R}^n$ be as in the statement of Lemma 5.1. Define the Gaussian scheme $\mathcal{G}$ as in Section 4, in terms of $N(0, \sigma^2)$ . Then, for any measurable subset S of K, we have

$${\Phi _{{\cal C},{\pi _K}}}(S,K - S) \ge {{\sigma \sqrt \pi } \over {R\sqrt 2 }}\cdot{\Phi _{{\cal G},{\pi _K}}}(S,K - S).$$

Proof. The measures $\mathcal{G}_x$ and $\mathcal{C}_x$ corresponding to transitions from any point $x \in S$ for the two schemes $\mathcal{G}$ and $\mathcal{C}$ , respectively, are absolutely continuous with respect to each other at all points $y \neq x$ (in particular, for all $y \in K - S$ ) in the support $\mathrm{supp}(\mathcal{G}_x)$ of $\mathcal{G}_x$ . Further, the Radon–Nikodym derivative of $\mathcal{C}_x$ with respect to $\mathcal{G}_x$ at any $y \neq x$ in $\mathrm{supp}(\mathcal{G}_x)$ is bounded below by $(\sqrt{2\pi} \sigma/(2R))$ . The claim now follows by integration.

We now have all the ingredients to give a lower bound on the s-conductance of the CHR chain.

Lemma 5.3 Let $n \geq 2, R \geq 1$ and the convex body $K \in {\mathbb R}^n$ be as in the statement of Lemma 5.1. Then, for any s satisfying $0 < s < 1/2$ , the s-conductance $\Phi_s$ of the CHR chain $\mathcal{C}$ on K satisfies

$${\Phi _s}{\mkern 1mu} : = {\mkern 1mu} \mathop {\inf }\limits_{A\;:\;s < {\pi _K}(A) \le 1/2} {{{\Phi _{{\cal C},{\pi _K}}}(A)} \over {{\pi _K}(A) - s}} \ge \Omega \left( {{{{s^2}} \over {{R^2}{n^{3.5}}{{\ln }^3}n}}} \right).$$

Here, the constants implicit in the $\Omega(\!\cdot\!)$ notation are independent of n, R and K.

Proof. Let the constants C and c be as in the statement of Lemma 5.1. Set $\sigma = s/(Cn \ln n) \leq 1/2$ , so that the quantity $\epsilon$ in Lemma 5.1 satisfies $\epsilon = s < 1/2$ . Let $\tau(n) = {\left\lceil{20n \ln n}\right\rceil}$ , and define the schemes $\mathcal{G}$ and $\mathcal{G}^{(\tau)}$ in terms of $N(0, \sigma^2)$ , again as in the statement of Lemma 5.1.

Let S be an arbitrary measurable subset of K. Consider the following experiment. Let $x_0$ be sampled from $\pi_K$ , and let $x_0, x_1, \dots, x_\tau$ be a walk of length $\tau$ according to the scheme $\mathcal{G}$ . For $0 \leq i < \tau$ , let $E_i$ denote the event that $x_i \in S$ and $x_{i+1} \in K - S$ . Similarly, let E denote the event that $x_0 \in S$ and $x_\tau \in K - S$ . Note that ${\mathbb{P}}[E] \leq \sum_{i=0}^{\tau-1}{\mathbb{P}}[E_i]$ . On the other hand, since $\mathcal{G}$ is reversible with respect to $\pi_K$ , we have $x_i \sim \pi_K$ for each $0 \leq i < \tau$ , so that ${\mathbb{P}}[E_i] = \Phi_{\mathcal{G}, \pi_K}(S, K - S)$ . Similarly, ${\mathbb{P}}[E] = \Phi_{\mathcal{G}^{(\tau)}, \pi_K}(S, K - S)$ . Thus, we get that

(5.1) \begin{equation} \Phi_{\mathcal{G}, \pi_K}(S, K - S) \geq \frac{1}{\tau}\cdot \Phi_{\mathcal{G}^{(\tau)}, \pi_K}(S, K - S). \end{equation}

Combining this with Observation 5.2, we therefore obtain

(5.2) \begin{equation} \Phi_{\mathcal{C}, \pi_K}(S, K - S) \geq \frac{c'\sigma}{\tau R} \Phi_{\mathcal{G}^{(\tau)}, \pi_K}(S, K - S), \end{equation}

where c $^{\prime}$ is an absolute positive constant.

Finally, applying Lemma 5.1, we then see that for any measurable subset ${S \subset K}$ such that $\pi(S) > s$ , we have

(5.3) \begin{equation} \Phi_{\mathcal{G}^{(\tau)}, \pi_K}(S, K - S) \geq \left(\frac{c\sigma}{R\sqrt{n}}\right) \left(\min\left\{{\pi_K(S), \pi_K(K-S)}\right\} - s\right). \end{equation}

Combining this with equation (5.2), we see that for every measurable $S \subseteq K$ such that $s < \pi_K(S) \leq 1/2$ , we have

(5.4) \begin{align} \Phi_{\mathcal{C}, \pi_K}(S, K - S) & \geq \left(\frac{c\cdot c' \cdot \sigma^2}{\tau \cdot R^2\sqrt{n}}\right) \left(\min\left\{{\pi_K(S), \pi_K(K-S)}\right\} - s\right) \nonumber\\ & \geq \left(\frac{c'' s^2}{R^2 n^{3.5} \ln^3 n}\right) \left({\pi_K(S) -s}\right), \end{align}

where c $^{\prime\prime}$ is an absolute positive constant. The claim follows immediately from equation (5.4).

6. Mixing time of CHR

We now restate and prove our main theorem (Theorem 1.1). Given the lower bound on the s-conductance of the CHR scheme derived in Lemma 5.3, the proof follows immediately from Theorem 2.1

Proof. Let $0 < s < 1/2$ be arbitrary. We apply Theorem 2.1 to the CHR scheme $\mathcal{C}$ and its stationary distribution $\pi_K$ . Let $H_s$ be as defined in Theorem 2.1. The absolute continuity constraint imposed on $\mu_0$ with respect to $\pi_K$ then implies that $H_s \leq M\cdot s$ . Let $\mu_k$ denote the distribution after k iterations of $\mathcal{C}$ starting with the initial distribution $\mu_0$ . Theorem 2.1, along with the bound on $\Phi_s(\mathcal{C})$ obtained in Lemma 5.3 then implies that (for some absolute constant c)

$${d_{TV}}({\mu _{k,{\cal C}}},{\pi _K}) \le Ms + M\exp \left( {{{ - ck{s^4}} \over {{R^4}{n^7}{{\ln }^6}n}}} \right).$$

Choosing $s = \epsilon/(2M)$ , we then see that for any $k \geq {\left\lceil{\frac{16 M^4 R^4n^7 \ln^6 n\ln(2M/\epsilon)}{c{\epsilon}^4}}\right\rceil}$ , we have $d_{TV}(\mu_{k, \mathcal{C}}, \pi_K) \leq {\epsilon}.$