# Concentration inequalities for some negatively dependent binary random
variables

Radosław Adamczak  and  Bartłomiej Polaczyk  Institute of Mathematics,
University of Warsaw, Poland  R.Adamczak, B.Polaczyk @mimuw.edu.pl

(Date: Last changes: )

###### Abstract.

We investigate concentration properties of functions of random vectors with
values in the discrete cube, satisfying the stochastic covering property (SCP)
or the strong Rayleigh property (SRP).

Our result for SCP measures include subgaussian inequalities of bounded-
difference type extending classical results by Pemantle and Peres and their
counterparts for matrix-valued setting strengthening recent estimates by Aoun,
Banna and Youssef. Under a stronger assumption of the SRP we obtain Bernstein-
type inequalities for matrix-valued functions, generalizing recent bounds for
linear combinations of positive definite matrices due to Kyng and Song.

We also treat in detail the special case of independent Bernoulli random
variables conditioned on their sum for which we obtain strengthened estimates,
deriving in particular modified log-Sobolev inequalities, Talagrand’s convex
distance inequality and, as corollaries, concentration results for convex
functions and polynomials, as well as improved estimates for matrix-valued
functions. These results generalize inequalities for the uniform measure on
slices of the discrete cube, studied extensively by many authors. Our approach
is based on recent results by Hermon and Salez and a general framework
involving modified log-Sobolev inequalities on the discrete cube, which is of
independent interest.

Keywords: concentration of measure, strong Rayleigh measure, stochastic
covering property

AMS Classification: 60E15, 60B20, 60J28

Research partially supported by the National Science Centre, Poland, via the
Sonata Bis grant no. 2015/18/E/ST1/00214 (RA) and the Preludium grant no.
2020/37/N/ST1/02667 (BP)

##  1\. Introduction

Investigating families of binary random variables with negatively dependent
coordinates is an important problem from the point of view of computer science
and combinatorics, which in the recent years has attracted considerable
attention, see, e.g., [43, 49, 14, 44, 34, 26, 10, 6, 8, 32]. A wide and
important class of such variables is constituted by those satisfying the
strong Rayleigh property (abbrev. SRP) introduced by Borcea et al. [14]. More
precisely, a probability measure $\pi$ on the hypercube
$\operatorname{\mathcal{B}_{n}}:=\\{0,1\\}^{n}$ satisfies the SRP if its
generating polynomial

$\mathbb{C}^{n}\ni
z\mapsto\sum_{x\in\operatorname{\mathcal{B}_{n}}}\pi(x)\prod_{i=1}^{n}z_{i}^{x_{i}}$

has no roots $z$ whose all coordinates lie in the (strict) upper half-plane.
The examples of such measures are, e.g., the law of independent Bernoulli
random variables conditioned on their sum, determinantal measures, uniform
measure on the bases of balanced matroids, laws of point processes or measures
obtained by running exclusion dynamics on the cube, cf. Pemantle and Peres
[44].

The main purpose of this article is to deepen the understanding of the
concentration of measure phenomenon in the context of strong Rayleigh
distributions and related classes of probability measures on the discrete
cube. In some of our considerations we will exploit only a more general notion
of the stochastic covering property (abbrev. SCP, cf. Definition 2.1)
introduced by Pemantle and Peres [44], since this condition already turns out
to provide a useful framework for proving concentration results [44, 29, 8,
34, 32, 2]. On the other hand for some more specialized inequalities we will
restrict our attention to independent Bernoulli variables conditioned on their
sum taking some fixed value. Distributions of this type generalize the uniform
measure on slices of the discrete cube, related to the Bernoulli–Laplace
model, which has been extensively studied, e.g., by Lee–Yau, Bobkov–Tetali,
Gao–Quastel [37, 13, 25] and more recently by Samson [48] and Sambale–Sinulis
[46]. The non-uniform distribution given by conditioned Bernoulli variables
has found applications, e.g., in survey sampling being a model of sampling
without replacement from a finite population, with prescribed inclusion
probabilities, which maximizes the entropy (often referred to as _conditional
Poisson sampling_). We refer to [20, 19, 21, 52, 10] for properties and
applications of this family of distributions.

###  1.1. State of the art

The landmark paper that initiated the study of concentration phenomenon
implied by the SCP is due to Pematle and Peres [44] who, using the martingale
method, proved a sub-Gaussian concentration bound for measures satisfying the
SCP and functions that are Lipschitz with respect to the Hamming distance
$d_{H}(x,y)=\sum_{i}\mathbf{1}_{x_{i}\neq y_{i}}$. Recently, Hermon and Salez
[29], building on the works [40, 31], retrieved this estimate by proving that
the SCP implies the modified log-Sobolev inequality.

These findings in terms of concentration of measure can be summarized as
follows (we use the notation $\pi(f):=\int f\,d\pi$ for a probability measure
$\pi$ on $\operatorname{\mathcal{B}_{n}}$ and
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$).

######  Theorem 1.1 (Pemantle–Peres [44]).

For a probability measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfying
the SCP and any $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ such that

$|f(x)-f(y)|\leq d_{H}(x,y)\quad\forall\,x,y\in\operatorname{\mathcal{B}_{n}}$

the following estimate holds for all $t>0$

(1.1) $\pi\big{(}f>\pi(f)+t\big{)}\leq\exp(-t^{2}/8n).$

If $\pi$ is $k$-homogeneous (i.e., it is supported on the set of binary
vectors with exactly $k$ coefficients equal to one), then $n$ in the above
expression can be replaced with $k$.

Recently, a sub-exponential version of Theorem 1.1 for matrix-valued functions
has been shown by Aoun et al. [8], who develop a general framework for
deducing concentration bounds for matrix-valued functions from the Poincaré
inequality. A Bernstein-type bound for measures with the SRP, which in certain
situations may give stronger concentration, has been also developed by Kyng
and Song [34] for functions of the form $f(x)=\sum_{i=1}^{n}x_{i}C_{i}$, where
$C_{i}$ are nonnegative definite matrices (see Theorem 2.8 and Remark 2.10
below).

While concentration estimates and functional inequalities for general SCP
measures are relatively recent, investigation of uniform measures on slices of
the discrete cube in this context has much longer history. Such measures are
of interest in relation to the Bernoulli–Laplace models of statistical physics
and with uniform sampling without replacement. In particular Lee and Yau
studied the Poincaré and log-Sobolev inequalities for such measures, whereas
Bobkov–Tetali [13] and independently Gao–Quastel [25] investigated modified
log-Sobolev inequalities relevant for concentration estimates. Strong
concentration results for this case can be also obtained by projection from
Talagrand’s convex distance inequality for uniform measure on the symmetric
group [51]. Samson [48] complemented this approach by proving corresponding
transportation inequalities. Very recently Sambale and Sinulis [46],
investigating general multislices, recovered convex distance inequalities by
means of functional inequalities and also obtained concentration for
polynomials. One should stress that concentration results for slices of the
cube provided by the above references are substantially stronger than those
coming from more general inequalities for SCP or SRP measures.

The uniform measure on slices of the cube can be seen as a special case of the
distribution of independent Bernoulli random variables conditioned on their
sum, when all the variables have the same probability of success. Such general
distributions are known to be strong Rayleigh. To our best knowledge there has
not been much work concerning refined concentration inequalities for general
measures of this type. The only exception we are aware of is a recent article
[10] by Bertail and Clémençon in which the authors, motivated by applications
to survey sampling, obtain precise Bernstein-type inequalities for linear
functionals.

###  1.2. Our contribution

We develop two types of results.

Firstly, for general measures satisfying the SCP we extend the martingale
argument from Pemantle and Peres [44] and generalize Theorem 1.1 to Lipschitz
functions with respect to more general weighted Hamming distances
$d_{\alpha}(x,y)=\sum\alpha_{i}\mathbf{1}_{x_{i}\neq y_{i}}$ obtaining a
bounded-difference type inequality. We use the approach developed for the
scalar case together with matrix bounded-difference inequality due to Tropp
[54] to get an analogous concentration for matrix-valued functions,
strengthening the results of Aoun et al. [8], in particular obtaining a
subgaussian inequality in place of a subexponential one. Under a stronger
assumption of the SRP we are also able to strengthen the Bernstein-type
inequality of Kyng and Song and extend it from linear combinations with
coefficients in nonnegative definite matrices to general functions satisfying
a matrix bounded-difference type assumptions.

Secondly, building up on the work of Hermon and Salez [29], we develop an
abstract condition which implies Talagrand’s convex distance inequality,
matrix-Bernstein inequality and higher order concentration for tetrahedral
polynomials. Finally, we prove that this condition is satisfied for the
distribution of Bernoulli random variables conditioned on their sum being
equal to some constant, yielding all the aforementioned results in this case.

###  1.3. Organization of the article

In Section 2 we present our results concerning concentration for general
measures satisfying the SCP/SRP. In Section 3 we specialize our analysis to
Bernoulli random variables conditioned on their sum being equal to some
constant. Then, in Section 4 we formulate an abstract framework that allows to
deduce the results of Section 3. Finally, all the proofs are presented in
Sections 5, 6 and 7.

##  2\. Concentration under the SCP and SRP

In this section we present our concentration results for general measures
satisfying the SCP or SRP. Let us start with introducing some notation. For
$x=(x_{1},\ldots,x_{n})\in\operatorname{\mathcal{B}_{n}}:=\\{0,1\\}^{n}$ and
any $S\subset\\{1,2,\ldots,n\\}=:[n]$ we use the shorthand notation
$x_{S}=(x_{i})_{i\in S}$. For any $r\in[n]$ we denote $x_{>r}=(x_{i})_{i>r}$
(and analogously with relations other than $>$)111We adopt the convention that
if $x\in\operatorname{\mathcal{B}_{n}}$ then $x_{>n}=\emptyset$ and as a
consequence, e.g.,
$\mathbb{P}\left(\cdot\,|\,X_{>n}=\emptyset\right)=\mathbb{P}\left(\cdot\right)$..
We also write $x^{i}$ for the vector obtained from
$x\in\operatorname{\mathcal{B}_{n}}$ by flipping its i-th coordinate and
$x^{ij}$ for the vector obtained by swapping the $i$-th and $j$-th coordinate,
i.e., $x^{i}=x\pm e_{i}$ and if $x_{i}\neq x_{j}$ then $x^{ij}=x\pm e_{i}\mp
e_{j}$ for $i,j\in[n]$, where $e_{i}\in\operatorname{\mathcal{B}_{n}}$ is the
vector with one on the $i$-th and zeros on the remaining coordinates; whereas
$x^{ij}=x$ if $x_{i}=x_{j}$. We remark that the notation $x^{ij}$ should not
be confused with $(x^{i})^{j}$. The law of a random variable $X$ is denoted by
$\mathcal{L}(X)$, whereas $\mathcal{L}(X|A)$ stands for the conditional law of
$X$ given an event $A$ (with an analogous convention for conditioning with
respect to $\sigma$-fields or other random variables).

Below, we recall the definition of the SCP.

######  Definition 2.1 (Stochastic covering property).

For $x,y\in\operatorname{\mathcal{B}_{n}}$, we say that $x$ covers $y$,
denoted $x\triangleright y$, if $x=y$ or $x=y+e_{i}$ for some $i\in[n]$.

A random variable $X$ taking values in $\operatorname{\mathcal{B}_{n}}$
satisfies the SCP if for any $S\subset[n]$ and any
$x,y\in\operatorname{\mathcal{B}_{n}}$ satisfying $x_{S}\triangleright y_{S}$
there exists a coupling $(U,V)$ between the conditional distributions
$\mathcal{L}(X_{S^{c}}\,|\,X_{S}=y_{S})$ and
$\mathcal{L}(X_{S^{c}}\,|\,X_{S}=x_{S})$ such that $U\triangleright V$. A
measure $\pi$ satisfies the SCP if $X$ with law $\pi$ does so.

######  Remark 2.2.

As indicated in the introduction, the SCP is implied by the SRP, cf. [44]. The
opposite however is not true, as is demonstrated, e.g., by Cryan et al. in
[22, Appendix A], where the authors show that yet another possible
generalization of the SRP, the strong log-concavity, is incomparable with the
SCP. In particular, they construct a distribution that is supported on the
bases of a matroid, and that satisfies the SCP and violates the log-concavity
(and whence the SRP as well).

For a finite sequence $x$, we denote by $x^{\downarrow}$ the non-increasing
rearrangement of the elements of $x$ and for
$\alpha\in[0,\infty)^{n}=:\mathbb{R}_{+}^{n}$ and
$x,y\in\operatorname{\mathcal{B}_{n}}$ we define the $\alpha$-weighted Hamming
distance $d_{\alpha}(x,y)=\sum_{i}\alpha_{i}\mathbf{1}_{x_{i}\neq y_{i}}$.
Finally, for $p\in[1,\infty]$, $|\cdot|_{p}$ is the $\ell_{p}$ norm on
$\mathbb{R}^{n}$ and $|\cdot|:=|\cdot|_{2}$ denotes the Euclidean norm.

The first main result of this paper is the following generalization of Theorem
1.1.

######  Theorem 2.3.

For a probability measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfying
the SCP, any $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ and
$\alpha\in\mathbb{R}_{+}^{n}$ such that

$|f(x)-f(y)|\leq
d_{\alpha}(x,y)\quad\forall\,x,y\in\operatorname{\mathcal{B}_{n}}$

the following estimate holds for all $t>0$:

$\displaystyle\pi\big{(}f>\pi(f)+t\big{)}\leq\exp(-t^{2}/8|\alpha|^{2}).$

If $\pi$ is $k$-homogeneous then $8|\alpha|^{2}$ in the above estimate can be
replaced with $16\sum_{i=1}^{k}(\alpha_{i}^{\downarrow})^{2}$.

######  Remark 2.4.

Theorem 2.3 implies Theorem 1.1 (up to an absolute constant in the exponent)
by taking $\alpha=(1,1,\ldots,1)$. Moreover, by considering functions of the
form $f(x)=\sum_{i}c_{i}x_{i}$ with $|c|^{2}\ll n|c|^{2}_{\infty}$ in the non-
homogeneous or $\sum_{i=1}^{k}(c_{i}^{\downarrow})^{2}\ll k|c|^{2}_{\infty}$
in the $k$-homogeneous case, one can see that Theorem 2.3 can give
substantially better concentration estimates than Theorem 1.1.

We now formulate the matrix analogue of Theorem 2.3. To this end, let us
denote the space of $d$-dimensional Hermitian matrices by
$\operatorname{\mathcal{H}_{d}}$, the identity matrix in
$\operatorname{\mathcal{H}_{d}}$ by $I_{d}$, the maximal eigenvalue of
$H\in\operatorname{\mathcal{H}_{d}}$ by $\lambda_{max}(H)$ and the operator
norm of $H$ by $\|H\|$.

######  Theorem 2.5.

For a probability measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfying
the SCP, any
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ and
$\alpha\in\mathbb{R}^{n}_{+}$ such that

(2.1) $\displaystyle\|f(x)-f(y)\|\leq
d_{\alpha}(x,y)\quad\forall\,x,y\in\operatorname{\mathcal{B}_{n}}$

the following estimate holds for all $t>0$

$\displaystyle\pi\big{(}\lambda_{max}(f-\pi(f))>t\big{)}\leq
d\exp(-t^{2}/32|\alpha|^{2}).$

If $\pi$ is $k$-homogeneous then $32|\alpha|^{2}$ in the above estimate can be
replaced with $64\sum_{i=1}^{k}(\alpha_{i}^{\downarrow})^{2}$.

######  Remark 2.6.

Recently, Aoun et al. [8] showed that for any $k$-homogeneous probability
measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfying the SCP and any
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ such
that

$\|f(x)-f(y)\|\leq
d_{H}(x,y)\quad\forall\,x,y\in\operatorname{\mathcal{B}_{n}}$

the following estimate applies

(2.2) $\pi\big{(}\lambda_{max}(f-\pi(f))>t\big{)}\leq
d\exp\Big{(}-\frac{t^{2}}{8k+2t\sqrt{2k}}\Big{)}.$

The exponent in (2.2) is proportional to $-t/2\sqrt{2k}$ for $t$ big enough
and whence for such $t$ Theorem 2.5 applied with $\alpha=(1,\ldots,1)$
strengthens on (2.2) (and on an analogous result from [32]) as it yields a
sub-Gaussian estimate.

######  Remark 2.7.

Using semigroup techniques together with matrix concentration results implied
by the Poincaré inequality due to Aoun et al. [8], we are also able to derive
a sub-exponential concentration inequality for general measures satisfying the
SCP under weaker assumptions on $f$ than those of Theorem 2.5, cf. Remark 3.7.

When comparing the inequality of Theorem 2.5 or the results from [8] with
results for matrix-valued functions of independent random variables, one can
ask if it is possible to weaken the assumptions on the function $f$ and
instead of the Lipschitz constant with respect to $d_{\alpha}$ use some weaker
parameter, involving bounds on the increments of the function in terms of the
positive semidefinite order. In many situations one encounters functions for
which $(f(x)-f(x^{i}))^{2}\preccurlyeq C_{i}^{2}$ where $C_{i}$ are some
positive semidefinite matrices and $\preccurlyeq$ stands for the positive
semidefinite order (note that considering arbitrary matrices $C_{i}$ is a
generalization of the condition (2.1), which corresponds to the special case
$C_{i}^{2}=\alpha_{i}^{2}I_{d}$). The simplest, yet important situation of
this type is given by $f(x)=\sum_{i=1}^{n}x_{i}C_{i}$. Inequalities for such
functions together with algorithmic applications were considered by Kyng and
Song in [34]. It turns out that their approach can be adapted to the setting
of general functions, yielding the following theorem.

######  Theorem 2.8.

Let $\pi$ be a $k$-homogeneous probability measure
$\operatorname{\mathcal{B}_{n}}$ satisfying the strong Rayleigh property and
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ be
such that there exists a sequence
$C_{1},\ldots,C_{n}\in\operatorname{\mathcal{H}_{d}}$ satisfying

(2.3) $\displaystyle(f(x)-f(x^{i}))^{2}\preccurlyeq
C_{i}^{2}\quad\forall\,x\in\operatorname{\mathcal{B}_{n}},\,i\in[n].$

Then for any $t>0$,

(2.4) $\pi\big{(}\lambda_{max}(f-\pi(f))>t\big{)}\leq
d\exp\Big{(}-\frac{t^{2}}{8\|\pi(\tilde{f})\|\log(ek)+\frac{4}{3}Kt}\Big{)},$

where $\tilde{f}(x)=\sum_{i=1}^{n}x_{i}C^{2}_{i}$ and $K=\max_{i\leq
n}\|C_{i}\|$.

######  Remark 2.9.

In fact, the only place in the proof of Theorem 2.8 where we use the SRP in
its full strength is to get that
$\operatorname{\mathbb{P}}(X_{i}=1\,|\,X_{i_{1}}=1,\ldots,X_{i_{l}}=1)\leq\operatorname{\mathbb{P}}(X_{i}=1)$
for $X\sim\pi$ and any $i,k\in[n]$ and
$i_{1},\ldots,i_{k}\subset[n]\setminus\\{i\\}$. Therefore, in Theorem 2.8 it
suffices to assume that $\pi$ satisfies the SCP and negative association,
which is implied by the SRP, cf. [44].

######  Remark 2.10.

It is natural to expect that $\log(ek)$ in (2.4) is just an artefact of the
proof. Removing it even just for functions of the form
$f(x)=\sum_{i=1}^{n}x_{i}C_{i}$ for positive semidefinite matrices $C_{i}$
would lead to improvement of certain algorithmic constructions related to
graph sparsifiers obtained via random spanning trees, cf. [34].

Let us also point out that even though Theorem 2.8 applies to general
functions, when specialized to the function $f$ as discussed above, it
improves slightly on the results from [34], which instead of
$\|\pi(\tilde{f})\|$ use a larger quantity $K\|\pi(\hat{f})\|$ with
$\hat{f}(x)=\sum_{i=1}^{n}x_{i}C_{i}$ (recall that $C_{i}$’s are nonnegative
definite). One should stress however that we rely on the approach worked out
in [34].

##  3\. Concentration for conditional Bernoullis

In this section, we present our concentration results concerning Bernoulli
random variables conditioned on their sum being constant. These include
Talagrand’s convex distance inequality, matrix-Bernstein inequality and
concentration for polynomials.

We start with introducing the notation. For a sequence
$p=(p_{1},\ldots,p_{n})\in(0,1)^{n}$, let $B=(B_{1},\ldots,B_{n})$ be a
sequence of independent Bernoulli random variables with probabilities of
success $p_{i}$, i.e.,
$\operatorname{\mathbb{P}}(B_{i}=1)=1-\operatorname{\mathbb{P}}(B_{i}=0)=p_{i}$
for $i\in[n]$. Finally, set
$X=(X_{1},\ldots,X_{n})\sim\mathcal{L}\big{(}B\,|\sum_{i}B_{i}=k\big{)}$ for
some $k\in\\{0,\ldots,n\\}$ and denote the distribution of $X$ by $\pi(p,k)$.

Our first contribution is a counterpart of the celebrated convex distance
inequality, introduced for the first time by Talagrand [50] for product
measures on the cube.

######  Theorem 3.1.

If $\pi\sim\pi(p,k)$ for some $p\in(0,1)^{n}$ and $k\in\\{0,\ldots,n\\}$, then
for any $A\subset\operatorname{\mathcal{B}_{n}}$,

$\pi(A)\pi\big{(}d_{T}^{2}(\cdot,A)/84\big{)}\leq 1,$

where

$d_{T}(x,A)=\sup_{\alpha\colon|\alpha|\leq
1}d_{\alpha}(x,A)\quad\text{for}\quad
x\in\operatorname{\mathcal{B}_{n}},\,A\subset\operatorname{\mathcal{B}_{n}}.$

Let $\mathbb{M}_{\pi}f$ denote any median of $f$ with respect to the measure
$\pi$. A classical consequence of Theorem 3.1 is the following fact regarding
the concentration around the median of convex functions [17]. Let us recall
the classical observation that subgaussian concentration around median and
mean for convex Lipschitz functions are equivalent up to the change of
constants by a universal factor.

######  Corollary 3.2.

If $\pi\sim\pi(p,k)$ for some $p\in(0,1)^{n}$ and $k\in\\{0,\ldots,n\\}$, then
for any convex function $f\colon\mathbb{R}^{n}\to\mathbb{R}$ that is
$L$-Lipschitz with respect to the standard Euclidean distance on
$\mathbb{R}^{n}$ and any $t>0$,

$\pi\big{(}|f-\mathbb{M}_{\pi}f|>t\big{)}\leq
4\exp\big{(}-t^{2}/84L^{2}\big{)}.$

######  Remark 3.3.

If one is interested just in the lower tail of a convex function, then one can
in fact replace the Lipschitz constant $L$ by $\pi\big{(}|\nabla f|\big{)}$ or
even certain quantiles of $|\nabla f|$. We do not pursue this direction here
and refer the reader to [3].

######  Remark 3.4.

If $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ is $d_{\alpha}$
1-Lipschitz, then it can be extended to a function on $\mathbb{R}^{n}$ which
is $|\alpha|$-Lipschitz with respect to the standard Euclidean distance.
Therefore, Corollary 3.2 counterparts Theorem 2.3 in the sense that it yields
the same concentration profile while allowing for a weaker Lipschitz condition
on $f$ at the cost of assuming convexity.

Our next result concerns concentration for matrix-valued functions under
weaker assumptions than those in Theorem 2.5.

######  Theorem 3.5.

Let $\pi\sim\pi(p,k)$ for some $p\in(0,1)^{n}$ and $k\in\\{0,\ldots,n\\}$.
Assume that
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ is
such that there is a sequence of positive semidefinite matrices
$C_{1},\ldots,C_{n}$ satisfying

(3.1) $(f(x)-f(x^{i}))^{2}\preccurlyeq
C_{i}^{2},\quad\forall\;x\in\operatorname{\mathcal{B}_{n}},\,i\in[n],$

where $\preccurlyeq$ denotes the partial ordering of the set of positive
semidefinite matrices. Define the variance proxy

$\sigma^{2}=16\sup\Big{\\{}\,\big{\|}\sum_{i\in\mathcal{I}}C_{i}^{2}\big{\|}\,\colon\,|\mathcal{I}|=k,\,\mathcal{I}\subset[n]\,\Big{\\}}.$

Then for any $t>0$,

$\pi\big{(}\lambda_{max}(f-\mu(f))>t\big{)}\leq
d\exp\big{(}-t^{2}/(\sigma^{2}+{\sigma}t)\big{)}.$

######  Remark 3.6.

Condition (3.1) implies that $f$ is 1-Lipschitz with respect to the distance
$d_{\alpha}$ with $\alpha_{i}={\|C_{i}\|}$. On the other hand, for many
choices of matrices $C_{1},\ldots,C_{n}$ it happens that
$\sigma^{2}\ll\sum_{i=1}^{k}\big{(}\|C_{i}\|^{2}\big{)}^{\downarrow}$ as
$n,k\to\infty$. Therefore, while yielding only sub-exponential concentration
as opposed to the sub-Gaussian one given by Theorem 2.5, Theorem 3.5 may
improve significantly on Theorem 2.5 through better parameters in the
exponent.

######  Remark 3.7.

By an adaptation of the proof of Theorem 3.5, one can obtain a similar result
for general $k$-homogeneous measures satisfying the SCP condition with the
variance proxy parameter

$\sigma^{2}=8\sup\Big{\\{}\,\big{\|}{\sum_{i\in\mathcal{I}}C_{i}^{2}}\big{\|}+k\max_{i\notin\mathcal{I}}\big{\|}{C_{i}^{2}}\big{\|}\colon|\mathcal{I}|\leq
k,\,\mathcal{I}\subset[n]\,\Big{\\}}.$

Finally, let us turn to the higher order concentration. By the Fourier–Walsh
expansion (see e.g., [41]), every function
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ can be written in a
unique way as a tetrahedral polynomial, i.e., a polynomial which is affine
with respect to every variable (in particular the degree of the polynomial is
at most $n$). Therefore in what follows we restrict our attention to this
representation. In particular, when we speak about the gradient $\nabla
f=(\partial_{1}f,\ldots,\partial_{n}f)$ or higher order derivatives
$\nabla^{k}f$, we always think of the usual derivatives of the polynomial
function on $\mathbb{R}^{n}$ given by the tetrahedral representation of $f$
(sometimes referred to as the harmonic extension of $f$). We remark that the
directional derivatives $\partial_{i}f$ coincide on
$\operatorname{\mathcal{B}_{n}}$ with the discrete derivatives of $f$ given by
$D_{i}f(x)=f(\max(x,x^{i}))-f(\min(x,x^{i}))$, where the maximum and minimum
are taken coordinatewise.

In order to formulate concentration of measure estimates for tetrahedral
polynomials, we need to introduce a family of injective tensor product norms
on $d$-index matrices ($d$-tensors). Let us recall the notation introduced by
Latała in [35].

Let $|I|$ be the cardinality of a set $I$ and for ${\bf
i}=(i_{1},\ldots,i_{d})\in[n]^{d}$ let $|{\bf i}|=\max_{j\leq d}{i_{j}}$ and
$|{\bf i}_{I}|=\max_{j\in I}i_{j}$. Denote by $P_{d}$ the set of partitions of
$[d]$ into nonempty, pairwise disjoint sets. For a partition
$\mathcal{I}=\\{I_{1},\ldots,I_{k}\\}\in P_{d}$, and a $d$-indexed matrix
$A=(a_{\bf i})_{{\bf i}\in[n]^{d}}$, define

$\displaystyle\|A\|_{\mathcal{I}}=\sup\Big{\\{}\sum_{{\bf i}\in[n]^{d}}a_{{\bf
i}}\prod_{l=1}^{k}x^{(l)}_{{\bf i}_{I_{l}}}\colon|(x^{(l)}_{{\bf
i}_{I_{l}}})|\leq 1,1\leq l\leq k\Big{\\}},$

where $|(x_{{\bf i}_{I_{l}}})|=\sqrt{\sum_{|{\bf i}_{I_{l}}|\leq n}x_{{\bf
i}_{I_{l}}}^{2}}$. Therefore, for example,

$\displaystyle\|(a_{ij})_{i,j\leq n}\|_{\\{1,2\\}}$
$\displaystyle=\sup\Big{\\{}\sum_{i,j\leq n}a_{ij}x_{ij}\colon\sum_{i,j\leq
n}x_{ij}^{2}\leq 1\Big{\\}}=\sqrt{\sum_{i,j\leq
n}a_{ij}^{2}}=\|(a_{ij})_{i,j\leq n}\|_{HS},$
$\displaystyle\|(a_{ij})_{i,j\leq n}\|_{\\{1\\}\\{2\\}}$
$\displaystyle=\sup\Big{\\{}\sum_{i,j\leq n}a_{ij}x_{i}y_{j}\colon\sum_{i\leq
n}x_{i}^{2}\leq 1,\sum_{j\leq n}y_{j}^{2}\leq 1\Big{\\}}=\|(a_{ij})_{i,j\leq
n}\|,$ $\displaystyle\|(a_{ijk})_{i,j,k\leq n}\|_{\\{1,2\\}\\{3\\}}$
$\displaystyle=\sup\Big{\\{}\sum_{i,j,k\leq
n}a_{ijk}x_{ij}y_{k}\colon\sum_{i,j\leq n}x_{ij}^{2}\leq 1,\sum_{k\leq
n}y_{k}^{2}\leq 1\Big{\\}},$

where $\|\cdot\|_{HS}$ and $\|\cdot\|$ denote the Hilbert–Schmidt and the
operator norm respectively.

######  Theorem 3.8.

If $\pi\sim\pi(p,k)$ for some $p\in(0,1)^{n}$ and $k\in\\{0,\ldots,n\\}$, then
for any tetrahedral polynomial
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ of degree $d$,

$\pi\big{(}\big{|}f-\pi(f)\big{|}\geq t\big{)}\leq
2\exp\Big{(}-\frac{1}{C_{d}}\min_{1\leq r\leq d}\min_{\mathcal{J}\in
P_{r}}\Big{(}\frac{t}{\|\pi(\nabla^{r}f)\|_{\mathcal{J}}}\Big{)}^{2/|\mathcal{J}|}\Big{)},$

where $C_{d}$ is a constant depending only on the degree $d$ of $f$.

Inequalities of this type for polynomials of arbitrary degree were introduced
for the first time by Latała [35] for tetrahedral polynomials in i.i.d.
standard Gaussian variables. Subsequently they were extended to general
polynomials in independent subgaussian random variables and to certain
dependent situations related to Glauber dynamics (see [4, 1, 47, 46, 2]). We
remark that in the independent, subgaussian case and $d=2$ they reduce to the
well known Hanson–Wright inequality for quadratic forms, which has proved
useful in non-asymptotic analysis of random matrices and in asymptotic
geometric analysis (see, e.g., [55, Chapter 6]). It is worth mentioning that
in the Gaussian case they may be reversed up to the value of the absolute
constants, thus Theorem 3.8 shows that the measures $\pi(p,k)$ exhibit
Gaussian type concentration for polynomials. While calculating the norms
$\|\cdot\|_{\mathcal{J}}$ is usually difficult, estimating them is sometimes
possible, leading to applications involving subgraph counts (in the Erdős-
Rényi case or for some models of random graphs with dependencies [4, 47, 46])
or to statistical applications, e.g., in testing Ising models [23] and signal
processing [56].

##  4\. Abstract formulations

In this section we recall some notions from the theory of Markov semigroups
and formulate the abstract counterparts of the results of Section 3 and of
Theorem 2.3. We believe that the results presented in this section might be of
separate interest as they provide a general framework for proving
concentration on the hypercube. We stress that most of the proof techniques
that we exploit were known previously – our main contribution is the abstract
formulation of these results by means of the novel stability condition (cf.
Definition 4.3).

Throughout this section we will rely on the usual notions from the theory of
Markov processes and Dirichlet forms specialized to finite state space. We
will briefly recall them and refer to [39, 9, 13] for details.

###  4.1. Modified log-Sobolev inequalities

Let $L$ be the generator of a jump Markov process on some finite probability
space $(M,\pi)$. In what follows we will sometimes treat $L$ as a linear
operator on $\mathbb{R}^{M}$ and sometimes identify it with the corresponding
matrix, indexed by the elements of $M$.

Assume that $L$ satisfies the detailed-balance condition

(4.1) $\forall\;x,y\in M\quad\pi(x)L(x,y)=\pi(y)L(y,x),$

which implies that $\pi$ is a stationary measure for the Markov process and
$L$ is self-adjoint on $L^{2}(\pi)$. In this article we consider only Markov
processes satisfying the above condition, which may not be stated explicitly
in all the results.

For a given $L$, we define $\Delta(L):=\max_{x}-L(x,x)=\max_{x}\sum_{y\colon
y\neq x}L(x,y)$ and write $\operatorname{\mathcal{E}}(f,g)=-\pi(fLg)$ for the
Dirichlet form associated with $L$. In particular
$\operatorname{\mathcal{E}}(f,g)=\pi\big{(}\Gamma(f,g)\big{)}$, where
$\Gamma\colon\mathbb{R}^{M}\times\mathbb{R}^{M}\to\mathbb{R}^{M}$ given by

(4.2) $\Gamma(f,g)(x)=\frac{1}{2}\sum_{y\in M}(f(x)-f(y))(g(x)-g(y))L(x,y)$

is the corresponding carré-du-champ operator. We use shorthand notation
$\Gamma(f,f)=:\Gamma(f)$ and observe that by the detailed-balance condition
(4.1) we have $\pi\big{(}\Gamma(f)\big{)}=\pi(\Gamma_{+}(f))$, where

(4.3) $\Gamma_{+}(f)(x)=\sum_{y\in M}(f(x)-f(y))_{+}^{2}L(x,y).$

Finally, we denote by $\rho(L)$ the best (the greatest) constant such that the
following modified log-Sobolev inequality is satisfied

(4.4) $\rho(L)\operatorname{Ent}_{\pi}(f)\leq\operatorname{\mathcal{E}}(f,\log
f)$

for all non-constant functions $f\colon M\to[0,\infty)$, where
$\operatorname{Ent}_{\pi}(f)=\pi(f\log f)-\pi(f)\log\pi(f)$ is the entropy
functional (we adopt the convention $0\log 0=0$). We remark that $\rho(L)$ is
positive iff $L$ is irreducible on the support of $\pi$ (see the discussion in
[13] and [38, Chapter 12]). In what follows we will restrict our attention to
this situation, without mentioning this assumption explicitly in each
statement.

A classical observation, often referred to as Herbst’s argument (cf. the
monographs [36] by Ledoux and [17] by Boucheron et al.), says that for any
$f\colon M\to\mathbb{R}$,

(4.5)
$\pi\big{(}f>\pi(f)+t\big{)}\leq\exp(-t^{2}\rho(L)/4\|\Gamma_{+}(f)\|_{\infty}),$

where $\|\cdot\|_{\infty}$ stands for the norm in $L^{\infty}(\pi)$.

###  4.2. Flip-swap random walks

After Hermon and Salez [29], we say that a kernel $L$ generates a flip-swap
random walk if $L(x,y)>0$ implies that $x=y^{i}$ for some $i\in[n]$ (i.e., $x$
and $y$ differ by a flip) or $x=y^{ij}$ for some $i\neq j$, $i,j\in[n]$ (i.e.,
$x$ and $y$ differ by a swap). The main contribution of [29] can be stated in
the following way.

######  Theorem 4.1 (Hermon–Salez [29]).

For any measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfying the SCP,
there exists a kernel $L$ generating a reversible flip-swap random walk with
stationary measure $\pi$ such that $\rho(L)\geq 1$ and $\Delta(L)\leq n$. If
$\pi$ is also $k$-homogeneous, then $\Delta(L)\leq 2k$ as well.

Theorem 4.1, by means of Herbst’s argument (4.5), implies (up to an absolute
constant in the exponent) the estimate from Theorem 1.1 after observing that
for a flip-swap random walk and any
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ that is 1-Lipschitz with
respect to the Hamming distance $d_{H}$

(4.6)
$\displaystyle\|\Gamma_{+}(f)\|_{\infty}\leq\Delta(L)\cdot\max_{x,y\in\operatorname{\mathcal{B}_{n}}}\\{\,(f(y)-f(x))_{+}^{2}\colon
L(x,y)>0\,\\}\leq 4\Delta(L).$

Finally, Theorem 4.1 is constructive – in Section 7 we revisit the inductive
construction of $L$ from [29] in the context of conditional Bernoulli
distribution.

######  Remark 4.2.

There are many examples of flip-swap random walks on the hypercube in the
literature, including, e.g., the Bernoulli–Laplace model, Glauber dynamics or
base exchange random walk on matroids, cf. e.g., [13, 28, 47, 22]. We note
that the results of this section apply to any flip-swap random walk as long as
we have control of its stability (cf. Definition 4.3) constant.

It turns out that for the proofs of all the statements of Section 3 it
suffices to demonstrate that the following condition is true for some
reversible generator $L$ with stationary measure $\pi(p,k)$ for which the
modified log-Sobolev inequality (4.4) is known.

######  Definition 4.3 (Stability condition).

Let $L$ be a generator of a flip-swap random walk on
$\operatorname{\mathcal{B}_{n}}$ with invariant probability distribution
$\pi$. We say that the pair $(L,\pi)$ meets the stability condition with
constant $R\geq 0$ (i.e., is $R$-stable) if it satisfies the modified log-
Sobolev inequality (4.4) and

(4.7) $\displaystyle\max_{x\in\operatorname{supp}\pi;\,i\in[n]}\sum_{y\colon
y_{i}\neq x_{i}}L(x,y)\leq R\rho(L).$

If it is clear from the context which measure $\pi$ is associated with $L$, we
will often omit it in the discussion and simply say that $L$ is $R$-stable.

######  Remark 4.4.

If $\pi$ is not concentrated on a single point, then a random walk on
$\operatorname{\mathcal{B}_{n}}$ with a generator $L$ that satisfies the
modified log-Sobolev inequality (4.4) may be at best $0.25$-stable (i.e.,
$R\geq 0.25$). Indeed, in this case there exists $i$ such that
$\pi(\\{x_{i}=1\\}),\pi(\\{x_{i}=0\\})>0$. If $L$ satisfies the modified log-
Sobolev inequality, then it also satisfies the Poincaré inequality
$\frac{1}{2}\rho(L)\operatorname{Var}_{\pi}(f)\leq\operatorname{\mathcal{E}}(f,f)$,
see e.g., [2, Proposition B.5]. Therefore, by the stability condition (4.7)
applied to the function $f(x)=\mathbf{1}_{\\{x_{i}=1\\}}$ and reversibility of
$L$ we get that

$\displaystyle R\rho(L)\pi(\\{x_{i}=1\\})$ $\displaystyle\geq\sum_{x\colon
x_{i}=1}\sum_{y\colon y_{i}=0}L(x,y)\pi(x)$
$\displaystyle=\sum_{x,y}(x_{i}-y_{i})^{2}_{+}L(x,y)\pi(x)$
$\displaystyle=\operatorname{\mathcal{E}}(f,f)$
$\displaystyle\geq\frac{1}{2}\rho(L)\operatorname{Var}_{\pi}(f)=\frac{1}{2}\rho(L)\pi(\\{x_{i}=1\\})\pi(\\{x_{i}=0\\}),$

which gives $R\geq 0.5\cdot\pi(\\{x_{i}=0\\})$. Similarly, by considering
$f(x)=\mathbf{1}_{\\{x_{i}=0\\}}$ we get that $R\geq
0.5\cdot\pi(\\{x_{i}=1\\})$ as well, yielding $R\geq 0.25$.

This bound is optimal, as can be seen for $\pi$ being the uniform measure on
$\operatorname{\mathcal{B}_{n}}$ and $L(x,y)=1$ if there exists $i$ such that
$y=x^{i}$, $L(x,y)=-n$ if $y=x$ and $L(x,y)=0$ otherwise (this corresponds to
the special case of Glauber dynamics, in which at rate $n$, a random
coordinate is flipped). In this case $\rho(L)=4$ (see [13, Example 3.7], note
a different normalization of both the Dirichlet form and the constant in the
modified log-Sobolev inequality), whereas for all
$x\in\operatorname{\mathcal{B}_{n}}$

$\max_{i}\sum_{y\colon y_{i}\neq x_{i}}L(x,y)=L(x,x^{i})=1=0.25\cdot\rho(L).$

Let us illustrate the notion of $R$-stability with another classical example.

######  Example 4.5 (Bernoulli–Laplace model).

Let $\pi$ be the uniform measure on the slice of
$\operatorname{\mathcal{B}_{n}}$ consisting of elements with exactly $k$ ones
and let $L$ be given by $Lf(x)=\frac{1}{n}\sum_{i<j}(f(x^{ij})-f(x))$ (thus
the corresponding Markov process at rate $(n-1)/2$ swaps a uniformly chosen
pair of coordinates). In the matrix form this corresponds to
$L(x,y)=\frac{1}{n}$ if $x\neq y$ and $y=x^{ij}$, $L(x,x)=-k(n-k)/n$ and
$L(x,y)=0$ otherwise. It has been proved in [25] and independently in [13]
that $\rho_{0}(L)\geq 1/2$. At the same time $\sum_{y\colon y_{i}\neq
x_{i}}L(x,y)$ equals to $(n-k)/n$ if $x_{i}=1$ and to $k/n$ otherwise. This
shows that $L$ is $2$-stable, independently of $n$ and $k$. As mentioned in
the introduction, the uniform measure on the slice of the discrete cube can be
interpreted as the distribution of i.i.d. Bernoulli variables conditioned on
their sum being equal to $k$. In Proposition 7.3 we generalize the above
observation on stability and show that if $\mu$ is the law of general
independent Bernoulli variables conditioned on their sum being equal to a
fixed constant, there exists a $2$-stable generator of a random walk
reversible with respect to $\mu$.

######  Remark 4.6.

Observe that the notion of stability is invariant under scaling of $L$ (change
of time), i.e., if $L$ is $R$-stable then so is $aL$ for any $a>0$. This leads
to a tensorization property for measures admitting an $R$-stable generator.
More precisely, let $\pi_{1},\ldots,\pi_{m}$ be measures on
$\mathcal{B}_{n_{1}},\ldots,\mathcal{B}_{n_{m}}$, for which there exist
reversible flip-swap random walks with $R$-stable generators
$L_{1},\ldots,L_{m}$. By changing time, we can assume without loss of
generality that $\rho(L_{i})=\rho$ for all $i\leq m$. Let
$n=n_{1}+\ldots+n_{m}$ and consider the product measure
$\pi=\pi_{1}\otimes\cdots\otimes\pi_{m}$ on $\operatorname{\mathcal{B}_{n}}$
together with the generator $L=L_{1}+\ldots+L_{m}$, where we think of $L_{i}$
as acting only on the $i$-th block of coordinates on
$\operatorname{\mathcal{B}_{n}}=\mathcal{B}_{n_{1}}\times\cdots\times\mathcal{B}_{n_{m}}$,
i.e., we identify $L_{i}$ with its tensor product with identity on
$\otimes_{j\neq i}\mathbb{R}^{\mathcal{B}_{n_{j}}}$. In the matrix form we
have the representation

$L(x,y)=\sum_{i=1}^{m}L_{i}(P_{i}x,P_{i}y)\prod_{j\neq
i}\mathbf{1}_{\\{P_{j}x=P_{j}y\\}},$

where $P_{j}\colon\operatorname{\mathcal{B}_{n}}\to\mathcal{B}_{j}$ is the
projection onto the $j$-th factor in the product
$\operatorname{\mathcal{B}_{n}}=\mathcal{B}_{n_{1}}\times\cdots\times\mathcal{B}_{n_{m}}$
Thanks to the well known tensorization property of the entropy (see, e.g., [7,
Chapter 3]) we have $\rho(L)=\rho$. Moreover, for
$i\in(n_{1}+\ldots+n_{j-1},n_{1}+\ldots+{n_{j}}]$,

$\sum_{y\in\operatorname{\mathcal{B}_{n}}\colon y_{i}\neq
x_{i}}L(x,y)=\sum_{y\in\mathcal{B}_{n_{j}}\colon
y_{l}\neq(P_{j}x)_{l}}L_{j}((P_{j}x),y)\leq R\rho,$

where $l=i-(n_{1}+\ldots+n_{j-1})$. Thus $L$ is indeed $R$-stable.

This observation allows in particular to extend all the theorems od Section 3
to product of measures $\pi(n,k)$ allowing for more general conditioning of
Bernoulli variables.

###  4.3. Abstract formulations

Finally, let us present the counterparts of the results of Section 2 and of
Theorem 2.3 from Section 3 in the abstract language of the stability condition
(4.7). We stress here that it is the sole property needed for their proofs,
which are deferred to Section 7.

We start with a bounded-difference type inequality for real valued functions.

######  Proposition 4.7.

If a flip-swap random walk on $\operatorname{\mathcal{B}_{n}}$ with stationary
distribution $\pi$ and generator $L$ satisfies the stability condition (4.7),
then for any $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ and
$\alpha\in\mathbb{R}_{+}^{n}$ such that

$|f(x)-f(y)|\leq
d_{\alpha}(x,y)\quad\forall\,x,y\in\operatorname{\mathcal{B}_{n}}$

the following estimate holds for all $t>0$

$\displaystyle\pi\big{(}f>\pi(f)+t\big{)}\leq\exp\Big{(}-\frac{t^{2}}{8R|\alpha|^{2}}\Big{)}.$

In the above estimate one can also replace $8|\alpha|^{2}$ with
$16\sum_{i=1}^{\lceil\Delta(L)/R\rho(L)\rceil}(\alpha_{i}^{\downarrow})^{2}$.

######  Remark 4.8.

Using the definitions of $R$-stability and of $\Delta(L)$ one can see that
$\Delta(L)/R\rho(L)\leq n$ and if $\pi$ is $k$-homogeneous, then
$\Delta(L)/R\rho(L)\leq k$.

Let us now pass to the matrix-valued case.

######  Proposition 4.9.

Let a flip-swap random walk on $\operatorname{\mathcal{B}_{n}}$ with
stationary distribution $\pi$ and generator $L$ satisfy the stability
condition (4.7). Assume also that
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ is
such that there is a sequence of positive semidefinite matrices
$C_{1},\ldots,C_{n}$ satisfying

(4.8) $(f(x)-f(x^{i}))^{2}\preccurlyeq
C_{i}^{2}\quad\forall\;x\in\operatorname{\mathcal{B}_{n}},\,i\in[n],$

where $\preccurlyeq$ denotes the positive semidefinite order on the set of
symmetric matrices. Set the variance proxy

$\sigma^{2}=8R\cdot\sup\Big{\\{}\,\big{\|}\sum_{i\in\mathcal{I}}C_{i}^{2}\big{\|}\,\colon\,|\mathcal{I}|=\lceil\Delta(L)/R\rho(L)\rceil,\,\mathcal{I}\subset[n]\,\Big{\\}}.$

Then for any $t>0$,

$\pi\big{(}\lambda_{max}(f-\pi(f))>t\big{)}\leq
d\exp\big{(}-t^{2}/(\sigma^{2}+\sigma t)\big{)}.$

Our next proposition is the convex distance inequality under $R$-stability.

######  Proposition 4.10.

If a flip-swap random walk on $\operatorname{\mathcal{B}_{n}}$ with some
stationary distribution $\pi$ and a generator $L$ satisfies the stability
condition (4.7), then for any set $A\subset\operatorname{\mathcal{B}_{n}}$

$\pi(A)\pi\Big{(}\exp\Big{(}\frac{1}{40R+4}\cdot
d_{T}^{2}(\cdot,A)\Big{)}\Big{)}\leq 1.$

Finally, let us state the concentration result for polynomials in an abstract
version.

######  Proposition 4.11.

If a flip-swap random walk on $\operatorname{\mathcal{B}_{n}}$ with some
stationary distribution $\pi$ and a generator $L$ satisfies the stability
condition (4.7), then for any tetrahedral polynomial
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ of degree $d$

$\pi\big{(}\big{|}f-\pi(f)\big{|}\geq t\big{)}\leq
2\exp\Big{(}-\frac{1}{C_{d}}\min_{1\leq r\leq d}\min_{\mathcal{J}\in
P_{r}}\Big{(}\frac{t}{R^{r/2}\|\pi(\nabla^{r}f)\|_{\mathcal{J}}}\Big{)}^{2/|\mathcal{J}|}\Big{)},$

where $C_{d}$ is a constant depending only on the degree $d$ of $f$.

######  Remark 4.12.

Although Proposition 4.7 gives a worse constant in the exponent than Theorem
2.3 even in the case of conditional Bernoulli distributions $\pi(p,k)$, we
state it here as in principle it does not assume that $\pi$ satisfies the SCP
and thus potentially can be applied in other settings.

######  Remark 4.13.

The above propositions can be transferred to more general random walks that
change at each step at most a fixed number of coordinates $N$ (with $N=2$ in
case of flip-swap random walks). We do not pursue this direction though and do
not write all the theorems in full generality for the sake of readability.

######  Remark 4.14.

Recently, Cryan et al. [22] have shown a version of Theorem 4.1 for
$k$-homogeneous strongly log-concave measures. Strong log-concavity is yet
another possible generalization of the SRP, which is in general incomparable
with the SCP [22]. It is known, cf. Brändén and Huh [18], that any
$k$-homogeneous strongly log-concave measure is supported on the set of bases
of some matroid of rank $k$. Using this fact, and extending the previous
results for uniform measures on the bases of matroids by Anari et al. [6] and
Kaufman and Oppenheim [33], Cryan et al. [22] explicitly construct a base-
exchange random walk, which has any given strongly log-concave measure as a
stationary distribution, and verify it satisfies the modified log-Sobolev
inequality (4.4).

Since the base-exchange random walk proposed therein is a particular instance
of a flip-swap random walk, a natural question is whether it satisfies the
stability condition (4.7), which would allow to deduce concentration results
presented in this section. Unfortunately, the answer seems to be negative in
full generality as can be seen already in the case of independent Bernoulli
random variables $B=(B_{1},\ldots,B_{n})$ with different probabilities of
success $\operatorname{\mathbb{P}}(B_{i}=1)=p_{i}$ conditioned on their sum
being $k$, i.e., for the distribution
$\pi(p,k)\sim\mathcal{L}(B\,|\,\sum_{i}B_{i}=k)$. If one chooses $p_{1}\to
1^{-}$ and $p_{j}=c$ for $j>1$ and some $c\in(0,1)$, then it is
straightforward to verify that the base-exchange random walk of [22] is at
best $k$-stable. Therefore, applying propositions of Section 4.3 to the base-
exchange random walk gives much worse concentration constants than those of
Section 3. On the other hand, the flip-swap random walk proposed by Hermon and
Salez [29] with stationary measure $\pi(p,k)$, which we use to prove the
results of Section 3, turns out to be $2$-stable.

In view of the above, it is an interesting problem to analyze what other known
kernels satisfy the stability condition (4.7) with good (dimension-
independent) constant and to look for some other criteria that would allow to
deduce this condition.

##  5\. Proofs of the results of Section 2

In this section we provide proofs of Theorems 2.3, 2.5 and 2.8. All these
results follow by modifications of the martingale argument due to Pemantle and
Peres [44].

Let $X\sim\pi$ be a random variable with values in
$\operatorname{\mathcal{B}_{n}}$ satisfying the SCP and denote
$\operatorname{supp}X=\\{\,i\in\\{1,\ldots,n\\}:X_{i}=1\,\\}$. In the non-
homogeous case define a filtration
$\operatorname{\mathcal{F}}=(\operatorname{\mathcal{F}}_{l})_{l=0}^{n}$ by
letting simply $\operatorname{\mathcal{F}}_{0}=\\{\emptyset,\Omega\\}$ and
$\operatorname{\mathcal{F}}_{l}=\sigma(X_{1},\ldots,X_{l})$ for
$l=1,\ldots,n$. In the $k$-homogeous case introduce a family of random
variables $Y_{1},\ldots,Y_{k}$ given by the conditions

(5.1)
$\displaystyle\mathcal{L}(Y_{1}\,|\,X)=\operatorname{Unif}(\operatorname{supp}X\backslash\\{1,\ldots,k\\})\quad\text{and}$
$\displaystyle\mathcal{L}(Y_{l}\,|\,X,Y_{1},\ldots,Y_{l-1})=\operatorname{Unif}(\operatorname{supp}X\setminus\\{1,\ldots,k,Y_{1},\ldots,Y_{l-1}\\}),\quad\text{for}\quad
l=2,\ldots,k,$

where $\operatorname{Unif}(A)$ stands for the uniform distribution on the set
$A$, and for notational simplicity we set $\operatorname{Unif}(\emptyset)$ to
be the Dirac mass at $0$ and $X_{0}\equiv 1$ (i.e., we add to $X$ an
additional coordinate providing no information and if the above sampling
scheme yields all elements from $\operatorname{supp}X$ before sampling some
$Y_{l}$, we set $Y_{i}$ to zero for all $i\geq l$). Finally, define a
filtration
$\operatorname{\mathcal{G}}=(\operatorname{\mathcal{G}}_{l})_{l=0}^{2k}$
setting $\operatorname{\mathcal{G}}_{0}=\\{\emptyset,\Omega\\}$ and
$\operatorname{\mathcal{G}}_{l}=\sigma(X_{1},\ldots,X_{l})$ for $l\in[k]$,
$\operatorname{\mathcal{G}}_{k+r}=\sigma(X_{1},\ldots,X_{k},Y_{1},\ldots,Y_{r}\\}$
for $r\in[k]$.

In other words in the first $k$-steps the subsequent values of $X$ at the
first $k$ coordinates are revealed, while in the last $k$ steps one reveals in
a uniformly random order the remaining coordinates at which $X$ takes the
value $1$. Note that if $\alpha$ is nonincreasing (which we may assume without
loss of generality) and $f$ is 1-Lipschitz with respect to $d_{\alpha}$ then
the first part of this sampling scheme promotes the coordinates which may have
the greatest impact on the value of $f(X)$. The construction can be thought of
as a modification of the sampling scheme proposed by Pemantle and Peres in
which one immediately starts revealing in a random order the coordinates at
which $X$ takes the value $1$.

The proof of Theorems 2.3 and 2.5 will be based on the following two lemmas.

######  Lemma 5.1.

Let $\alpha\in\mathbb{R}_{+}^{n}$ be nonincreasing and let
$f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}}$ be
$1$-Lipschitz with respect to the distance $d_{\alpha}$. Assume that $X$ is a
$\operatorname{\mathcal{B}_{n}}$-valued random vector satisfying the SCP. Let
$M_{l}=\operatorname{\mathbb{E}}[f(X)\,|\,\operatorname{\mathcal{F}}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,\operatorname{\mathcal{F}}_{l-1}]$
for $l\in[n]$. Then for every $l\in[n]$,

(5.2) $M_{l}^{2}\preccurlyeq 4\alpha_{l}^{2}I_{d}.$

######  Lemma 5.2.

In the setting of Lemma 5.1 assume additionally that $X$ is $k$-homogeneous.
For $l\in[2k]$ define
$N_{l}=\operatorname{\mathbb{E}}[f(X)\,|\,\operatorname{\mathcal{G}}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,\operatorname{\mathcal{G}}_{l-1}]$.
Then for $l\in[k]$,

(5.3) $N_{l}^{2}\preccurlyeq 4\alpha_{l}^{2}I_{d},$

while for $l=k+1,\ldots,2k$,

(5.4) $N_{l}^{2}\preccurlyeq 4\alpha_{k}^{2}I_{d}.$

We postpone for now the proof of the above lemmas and firstly show how they
imply Theorems 2.3 and 2.5. To this end let us recall the matrix version of
the Azuma-Hoeffding inequality due to Tropp [54, Theorem 7.1], which asserts
that if $D_{l}$, $l=1,\ldots,n$ are $\operatorname{\mathcal{H}_{d}}$-valued
martingale differences and $D_{l}^{2}\preccurlyeq C_{l}^{2}$ for some
deterministic matrices $C_{l}\in\operatorname{\mathcal{H}_{d}}$, then for all
$t\geq 0$,

$\operatorname{\mathbb{P}}\Big{(}\lambda_{max}\Big{(}\sum_{l=1}^{n}D_{l}\Big{)}\geq
t\Big{)}\leq de^{-t^{2}/8\sigma^{2}},$

where $\sigma^{2}=\|\sum_{l=1}^{n}C_{l}^{2}\|$. Note also that for $d=1$ the
classical Azuma-Hoeffding inequality (see, e.g., [24, Theorem 5.8]) allows to
replace the constant $1/8$ by $1/2$.

###### Proof of Theorems 2.3 and 2.5.

Since the SCP is invariant under permutations of coordinates of $X$, we may
and do assume that $\alpha=\alpha^{\downarrow}$. By Lemma 5.1 the martingale
differences $M_{l}$ satisfy $M_{l}^{2}\preccurlyeq
C_{l}^{2}:=4\alpha_{l}^{2}I_{d}$. Clearly

(5.5) $\Big{\|}\sum_{l=1}^{n}C_{l}^{2}\Big{\|}=4|\alpha|^{2}.$

If $X$ is $k$-homogeneous, then by Lemma 5.2,
$N_{l}^{2}\preccurlyeq\widetilde{C}_{l}^{2}:=4\alpha_{\min(l,k)}^{2}I_{d}$. In
this case

(5.6)
$\Big{\|}\sum_{l=1}^{2k}\widetilde{C}_{l}^{2}\Big{\|}=4\Big{[}\Big{(}\sum_{l=1}^{k}\alpha_{l}^{2}\Big{)}+k\alpha_{k}^{2}\Big{]}\leq
8\sum_{l=1}^{k}\alpha_{l}^{2}.$

We have $f(X)=\sum_{l=1}^{n}M_{l}$, whereas in the $k$-homogeneous case
$f(X)=\sum_{l=1}^{2k}N_{l}$ (observe that after $2k$-steps of the sampling
procedure all the nonzero coordinates of $X$ are revealed and so $X$ is
$\mathcal{G}_{2k}$-measurable). Thus the conclusion of Theorem 2.3 follows by
applying estimates (5.5) and (5.6) for $d=1$ together with the classical
Azuma-Hoeffding inequality. Similarly, Theorem 2.5 follows from the matrix
version of the Azuma-Hoeffding inequality. ∎

It remains to prove Lemmas 5.1 and 5.2.

###### Proof of Lemma 5.1.

Let $A^{x}_{l}=\\{X_{1}=x_{1},\ldots,X_{l}=x_{l}\\}$ for
$x=(x_{1},\ldots,x_{n})\in\operatorname{\mathcal{B}_{n}}$ and $l=0,\ldots,n$.
Then, for $l=1,\ldots,n$ and any $x\in\operatorname{\mathcal{B}_{n}}$ such
that $\operatorname{\mathbb{P}}(A_{l}^{x})>0$,

$\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1}]=\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1},X_{l}=x_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1}]\\\
=\operatorname{\mathbb{P}}(X_{l}\neq
x_{l}\,|\,A^{x}_{l-1})\big{(}\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1},X_{l}=x_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1},X_{l}\neq
x_{l}]\big{)}.$

If $\operatorname{\mathbb{P}}(X_{l}\neq x_{l}\,|\,A^{x}_{l-1})\neq 0$, then by
the SCP there exist a coupling $(\hat{X},\hat{Y})$ between the distributions
$\mathcal{L}(X\,|\,A^{x}_{l-1},X_{l}=x_{l})$ and
$\mathcal{L}(X\,|\,A^{x}_{l-1},X_{l}\neq x_{l})$ that is supported on the set
$\\{\,(y,z)\in\mathcal{B}_{n}^{2}\,\colon\,d_{H}((y_{i})_{i>l},(z_{i})_{i>l})\leq
1\,\\}$. Using this coupling, the Lipschitz property of $f$, Jensen’s
inequality and the fact that $\alpha_{i}\leq\alpha_{l}$ for any $i>l$, we get
that

$\|\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,A^{x}_{l-1}]\|\\\
\leq\operatorname{\mathbb{P}}(X_{l}\neq
x_{l}\,|\,A^{x}_{l-1})\operatorname{\mathbb{E}}\|f((x_{i})_{i\leq
l},\hat{X}_{i>l})-f((x_{i})_{i<l},1-x_{l},\hat{Y}_{i>l})\|\\\
\leq\operatorname{\mathbb{P}}(X_{l}\neq x_{l}\,|\,A^{x}_{l-1})\cdot
2\alpha_{l}\leq 2\alpha_{l},$

which is equivalent to (5.2). ∎

###### Proof of Lemma 5.2.

Note that for $l\leq k$, we have
$\operatorname{\mathcal{G}}_{l}=\operatorname{\mathcal{F}}_{l}$. As a
consequence $N_{l}=M_{l}$, where $M_{l}$ are martingale increments defined in
Lemma 5.1, which implies (5.3).

Consider now $l>k$ of the form $l=k+r$ and for
$x=(x_{1},\ldots,x_{k})\in\mathcal{B}_{k}$ and
$v=(v_{1},\ldots,v_{k})\in(\\{0\\}\cup\\{k+1,\ldots,n\\})^{k}$ set
$A^{x,v}_{l}=\\{X_{1}=x_{1},\ldots,X_{k}=x_{k},Y_{1}=v_{1},\ldots,Y_{r}=v_{r}\\}$.
Then $\operatorname{\mathcal{F}}_{l}$ is generated by the sets $A^{x,v}_{l}$.
By the definition of the variables $Y_{r}$, we have
$\\{Y_{r}=i\\}\subseteq\\{X_{i}=1\\}$ and so for any $x,v$ such that
$\operatorname{\mathbb{P}}(A^{x,v}_{l})>0$,

(5.7)
$\displaystyle\operatorname{\mathbb{E}}[f(X)\,|\,A^{x,v}_{l}]=\frac{\operatorname{\mathbb{E}}[f(X)\mathbf{1}_{A^{x,v}_{l-1}}\mathbf{1}_{\\{X_{v_{r}}=1\\}}\mathbf{1}_{\\{Y_{r}=v_{r}\\}}]}{\operatorname{\mathbb{P}}(A^{x,v}_{l-1},X_{v_{r}}=1,Y_{r}=v_{r})}.$

For $s\in[r]$ let $m_{s}=|\\{i\in[k]\colon x_{i}=1\\}|+|\\{j\in[s-1]\colon
v_{j}\neq 0\\}|$ be the number of ones sampled by the time $k+s-1$. It follows
from (5.1) that if $m_{s}<k$ then $\operatorname{\mathbb{P}}(A^{x,v}_{k+s})>0$
implies that $v_{s}\neq 0$ and
$\operatorname{\mathbb{P}}(Y_{s}=v_{s}|X,Y_{1},\ldots,Y_{s-1})=\frac{1}{k-m_{s}}$
on $A^{x,v}_{k+s-1}\cap\\{X_{v_{s}}=1\\}$, whereas if $m_{s}=k$, then
$\operatorname{\mathbb{P}}(A^{x,v}_{k+s})>0$ implies that $v_{s}=0$ and
$\operatorname{\mathbb{P}}(Y_{s}=v_{s}\,|\,X,Y_{1},\ldots,Y_{s-1})=1$ on
$A^{x,v}_{k+s-1}\cap\\{X_{v_{s}}=1\\}=A^{x,v}_{k+s-1}$. Going back to (5.7)
and using this observation for $s=r,\ldots,1$, we obtain that

$\operatorname{\mathbb{E}}[f(X)\,|\,A^{x,v}_{l}]=\operatorname{\mathbb{E}}[f(X)\,|\,B^{x,v}_{l}],$

where
$B^{x,v}_{l}=\\{X_{1}=x_{1},\ldots,X_{k}=x_{k},X_{v_{1}}=\ldots=X_{v_{l-k}}=1\\}$.
We thus obtain

$\operatorname{\mathbb{E}}[f(X)\,|\,A^{x,v}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,A^{x,v}_{l-1}]\\\
=\operatorname{\mathbb{P}}(X_{v_{r}}\neq
1\,|\,B^{x,v}_{l-1})(\operatorname{\mathbb{E}}[f(X)\,|\,B^{x,v}_{l-1},X_{v_{r}}=1]-\operatorname{\mathbb{E}}[f(X)\,|\,B^{x,v}_{l-1},X_{v_{r}}\neq
1]).$

Note that the right-hand side may be non-zero only if $v_{r}\neq 0$. In this
case using the inequality $\alpha_{v_{s}}\leq\alpha_{k}$ for $s\in[k]$ we can
conclude as in the proof of Lemma 5.1.

∎

Let us now pass to the proof of Theorem 2.8.

###### Proof of Theorem 2.8.

We will rely on the martingale used in the article by Pemantle and Peres. Let
$X$ be a random vector with law $\pi$ and define the random variables $Y_{l}$
for $l\leq n$ as

(5.8)
$\displaystyle\mathcal{L}(Y_{1}\,|\,X)=\operatorname{Unif}(\operatorname{supp}X)\quad\text{and}$
$\displaystyle\mathcal{L}(Y_{l}\,|\,X,Y_{1},\ldots,Y_{l-1})=\operatorname{Unif}(\operatorname{supp}X\setminus\\{Y_{1},\ldots,Y_{l-1}\\}),\quad\text{for}\quad
l=2,\ldots,k,$

i.e., $Y_{l}^{\prime}s$ reveal in a uniformly random order the elements of
$\operatorname{supp}X$. Let $\mathcal{H}_{0}=\\{\emptyset,\Omega\\}$ and
$\mathcal{H}_{l}=\sigma(Y_{1},\ldots,Y_{l})$ for $l=1,\ldots,k$. Then
$f(X)-\operatorname{\mathbb{E}}f(X)=\sum_{l=1}^{k}\operatorname{\mathbb{E}}[f(X)\,|\,\mathcal{H}_{l}]-\operatorname{\mathbb{E}}[f(X)\,|\,\mathcal{H}_{l-1}]=:\sum_{l=1}^{k}D_{l}$.
We will use the matrix version of Freedman’s inequality due to Tropp [53],
which asserts (in a version specialized for our application) that if
$\|D_{l}\|\leq a$ a.s. for all $l$, and
$\|\sum_{l=1}^{k}\operatorname{\mathbb{E}}[D_{l}^{2}\,|\,\mathcal{H}_{l-1}]\|\leq\sigma^{2}$
a.s., then for any $t\geq 0$,

(5.9) $\operatorname{\mathbb{P}}(\|f(X)-\operatorname{\mathbb{E}}f(X)\|\geq
t)\leq 2d\exp\Big{(}-\frac{t^{2}}{2\sigma^{2}+2at/3}\Big{)}.$

Consider thus a sequence of pairwise distinct $v_{1},\ldots,v_{k}\in[n]$ and
denote $A^{v}_{l}=\\{Y_{1}=v_{1},\ldots,Y_{l}=v_{l}\\}$. Similarly as in the
proof of Lemma 5.2, if $\operatorname{\mathbb{P}}(A^{v}_{l})>0$, then we have

$\operatorname{\mathbb{E}}[f(X)\,|\,A^{v}_{l}]=\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l}],$

where $B_{l}^{v}=\\{X_{v_{1}}=\ldots=X_{v_{l}}=1\\}$. Therefore we have

(5.10)
$D_{l}\mathbf{1}_{A^{v}_{l}}=\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\big{(}\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l-1},X_{v_{l}}=1]-\operatorname{\mathbb{E}}[f(X)|B^{v}_{l-1},X_{v_{l}}=0]\big{)}\mathbf{1}_{A^{v}_{l}}.$

Since the SRP implies the SCP, there exists a coupling $(\tilde{Z},\hat{Z})$
between the distributions $\mathcal{L}(X\,|\,B^{v}_{l})$ and
$\mathcal{L}(X\,|\,B^{v}_{l-1},X_{v_{l}}=0)$ such that $\tilde{Z}$ and
$\hat{Z}$ differ just at coordinate $v_{l}$ and one additional coordinate (at
which by $k$-homogeneity $\hat{Z}$ necessarily takes the value one). Let
$\tilde{Y}_{l}$ be this coordinate. We have

(5.11)
$\displaystyle\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l-1},X_{v_{l}}=1]-\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l-1},X_{v_{l}}=0]=\operatorname{\mathbb{E}}[f(\tilde{Z})-f(\hat{Z})],$

Since $\hat{Z}^{\tilde{Y}_{l}}=\tilde{Z}^{v_{l}}$, we have

(5.12)
$\Big{(}\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l-1},X_{v_{l}}=1]-\operatorname{\mathbb{E}}[f(X)\,|\,B^{v}_{l-1},X_{v_{l}}=0]\Big{)}^{2}=\Big{(}\operatorname{\mathbb{E}}[f(\tilde{Z})-f(\hat{Z})]\Big{)}^{2}\\\
\preccurlyeq\operatorname{\mathbb{E}}\Big{[}\big{(}f(\tilde{Z})-f(\hat{Z})\big{)}^{2}\Big{]}=\operatorname{\mathbb{E}}\Big{[}\big{(}f(\tilde{Z})-f(\tilde{Z}^{v_{l}})+f(\hat{Z}^{\tilde{Y}_{l}})-f(\hat{Z})\big{)}^{2}\Big{]}\\\
\preccurlyeq
2\operatorname{\mathbb{E}}\Big{[}\big{(}f(\tilde{Z})-f(\tilde{Z}^{v_{l}})\big{)}^{2}\Big{]}+2\operatorname{\mathbb{E}}\Big{[}\big{(}f(\hat{Z}^{\tilde{Y}_{l}})-f(\hat{Z})\big{)}^{2}\Big{]}\preccurlyeq
2C_{v_{l}}^{2}+2\operatorname{\mathbb{E}}C_{\tilde{Y}_{l}}^{2},$

where in the first and second inequality we used the operator convexity of the
function $x\mapsto x^{2}$ (see [11, Example V.1.3]), and in the last
inequality the assumption (2.3).

In particular, using (5.10), we obtain $\|D_{l}^{2}\|\leq
4\max_{i}\|C_{i}^{2}\|$, so $\|D_{l}\|\leq 2K$. Moreover as on $A^{v}_{l}$ we
have $Y_{l}=v_{l}$, by (5.10) and (5.12) we get that

$\displaystyle D_{l}^{2}\mathbf{1}_{A^{v}_{l}}\preccurlyeq
2(C_{Y_{l}}^{2}+\operatorname{\mathbb{E}}C_{\tilde{Y}_{l}}^{2})\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})^{2}\mathbf{1}_{A^{v}_{l}}.$

Let us now slightly change our notation and think of $\tilde{Y}_{l}$ as of
random variable defined on the same probability space as $X$, with conditional
distribution with respect to the $\sigma$-field $\mathcal{H}_{l}$ given on
each of its atoms $A^{v}_{l}$ by the above construction, using the
corresponding coupling (which depends on $v_{1},\ldots,v_{l}$). Then the above
inequality can be written as

(5.13) $\displaystyle D_{l}^{2}\preccurlyeq
2\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\big{(}C_{Y_{l}}^{2}+\operatorname{\mathbb{E}}[C_{\tilde{Y}_{l}}^{2}\,|\,A^{v}_{l}]\big{)}\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})^{2}\mathbf{1}_{A^{v}_{l}}.$

Let us now go back to the equations (5.10) and (5.11) and let us apply them in
the special case of the function $\tilde{f}(x)=\sum_{i=1}^{n}x_{i}C_{i}^{2}$,
denoting the corresponding martingale increment by $\tilde{D}_{l}$. We obtain
that

$\tilde{D}_{l}\mathbf{1}_{A^{v}_{l}}=\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\big{(}C^{2}_{Y_{l}}-\operatorname{\mathbb{E}}[C^{2}_{\tilde{Y}_{l}}\,|\,A^{v}_{l}]\big{)}\mathbf{1}_{A^{v}_{l}}.$

Thus we get that

$0=\operatorname{\mathbb{E}}[\tilde{D}_{l}\,|\,A^{v}_{l-1}]=\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\mathbf{1}_{A^{v}_{l}}\big{(}C^{2}_{Y_{l}}-\operatorname{\mathbb{E}}[C^{2}_{\tilde{Y}_{l}}\,|\,A^{v}_{l}]\big{)}\,\Big{|}\,A^{v}_{l-1}\Big{]},$

i.e.,

$\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\mathbf{1}_{A^{v}_{l}}C^{2}_{Y_{l}}\,\Big{|}\,A^{v}_{l-1}\Big{]}\\\
=\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\mathbf{1}_{A^{v}_{l}}\operatorname{\mathbb{E}}(C^{2}_{\tilde{Y}_{l}}\,|\,A^{v}_{l})\,\Big{|}\,A^{v}_{l-1}\Big{]},$

which combined with the estimate (5.13) on $D_{l}^{2}$ (replacing
$\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})^{2}$ by
$\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})$) gives

$\displaystyle\operatorname{\mathbb{E}}[D_{l}^{2}\,|\,A^{v}_{l-1}]$
$\displaystyle\preccurlyeq
2\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\operatorname{\mathbb{E}}\Big{[}(C_{Y_{l}}^{2}+\operatorname{\mathbb{E}}[C_{\tilde{Y}_{l}}^{2}\,|\,A^{v}_{l}])\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\mathbf{1}_{A^{v}_{l}}\,\Big{|}\,A^{v}_{l-1}\Big{]}$
$\displaystyle=4\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}\operatorname{\mathbb{E}}\Big{[}C_{Y_{l}}^{2}\operatorname{\mathbb{P}}(X_{v_{l}}=0\,|\,B^{v}_{l-1})\mathbf{1}_{A^{v}_{l}}\,\Big{|}\,A^{v}_{l-1}\Big{]}$
$\displaystyle\preccurlyeq
4\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}C_{v_{l}}^{2}\operatorname{\mathbb{P}}(A^{v}_{l}\,|\,A^{v}_{l-1})$
$\displaystyle=4\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}C_{v_{l}}^{2}\frac{1}{k-l+1}\operatorname{\mathbb{P}}(X_{v_{l}}=1\,|\,B^{v}_{l-1})$
$\displaystyle\preccurlyeq
4\sum_{v_{l}\in[n]\setminus\\{v_{1},\ldots,v_{l-1}\\}}C_{v_{l}}^{2}\frac{1}{k-l+1}\operatorname{\mathbb{P}}(X_{v_{l}}=1),$

where in the last inequality we used [34, Lemma 1.10], which asserts that
$\operatorname{\mathbb{P}}(X_{v_{l}}=1)\geq\operatorname{\mathbb{P}}(X_{v_{l}}=1|B^{v}_{l-1})$
(we remark that this is the only place in the proof in which we use the full
strength of the strong Rayleigh property).

Extending the summation to $[n]$, we thus obtain

$\operatorname{\mathbb{E}}[D_{l}^{2}\,|\,\mathcal{H}_{l-1}]\preccurlyeq
4\sum_{v=1}^{n}C_{v}^{2}\operatorname{\mathbb{P}}(X_{v}=1)\frac{1}{k-l+1},$

whence

$\sum_{l=1}^{k}\operatorname{\mathbb{E}}[D_{l}^{2}|\mathcal{H}_{l-1}]\preccurlyeq
4\sum_{v=1}^{n}C_{v}^{2}\operatorname{\mathbb{P}}(X_{v}=1)\log(ek)\preccurlyeq
4\log(ek)\cdot\operatorname{\mathbb{E}}\Big{[}\sum_{v=1}^{n}X_{v}C_{v}^{2}\Big{]}.$

Combining this with the already obtained bound on $\|D_{l}\|$ allows us to
apply (5.9) with $a=2K$ and
$\sigma^{2}=4\|\operatorname{\mathbb{E}}\sum_{v=1}^{n}X_{v}C_{v}^{2}\|\log(ek)$,
which ends the proof of the theorem. ∎

##  6\. Proofs of the results of Section 4

###  6.1. Propositions 4.7 and 4.9

The main idea behind the proof of Proposition 4.7 is to find an estimate on
$\|\Gamma_{+}(f)\|_{\infty}$ in terms of $\alpha$, refining (4.6), and then to
use the Herbst argument. We will need the following lemma which we state in
the matrix setting as it will be useful for the proof of Proposition 4.9 as
well.

######  Lemma 6.1.

Let $t=(t_{1},\ldots,t_{n})$ be a sequence of nonnegative numbers and let
$D_{1},\ldots,D_{n}\in\operatorname{\mathcal{H}_{d}}$ be positive semidefinite
matrices. Then for any $T_{1}\geq|t|_{1}$ and $T_{\infty}\geq|t|_{\infty}$

(6.1) $\displaystyle\big{\|}\sum_{i=1}^{n}t_{i}D_{i}\big{\|}\leq
T_{\infty}\cdot\sup\Big{\\{}\,\big{\|}\sum_{i\in\mathcal{I}}D_{i}\big{\|}\colon\mathcal{I}\subset[n],\,|\mathcal{I}|\leq\lceil
T_{1}/T_{\infty}\rceil\,\Big{\\}}.$

###### Proof.

By homogeneity we may assume without loss of generality that $T_{\infty}=1$.
We may also assume that $T_{1}$ is a positive integer. Let

$\mathcal{X}=\Big{\\{}\,x\in[0,1]^{n}\colon\sum_{i=1}^{n}x_{i}\leq
T_{1}\,\Big{\\}},\;\mathcal{Y}=\Big{\\{}\,y\in\\{0,1\\}^{n}\colon\sum_{i=1}^{n}y_{i}\leq
T_{1}\,\Big{\\}}.$

Since the right-hand side of (6.1) equals to
$\max\\{\|\sum_{i=1}^{n}y_{i}D_{i}\|\colon y\in\mathcal{Y}\\}$, whereas the
left-hand side is a convex function of $t$, the lemma will follow once we
prove that $\mathcal{X}\subset\operatorname{conv}\mathcal{Y}$. To this end, by
the Krein–Milman theorem, it is enough to show that $\mathcal{Y}$ is the set
of all extreme points of the closed convex set $\mathcal{X}$. Consider any
$x\in\mathcal{X}\setminus\mathcal{Y}$. Let $i_{0}\in[n]$ be such that
$x_{i_{0}}\in(0,1)$. If $\sum_{i}x_{i}<T_{1}$ then for $\varepsilon$
sufficiently close to zero, $x+\varepsilon e_{i_{0}},x-\varepsilon
e_{i_{0}}\in\mathcal{X}$ and so $x=\frac{1}{2}(x+\varepsilon
e_{i_{0}})+\frac{1}{2}(x-\varepsilon e_{i_{0}})$ is not an extreme point of
$\mathcal{X}$. If $\sum_{i}x_{i}=T_{1}$, then since $T_{1}$ is an integer,
there exists ${i_{1}}\neq{i_{0}}$ such that $x_{i_{1}}\in(0,1)$. Then
$x=\frac{1}{2}u+\frac{1}{2}v$, where $u=x+\varepsilon e_{i_{0}}-\varepsilon
e_{i_{1}}$, $v=x-\varepsilon e_{i_{0}}+\varepsilon e_{i_{1}}$. For
$\varepsilon$ close to zero $u,v\in\mathcal{X}$, thus again, $x$ is not an
extreme point. ∎

###### Proof of Proposition 4.7.

We recall that for $x\in\operatorname{\mathcal{B}_{n}}$ and $i,j\in[n]$,
$x^{i}$ and $x^{ij}$ denote the vectors obtained from $x$ by flipping the
$i$-th and swapping the $i$-th and $j$-th coordinates respectively. For any
$x\in\operatorname{\mathcal{B}_{n}}$, using the definition (4.3) of
$\Gamma_{+}$, Lipschitz property of $f$ and inequality $(a+b)^{2}\leq
2(a^{2}+b^{2})$ we get

(6.2)
$\displaystyle\begin{split}\Gamma_{+}(f)(x)&=\sum_{i=1}^{n}(f(x)-f(x^{i}))_{+}^{2}L(x,x^{i})+\frac{1}{2}\sum_{i,j=1}^{n}(f(x)-f(x^{ij}))_{+}^{2}L(x,x^{ij})\\\
&\leq\sum_{i=1}^{n}\alpha_{i}^{2}L(x,x^{i})+\frac{1}{2}\sum_{i,j=1}^{n}(\alpha_{i}+\alpha_{j})^{2}L(x,x^{ij})\mathbf{1}_{\\{x\neq
x^{ij}\\}}\\\
&\leq\sum_{i=1}^{n}\alpha_{i}^{2}L(x,x^{i})+2\sum_{i=1}^{n}\alpha_{i}^{2}\sum_{j=1}^{n}L(x,x^{ij})\mathbf{1}_{\\{x\neq
x^{ij}\\}}\leq 2\sum_{i=1}^{n}\alpha_{i}^{2}\sum_{y\colon y_{i}\neq
x_{i}}L(x,y).\end{split}$

Therefore, by the stability condition (4.7) we estimate
$\|\Gamma_{+}(f)\|_{\infty}\leq 2R\rho(L)|\alpha|^{2}$. Herbst’s argument
(4.5) allows to conclude the first part.

The second part of the proposition follows by observing that for a flip-swap
random walk

$\sum_{i=1}^{n}\sum_{y\colon y_{i}\neq x_{i}}L(x,y)\leq 2\cdot\Delta(L)$

so by (6.2), Lemma 6.1 applied in the scalar setting $d=1$ with
$t_{i}=2\sum_{y\colon y_{i}\neq x_{i}}L(x,y)$, $D_{i}=\alpha_{i}^{2}$,
$T_{1}=4\Delta(L)$ and $T_{\infty}=4R\rho(L)$ we can estimate

$\|\Gamma_{+}(f)\|_{\infty}\leq
4R\rho(L)\sum^{\lceil\Delta(L)/R\rho(L)\rceil}_{i=1}(\alpha_{i}^{\downarrow})^{2}$

and conclude again in virtue of Herbst’s argument (4.5). ∎

The proof of Proposition 4.9 follows along similar lines to the proof of
Proposition 4.7, the difference being that in the end, instead of Herbst’s
argument, we apply the concentration result of Aoun et al. [8], which asserts
that if $L$ satisfies the matrix Poincaré inequality with constant $C_{P}>0$

(6.3) $\operatorname{Var}(f)\preccurlyeq-
C_{P}\pi(fLf)\quad\forall\,f\colon\operatorname{\mathcal{B}_{n}}\to\operatorname{\mathcal{H}_{d}},$

(where $L$ acts on the matrix-valued function $f$ elementwise and $fLf$ is the
matrix product), then it satisfies the exponential concentration bound of the
form

(6.4) $\pi\big{(}\lambda_{max}(f-\pi(f))>t\big{)}\leq
d\exp\Big{(}\frac{-t^{2}}{2C_{P}v_{f}+t\sqrt{2C_{P}v_{f}}}\Big{)},$

where $v_{f}=\sup_{x}\|\Gamma(f)(x)\|$ (where $\Gamma$ is defined via (4.2),
again with matrix multiplication, and $\|\cdot\|$ stands for the operator
norm). Note that for $d=1$, (6.3) is just the usual scalar Poincaré
inequality.

###### Proof of Proposition 4.9.

For any $x\in\operatorname{\mathcal{B}_{n}}$ and $i,j\in[n]$, using operator
convexity of the function $x\mapsto x^{2}$ (see [11, Example V.1.3]) we get
that

(6.5)
$\big{(}f(x)-f(x^{ij})\big{)}^{2}=\big{[}\big{(}f(x)-f(x^{i})\big{)}+\big{(}f(x^{i})-f(x^{ij})\big{)}\big{]}^{2}\\\
\preccurlyeq
2\big{(}f(x)-f(x^{i})\big{)}^{2}+2\big{(}f(x^{i})-f(x^{ij})\big{)}^{2}.$

Therefore, by the definition (4.2) of $\Gamma$, by the assumed Lipschitz
property (4.8) of $f$ and by (6.5), for any
$x\in\operatorname{\mathcal{B}_{n}}$,

(6.6)
$\displaystyle\begin{split}\Gamma(f)(x)&=\frac{1}{2}\sum_{i=1}^{n}(f(x)-f(x^{i}))^{2}L(x,x^{i})+\frac{1}{4}\sum_{i,j=1}^{n}(f(x)-f(x^{ij}))^{2}L(x,x^{ij})\\\
&\preccurlyeq\frac{1}{2}\sum_{i=1}^{n}C_{i}^{2}L(x,x^{i})+\frac{1}{2}\sum_{i,j=1}^{n}(C_{i}^{2}+C_{j}^{2})L(x,x^{ij})\mathbf{1}_{\\{x\neq
x^{ij}\\}}\\\ &\preccurlyeq\sum_{i=1}^{n}C_{i}^{2}\cdot\big{[}\sum_{y\colon
y_{i}\neq x_{i}}L(x,y)\big{]}.\end{split}$

As both hand sides of (6.6) are positive semidefinite, their norms compare as
well. Therefore, as in the proof of Proposition 4.7, by Lemma 6.1 with
$t_{i}=\sum_{y\colon y_{i}\neq x_{i}}L(x,y)$, $T_{1}=2\Delta(L)$,
$T_{\infty}=2R\rho(L)$ and $D_{i}=C_{i}^{2}$

$\sup_{x\in\operatorname{\mathcal{B}_{n}}}\|\Gamma(f)(x)\|\leq
2R\rho(L)\cdot\sup\Big{\\{}\big{\|}\sum_{i\in\mathcal{I}}C_{i}^{2}\big{\|}\colon\mathcal{I}\subset[n],\,|\mathcal{I}|\leq\lceil\Delta(L)/R\rho(L)\rceil\Big{\\}}.$

Since $L$ satisfies the (scalar) modified log-Sobolev inequality (4.4), then
it satisfies the (scalar) Poincaré inequality with constant $C_{P}=2/\rho(L)$
(see, e.g., [13, p. 292], noting slightly different definitions of constants
in functional inequalities used therein) and whence by [30, Proposition 2.2]
or [27, Theorem 1.1] it satisfies the matrix Poincaré inequality (6.3) with
the same constant, which yields the conclusion in virtue of (6.4). ∎

###  6.2. Proposition 4.10

The proof of Proposition 4.10 is based on the idea introduced by Boucheron et
al. [16] and then developed by Paulin [42]. We follow the exposition from the
works of Sambale and Sinulis [45, 46]. We start with the following lemmas.

######  Lemma 6.2.

For any flip-swap random walk with generator $L$ satisfying the stability
condition (4.7) and for any $A\subset\operatorname{\mathcal{B}_{n}}$

(6.7) $\Gamma_{+}(d_{T}^{2}(\cdot,A))(x)\leq 8R\rho(L)\cdot d_{T}^{2}(x,A).$

Moreover, for any $x,y\in\operatorname{\mathcal{B}_{n}}$ and any set
$A\subset\operatorname{\mathcal{B}_{n}}$,

(6.8) $d_{T}^{2}(x,A)-d_{T}^{2}(y,A)\leq d_{H}(x,y).$

###### Proof.

For $x\in\operatorname{\mathcal{B}_{n}}$, $\alpha\in\mathbb{R}^{n}$ and a
probability measure $\mu$ on $\operatorname{\mathcal{B}_{n}}$, let
$h_{x}(\mu,\alpha)=\sum_{i}\alpha_{i}\mu(z\colon z_{i}\neq x_{i})$. By Sion’s
minmax theorem, cf. [17, p. 227],

(6.9) $d_{T}(x,A)=\inf_{\mu\in\mathcal{M}(A)}\sup_{\alpha\in
B_{2}^{n}}h_{x}(\mu,\alpha),$

where $\mathcal{M}(A)$ is the set of probability measures on $A$ and
$B_{2}^{n}=\\{\,x\in\mathbb{R}^{n}\colon|x|\leq 1\,\\}$ is the unit ball in
$\mathbb{R}^{n}$. Let $\alpha^{\ast}\in\mathbb{R}^{n}_{+}\cap B_{2}^{n}$,
$\mu^{\ast}\in\mathcal{M}(A)$ be such that
$d_{T}(x,A)=h_{x}(\mu^{\ast},\alpha^{\ast})$ and set
$\nu_{y}=\operatorname{argmin}_{\nu\in\mathcal{M}(A)}h_{y}(\nu,\alpha^{\ast})$.
Then

$\displaystyle\Gamma_{+}\big{(}d_{T}(\cdot,A)\big{)}(x)$
$\displaystyle=\sum_{y}\big{[}h_{x}(\mu^{\ast},\alpha^{\ast})-\inf_{\nu\in\mathcal{M}(A)}\sup_{\alpha\in
B_{2}^{n}}h_{y}(\nu,\alpha)\big{]}_{+}^{2}L(x,y)$
$\displaystyle\leq\sum_{y}\big{[}h_{x}(\mu^{\ast},\alpha^{\ast})-h_{y}(\nu_{y},\alpha^{\ast})\big{]}_{+}^{2}L(x,y)$
$\displaystyle\leq\sum_{y}\big{[}h_{x}(\nu_{y},\alpha^{\ast})-h_{y}(\nu_{y},\alpha^{\ast})\big{]}_{+}^{2}L(x,y)$
$\displaystyle=\sum_{y}\big{[}\sum_{i}\alpha^{\ast}_{i}\big{(}\nu_{y}(z\colon
z_{i}\neq x_{i})-\nu_{y}(z\colon z_{i}\neq y_{i})\big{)}\big{]}_{+}^{2}L(x,y)$
$\displaystyle\leq\sum_{y}\big{[}\sum_{i}\alpha^{\ast}_{i}\mathbf{1}_{\\{x_{i}\neq
y_{i}\\}}\big{]}^{2}L(x,y)$ $\displaystyle\leq
2\sum_{i}(\alpha^{\ast}_{i})^{2}\sum_{y\colon y_{i}\neq x_{i}}L(x,y)\leq
2R\rho(L),$

where the penultimate inequality follows since $L$ is a flip-swap random walk
and therefore $L(x,y)>0$ implies that $d_{H}(x,y)\leq 2$ and so at most two
elements of the sum $\sum_{i}\alpha_{i}^{\ast}\mathbf{1}_{\\{x_{i}\neq
y_{i}\\}}$ are non-zero, whence we may apply the inequality $(a+b)^{2}\leq
2(a^{2}+b^{2})$. The last inequality is a consequence of the condition
$\alpha^{\ast}\in B_{2}^{n}$ and the stability condition (4.7). We conclude
(6.7) using the definition of $\Gamma_{+}$ and estimating
$(a-b)^{2}_{+}(a+b)_{+}^{2}\leq 4a^{2}(a-b)_{+}^{2}$.

To show the second part, note that (6.9) together with the Cauchy–Schwarz
inequality imply that

$d_{T}^{2}(x,A)=\inf_{\mu\in\mathcal{M}(A)}\sum_{i}\big{(}\mu(z\colon
z_{i}\neq x_{i})\big{)}^{2}=\sum_{i}\big{(}\mu^{\ast}_{x}(z\colon z_{i}\neq
x_{i})\big{)}^{2}$

for some $\mu^{\ast}_{x}\in\mathcal{M}(A)$. Therefore, for any
$x,y\in\operatorname{\mathcal{B}_{n}}$

$d_{T}^{2}(x,A)-d_{T}^{2}(y,A)\leq\sum_{i}\Big{[}\big{(}\mu^{\ast}_{x}(z\colon
z_{i}\neq x_{i})\big{)}^{2}-\big{(}\mu^{\ast}_{x}(z\colon z_{i}\neq
y_{i})\big{)}^{2}\Big{]}\leq\sum_{i}\mathbf{1}_{\\{x_{i}\neq y_{i}\\}},$

as desired. ∎

Using the inequality $1-e^{-z}\leq z$ we observe that for any
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$,

$\displaystyle\operatorname{\mathcal{E}}(e^{f},f)=\sum_{x}\pi(x)e^{f(x)}\Big{[}\sum_{y}(f(x)-f(y))_{+}(1-e^{f(y)-f(x)})L(x,y)\Big{]}\leq\pi\big{(}e^{f}\Gamma_{+}(f)\big{)}.$

Therefore, the modified log-Sobolev inequality (4.4) implies the following
inequality stated in Bobkov and Götze [12]:

(6.10)
$\rho(L)\operatorname{Ent}_{\pi}(e^{f})\leq\pi\big{(}e^{f}\tilde{\Gamma}(f)^{2}\big{)}$

with operator $\tilde{\Gamma}(f)=\sqrt{\Gamma_{+}(f)}$ (note that in [12]
$\tilde{\Gamma}$ is denoted by $\Gamma$, we use $\tilde{\Gamma}$ to avoid a
conflict of notation). As a consequence, the hypothesis of [12, Theorem 2.1]
(formula (1.1)) therein holds under the assumption of the modified log-Sobolev
inequality (4.4) (with $c=2/\rho(L)$). As a result, the following lemma
follows directly by the derivation of [12, equation (2.4)] with a slight
adjustment of constants (see also [5]).

######  Lemma 6.3.

If a measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfies the modified
log-Sobolev inequality (4.4) and
$f\colon\operatorname{\mathcal{B}_{n}}\to[0,\infty)$ is such that
$\Gamma_{+}(f)\leq Cf$ for some constant $C>0$, then for all $t>C/\rho(L)$,

(6.11)
$\pi\big{(}\exp(f/t)\big{)}\leq\exp\Big{(}\frac{\pi(f)}{t-C/\rho(L)}\Big{)}.$

We are finally in position to prove Proposition 4.10.

###### Proof of Proposition 4.10.

To lighten notation, denote $f(x)=d_{T}^{2}(x,A)$ for
$x\in\operatorname{\mathcal{B}_{n}}$ and some fixed set
$A\subset\operatorname{\mathcal{B}_{n}}$. Denote also $h(z)=({e^{z}-1})/{z}$
for $z\in[0,\infty)$ and $Df_{y}(x)=f(x)-f(y)$ for
$x,y\in\operatorname{\mathcal{B}_{n}}$, and note that $h$ is an increasing
function. Starting with the modified log-Sobolev inequality (4.4) we have for
all $\lambda>0$,

$\displaystyle\operatorname{Ent}_{\pi}(e^{-\lambda f})$
$\displaystyle\leq\lambda/\rho(L)\cdot\operatorname{\mathcal{E}}(e^{-\lambda
f},-f)$ (by reversibility of $L$)
$\displaystyle=\lambda/\rho(L)\sum_{x,y}\big{(}Df_{y}(x)\big{)}_{+}\big{(}e^{-\lambda
f(y)}-e^{-\lambda f(x)}\big{)}L(x,y)\pi(x)$
$\displaystyle=\lambda^{2}/\rho(L)\sum_{x}\pi(x)e^{-\lambda
f(x)}\Big{[}\sum_{y}\big{(}Df_{y}(x)\big{)}_{+}^{2}h\big{(}\lambda
Df_{y}(x)\big{)}L(x,y)\Big{]}$ (by (6.8))
$\displaystyle\leq\lambda^{2}h(2\lambda)/\rho(L)\cdot\pi\big{(}e^{-\lambda
f}\Gamma_{+}(f)\big{)}$ (by (6.7)) $\displaystyle\leq
8R\lambda^{2}h(2\lambda)\cdot\pi\big{(}e^{-\lambda f}f\big{)}$
$\displaystyle\leq 8R\lambda^{2}h(2\lambda)\cdot\pi(e^{-\lambda f})\pi(f),$

where the last inequality follows by convexity of the function $t\mapsto t\log
t$. Therefore, using the entropy method (cf., e.g., [17, Chapter 6]) and
monotonicity of $h$, we have for every $\lambda>0$,

$\displaystyle\pi\big{(}\exp(\lambda(\pi(f)-f)\big{)}$
$\displaystyle=\exp\Big{(}\lambda\int_{0}^{\lambda}\frac{d}{ds}\Big{[}\frac{1}{s}\log\pi(e^{-sf})\Big{]}\,ds\Big{)}$
$\displaystyle=\exp\Big{(}\lambda\int_{0}^{\lambda}\frac{\operatorname{Ent}_{\pi}(e^{-sf)}}{s^{2}\pi(e^{-sf})}\,ds\Big{)}$
$\displaystyle\leq\exp\Big{(}\lambda\cdot
8R\pi(f)\int_{0}^{\lambda}h(2s)\,ds\Big{)}\leq\exp\big{(}4R\lambda(e^{2\lambda}-1)\pi(f)\big{)}.$

By Chebyshev’s exponential inequality

$\pi(A)=\pi\big{(}\pi(f)-f\geq\pi(f)\big{)}\leq\exp\Big{(}\lambda\big{(}4R(e^{2\lambda}-1)-1\big{)}\pi(f)\Big{)}.$

Taking $\lambda=\frac{1}{2}\log(1+\frac{1}{8R})$ and estimating $\log(1+x)\geq
x/(x+1)$ for $x\geq 1$ gives

(6.12)
$\pi(A)\leq\exp\Big{(}-\frac{1}{4}\log\big{(}1+\frac{1}{8R}\big{)}\pi(f)\Big{)}\leq\exp\Big{(}-\frac{\pi(f)}{32R+4}\Big{)}.$

We conclude by dividing (6.12) by its right hand side and using Lemma 6.3 with
$t=4+40R$ and $C=8R\rho(L)$ (in virtue of Lemma 6.2). ∎

###  6.3. Proposition 4.11

Before we move to the proof of Proposition 4.11, let us comment a bit on a
background result. Using the equivalence between the modified log-Sobolev
inequality (4.4) and the family of Beckner inequalities together with the
approach developed by Boucheron et al. [15], it was shown in [2, Proposition
3.1] that the following moment estimate is implied by the modified log-Sobolev
inequality. Below we will denote by $\|\cdot\|_{p}$ the norm in $L^{p}(\pi)$.

######  Proposition 6.4.

If a probability measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$ satisfies
the modified log-Sobolev inequality (4.4), then for any $p\geq 2$,

(6.13) $\|(f-\pi(f))_{+}\|_{p}\leq
C\sqrt{p/{\rho(L)}}\|\sqrt{\Gamma_{+}(f)}\|_{p},$

where $C=\sqrt{{3\sqrt{e}}/({\sqrt{e}-1})}$.

A general method of deriving estimates for polynomials from moment
inequalities of the form (6.13) has been presented in [4] in the continuous
case, and in [1, 2] in the context of Glauber dynamics. To obtain results for
flip-swap random walks we will adapt a version of this method introduced
recently by Sambale and Sinulis [46] for multislices.

###### Proof of Proposition 4.11.

Below we write $C$ to denote universal constants and $C_{a}$ to denote
constants depending only on the parameter $a$. In both cases the constants may
change values between occurrences. Let
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ be a tetrahedral
polynomial. By $\partial_{i}$ we denote the partial derivative with respect to
the $i$-th coordinate. If $x,y\in\operatorname{\mathcal{B}_{n}}$ differ at the
$i$-th coordinate only, then by the fact that $f$ is linear in each coordinate

$|f(x)-f(y)|=\big{|}\partial_{i}f(x)\big{|}.$

Similarly, if $x$ and $y$ differ only by a swap of the $i$-th and $j$-th
coordinate, we have

$|f(x)-f(y)|=|\partial_{i}f(x)(y_{i}-x_{i})+\partial_{j}f(x)(y_{j}-x_{j})+\partial_{i}\partial_{j}f(x)(y_{i}-x_{i})(y_{j}-x_{j})|\\\
\leq|\partial_{i}f(x)|+|\partial_{j}f(x)|+|\partial_{i}\partial_{j}f(x)|.$

Thus

$\Gamma(f)(x)=\frac{1}{2}\sum_{i=1}^{n}(f(x)-f(x^{i}))^{2}L(x,x^{i})+\frac{1}{2}\sum_{1\leq
i<j\leq n}(f(x)-f(x^{ij}))^{2}L(x,x^{ij})\\\
\leq\frac{1}{2}\sum_{i=1}^{n}|\partial_{i}f(x)|^{2}L(x,x^{i})+\frac{3}{2}\sum_{\stackrel{{\scriptstyle
1\leq i<j\leq n}}{{x^{ij}\neq
x}}}(|\partial_{i}f(x)|^{2}+|\partial_{j}f(x)|^{2}+|\partial_{i}\partial_{j}f(x)|^{2})L(x,x^{ij})\\\
\leq
R\rho(L)\Big{(}3.5\sum_{i=1}^{n}|\partial_{i}f(x)|^{2}+0.75\sum_{i,j=1}^{n}|\partial_{i}\partial_{j}f(x)|^{2}\Big{)},$

where in the last inequality we used the stability condition (4.7). Note that
since $f$ is tetrahedral, $\partial_{i}\partial_{i}f(x)=0$ for all $i$.

Combining the above equality with Proposition 6.4 we obtain that for every
tetrahedral polynomial $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$

(6.14) $\displaystyle\|f-\pi(f)\|_{p}\leq
C\sqrt{p}\sqrt{R}\Big{(}\big{\|}|\nabla
f|\big{\|}_{p}+\big{\|}\|\nabla^{2}f\|_{HS}\big{\|}_{p}\Big{)},$

where $C$ is a universal constant.

In the subsequent part of the proof we are going to need some auxiliary
notation. For $d$-tensors $A=(a_{{\bf i}})_{{\bf i}\in[n]^{d}}$, $B=(b_{\bf
i})_{{\bf i}\in[n]^{d}}$ define

$\langle A,B\rangle=\sum_{{\bf i}\in[n]^{d}}a_{\bf i}b_{\bf i}.$

Let us now consider a family of stochastically independent random tensors
$\\{G^{I}\colon I\subseteq\mathbb{N},|I|\in\\{1,2\\}\\}$, given by
$G^{\\{m\\}}=(g^{\\{m\\}}_{i})_{i\in[n]}$,
$G^{\\{l,k\\}}=(g^{\\{l,k\\}}_{i,j})_{i,j\in[n]}$, with coefficients being
i.i.d. standard Gaussian variables. Denote by $P_{d,\leq 2}$ the family of all
partitions of the set $[d]$ into non-empty subsets of cardinality at most 2.
Finally, for any positive integers $d$ and $l$ and
$\mathcal{J}=\\{J_{1},\ldots,J_{l}\\}\in P_{d,\leq 2}$ define the random
$d$-tensor $G_{\mathcal{J}}=(\prod_{j=1}^{l}g^{J_{j}}_{{\bf i}_{J_{j}}})_{{\bf
i}\in[n]^{d}}$. For instance
$G_{\\{\\{1,3\\},\\{2\\}\\}}=(g^{\\{1,3\\}}_{i_{1}i_{3}}g^{\\{2\\}}_{i_{2}})_{i_{1},i_{2},i_{3}\in[n]}$.

Using the fact that the $p$-th moment of a mean zero Gaussian variable with
variance $\sigma^{2}$ is for $p\geq 2$ comparable to $\sqrt{p}\sigma$ up to
universal constants, we can rewrite (6.14) as

(6.15) $\displaystyle\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq
C\sqrt{R}\Big{(}\|\langle\nabla
f(X),G^{\\{1\\}}\rangle\|_{p}+\|\langle\nabla^{2}f(X),G^{\\{1,2\\}}\rangle\|_{p}\Big{)},$

where $X$ is a random vector with law $\pi$, independent of the family
$\\{G^{I}\\}$.

The inequality (6.15) constitutes a basis for the induction argument leading
to the following inequality valid for any
$f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ , $d\geq 1$ and $p\geq
2$,

(6.16)
$\displaystyle\begin{split}\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq&C_{d}\Big{(}\sum_{l=d}^{2d}\sum_{\mathcal{J}\in
P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\\\
&+\sum_{l=1}^{2d-2}\sum_{\mathcal{J}\in P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\Big{)}.\end{split}$

Before we prove the above estimate, let us show how it implies the statement
of the proposition. If $f$ is a tetrahedral polynomial of degree $d$, then
$\nabla^{l}f=0$ for $l>d$, moreover $\nabla^{d}f$ is constant and so
$\nabla^{d}f(X)=\operatorname{\mathbb{E}}\nabla^{d}f(X)$. Thus (6.16) reduces
to

$\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq
C_{d}\sum_{l=1}^{d}\sum_{\mathcal{J}\in P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}.$

We can now use moment estimates for tetrahedral homogeneous polynomials in
i.i.d. standard Gaussian variables due to Latała [35], which assert that for
any $l$-tensor $A=(a_{\bf i})_{{\bf i}\in[n]^{l}}$ and $p\geq 2$,

$\|\langle A,G_{\\{\\{1\\},\ldots,\\{l\\}\\}}\rangle\|_{p}\leq
C_{l}\sum_{\mathcal{J}\in P_{l}}p^{|\mathcal{J}|/2}\|A\|_{\mathcal{J}}.$

Applying this inequality to
$\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle$
(we treat here $\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X)$ as a
$|\mathcal{J}|$-tensor by merging the indices according to the partition
$\mathcal{J}$), we obtain

$\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq
C_{d}\sum_{l=1}^{d}\sum_{\mathcal{J}\in P_{l,\leq
2}}R^{|\mathcal{J}|/2}\sum_{\mathcal{I}\in
P_{l}\colon\mathcal{I}\succ\mathcal{J}}p^{|\mathcal{I}|/2}\|\operatorname{\mathbb{E}}\nabla^{l}f(X)\|_{\mathcal{I}},$

where $\mathcal{I}\succ\mathcal{J}$ if every element of $\mathcal{I}$ is a
union of certain elements of $\mathcal{J}$. Rearranging the terms and taking
into account that in a non-trivial case $R$ is bounded away from zero by an
absolute constant (see Remark 4.4), which gives $R^{|\mathcal{J}|/2}\leq
C_{d}R^{l/2}$ for $\mathcal{J}\in P_{l,\leq 2}$, we get

$\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq
C_{d}\sum_{l=1}^{d}\sum_{\mathcal{I}\in
P_{l}}R^{l/2}p^{|\mathcal{I}|/2}\|\operatorname{\mathbb{E}}\nabla^{l}f(X)\|_{\mathcal{I}}$

for $p\geq 2$. This implies the tail inequality of the proposition in the
standard way by the use of Chebyshev’s inequality
$\operatorname{\mathbb{P}}(|f(X)-\operatorname{\mathbb{E}}f(X)|\geq
e\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p})\leq e^{-p}$ followed by an
appropriate change of variables and adjustment of constants. We leave the
details to the reader and turn to the proof of (6.16).

We will proceed by induction on $d$. For $d=1$, using the definitions of
$G_{\\{1\\}}$ and $G_{\\{\\{1,2\\}\\}}$ one can easily see that (6.16) reads
as

$\displaystyle\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq$ $\displaystyle
C\Big{(}\sqrt{R}\|\langle\nabla
f(X),G^{\\{1\\}}\rangle\|_{p}+\sqrt{R}\|\langle\nabla^{2}f(X),G^{\\{1,2\\}}\rangle\|_{p}$
$\displaystyle+R\|\langle\nabla^{2}f(X),G_{\\{\\{1\\},\\{2\\}\\}}\rangle\|_{p}\Big{)},$

which is clearly weaker than (6.15). Let us thus assume that the inequality
holds for all positive integers smaller than $d$. Applying the inequality with
$d-1$ and combining it with the triangle inequality in $L_{p}$ we get (recall
that the value of $C_{d}$ may change between occurences)

(6.17)
$\displaystyle\begin{split}\|f(X)-\operatorname{\mathbb{E}}f(X)\|_{p}\leq&C_{d}\Big{(}\sum_{l=d-1}^{2d-2}\sum_{\mathcal{J}\in
P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\\\
&+\sum_{l=1}^{2d-4}\sum_{\mathcal{J}\in P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\Big{)}\\\
\leq&C_{d}\Big{(}\sum_{l=d-1}^{2d-2}\sum_{\mathcal{J}\in P_{l,\leq
2}}R^{|\mathcal{J}|/2}\|\langle\nabla^{l}f(X),G_{\mathcal{J}}\rangle-\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\\\
&+\sum_{l=1}^{2d-2}\sum_{\mathcal{J}\in P_{l,\leq
2}}2R^{|\mathcal{J}|/2}\|\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\Big{)}.\end{split}$

An application of inequality (6.15) conditionally on $G_{\mathcal{J}}$ to the
functions $g_{l,\mathcal{J}}(x)=\langle\nabla^{l}f(x),G_{\mathcal{J}}\rangle$
for $l=d-1,\ldots,2d-2$ and $\mathcal{J}\in P_{l,\leq 2}$ (note that
$g_{l,\mathcal{J}}$’s are tetrahedral polynomials), followed by the Fubini
theorem, gives

$\|\langle\nabla^{l}f(X),G_{\mathcal{J}}\rangle-\langle\operatorname{\mathbb{E}}_{X}\nabla^{l}f(X),G_{\mathcal{J}}\rangle\|_{p}\leq
C\sqrt{R}\Big{(}\|\langle\nabla^{l+1}f(X),G_{\mathcal{J}\cup\\{\\{l+1\\}\\}}\rangle\|_{p}\\\
+\|\langle\nabla^{l+2}f(X),G_{\mathcal{J}\cup\\{\\{l+1,l+2\\}\\}}\rangle\|_{p}\Big{)},$

which combined with (6.17) concludes the induction step, thus proving (6.16).
∎

##  7\. Proofs of the results of Section 3

By virtue of the abstract results of Section 4, all the results of Section 3
follow from the observation that there exist a flip-swap random walk on
$\operatorname{\mathcal{B}_{n}}$ with stationary measure $\pi=\pi(p,k)$ that
satisfy the stability condition (4.7) with constant $R=2$ for all
$p\in(0,1)^{n}$ and $k=0,\ldots,n$ (cf. Proposition 7.3). The rest of this
section is devoted to proving this fact.

We start with the following lemma, the proof of which is postponed until the
end of this section.

######  Lemma 7.1.

For every $n\in\mathbb{N}$, $p\in(0,1)^{n}$ and $k\in[n]$, there exist a
coupling $(Z,Z^{\prime})$ of measures $\pi(p,k)$ and $\pi(p,k-1)$ such that
for all $x\in\operatorname{supp}\pi(p,k-1)$, and $r\in[n]$ such that
$x_{r}=0$,

(7.1)
$\operatorname{\mathbb{P}}(Z=x+e_{r}\,|\,Z^{\prime}=x)=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{Z_{r}=1\\}}}{\sum_{l=1}^{n}\mathbf{1}_{\\{Z_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}}\Big{]}$

and for all $x\in\operatorname{supp}\pi(p,k)$, and $r\in[n]$ such that
$x_{r}=1$,

(7.2)
$\operatorname{\mathbb{P}}(Z^{\prime}=x-e_{r}\,|\,Z=x)=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{Z^{\prime}_{r}=0\\}}}{\sum_{l=1}^{n}\mathbf{1}_{\\{Z^{\prime}_{l}=0\\}}\mathbf{1}_{\\{x_{l}=1\\}}}\Big{]}.$

Our approach to defining an $R$-stable generator $L_{\pi}$ will be based on
the inductive construction of Hermon and Salez [29] in the $k$-homogeneous
case, which we will now recall. The construction works for any $k$-homogeneous
probability measure $\pi$ on $\operatorname{\mathcal{B}_{n}}$, satisfying the
SCP and produces a generator of a $\pi$-reversible flip-swap random walk
$Q^{\ast}$ such that $\rho(Q^{\ast})\geq 1$ and $\Delta(Q^{\ast})\leq 2k$.

To simplify the notation, we are going to treat vectors $x_{\neq l}$ for
$x\in\operatorname{\mathcal{B}_{n}}$ and $l\in[n]$ sometimes as elements of
$\\{0,1\\}^{[n]\setminus\\{l\\}}$ (this is how they were defined at the
beginning of Section 2) and sometimes as elements of $\mathcal{B}_{n-1}$ (with
the natural identification, i.e., preserving the order of coordinates). The
exact meaning will be clear from the context. The same convention will apply
to random vectors, e.g., to $X_{\neq l}$.

In the case $n=1$, we let $Q$ be the trivial generator on a one-point space.
Clearly then $\rho(Q)=\infty$ and $\Delta(Q)=0$.

For $n>1$, $l\in[n]$ and $x,y\in\operatorname{supp}\pi$, $x\neq y$, we set

(7.3) $\displaystyle Q^{(l)}(x,y)=\begin{cases}\mathbb{P}\left(U=y_{\neq
l}\,|\,V=x_{\neq l}\right)\mathbb{P}\left(X_{l}\neq
x_{l}\right)\quad&\text{if}\quad x_{l}\neq y_{l},\\\ Q^{(l)}_{x_{l}}(x_{\neq
l},y_{\neq l})\quad&\text{else},\end{cases}$

where $X$ is a random vector with law $\pi$ and $(U,V)$ is any coupling
between $\mathcal{L}(X_{\neq l}\,|\,X_{l}=y_{l})$ and $\mathcal{L}(X_{\neq
l}\,|\,X_{l}=x_{l})$ given by the SCP222We note a small typo in the cited
preprint version of [29] – for $Q$ to be self-adjoint we need to have $\pi(x)$
in the denominator of each expression in [29, equation (90)]. This change is
also consistent with the subsequent part of the proof in [29]. and
$Q^{(l)}_{x_{l}}$ is any flip-swap generator on $\mathcal{B}_{n-1}$ with
stationary distribution $\mathcal{L}(X_{\neq l}\,|\,X_{l}=x_{l})$ such that
$\rho(Q^{(l)}_{x_{l}})\geq 1$ and $\Delta(Q^{(l)}_{x_{l}})\leq 2(k-x_{i})$,
the existence of which is provided by the induction scheme. We define the
diagonal elements of $Q^{(l)}$ so that the row sums vanish. Finally put

(7.4) $\displaystyle Q^{\ast}=\frac{1}{n}\sum_{l=1}^{n}Q^{(l)}.$

Then by (the proof of) [29, Theorem 2], we have $\rho(Q^{\ast})\geq 1$,
$\Delta(Q^{\ast})\leq 2k$.

Now we are in position to construct the generator $L_{\pi}$. Let
$X\sim\pi=\pi(p,k)$ for some $p\in(0,1)^{n}$ and $k\in\\{0,\ldots,n\\}$.
Observe that for any $y_{l}\in\\{0,1\\}$, we have $\mathcal{L}(X_{\neq
l}\,|\,X_{l}=y_{l})=\pi(p_{\neq l},k-y_{l})$, in particular in the above
recursive construction we can restrict our attention to the class of
conditional Bernoulli distributions and use as $Q_{x_{l}}^{(l)}$ the
generators defined for such measures in dimension $n-1$. Moreover, for $(U,V)$
we can take the coupling $(Z,Z^{\prime})$ (if $y_{l}=0$) or $(Z^{\prime},Z)$
(if $y_{l}=1$) given by Lemma 7.1 applied in dimension $n-1$ with $p_{\neq l}$
instead of $p$ (note that since the right-hand side of (7.1) summed over $r$
such that $x_{r}=0$ gives one, we indeed have $Z\triangleright Z^{\prime}$,
which makes this coupling a legitimate choice in the Hermon–Salez
construction). Let us define $L_{\pi}$ as the outcome of the Hermon–Salez
construction with the above choices of $Q_{x_{l}}^{(l)}$ and $(U,V)$. Thus,
formally for $n=1$ we let $L_{\pi}$ be the trivial generator and for $n>1$ and
$l\in[n]$ we set

(7.5) $\displaystyle L_{\pi}=\frac{1}{n}\sum_{l=1}^{n}L^{(l)}$

with

(7.6) $\displaystyle L^{(l)}(x,y)=\begin{cases}\mathbb{P}\left(U=y_{\neq
l}\,|\,V=x_{\neq l}\right)\mathbb{P}\left(X_{l}\neq
x_{l}\right)\quad&\text{if}\quad x_{l}\neq y_{l},\\\ L_{\pi_{l}}(x_{\neq
l},y_{\neq l})\quad&\text{else},\end{cases}$

for $x\neq y$, where $(U,V)$ is the coupling of $\pi(p_{\neq l},k-y_{l})$ and
$\pi(p_{\neq l},k-x_{l})$ given by Lemma 7.1, and $\pi_{l}=\pi(p_{\neq
l},k-y_{l})$ (again the diagonal elements are adjusted so that the row sums
vanish).

Then, the results by Hermon and Salez, specialized to $L_{\pi}$ give

######  Proposition 7.2.

The generator $L_{\pi}$ constructed according to (7.5) generates a reversible
flip-swap random walk with stationary measure $\pi$ such that
$\rho(L_{\pi})\geq 1$ and $\Delta(L_{\pi})\leq 2k$.

Our main result concerning conditional Bernoulli distributions, underlying all
the results from Section 3 is

######  Proposition 7.3.

The generator $L_{\pi}$ constructed according to (7.5) with stationary measure
$\pi$ satisfies the stability condition (4.7) with $R=2$.

###### Proof of Proposition 7.3.

We proceed by induction in the dimension $n$.

For $n=1$ the only possibilities are $k=0$ and $k=1$ and in both cases the
left-hand side of (4.7) vanishes. Thus the stability condition (4.7) is
satisfied with any nonnegative $R$.

Assume the induction hypothesis holds for $n-1$ and fix
$x\in\operatorname{supp}\pi$ and $i\in[n]$. We may and do assume that
$k\in\\{1,\ldots,n-1\\}$ as otherwise $L_{\pi}$ trivializes.

Since $\rho(L_{\pi})\geq 1$, it is enough to show that

(7.7) $\displaystyle\max_{x\in\operatorname{supp}\pi;\,i\in[n]}\sum_{y\colon
y_{i}\neq x_{i}}L_{\pi}(x,y)\leq 2.$

As in the definition of $L_{\pi}$ we will denote by $X$ a random variable with
distribution $\pi$.

If $x_{i}=0$, then by (7.5)

(7.8) $\sum_{y\colon y_{i}\neq x_{i}}L_{\pi}(x,y)=\sum_{j\colon
x_{j}=1}\frac{1}{n}\sum_{l=1}^{n}L^{(l)}(x,x^{ij})\\\
=\sum_{l\in[n]\setminus\\{i,j\\}}\frac{1}{n}\sum_{j\colon
x_{j}=1}L^{(l)}(x,x^{ij})+\frac{1}{n}\sum_{j\colon
x_{j}=1}L^{(i)}(x,x^{ij})+\frac{1}{n}\sum_{j\colon x_{j}=1}L^{(j)}(x,x^{ij}),$

where we recall that $x^{ij}=x+e_{i}-e_{j}$. We estimate each term on the
right hand side separately.

For $l\in[n]$ let $\zeta_{l}$ be the unique increasing bijection between
$[n]\setminus\\{l\\}$ and $[n-1]$. If $l\neq i,j$, then for $y=x^{ij}$ we have
$y_{l}=x_{l}$ and so, by (7.6), $L^{(l)}(x,y)=L_{\pi_{l}}(x_{\neq l},y_{\neq
l})$, where $\pi_{l}=\pi(p_{\neq l},k-x_{l})$. Thus, denoting
$r_{l}=\zeta_{l}(i)$, we get

(7.9) $\sum_{l\in[n]\setminus\\{i,j\\}}\frac{1}{n}\sum_{j\colon
x_{j}=1}L^{(l)}(x,x^{ij})=\frac{1}{n}\sum_{l\in[n]\setminus\\{i\\}}\sum_{j\neq
l\colon x_{j}=1}L_{\pi_{l}}(x_{\neq l},(x^{ij})_{\neq l})\\\
=\frac{1}{n}\sum_{l\in[n]\setminus\\{i\\}}\sum_{y\in\mathcal{B}_{n-1}\colon
y_{r_{l}}\neq(x_{\neq l})_{r_{l}}}L_{\pi_{l}}(x_{\neq
l},y)\leq\frac{n-1}{n}\cdot 2,$

where the last inequality follows from the induction assumption applied to
$\pi_{l}$.

The second term of (7.8) is estimated again using the definition (7.6).
Indeed, if $x_{j}=1$, then for $y=x^{ij}$ we have $x_{i}\neq y_{i}$. Thus,
recalling that $(U,V)$ is a coupling between the laws $\mathcal{L}(X_{\neq
i}\,|\,X_{i}=1)$ and $\mathcal{L}(X_{\neq i}\,|\,X_{i}=0)$ such that
$V\triangleright U$, we obtain

(7.10) $\frac{1}{n}\sum_{j\colon
x_{j}=1}L^{(i)}(x,x^{ij})=\frac{1}{n}\sum_{j\colon
x_{j}=1}\mathbb{P}\left(U=(x^{ij})_{\neq i}\,|\,V=x_{\neq
i}\right)\mathbb{P}\left(X_{i}\neq x_{i}\right)\\\
=\frac{1}{n}\operatorname{\mathbb{P}}\big{(}X_{i}=1\big{)}\leq\frac{1}{n}.$

Let us pass to the last term of (7.8). We stress that this is the crucial part
of the proof, the only one in which we use the specific form of the coupling
$(U,V)$ used in the construction of $L_{\pi}$.

To estimate this last term we use (7.1) from Lemma 7.1 combined with the fact
that if $x_{i}=0$ and $x_{j}=1$, then for $y=x^{ij}$, $y_{j}=0\neq x_{j}$ and
so $(U,V)$ from (7.6) is the coupling between the laws $\pi(p_{\neq j},k)$ and
$\pi(p_{\neq j},k-1)$ given by Lemma 7.1 (in dimension $n-1$). For $j\in[n]$
consider a $\mathcal{B}_{n-1}$-valued random vector
$Z^{(j)}\sim\mathcal{L}(X_{\neq j}\,|\,X_{j}=0)=\pi(p_{\neq j},k)$. Note also
that since $X,x$ have the same number of ones, we have

(7.11)
$\displaystyle\sum_{l=1}^{n}\mathbf{1}_{\\{X_{l}=0\\}}\mathbf{1}_{\\{x_{l}=1\\}}=\sum_{l=1}^{n}\mathbf{1}_{\\{X_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}.$

Putting all the above observations together, we obtain

$\displaystyle\frac{1}{n}\sum_{j\colon x_{j}=1}L^{(j)}(x,x^{ij})$
$\displaystyle\stackrel{{\scriptstyle\text{\eqmakebox[a][c]{{\rm Lemma}\,
\ref{L:CB_coupling},\, \eqref{def:Ll}}}}}{{=}}\frac{1}{n}\sum_{j\colon
x_{j}=1}\operatorname{\mathbb{E}}\big{[}\frac{\mathbf{1}_{\\{Z^{(j)}_{i}=1\\}}}{\sum_{l\neq
j}\mathbf{1}_{\\{Z^{(j)}_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}}\big{]}\operatorname{\mathbb{P}}\big{(}X_{j}=0\big{)}$
(7.12)
$\displaystyle\begin{split}&\stackrel{{\scriptstyle\text{\eqmakebox[a][c]{}}}}{{=}}\frac{1}{n}\sum_{j\colon
x_{j}=1}\operatorname{\mathbb{E}}\big{[}\mathbf{1}_{\\{X_{i}=1\\}}\frac{\mathbf{1}_{\\{X_{j}=0\\}}}{\sum_{l\neq
j}\mathbf{1}_{\\{X_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}}\big{]}\\\
&\stackrel{{\scriptstyle\text{\eqmakebox[a][c]{$x_{j}=1$}}}}{{=}}\frac{1}{n}\sum_{j\colon
x_{j}=1}\operatorname{\mathbb{E}}\big{[}\mathbf{1}_{\\{X_{i}=1\\}}\frac{\mathbf{1}_{\\{X_{j}=0\\}}}{\sum_{l}\mathbf{1}_{\\{X_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}}\big{]}\\\
&\stackrel{{\scriptstyle\text{\eqmakebox[a][c]{\eqref{eq:zmiana}}}}}{{=}}\frac{1}{n}\sum_{j\colon
x_{j}=1}\operatorname{\mathbb{E}}\big{[}\mathbf{1}_{\\{X_{i}=1\\}}\frac{\mathbf{1}_{\\{X_{j}=0\\}}}{\sum_{l}\mathbf{1}_{\\{X_{l}=0\\}}\mathbf{1}_{\\{x_{l}=1\\}}}\big{]}\\\
&\stackrel{{\scriptstyle\text{\eqmakebox[a][c]{}}}}{{=}}\frac{1}{n}\operatorname{\mathbb{P}}\big{(}X_{i}=1\big{)}\leq\frac{1}{n}.\end{split}$

Combining the estimates (7.9), (7.10) and (7) with (7.8) yields (7.7) and thus
the stability condition (4.7) with $R=2$ in the case $x_{i}=0$. The case
$x_{i}=1$ is analogous, the main difference being that in (7) we use (7.2) in
place of (7.1) from Lemma 7.1.

Together the two cases give the induction step and conclude the proof of the
proposition. ∎

Let us conclude this section with the proof of Lemma 7.1.

###### Proof of Lemma 7.1.

For $x\in\operatorname{\mathcal{B}_{n}}$, let $\kappa(x)=\sum_{i}x_{i}$ and
let $B$ be a vector of independent Bernoulli random variables with
probabilities of success given by $p=(p_{1},\ldots,p_{n})$. Consider three
$\operatorname{\mathcal{B}_{n}}$-valued random variables:
$\widehat{Z}\sim\mathcal{L}(B\,|\,\kappa(B)=k)$,
$Z^{\prime}\sim\mathcal{L}(B\,|\,\kappa(B)=k-1)$ and $Z$ such that for all
$x,y\in\operatorname{\mathcal{B}_{n}}$,

(7.13) $\displaystyle\operatorname{\mathbb{P}}(Z=y|Z^{\prime}=x)=h(y,x),$

where

$h(y,x)=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{\widehat{Z}_{r}=1\\}}}{\sum_{l}\mathbf{1}_{\\{\widehat{Z}_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}}\Big{]}$

if $y=x+e_{r}$ for some $r\in[n]$ and $\kappa(x)=k-1$, and $h(y,x)=0$
otherwise. Note that for $x\in\operatorname{\mathcal{B}_{n}}$ such that
$\kappa(x)=k-1$,
$\sum_{l}\mathbf{1}_{\\{\widehat{Z}_{l}=1\\}}\mathbf{1}_{\\{x_{l}=0\\}}>0$
with probability one, so $h(y,x)$ is well defined. Moreover, for such $x$

$\sum_{y\in\operatorname{\mathcal{B}_{n}}}h(y,x)=\sum_{r\colon
x_{r}=0}h(x+e_{r},x)=1,$

which guarantees the existence of the couple $(Z,Z^{\prime})$ satisfying
(7.13). Thus to prove (7.1) it is enough to show that $Z\sim\widehat{Z}$,
i.e., that
$\sum_{x\in\operatorname{\mathcal{B}_{n}}}h(y,x)\operatorname{\mathbb{P}}(Z^{\prime}=x)=\operatorname{\mathbb{P}}(\widehat{Z}=y)$
for any $y\in\operatorname{\mathcal{B}_{n}}$ such that $\kappa(y)=k$.

Observe that for any $r\in[n]$ such that $x_{r}=0$ and $\kappa(x)=k-1$

(7.14)
$\frac{\mathbb{P}\left(Z^{\prime}=x\right)}{\operatorname{\mathbb{P}}({\widehat{Z}=x+e_{r}})}=\frac{\mathbb{P}\left(B=x\right)}{\mathbb{P}\left(B=x+e_{r}\right)}\frac{\mathbb{P}\left(\kappa(B)=k\right)}{\mathbb{P}\left(\kappa(B)=k-1\right)}=\frac{1-p_{r}}{p_{r}}\frac{\mathbb{P}\left(\kappa(B)=k\right)}{\mathbb{P}\left(\kappa(B)=k-1\right)}.$

Moreover, for any $f\colon\operatorname{\mathcal{B}_{n}}\to\mathbb{R}$ and
$r\in[n]$,

(7.15)
$\operatorname{\mathbb{E}}\big{[}f(B)\mathbf{1}_{\\{B_{r}=1\\}}\big{]}\frac{1-p_{r}}{p_{r}}=\operatorname{\mathbb{E}}\big{[}f(B+e_{r})\mathbf{1}_{\\{B_{r}=0\\}}\big{]}.$

We use (7.14) and (7.15) to get that for any such $y$ and any $r\in[n]$ such
that $y_{r}=1$ and $\kappa(y)=k$,

$\displaystyle\frac{h(y,y-e_{r})\operatorname{\mathbb{P}}(Z^{\prime}=y-e_{r})}{\operatorname{\mathbb{P}}(\widehat{Z}=y)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:CB_coupling_quotient}}}{{=}}h(y,y-e_{r})\frac{1-p_{r}}{p_{r}}\frac{\mathbb{P}\left(\kappa(B)=k\right)}{\mathbb{P}\left(\kappa(B)=k-1\right)}$
(7.16)
$\displaystyle\begin{split}&=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{B_{r}=1\\}}\mathbf{1}_{\\{\kappa(B)=k\\}}}{\mathbf{1}_{\\{B_{r}=1\\}}+\sum_{l\neq
r}\mathbf{1}_{\\{B_{l}=1\\}}\mathbf{1}_{\\{y_{l}=0\\}}}\Big{]}\frac{(1-p_{r})/p_{r}}{\mathbb{P}\left(\kappa(B)=k-1\right)}\\\
&\stackrel{{\scriptstyle\eqref{eq:CB_measure_change}}}{{=}}\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{B_{r}=0\\}}\mathbf{1}_{\\{\kappa(B)=k-1\\}}}{\mathbf{1}_{\\{B_{r}=0\\}}+\sum_{l\neq
r}\mathbf{1}_{\\{B_{l}=1\\}}\mathbf{1}_{\\{y_{l}=0\\}}}\Big{]}\frac{1}{\mathbb{P}\left(\kappa(B)=k-1\right)}\\\
&=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{B_{r}=0\\}}\mathbf{1}_{\\{\kappa(B)=k-1\\}}}{\mathbf{1}_{\\{B_{r}=0\\}}+\sum_{l\neq
r}\mathbf{1}_{\\{B_{l}=0\\}}\mathbf{1}_{\\{y_{l}=1\\}}}\Big{]}\frac{1}{\mathbb{P}\left(\kappa(B)=k-1\right)}\\\
&=\operatorname{\mathbb{E}}\Big{[}\frac{\mathbf{1}_{\\{Z^{\prime}_{r}=0\\}}}{\sum_{l}\mathbf{1}_{\\{Z^{\prime}_{l}=0\\}}\mathbf{1}_{\\{y_{l}=1\\}}}\Big{]}\end{split}$

where the penultimate step comes from the fact that for any $u,v$ such that
$\kappa(u)=\kappa(v)$ one has
$\sum\mathbf{1}_{\\{u=0\\}}\mathbf{1}_{\\{v=1\\}}=\sum\mathbf{1}_{\\{u=1\\}}\mathbf{1}_{\\{v=0\\}}$
applied to $u=\xi_{r}(B)$, $v=\xi_{r}(y)$, where $\xi_{r}$ is the projection
from $\operatorname{\mathcal{B}_{n}}$ to $\mathcal{B}_{n-1}$ obtained by
skipping the $r$-th coordinate (note that if $B_{r}=0$ and $\kappa(B)=k-1$
then $\kappa(u)=\kappa(v)=k-1$). Therefore by (7)

$\frac{\sum_{x}h(y,x)\operatorname{\mathbb{P}}(Z^{\prime}=x)}{\operatorname{\mathbb{P}}(\widehat{Z}=y)}=\frac{\sum_{r\colon
y_{r}=1}h(y,y-e_{r})\operatorname{\mathbb{P}}(Z^{\prime}=y-e_{r})}{\operatorname{\mathbb{P}}(\widehat{Z}=y)}=1,$

which completes the proof of (7.1). The equality (7.2) follows again by (7). ∎

## References

  * [1] Radosław Adamczak, Michał Kotowski, Bartłomiej Polaczyk, and Michał Strzelecki, _A note on concentration for polynomials in the Ising model_ , Electron. J. Probab. 24 (2019), Paper No. 42, 22. MR 3949267
  * [2] Radosław Adamczak, Bartłomiej Polaczyk, and Michał Strzelecki, _Modified log-Sobolev inequalities, Beckner inequalities and moment estimates_ , arXiv preprint arXiv:2007.10209 (2020).
  * [3] Radosław Adamczak and Michał Strzelecki, _On the convex Poincaré inequality and weak transportation inequalities_ , Bernoulli 25 (2019), no. 1, 341–374. MR 3892322
  * [4] Radosław Adamczak and Paweł Wolff, _Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order_ , Probab. Theory Related Fields 162 (2015), no. 3-4, 531–586. MR 3383337
  * [5] Shigeki Aida, Takao Masuda, and Ichirō Shigekawa, _Logarithmic Sobolev inequalities and exponential integrability_ , J. Funct. Anal. 126 (1994), no. 1, 83–101. MR 1305064
  * [6] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, _Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid_ , STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 1–12. MR 4003314
  * [7] Cécile Ané, Sébastien Blachère, Djalil Chafaï, Pierre Fougères, Ivan Gentil, Florent Malrieu, Cyril Roberto, and Grégory Scheffer, _Sur les inégalités de Sobolev logarithmiques_ , Panoramas et Synthèses [Panoramas and Syntheses], vol. 10, Société Mathématique de France, Paris, 2000, With a preface by Dominique Bakry and Michel Ledoux. MR 1845806
  * [8] Richard Aoun, Marwa Banna, and Pierre Youssef, _Matrix Poincaré inequalities and concentration_ , Adv. Math. 371 (2020), 107251, 33. MR 4108222
  * [9] Dominique Bakry, Michel Ledoux, and Laurent Saloff-Coste, _Markov semigroups at Saint-Flour_ , Probability at Saint-Flour, Springer, Heidelberg, 2012. MR 3075390
  * [10] Patrice Bertail and Stephan Clémençon, _Bernstein-type exponential inequalities in survey sampling: conditional Poisson sampling schemes_ , Bernoulli 25 (2019), no. 4B, 3527–3554. MR 4010964
  * [11] Rajendra Bhatia, _Matrix analysis_ , Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662
  * [12] S. G. Bobkov and F. Götze, _Exponential integrability and transportation cost related to logarithmic Sobolev inequalities_ , J. Funct. Anal. 163 (1999), no. 1, 1–28. MR 1682772
  * [13] Sergey G. Bobkov and Prasad Tetali, _Modified logarithmic Sobolev inequalities in discrete settings_ , J. Theoret. Probab. 19 (2006), no. 2, 289–336. MR 2283379
  * [14] Julius Borcea, Petter Brändén, and Thomas M. Liggett, _Negative dependence and the geometry of polynomials_ , J. Amer. Math. Soc. 22 (2009), no. 2, 521–567. MR 2476782
  * [15] Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, and Pascal Massart, _Moment inequalities for functions of independent random variables_ , Ann. Probab. 33 (2005), no. 2, 514–560. MR 2123200
  * [16] Stéphane Boucheron, Gábor Lugosi, and Pacal Massart, _On concentration of self-bounding functions_ , Electron. J. Probab. 14 (2009), no. 64, 1884–1899. MR 2540852
  * [17] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, _Concentration inequalities. A nonasymptotic theory of independence_ , Oxford University Press, Oxford, 2013. MR 3185193
  * [18] Petter Brändén and June Huh, _Lorentzian polynomials_ , Ann. of Math. (2) 192 (2020), no. 3, 821–891. MR 4172622
  * [19] Sean X. Chen, _General properties and estimation of conditional Bernoulli models_ , J. Multivariate Anal. 74 (2000), no. 1, 69–87. MR 1790614
  * [20] Sean X. Chen and Jun S. Liu, _Statistical applications of the Poisson-binomial and conditional Bernoulli distributions_ , Statist. Sinica 7 (1997), no. 4, 875–892. MR 1488647
  * [21] Xiang-Hui Chen, Arthur P. Dempster, and Jun S. Liu, _Weighted finite population sampling to maximize entropy_ , Biometrika 81 (1994), no. 3, 457–469. MR 1311090
  * [22] Mary Cryan, Heng Guo, and Giorgos Mousa, _Modified log-Sobolev inequalities for strongly log-concave distributions_ , Ann. Probab. 49 (2021), no. 1, 506–525. MR 4203344
  * [23] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros, _Learning Ising models from one or multiple samples_ , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2021, Association for Computing Machinery, 2021, p. 161–168.
  * [24] Devdatt P. Dubhashi and Alessandro Panconesi, _Concentration of measure for the analysis of randomized algorithms_ , Cambridge University Press, Cambridge, 2009. MR 2547432
  * [25] Fuqing Gao and Jeremy Quastel, _Exponential decay of entropy in the random transposition and Bernoulli-Laplace models_ , Ann. Appl. Probab. 13 (2003), no. 4, 1591–1600. MR 2023890
  * [26] Kevin Garbe and Jan Vondrak, _Concentration of Lipschitz functions of negatively dependent variables_ , arXiv preprint arXiv:1804.10084 (2018).
  * [27] Ankit Garg, Tarun Kathuria, and Nikhil Srivastava, _Scalar Poincaré implies matrix Poincaré_ , Electron. Commun. Probab. 26 (2021), Paper No. 20, 4. MR 4245747
  * [28] Sharad Goel, _Modified logarithmic Sobolev inequalities for some models of random walk_ , Stochastic Process. Appl. 114 (2004), no. 1, 51–79. MR 2094147
  * [29] Jonathan Hermon and Justin Salez, _Modified log-Sobolev inequalities for strong-Rayleigh measures_ , arXiv preprint arXiv:1902.02775 (2019).
  * [30] De Huang and Joel A. Tropp, _Nonlinear matrix concentration via semigroup methods_ , Electron. J. Probab. 26 (2021), Paper No. 8, 31. MR 4216521
  * [31] Mark Jerrum, Jung-Bae Son, Prasad Tetali, and Eric Vigoda, _Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains_ , Ann. Appl. Probab. 14 (2004), no. 4, 1741–1765. MR 2099650
  * [32] Tarun Kathuria, _A Matrix Bernstein Inequality for Strong Rayleigh Distributions_ , arXiv preprint arXiv:2011.13340 (2020).
  * [33] Tali Kaufman and Izhar Oppenheim, _High order random walks: beyond spectral gap_ , Approximation, randomization, and combinatorial optimization. Algorithms and techniques, LIPIcs. Leibniz Int. Proc. Inform., vol. 116, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 47, 17. MR 3857285
  * [34] Rasmus Kyng and Zhao Song, _A matrix Chernoff bound for strongly Rayleigh distributions and spectral sparsifiers from a few random spanning trees_ , 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 373–384. MR 3899605
  * [35] Rafał Latała, _Estimates of moments and tails of Gaussian chaoses_ , Ann. Probab. 34 (2006), no. 6, 2315–2331. MR 2294983
  * [36] Michel Ledoux, _The concentration of measure phenomenon_ , Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347
  * [37] Tzong-Yow Lee and Horng-Tzer Yau, _Logarithmic Sobolev inequality for some models of random walks_ , Ann. Probab. 26 (1998), no. 4, 1855–1873. MR 1675008
  * [38] David A. Levin and Yuval Peres, _Markov chains and mixing times_ , American Mathematical Society, Providence, RI, 2017, Second edition of [ MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. MR 3726904
  * [39] Thomas M. Liggett, _Continuous time Markov processes_ , Graduate Studies in Mathematics, vol. 113, American Mathematical Society, Providence, RI, 2010, An introduction. MR 2574430
  * [40] Sheng Lin Lu and Horng-Tzer Yau, _Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics_ , Comm. Math. Phys. 156 (1993), no. 2, 399–433. MR 1233852
  * [41] Ryan O’Donnell, _Analysis of Boolean functions_ , Cambridge University Press, New York, 2014. MR 3443800
  * [42] Daniel Paulin, _The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems_ , Electron. J. Probab. 19 (2014), no. 68, 34. MR 3248197
  * [43] Robin Pemantle, _Towards a theory of negative dependence_ , vol. 41, 2000, Probabilistic techniques in equilibrium and nonequilibrium statistical physics, pp. 1371–1390. MR 1757964
  * [44] Robin Pemantle and Yuval Peres, _Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures_ , Combin. Probab. Comput. 23 (2014), no. 1, 140–160. MR 3197973
  * [45] Holger Sambale and Arthur Sinulis, _Modified log-Sobolev inequalities and two-level concentration_ , arXiv preprint arXiv:1905.06137 (2019).
  * [46] by same author, _Concentration inequalities on the multislice and for sampling without replacement_ , arXiv preprint arXiv:2010.16289 (2020).
  * [47] by same author, _Logarithmic Sobolev inequalities for finite spin systems and applications_ , Bernoulli 26 (2020), no. 3, 1863–1890. MR 4091094
  * [48] Paul-Marie Samson, _Transport-entropy inequalities on locally acting groups of permutations_ , Electron. J. Probab. 22 (2017), Paper No. 62, 33. MR 3690287
  * [49] Qi-Man Shao, _A comparison theorem on moment inequalities between negatively associated and independent random variables_ , J. Theoret. Probab. 13 (2000), no. 2, 343–356. MR 1777538
  * [50] Michel Talagrand, _An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities_ , Proc. Amer. Math. Soc. 104 (1988), no. 3, 905–909. MR 964871
  * [51] by same author, _Concentration of measure and isoperimetric inequalities in product spaces_ , Inst. Hautes Études Sci. Publ. Math. (1995), no. 81, 73–205. MR 1361756
  * [52] Yves Tillé, _Sampling algorithms_ , Springer Series in Statistics, Springer, New York, 2006. MR 2225036
  * [53] Joel A. Tropp, _Freedman’s inequality for matrix martingales_ , Electron. Commun. Probab. 16 (2011), 262–270. MR 2802042
  * [54] by same author, _User-friendly tail bounds for sums of random matrices_ , Found. Comput. Math. 12 (2012), no. 4, 389–434. MR 2946459
  * [55] Roman Vershynin, _High-dimensional probability_ , Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018, An introduction with applications in data science, With a foreword by Sara van de Geer. MR 3837109
  * [56] Nicolas Verzelen and Elisabeth Gassiat, _Adaptive estimation of high-dimensional signal-to-noise ratios_ , Bernoulli 24 (2018), no. 4B, 3683–3710. MR 3788186