# Stein’s method for Conditional Central Limit Theorem

Partha S. Deylabel=e1 [<EMAIL_ADDRESS>Grigory Terlovlabel=e2 [
<EMAIL_ADDRESS>Department of Mathematics, University of Illinois
at Urbana-Champaign

###### Abstract

In the seventies, Charles Stein revolutionized the way of proving the Central
Limit Theorem by introducing a method that utilizes a characterization
equation for Gaussian distribution. In the last fifty years, much research has
been done to adapt and strengthen this method to a variety of different
settings and other limiting distributions. However, it has not been yet
extended to study conditional convergences. In this article, we develop a
novel approach using Stein’s method for exchangeable pairs to find a rate of
convergence in the Conditional Central Limit Theorem of the form $(X_{n}\mid
Y_{n}=k)$, where $(X_{n},Y_{n})$ are asymptotically jointly Gaussian, and
extend this result to a multivariate version. We apply our general result to
several concrete examples, including pattern count in a random binary sequence
and subgraph count in Erdős-Rényi random graph.

60F05,

60G50,

60B10,

05C80,

62E17,

Stein’s method,

Central Limit Theorem,

Rate of convergence,

Conditional Law,

Multivariate normal approximation,

###### keywords:

[class=MSC2020]

###### keywords:

and

###### Contents

  1. 1 Introduction
    1. 1.1 Conditional Central Limit Theorem
    2. 1.2 Stein’s Method
    3. 1.3 Multivariate Stein’s method via exchangeable pairs
    4. 1.4 Local Limit Theorem
    5. 1.5 Strategy
    6. 1.6 Toy Example
    7. 1.7 Assumptions
    8. 1.8 Notations
    9. 1.9 Road Map
  2. 2 Main results: Univariate Case
  3. 3 Main results: Multivariate Case
  4. 4 Applications
    1. 4.1 Classical methods in CCLT
    2. 4.2 Applications of main results in one dimension
    3. 4.3 Applications of main result in higher dimension
    4. 4.4 General subgraph count given the number of edges
  5. 5 Proofs of Main Results
    1. 5.1 Proof of Theorem 2.1
    2. 5.2 Proof of Lemma 2.3
    3. 5.3 Proof of Theorem 3.1
  6. 6 Change of variables
  7. 7 Closing remarks and further work
    1. 7.1 Change of variable and the assumptions
    2. 7.2 Range of $\Delta\\!Y$
    3. 7.3 Other types of events than $\\{Y=k\\}$
    4. 7.4 Sufficient statistic
    5. 7.5 Other approaches
    6. 7.6 Other distances between distributions
  8. A From Smooth functions to Lipschitz functions
  9. B Computations for Lemma 4.9

##  1 Introduction

One of the oldest and most outstanding results in Probability theory is the
Central Limit Theorem (CLT), which in classical form states that the sum of
i.i.d. finite variance random variables, appropriately centered and scaled,
converges to the standard normal distribution asymptotically. There are
several generalizations and variations, such as Multivariate CLT, Martingale
CLT, Local Limit Theorem (LLT), and Conditional CLT (CCLT), among others;
however, the essence is the same as in the simplest classical CLT. Though the
classical proof of CLT uses characteristic functions and their
characterization of distributions, over the last century, various methods,
such as the moment method and Lindeberg’s technique, have been developed to
prove CLT even in highly dependent structures. State of the art in
establishing CLT and getting a convergence rate is Stein’s method, which we
will discuss in further detail in Section 1.2. Researchers have applied
Stein’s method to prove and find a rate of convergence in Multivariate CLT [3,
12, 5, 28, 29, 41, 44], Martingale CLT [45], Local Limit theorem [5, 42], and
in other non-Gaussian limit theorems (see [1, 11, 13, 14, 35] among many
others). Stein’s method has also been applied to prove concentration
inequalities [8, 10, 24, 26], moderate deviation results [15], and strong
coupling [9]. For a more detailed overview of the topic, we refer to the books
[16, 20] and the survey [47]. However, to our knowledge, very little is known
about proving and getting a convergence rate in CCLT of the form $X$ given
$Y=y$ (see [7, 19, 32, 50]), especially in structures with dependence.

The main focus of this article is to develop Stein’s method for exchangeable
pairs to prove and get an explicit rate of convergence in Conditional Central
Limit Theorems of the form $X_{n}$ given $Y_{n}=k$. Our focus will be on the
case where the random vector $(X_{n},Y_{n})$ converges to a multivariate
normal distribution as $n$ tends to infinity, and $Y_{n}$ is a discrete random
variable. We believe that this is the first application of Stein’s method in
proving CCLT and one of the first works that study the explicit rate of
convergence in CCLT. In the rest of this section, we briefly discuss
literature on CCLT and Stein’s method. We present the main idea behind the
exchangeable pair approach on which our result is based. We state our main
result in full generality in Section 2 and extend it to the multivariate
setting in Section 3.

###  1.1 Conditional Central Limit Theorem

It is common in Probability theory and Statistics to study conditional
convergence of random variables. In general, the study of conditional
probabilities played an important role in shaping the field as we know it and
related to notions such as Markov chains and martingales. Even though
Conditional Central Limit Theorem (CCLT) has been studied in the last forty
years, it has been mostly looked at on particular examples or under specific
assumptions. The strongest result is known for the sum of a stationary
sequence $\Sigma_{i=1}^{n}(X\circ T^{i}),$ ${n\geqslant 1}$ conditioned on a
non-decreasing filtration $\mathcal{M}_{i}:=T^{-i}(\mathcal{M}_{0})$ with a
bi-measurable probability measure-preserving map $T$. The necessary and
sufficient conditions for such CCLT were obtained by Dedecker and Merlevède in
[19]. In [6, Theorem 4], Bolthausen proved CCLT with explicit rate of
convergence in Kolmogorov–Smirnov distance for a positively recurrent Markov
chain with finite absolute third moment conditioned on the time of the
$n^{\textrm{th}}$ return to $0$. This result was recently extended by Guo and
Peterson [31, Theorem 4.2] to a CCLT for sums of i.i.d. sequence of random
vectors $(X_{i},Y_{i})$ with
$\operatorname{\mathds{E}}(|X_{1}|+|Y_{1}|)^{2+\delta}<\infty$ conditioned on
$\sum Y_{i}=k$. Another general CCLT was proved by Holst in [32]. In that
work, he also considered an i.i.d. sequence of random vectors $(X_{i},Y_{i})$.
Assuming that $\sum Y_{i}$ is a sufficient statistic and a certain
multivariate CLT holds, he derived CCLT for $(\sum{X}_{i}\mid\sum{Y}_{i}=k)$,
after appropriate centering and scaling. In all of the relevant results from
[6, 31, 32], the authors used variations of the method of characteristic
functions and thus crucially relied on the independence among the random
variables. Other settings in the literature include CCLT for conditionally
independent random variables, which reduces to the classical setting see [7,
50], among others.

All of the above results use independence in one way or the other, which could
lead one to believe that asymptotic independence and joint convergence to a
multivariate normal are sufficient for CCLT to hold. However, the following
artificial, but still insightful, example shows that it is not the case. Let
$X_{n}$ and $Y_{n}$ be centered Binomial$(n,1/2)$ independent random
variables. Define

$\displaystyle\bigl{(}\widehat{X}_{n},\widehat{Y}_{n}\bigr{)}=\begin{cases}(X_{n},Y_{n})&\text{w.~{}p.}\quad
1-\alpha_{n}\\\ (U,\delta_{0})&\text{w.~{}p.}\quad\alpha_{n},\end{cases}$

where $n^{-\nicefrac{{1}}{{2}}}\ll\alpha_{n}\ll 1$, $\delta_{0}$ is Dirac
measure at $0$, and $U$ has arbitrary distribution. By Local Limit Theorem we
have $\operatorname{\mathds{P}}(Y_{n}=0)\approx
n^{-\nicefrac{{1}}{{2}}}\ll\alpha_{n}$ and
$(\widehat{X}_{n}\mid\widehat{Y}_{n}=0)\Rightarrow U$, even though
$\widehat{X}_{n}$ and $\widehat{Y}_{n}$ are asymptotically independent and
$(\widehat{X}_{n},\widehat{Y}_{n})$ converges to the two dimensional standard
normal distribution. Therefore a more careful characterisation of dependency
is needed to have even heuristic understanding of when to expect CCLT to hold
in a general setting.

###  1.2 Stein’s Method

Over the last few decades, Stein’s methods have become one of the essential
tools to prove and get a rate of convergence in Central Limit Theorems for
sums of dependent random variables. It was first introduced by Charles Stein
in 1972 [48], who combined Gaussian Integration by parts or “Stein
characterizing equation for standard normal distribution” with certain “noise
robustness” property, which is now called the exchangeable pair approach. This
method can now be applied using a variety of approaches, namely exchangeable
pairs, dependency graphs or local dependencies [18, 40], size-bias [29] and
zero-bias couplings [27], Stein coupling [17], and through Malliavin calculus
[37] among others. The main underlying idea in Stein’s methods for CLT is as
follows:

_A random variable $W$ is close to the standard normal distribution with
respect to an appropriate metric if
$\sup_{f\in\mathcal{D}}\operatorname{\mathds{E}}(f^{\prime}(W)-Wf(W))$ is
small for an adequately chosen class of functions $\mathcal{D}$ depending on
the metric._

Our work is built on the exchangeable pair approach, which we state here and
refer to [16, 20, 47] for further details.

######  Definition 1.1.

Two random variables $W$ and $W^{\prime}$ are said to be exchangeable if
$(W,W^{\prime})\,{\buildrel d\over{=}}\,(W^{\prime},W)$.

While most works on Stein’s method using exchangeable pairs require
exchangeability, this assumption can usually be relaxed to the requirement of
$W$ and $W^{\prime}$ to be equidistributed as pointed out in [43]. This remark
applies to the majority of our work as well. The only place where we use
exchangeability to the fullest extent is in the last step in the proof of
Theorem 2.4 and the analogous place in the multivariate result in Theorem 3.1.

The method of exchangeable pairs is usually applicable in systems where small
perturbations do not change the distribution significantly. Classical results
due to Stein [48, 49] can be stated in the following way.

######  Theorem 1.1.

Let $(W,W^{\prime})$ be an exchangeable pair of random variables defined on
the same probability space. Suppose $\operatorname{\mathds{E}}W=0$,
$\operatorname{\mathds{E}}W^{2}=1$,
$\operatorname{\mathds{E}}\left|W\right|^{3}<\infty$, and $\Delta
W:=W^{\prime}-W$ almost surely satisfies

$\displaystyle\operatorname{\mathds{E}}(\Delta W\mid
W)=-\lambda(W+R_{1})\text{ and }\operatorname{\mathds{E}}\left(\Delta
W^{2}\mid W\right)=2\lambda(1+R_{2})$

for some constant $\lambda\in(0,1)$ and random variables $R_{i}=R_{i}(W)$ for
$i=1,2$. Then

$\displaystyle
d_{\mathcal{W}}(W,Z)\leqslant\operatorname{\mathds{E}}|R_{1}|+\sqrt{\frac{2}{\pi}}\operatorname{\mathds{E}}|R_{2}|+\frac{1}{3\lambda}\operatorname{\mathds{E}}|\Delta
W|^{3},$

where $Z$ is a standard normal random variable and $d_{\mathcal{W}}(W,Z)$
denotes the Wasserstein distance.

The outline of the proof is usually of the following form. One first finds an
antisymmetric function, then using Taylor expansion and the properties of the
conditional expectation one derives a bound on the Stein operator. In
particular, given a bounded twice differentiable function $f$, one can find a
function $F$ with $F^{\prime}=f$. Then
$\operatorname{\mathds{E}}(F(W^{\prime})-F(W))=0$ and expanding the expression
inside of the parenthesis around $W$, one gets

$\displaystyle F(W^{\prime})-F(W)\approx\Delta W\cdot f(W)+\frac{1}{2}(\Delta
W)^{2}\cdot f^{\prime}(W)+\frac{1}{6}(\Delta W)^{3}\cdot f^{\prime\prime}(W).$

Using the tower property of the conditional expectation together with the
assumptions on $\operatorname{\mathds{E}}(\Delta W\mid W)$ and
$\operatorname{\mathds{E}}(\Delta W^{2}\mid W)$ one can derive the bound on
$\left|\operatorname{\mathds{E}}(Wf(W)-f^{\prime}(W))\right|.$

To derive the rate of convergence one aims to bound
$\sup_{h\in\mathcal{C}}|\operatorname{\mathds{E}}h(W)-\operatorname{\mathds{E}}h(Z)|$
for the corresponding class of functions $\mathcal{C}$ and standard normal
random variable $Z$. Given a function $h$, let $f$ be the “bounded” solution
to the following differential equation

$\displaystyle f^{\prime}(w)-wf(w)=h(w)-\operatorname{\mathds{E}}h(Z).$ (1.1)

The core idea behind Stein’s method is to work with the expectation of the
left hand side in order to derive the desired bound on the distance. By
inverting Ornstein-Uhlenbeck operator one can see that $f$ has one more
derivative than $h$ and that
$\left\|f\right\|_{\infty}\leqslant\left\|h^{\prime}\right\|_{\infty},$
$\left\|f^{\prime}\right\|_{\infty}\leqslant\sqrt{2/\pi}\left\|h^{\prime}\right\|_{\infty},$
and $\left\|f^{\prime\prime}\right\|_{\infty}\leqslant
2\left\|h^{\prime}\right\|_{\infty}$.

###  1.3 Multivariate Stein’s method via exchangeable pairs

The definition of exchangeability can be extended to a multidimensional case
in a natural way; we say that a pair of random vectors
$(\bm{W},\bm{W}^{\prime})$ is exchangeable if
$(\bm{W},\bm{W}^{\prime})\,{\buildrel d\over{=}}\,(\bm{W}^{\prime},\bm{W})$.
Multivariate versions of Stein’s method first appeared in [3, 30]. It was
extended to exchangeable pairs more than a decade later in [12] under the
assumptions

$\displaystyle\operatorname{\mathds{E}}(\Delta\\!\bm{W}\mid\bm{W})=-\lambda\left(\bm{W}+\bm{R}\right)\text{
and
}\operatorname{\mathds{E}}\left(\Delta\\!\bm{W}\Delta\\!\bm{W}^{T}\mid\bm{W}\right)=2\lambda(I+\Gamma),$

where $\Delta\\!\bm{W}:=\bm{W}^{\prime}-\bm{W}$, $\lambda\in(0,1)$, $I$ is the
identity matrix, and $\Gamma=\Gamma(\bm{W})$ is a random matrix. It was later
extended in [39] to the case of a general covariance matrix $\Sigma$.

For the multivariate case one can derive an analogous relation to (1.1). Let
$h$ be a $1$-Lipschitz function on $\mathds{R}^{d}$, _i.e.,_

$\sup_{\bm{w}_{1},\bm{w}_{2}\in\mathds{R}^{d}}\frac{\left|h(\bm{w}_{1})-h(\bm{w}_{2})\right|}{\left|\bm{w}_{1}-\bm{w}_{2}\right|}\leqslant
1.$

Here, $\left|\cdot\right|$ denotes the Euclidean norm. If $\Sigma$ is a
$d\times d$ symmetric and positive definite matrix, there is a “bounded”
solution $f$ to the equation

$\displaystyle\mathscr{S}f(\bm{w})=h(\bm{w})-\operatorname{\mathds{E}}h(\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z}),$
(1.2)

where the operator

$\displaystyle\mathscr{S}f(\bm{x}):=\langle\Sigma,\operatorname{Hess}f(\bm{x})\rangle_{\operatorname{H.S.}}-\langle\bm{x},\nabla
f(\bm{x})\rangle$ (1.3)

defined for two times continuously differentiable function $f$ characterizes
$d$-dimensional normal distribution with mean zero and variance-covariance
matrix $\Sigma$.

Both [12, 39] bound the rate of convergence to the appropriate multivariate
Gaussian vector in terms of smooth function metrics (also see [36] for a
unified approach). A decade later [38] presented a smoothing scheme that
allows one to go from a smooth test function to Lipschitz ones. These
approaches of [12, 39, 38] were recently combined and extended in [23], under
additional assumption on the finiteness of the fourth moment, to apply Stein’s
method for exchangeable pairs under Wasserstein distance. The result from [23]
can be stated in the following form.

######  Theorem 1.2 ([23, Theorem 2.1]).

Let $(\bm{W},\bm{W}^{\prime})$ be an exchangeable pair of $d$-dimensional
random vectors satisfying the linearity assumption

$\operatorname{\mathds{E}}(\Delta\\!\bm{W}\mid\bm{W})=-\Lambda(\bm{W}+\bm{R}),$

where $\Delta\\!\bm{W}:=\bm{W}^{\prime}-\bm{W}$. Assume that
$\operatorname{\mathds{E}}\left|\bm{W}\right|^{4}<\infty$. Let $\Sigma$ be a
$d\times d$ positive definite symmetric matrix such that

$\displaystyle\operatorname{\mathds{E}}(\Delta\\!\bm{W}\Delta\\!\bm{W}^{T}\mid\bm{W})=2\Lambda(\Sigma+\Gamma)$
(1.4)

for some symmetric matrix $\Gamma$. Then

$\displaystyle d_{\mathcal{W}}(\bm{W},\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z})$
$\displaystyle=\sup_{h\text{
$1$-Lipschitz}}\left|\operatorname{\mathds{E}}h(\bm{W})-\operatorname{\mathds{E}}h(\Sigma^{1/2}\bm{Z})\right|$
$\displaystyle\leqslant\operatorname{\mathds{E}}\left|\bm{R}\right|+\left\|\Sigma^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{op}}\operatorname{\mathds{E}}\left\|\Gamma\right\|_{\operatorname{H.S.}}$
$\displaystyle\quad+\left\|\Sigma^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{op}}^{3/2}\left(\frac{\pi}{8}\right)^{\frac{1}{4}}\max\left(\operatorname{\mathds{E}}\left|\bm{W}\right|^{2},\operatorname{Tr}(\Sigma)\right)^{\frac{1}{4}}\sqrt{\operatorname{\mathds{E}}\left(\left|\Lambda^{-1}\Delta\\!\bm{W}\right|\cdot\left|\Delta\\!\bm{W}\right|^{3}\right)}$

where $Z$ is a $d$-dimensional standard normal vector, $\left|\cdot\right|$
denotes the Euclidean $\ell_{2}$ norm,
$\left\|\cdot\right\|_{\operatorname{op}}$ denotes the operator norm and
$\left\|\cdot\right\|_{\operatorname{H.S.}}$ denotes the Hilbert-Schmidt norm.

In particular, if $\operatorname{\mathds{E}}\bm{W}\bm{W}^{T}=\Sigma=I_{d}$ the
error bound reduces to

$\displaystyle d_{\mathcal{W}}(\bm{W},\bm{Z})$
$\displaystyle\leqslant\operatorname{\mathds{E}}\left|\bm{R}\right|+\operatorname{\mathds{E}}\left\|\Gamma\right\|_{\operatorname{H.S.}}+\left(\frac{\pi}{8}\right)^{\frac{1}{4}}d^{\frac{1}{4}}\sqrt{\operatorname{\mathds{E}}\left(\left|\Lambda^{-1}\Delta\\!\bm{W}\right|\cdot\left|\Delta\\!\bm{W}\right|^{3}\right)}.$
(1.5)

###  1.4 Local Limit Theorem

While Central Limit Theorem provides the global limiting behavior for the
distribution of the scaled sum of random variables, the Local Limit Theorem
provides the behavior for the probabilities of the scaled sum of random
variables to be equal to a particular number. The classical case for
independent lattice distributed random variables is well understood (see [21,
25], among others) and can be stated in the following way.

######  Theorem 1.3.

Let $X_{1},X_{2},\ldots$ be i.i.d. random variables with mean zero, variance
$\sigma^{2}$ and having a common lattice distribution with span $1$, _i.e.,_
$\operatorname{\mathds{P}}(X_{i}\in\zeta+\mathds{Z})=1$ for some
$\zeta\in\mathds{R}$. Let $W_{n}=n^{-\nicefrac{{1}}{{2}}}\sum_{i=1}^{n}X_{i}$
and $\mathcal{L}_{n}:=\left\\{n^{-1/2}(n\zeta+\mathds{Z})\right\\}$, then as
$n\to\infty$, we have

$\displaystyle\sup_{x\in\mathcal{L}_{n}}\left|\sqrt{n}\operatorname{\mathds{P}}\left(W_{n}=x\right)-\varphi_{\sigma^{2}}(x)\right|\to
0,$

where is the density of the normal distribution with mean $0$ and variance
$\sigma^{2}$ given by

$\varphi_{\sigma^{2}}(x)=(2\pi\sigma^{2})^{-\nicefrac{{1}}{{2}}}e^{-{x^{2}}/{2\sigma^{2}}}.$

The analogous result for integer-valued dependent random variables was
introduced in [34] under certain ‘smoothness’ conditions on the distribution.
This approach was extended and connected to Stein’s method in [5, 42, 46]. The
main result of [5] is for general Stein coupling, which combines several
approaches of Stein’s method. In this article, we focus on the exchangeable
pair approach with an additional assumption that the change in the variable of
interest takes values in $\\{-1,0,1\\}$. Hence we present in Theorem 1.4 a
simplified version of the main result in [5, Theorem 2.1] in combination with
[5, Remark 2.2]. We refer to [5, Theorem 2.1] for the general statement.

######  Theorem 1.4 ([5, Theorem 2.1 and Remark 2.2]).

Let $Y$ be a mean zero random variable with variance $\sigma^{2}$ and taking
values in $\\{\zeta\\}+\mathds{Z}$ for some $\zeta\in[0,1)$. Assume that
$(Y^{\prime},Y)$ is an exchangeable pair satisfying the linearity condition
with some $\lambda\in(0,1)$,

$\operatorname{\mathds{E}}(\Delta\\!Y\mid Y)=-\lambda(Y+R_{1}),$ (1.6)

and $\Delta\\!Y\in\\{-1,0,1\\}$ almost surely. Then

$\displaystyle\sup_{k\in\\{\zeta\\}+\mathds{Z}}\left|\sigma\operatorname{\mathds{P}}(Y=k)-\sigma\varphi_{\sigma^{2}}(k)\right|$
$\displaystyle\leqslant\frac{C}{\sigma}+\frac{\sqrt{\operatorname{\mathds{E}}R_{1}^{2}}}{\sigma}\left(2+\frac{1}{\sqrt{2e}}+\sigma\sup_{k}\operatorname{\mathds{P}}(Y=k)\right)$
(1.7)
$\displaystyle+\frac{\operatorname{\mathds{E}}R_{2}}{\sigma^{2}\sqrt{2e}}+\frac{\operatorname{\mathds{E}}(R_{2}\left|Y\right|)}{\sigma^{3}}+\frac{2+\sup_{k}\operatorname{\mathds{E}}(R_{2}\mathds{1}_{Y=k})}{\sigma},$
(1.8)

where $C$ is some universal positive constant and
$R_{2}:=\frac{1}{\lambda}\left|\operatorname{\mathds{P}}(\Delta\\!Y=1\mid
Y)-\operatorname{\mathds{P}}(\Delta\\!Y=1)\right|$.

Notice that the original result in [5] is concerned with bounding the local
distance to a translated Poisson random variable. However, [5, Lemma 1.1]
yields that on the set of integers translated Poisson probability is within
$\frac{C}{\sigma^{2}}$ of the discretized normal probability with the same
mean and variance. Hence the same holds after shifting the lattice by
$-\operatorname{\mathds{E}}Y$; this additional step in the approximation is
accounted for in the first error term in (1.7) with a universal constant $C$.

###  1.5 Strategy

The main strategy behind our result is similar to the one outlined under
Theorem 1.1, however we need to work with a bivariate function that is anti-
symmetric in the first coordinate and symmetric in the second one. We need
continuous approximation in terms of $(w^{\prime},w)$, but discrete
approximation in terms of $(y^{\prime},y)$. More precisely, we will consider
functions of the following form

$\displaystyle(F(w^{\prime})-F(w))\cdot G(y^{\prime},y)$ (1.9)

where $G$ is a symmetric function of two variables. Note that, similar to the
classical exchangeable pair approach, with $f=F^{\prime}$ we have

$\displaystyle F(w^{\prime})-F(w)\approx\Delta w\cdot f(w)+\frac{1}{2}\Delta
w^{2}\cdot f^{\prime}(w)+\frac{1}{6}\Delta w^{3}\cdot f^{\prime\prime}(w).$

We can choose $G$ depending on the behavior of the exchangeable pair. We
consider two cases:

Case I. $\operatorname{\mathds{P}}(\Delta W\neq 0,\Delta\\!Y=0)>0$. In this
case we can take

$\displaystyle
G(y^{\prime},y):=\frac{1}{2}(\mathds{1}_{y=k}+\mathds{1}_{y^{\prime}=k})\cdot\mathds{1}_{y^{\prime}-y=0}=\mathds{1}_{y^{\prime}=y=k}.$

Here we need

$\displaystyle\operatorname{\mathds{E}}(\Delta
W\cdot\mathds{1}_{Y^{\prime}=Y=k}\mid W,Y)$
$\displaystyle=-\lambda\cdot(W+\text{``error''})\cdot\mathds{1}_{Y=k}\text{
and }$ $\displaystyle\operatorname{\mathds{E}}(\Delta
W^{2}\cdot\mathds{1}_{Y^{\prime}=Y=k}\mid W,Y)$
$\displaystyle=2\lambda\cdot(\sigma_{W}^{2}+\text{``error''})\cdot\mathds{1}_{Y=k}$

with some $\lambda\in(0,1)$ for the classical idea to work.

######  Remark 1.5 (Classical techniques).

If the model falls into Case I, then conditioning on this event, one can
derive CCLT with the explicit rate of convergence using standard techniques as
in Theorem 1.1. We apply this method in detail to various examples in Section
4.1. In models where $\operatorname{\mathds{P}}(X^{\prime}\neq X\mid
Y^{\prime}=Y)=0$ (Case II described below) one can usually consider
$\bigl{(}\widehat{X}^{\prime},\widehat{Y}^{\prime}\bigr{)}$ that is a result
of the same Markov chain started at $(X,Y)$ after two steps it then would fall
into Case I. However, the computations get significantly more complicated and
often are not feasible in applications.

Case II. $\operatorname{\mathds{P}}(\Delta W\neq 0,\Delta\\!Y=0)=0$. In this
case we can take

$\displaystyle
G(y^{\prime},y):=g(y^{\prime}-k)\cdot\mathds{1}_{y^{\prime}-y=1}+g(y-k)\cdot\mathds{1}_{y^{\prime}-y=-1}$

for some function $g$. Details are given in Section 5. To simplify notations
we define for $\ell\geqslant 0$,

$\displaystyle M_{\ell,\pm}(W,Y):=\operatorname{\mathds{E}}((\Delta
W)^{\ell}\cdot\mathds{1}_{\Delta\\!Y=\pm 1}\mid W,Y).$ (1.10)

Using Taylor series expansion for the following mean zero random variable

$\displaystyle\begin{split}&\Theta_{f}(W,Y)\\\
&\quad:=\operatorname{\mathds{E}}\left((F(W^{\prime})-F(W))\cdot(g(Y^{\prime}-k)\cdot\mathds{1}_{\Delta\\!Y=1}+g(Y-k)\cdot\mathds{1}_{\Delta\\!Y=-1})\mid
W,Y\right),\end{split}$ (1.11)

we get

$\displaystyle\operatorname{\mathds{E}}(\ f(W)(M_{1+}(W,Y)\cdot
g(Y-k+1)+M_{1-}(W,Y)\cdot g(Y-k))\ )$
$\displaystyle\qquad\qquad+\frac{1}{2}\operatorname{\mathds{E}}(\
f^{\prime}(W)(M_{2+}(W,Y)\cdot g(Y-k+1)+M_{2-}(W,Y)\cdot g(Y-k))\ )\approx 0.$

If we have

$\displaystyle M_{1,\pm}(W,Y)\approx-\frac{1}{2}\lambda W\quad\text{ and
}\quad M_{2,\pm}(W,Y)\approx\lambda\sigma_{W}^{2},$ (1.12)

then to get the Stein characterizing equation for $(W\mid Y=k)$,

$\displaystyle\left|\operatorname{\mathds{E}}\left((Wf(W)-\sigma_{W}^{2}f^{\prime}(W))\cdot\mathds{1}_{Y=k}\right)\right|\ll\operatorname{\mathds{P}}(Y=k)$

we need a function $g$ such that $g(y+1)+g(y)$ is a constant multiple of
$\mathds{1}_{y=0}$. Such a function is given by

$\displaystyle g(y):=(-1)^{y}\cdot\mathds{1}_{y\leqslant 0}.$

In many examples we have $M_{1,\pm}(W,Y)\approx-a_{\pm}\cdot\lambda W$ where
$a_{+}\neq a_{-}$ are fixed positive constants, even though
$M_{2,\pm}(W,Y)\approx\lambda\sigma_{W}^{2}$. Thus we need a way to remove the
asymmetry in the two conditional means $M_{1,\pm}$. Similarly, even though we
can make $W,Y$ uncorrelated by subtracting an appropriate multiple of $Y$ from
$W$, in some examples, $M_{1,\pm}$ involves non-trivial linear terms with $Y$.
We will subtract an appropriate “small” random variable from $W$, which will
not change variance behavior but introduce symmetry and remove $Y$ dependence
from the conditional mean computation. The change of variable is explained in
Proposition 2.6 in Section 2 and applied in several concrete examples in
Section 4.2. The above setup can be generalized to high dimensions as given in
Section 3.

######  Remark 1.6.

Note that, in general, the function

$\displaystyle(f(W^{\prime},Y^{\prime})-f(W,Y^{\prime}))\cdot
G(y,y^{\prime})+(f(W^{\prime},Y)-f(W,Y))\cdot G(y^{\prime},y)$

is anti-symmetric in $(W^{\prime},Y^{\prime}),(W,Y)$ for any $f$ and $G$. So
one can use different $f$ and $G$ to get the Stein operator for $W$ multiplied
by $\mathds{1}_{Y=k}$.

For such choices of function $g(y)$, one can get CCLT for $(W\mid Y=k)$.
However, for an effective bound, one needs error terms with $\mathds{1}_{Y<k}$
to be small in comparison with $\sigma_{Y}^{-1}$ as one can see in Theorem
2.1. To avoid this issue we first consider the same function as in Case I,
_i.e.,_ $g(y)=\mathds{1}_{y=0}$, then the argument outlined in Case II yields
a CCLT for $(W\mid Y\in\\{k-1,k\\})$. Thus it remains to compare
$h(W)\mathds{1}_{Y=k-1}$ with $h(W)\mathds{1}_{Y=k}$ for appropriate smooth
function $h(w)$. Using the intuition that exchangeable pair is most applicable
in models where small perturbation does not change the system too much, we
upper bound the difference between these two quantities by error terms
involving $\operatorname{\mathds{E}}\left|W^{\prime}-W\right|$. We present
details of this argument in the proof of Theorem 2.4.

We now present a toy example to illustrate the ideas mentioned above.

###  1.6 Toy Example

Let $(\xi_{i},\omega_{i})_{i\geqslant 1}$ be independent random vectors with
$\xi_{i}-\varepsilon_{i}\omega_{i}$ independent with $\omega_{i}$ for all
$i\geqslant 1$ for some sequence of real numbers
$(\varepsilon_{i})_{i\geqslant 1}$. We assume that $\omega_{i}$’s are i.i.d.
Bernoulli$(p)$ and $X_{i}:=\xi_{i}-\varepsilon_{i}(\omega_{i}-p)$’s are i.i.d.
with mean zero variance one. Define

$\displaystyle\overline{\omega}_{i}:=\omega_{i}-p,\quad
Y=\sum_{i=1}^{n}\overline{\omega}_{i}\quad\text{ and }\quad
W:=\sum_{i=1}^{n}\xi_{i}=\sum_{i=1}^{n}X_{i}+\sum_{i=1}^{n}\varepsilon_{i}\overline{\omega}_{i}.$

We will assume that $\sum_{i=1}^{n}\varepsilon_{i}=0$ and
$\varepsilon_{\max}:=\max_{1\leqslant i\leqslant n}|\varepsilon_{i}|\ll 1$. It
is easy to check that the random vector $(W/\sqrt{n},Y/\sqrt{npq})$
asymptotically converges to independent standard Gaussian rvs. We want to
prove a CCLT for $(W\mid Y=k)$ when $|k|\ll n^{\nicefrac{{1}}{{2}}}$.

We consider the exchangeable pair created by independent re-sampling at a
randomly chosen coordinate from $\\{1,2,\ldots,n\\}$. We have,

$\displaystyle M_{1,+}(W,Y)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathds{E}}((\xi^{\prime}_{i}-\xi_{i})\cdot(1-\omega_{i})\omega^{\prime}_{i}\mid
W,Y)$
$\displaystyle=-\frac{p}{n}\sum_{i=1}^{n}\operatorname{\mathds{E}}((X_{i}+\varepsilon_{i})(q-\overline{\omega}_{i})\mid
W,Y)$
$\displaystyle=-\frac{pq}{n}\left(W-\frac{1}{q}\sum_{i=1}^{n}\operatorname{\mathds{E}}((X_{i}+(1+q)\varepsilon_{i})\overline{\omega}_{i}\mid
W,Y)\right)$
$\displaystyle=-\frac{pq}{n}\left(W-\frac{1}{q}\operatorname{\mathds{E}}\left(\frac{Y}{n}\cdot\sum_{i=1}^{n}X_{i}+(1+q)\sum_{i=1}^{n}\varepsilon_{i}\overline{\omega}_{i}\
\bigl{|}\ W,Y\right)\right).$

Similarly, we get

$\displaystyle M_{1,-}(W,Y)$
$\displaystyle=-\frac{pq}{n}\left(W+\frac{1}{p}\operatorname{\mathds{E}}\left(\frac{Y}{n}\cdot\sum_{i=1}^{n}X_{i}-(1+p)\sum_{i=1}^{n}\varepsilon_{i}\overline{\omega}_{i}\
\bigl{|}\ W,Y\right)\right),$ $\displaystyle M_{2,+}(W,Y)$
$\displaystyle=\frac{pq}{n}\left(2(n-Y/q)+\sum_{i=1}^{n}\operatorname{\mathds{E}}((X_{i}^{2}-1+\varepsilon_{i}^{2}-2\varepsilon_{i}X_{i})\cdot(1-\overline{\omega}_{i}/q)\mid
W,Y)\right),$ $\displaystyle\text{ and }M_{2,-}(W,Y)$
$\displaystyle=\frac{pq}{n}\left(2(n+Y/p)+\sum_{i=1}^{n}\operatorname{\mathds{E}}((X_{i}^{2}-1+\varepsilon_{i}^{2}+2\varepsilon_{i}X_{i})\cdot(1+\overline{\omega}_{i}/p)\mid
W,Y)\right).$

One can easily verify that $\sigma_{W}^{2}=\operatorname{Var}(W)=n+o(n)$.
Moreover, with $\lambda=2pq/n$, we have

$M_{1,\pm}(W,Y)\approx-\frac{1}{2}\lambda\cdot(W+o_{p}(\sqrt{n}))\quad\text{
and }\quad M_{2,\pm}(W,Y)\approx\lambda\cdot(\sigma_{W}^{2}+O_{p}(\sqrt{n})),$

as expected in (1.12). This allows us to apply the idea in Case II to get an
explicit rate of convergence for the CCLT.

We now write down all of the assumptions needed to state the main results.

###  1.7 Assumptions

It is natural to expect CCLT to hold for $(W\mid Y=k)$ under reasonable
structural assumptions when $W$ and $Y$ are asymptotically jointly Gaussian.
Since for jointly Gaussian random variables uncorrelated implies independent
the first assumption that we impose on $(W,Y)$ is the following.

######  Assumption I.

Assume that

  1. I.1

$\bm{W}=(W_{1},W_{2},\dots,W_{d})$, where $\bm{W}$ is a mean $0$ random vector
with variance-covariance matrix $\Sigma$, which is invertible. In the one
dimensional case we will assume the variance to be $1$.

  2. I.2

$Y$ is a mean $0$ random variable with variance $\sigma_{Y}^{2}$.

  3. I.3

$\bm{W}$ and $Y$ are uncorrelated.

  4. I.4

The random vectors $(\bm{W},Y)$ and $(\bm{W}^{\prime},Y^{\prime})$ are
exchangeable.

In this paper, for simplicity, we focus on the case when
$\Delta\\!Y:=Y^{\prime}-Y\in\\{-1,0,1\\}$ and the exchangeable pair approach
is applicable, which we state in the following assumptions. Recall the
definition of $M_{\ell,\pm}(\bm{W},Y)$ from (1.10).

######  Assumption II.

$Y$ takes values in $\zeta+\mathds{Z}$ for some $\zeta\in[0,1)$,
$\Delta\\!Y\in\\{-1,0,1\\}$ almost surely, and

$\displaystyle M_{0,\pm}(\bm{W},Y)=Q+R_{0,\pm},$

where $Q=\lambda\sigma_{Y}^{2}$ for some $\lambda\in(0,1)$. Further, for any
$k$ such that $\operatorname{\mathds{P}}(Y=k)>0$ and
$\operatorname{\mathds{P}}(Y=k-1)>0$ we define

$r_{k}:=\frac{\operatorname{\mathds{P}}(Y=k-1)}{\operatorname{\mathds{P}}(Y=k)}\in(0,\infty).$
(1.13)

The condition on $M_{0,\pm}$ is natural because, in order to apply our method
to $(\bm{W}\mid Y=k)$, we require the method of exchangeable pairs to be
applicable to $Y$ on its own. In other words, we expect
$\operatorname{\mathds{E}}(\Delta Y\mid\bm{W},Y)\approx-\lambda Y$. Since we
assume that $\Delta Y\in\\{-1,0,1\\}$, if $\operatorname{\mathds{P}}(\Delta
Y=1\mid\bm{W},Y)$ is concentrated at $Q$, $\operatorname{\mathds{P}}(\Delta
Y=-1\mid\bm{W},Y)$ has to also concentrate at $Q$. This also implies that
$Q\approx\lambda\sigma_{Y}^{2}$ as

$\displaystyle 2\lambda\sigma_{Y}^{2}$
$\displaystyle=\operatorname{\mathds{E}}(\operatorname{\mathds{E}}(\Delta
Y^{2}\mid\bm{W},Y))$
$\displaystyle=\operatorname{\mathds{E}}(\operatorname{\mathds{P}}(\Delta
Y=1\mid\bm{W},Y)+\operatorname{\mathds{P}}(\Delta Y=-1\mid\bm{W},Y))\approx
2Q.$

It is important to highlight that
$M_{0,\pm}(\bm{W},Y)=\operatorname{\mathds{P}}(\Delta\\!Y=\pm 1\mid\bm{W},Y)$,
but it is reasonable to expect that the extra conditioning on $\bm{W}$ does
not affect this condition too much. In most examples that we consider, $Y$ is
the sum of independent Bernoulli random variables and
$M_{0,\pm}(\bm{W},Y)\approx Q\mp\lambda a_{\pm}Y$ for some $a_{\pm}$ such that
$a_{+}+a_{-}=1$.

######  Observation 1.7.

Assumption II implies that $Y$ satisfies the linearity condition

$\operatorname{\mathds{E}}(\Delta\\!Y\mid Y)=-\lambda(Y+R),$

with $R=-Y-\frac{1}{\lambda}(R_{0,+}-R_{0,-})$. Moreover, if
$R_{0,\pm}=\mp\lambda a_{\pm}Y$, where $a_{+}+a_{-}=1$ like in the case when
$Y$ is the sum of i.i.d. Bernoulli$(p)$ random variables, $R$ simplifies to

$R=-Y-\frac{1}{\lambda}(-\lambda a_{+}Y-\lambda a_{-}Y)=-Y+(a_{+}+a_{-})Y=0.$

######  Remark 1.8 (Ratio of probabilities and LLT).

Let $p_{k}(n):=\operatorname{\mathds{P}}(Y=k)$ for $Y=Y_{n}$. Suppose the
random variable $Y$ satisfies the LLT (see Theorems 1.3 and 1.4) in the sense
that as $n\to\infty$

$\sup_{k}\left|\sigma_{Y}\operatorname{\mathds{P}}(Y=k)-\sigma_{Y}\varphi_{\sigma_{Y}^{2}}(k)\right|\to
0.$ (1.14)

Then for any $\left|k\right|\ll~{}\sigma_{Y}$ we have that

$\lim_{n\to\infty}\frac{p_{k-1}(n)}{p_{k}(n)}=1,$

see Lemma A.2 for a proof. Thus this ratio is uniformly bounded from above and
from below by positive constants that depend only on the law of $Y$ and the
value of $k$. In particular, condition (1.13) of Assumption II is satisfied.
Note that, for our results we only need $1+r_{k}$ to be bounded away from $0$
and $\infty$.

The next assumption corresponds to the linearity condition in Theorem 1.1.
However, since the change has been separated into two parts due to the change
in $Y$, we state it as two separate equalities.

######  Assumption III.

For a $d\times d$ invertible matrix $\Psi$ we have that

$\displaystyle
M_{1,\pm}(\bm{W},Y)=-\lambda\left(\frac{1}{2}\Psi\bm{W}+\bm{R}_{1,\pm}\right).$

In one dimensional case this assumption takes form of

$\displaystyle M_{1,\pm}(W,Y)=-\lambda\left(\frac{1}{2}\psi
W+R_{1,\pm}\right),$ (1.15)

for some number $\psi>0$.

Notice that, if $Y^{\prime}=Y$ implies $W^{\prime}=W$, using the fact that
$\Delta\\!Y\in\\{-1,0,1\\}$ a.s. and adding the equalities (1.15) together
yields exactly the same linearity condition as in Theorem 1.1, where $\psi$
accounts for the difference in $\lambda$ for $W$ and $Y$. In general, the
separation on the linearity condition based on the change to $Y$ need not be
symmetric, in the sense that the factor of $1/2$ in front of $W$ would be
replaced by $a_{\pm}$ with the property that $a_{+}+a_{-}=1$. We tackle this
difficulty by an appropriate change of variable that accounts for this
asymmetry.

######  Assumption IIIa.

Assume that for a $d\times d$ invertible matrix $\Psi$ we have that

$\displaystyle
M_{1,\pm}(\bm{W},Y)=-\lambda\left(\Psi_{\pm}\bm{W}+\bm{b}_{\pm}Y+\bm{R}_{1,\pm}\right),$

where $\Psi_{1,+}+\Psi_{1,-}=\Psi$, $\bm{b}_{+}+\bm{b}_{-}={\bf 0}$ and
$\bm{b}_{+}=\frac{1}{2}\Psi\bm{b}_{+}$. In the one dimensional case this
assumption becomes

$\displaystyle M_{1,\pm}(W,Y)=-\lambda\left(a_{\pm}\psi
W+b_{\pm}Y+R_{1,\pm}\right).$

for some number $\psi>0$, where $a_{+}+a_{-}=1$ and $b_{+}+b_{-}=0$.

The last assumption has to do with the behavior of the conditional second
moment of the change in $W$.

######  Assumption IV.

With the same notations as above we assume that

$\displaystyle\operatorname{\mathds{E}}\left(\Delta\\!\bm{W}\Delta\\!\bm{W}^{T}\mathds{1}_{\Delta\\!Y=\pm
1}\mid\bm{W},Y\right)=\lambda\left(\Psi\Sigma+\Gamma_{2,\pm}\right),$ (1.16)

for some random matrices $\Gamma_{2,\pm}=\Gamma_{2,\pm}(\bm{W},Y)$. In the one
dimensional case this assumption becomes

$\displaystyle M_{2,\pm}(W,Y)=\lambda\left(\psi+R_{2,\pm}\right).$ (1.17)

###  1.8 Notations

Throughout this paper, we will use the following conventions:

  * •

Capital Roman letters and lower case Greek letters such as $\omega$ and $\xi$
denote random variables.

  * •

Capital Roman letters in bold font, as well as $\bm{\omega}$, denote random
vectors.

  * •

Capital Greek letters denote Matrices.

  * •

Lowercase Greek and Roman letters denote deterministic functions or numbers
except for $\omega$ and $\xi$.

  * •

Unless explicitly needed to emphasize the dependence on $n$, we will omit the
subscript $n$ and use $U,V,W,\ldots$ instead of $U_{n},V_{n},W_{n},\ldots$.

  * •

Expressions involving $\pm$ and $\mp$ should be read as two different
expressions: taking all signs on the top and taking all signs on the bottom.

We will also use the following notations throughout the rest of the paper.

  * •

$Z$ always denotes a standard normal random variable

  * •

$\bm{Z}=(Z_{1},Z_{2},\ldots,Z_{d})$ denotes a $d$-dimensional standard
Gaussian vector.

  * •

$\overline{X}:=X-\operatorname{\mathds{E}}X$ denotes a centered version of a
random variable $X$.

  * •

$\sigma_{W}^{2}$ \- variance of a random variable $W$,

  * •

$W^{\prime}$ \- exchangeable copy of $W$,

  * •

$\Delta W:=W^{\prime}-W$,

  * •

$W_{i}$ represents its $i^{\textrm{th}}$ coordinate of a vector $\bm{W}$,

  * •

$f_{i_{1},i_{2},\ldots,i_{m}}:=\frac{\partial^{m}f}{\partial w_{i_{1}}\partial
w_{i_{2}}\cdots\partial w_{i_{m}}}$ for a function $f$,

  * •

$\left|f\right|_{m}:=\sup_{i_{1},i_{2},\ldots,i_{m}}\left\|\partial_{i_{1},i_{2},\ldots,i_{m}}f\right\|_{\infty}$
if such quantities exist for a function $f$,

  * •

$\mathcal{A}:=\left\\{f:\left|f\right|_{0}\leqslant
1,\left|f\right|_{1}\leqslant\sqrt{2/\pi},\left|f\right|_{2}\leqslant
2\right\\}$,

  * •

$d_{\mathcal{W}}(W,Z):=\sup_{h:1\textrm{-Lip.}}\left|\operatorname{\mathds{E}}h(W)-\operatorname{\mathds{E}}h(Z)\right|$
\- Wasserstein-$1$ distance,

  * •

$f\approx g$ if $f=\Theta(g)$, $f\lesssim g$ if $f=O(g)$, and $f\ll g$ if
$f=o(g)$,

  * •

$N:=\binom{n}{2}$,

  * •

$Q:=\lambda\sigma_{Y}^{2}$

  * •

$p\in(0,1)$ and $q:=1-p$,

  * •

$\left|\cdot\right|$ \- the Euclidean $\ell_{2}$ norm,

  * •

$\left\|\cdot\right\|_{\operatorname{op}}$ \- the operator norm of a square
matrix,

  * •

$\left\|\cdot\right\|_{\operatorname{H.S.}}$ \- Hilbert-Schmidt norm of a
square matrix, _i.e.,_ for a $d\times d$ matrix $\Gamma$,
$\left\|\Gamma\right\|_{\operatorname{H.S.}}:=\sqrt{\operatorname{Tr}(\Gamma^{T}\Gamma)}.$

  * •

$\left\|\cdot\right\|_{p-\operatorname{H.S.}}$ \- is the $p^{\textrm{th}}$
norm of the Hilbert-Schmidt norm of a random matrix for $p\geqslant 1$,
_i.e.,_
$\left\|A\right\|_{p-\operatorname{H.S.}}=(\operatorname{\mathds{E}}\left\|A\right\|_{\operatorname{H.S.}}^{p})^{1/p}$.

To simplify notations we also define for $\ell\geqslant 1$ the
$\ell^{\textrm{th}}$ conditional moment of the change in $W$ given the change
in $Y$ as follows

$\displaystyle M_{\ell,\pm}(W,Y):=\operatorname{\mathds{E}}((\Delta
W)^{\ell}\mathds{1}_{\\{\Delta\\!Y=\pm 1\\}}\mid W,Y).$

###  1.9 Road Map

This paper is organized as follows: after discussing preliminaries and
heuristics, we provide the statements of the main results in univariate and
multivariate settings in Section 2 and 3. We present applications of classical
methods to CCLT in Section 4.1, following that, we present applications of our
main results in Sections 4.2 and 4.3 for univariate and multivariate cases,
respectively. The remainder of this paper is dedicated to the proof of the
main results. We conclude by discussing future work, open questions, and the
difficulties of our approach. Below we provide an extended road map for
Section 2 and Section 4.

In Section 2 we first state our main result in the simplest case in Theorem
2.1. Lemma 2.3 functions as a stepping stone to the improved version of the
result in Theorem 2.4. After that we discuss the general case and the change
of variables that reduces Assumption IIIa to Assumption III in Proposition
2.6. In Section 3 we present the analogous results to Theorem 2.4 and
Proposition 2.6 in multivariate setting in Theorem 3.1 and Proposition 3.3.

In applications we focus on counting examples in variety of models most
notably subpattern counts in a binary sequence in Sections 4.1.3, 4.2.1, and
4.2.2; as well as subgraph counts in a random graph in Sections 4.1.4, 4.2.3,
and 4.3.2, in Section 4.4 we build on that and present a CCLT for a general
subgraph count joint with triangle and wedge counts given the number of edges
in Theorem 4.18.

##  2 Main results: Univariate Case

First, we state the simplest version of our main result.

######  Theorem 2.1 (Symmetric case).

Suppose $W$ and $Y$ are random variables satisfying Assumptions I, II, III and
IV. Let $p_{k}:=\operatorname{\mathds{P}}(Y=k)>0$. Then we have that

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid Y=k),Z\bigr{)}$
$\displaystyle\leqslant\frac{2}{\psi}\left(A_{k}+\frac{1}{p_{k}}C\right)+\sqrt{\frac{2}{\pi\psi^{2}}}\left(B_{k}+\frac{1}{p_{k}}D\right)+\frac{2}{3\lambda\psi
p_{k}}E,$

where

$\displaystyle A_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|R_{1,-}\right|\,\big{|}\,Y=k\right),\qquad$
$\displaystyle B_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|R_{2,-}\right|\,\big{|}\,Y=k\right),$
$\displaystyle C$
$\displaystyle=\operatorname{\mathds{E}}\left|R_{1,+}-R_{1,-}\right|,\qquad$
$\displaystyle D$
$\displaystyle=\operatorname{\mathds{E}}\left|R_{2,+}-R_{2,-}\right|,$
$\displaystyle\qquad\qquad\quad\text{ and }\quad
E\leqslant\operatorname{\mathds{E}}|\Delta W|^{3}.$

In the proof of Theorem 2.1 we consider $g(y):=(-1)^{y}\mathds{1}_{y\leqslant
0}$, so that

$g(y+1-k)+g(y-k)=\mathds{1}_{y=k}.$

This is the most straightforward function that satisfies all of the properties
that we require.

######  Remark 2.2 (Asymmetry in the error terms).

One can notice that the bound in the conclusion of Theorem 2.1 is asymmetric
with respect to the error terms $A_{k}$ and $B_{k}$, namely only $R_{1,-}$ and
$R_{2,-}$ appear, while $R_{1,+}$ and $R_{2,+}$ do not. The reason for this is
that we chose the indicator $\mathds{1}_{y\leqslant 0}$ inside of function
$g(y)$. If instead one uses
$\widehat{g}(y):=\left(-1\right)^{y}\cdot\mathds{1}_{y\geqslant 0}$ then the
similar argument would give a bound with only $R_{1,+}$ and $R_{2,+}$
appearing in the first term. Moreover, one could also consider their average
to get the following bound

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid Y=k),Z\bigr{)}$
$\displaystyle\leqslant\frac{1}{\psi}\left(A^{\prime}_{k}+\frac{1}{p_{k}}C\right)+\sqrt{\frac{1}{2\pi\psi^{2}}}\left(B^{\prime}_{k}+\frac{1}{p_{k}}D\right)+\frac{1}{3\lambda\psi
p_{k}}E,$

where

$\displaystyle A_{k}^{\prime}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|R_{1,+}+R_{1,-}\right|\
\big{|}\ Y=k\right)\quad\text{and}\quad
B_{k}^{\prime}=\operatorname{\mathds{E}}\left(\left|R_{2,+}+R_{2,-}\right|\
\big{|}\ Y=k\right),$

and the rest of the terms remain the same as in Theorem 2.1.

There are two aspects in which Theorem 2.1 needs improvement. First, it is
often the case that the term
$\frac{1}{p_{k}}\operatorname{\mathds{E}}\left|R_{2,\pm}\right|$ might not go
to zero even though $\operatorname{\mathds{E}}\left|R_{2,\pm}\right|$ are
small on their own. To improve this bound we consider a different function
$g(y)=\mathds{1}_{y=0}$. This adaptation with a similar proof to the one of
Theorem 2.1 allows us to derive the following CCLT.

######  Lemma 2.3.

Suppose $W$ and $Y$ are random variables satisfying Assumptions I, II, III and
IV. For any $k$ such that $p_{k}:=\operatorname{\mathds{P}}(Y=~{}k)>0$ and
$p_{k-1}:=\operatorname{\mathds{P}}(Y=~{}k-1)>0$ we have

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid
Y\in\\{k-1,k\\}),Z\bigr{)}\leqslant\frac{2}{\psi(1+r_{k})}\widehat{A}_{k}+\frac{\sqrt{2/\pi}}{\psi(1+r_{k})}\widehat{B}_{k}+\frac{2}{3\lambda\psi}\widehat{E}_{k},$
(2.1)

where $r_{k}=p_{k-1}/p_{k}$ and

$\displaystyle\widehat{A}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|R_{1,-}\right|\,\mid\,Y=k\right)+r_{k}\cdot\operatorname{\mathds{E}}\left(\left|R_{1,+}\right|\mid
Y=k-1\right),$ $\displaystyle\widehat{B}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|R_{2,-}\right|\,\big{|}\,Y=k\right)+r_{k}\cdot\operatorname{\mathds{E}}\left(\left|R_{2,+}\right|\,\big{|}\,Y=k-1\right),$
$\displaystyle\text{ and }\quad\widehat{E}_{k}$
$\displaystyle=\operatorname{\mathds{E}}(|\Delta W|^{3}\mid Y\in\\{k-1,k\\}).$

In most applications of our results we expect $r_{k}$ to be uniformly bounded
away from $0$ and infinity, see Remark 1.8 and Lemma A.2.

As we mentioned in Section 1.2, the exchangeable pair approach is most useful
in models where a small perturbation does not change the observed quantity too
much. Using this intuition it is natural that for a Lipschitz function $h(w)$
the difference between of $\operatorname{\mathds{E}}(h(W)\mid Y=k)$ and
$\operatorname{\mathds{E}}(h(W)\mid Y=k-1)$ should be negligible. To make this
heuristic rigorous, we use the fact that $M_{0,\pm}$ are concentrated at $Q$
(Assumption II) and exchangeability of $W$ and $W^{\prime}$ (see Lemma 5.1 for
the exact statement). Combining Lemma 2.3 with the fact that $W$ conditioned
on the event $\\{Y=k-1\\}$ is almost the same as $W$ conditioned on
$\\{Y=k\\}$ yields the improved version of the univariate result.

######  Theorem 2.4 (Improved symmetric case).

Suppose $W$ and $Y$ are random variables satisfying Assumptions I, II, III and
IV. Let $k$ be such that $\operatorname{\mathds{P}}(Y=k)>0$ and
$\operatorname{\mathds{P}}(Y=k-1)>0$. Then

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid Y=k),Z\bigr{)}$
$\displaystyle\leqslant\frac{1}{\psi}\widehat{A}_{k}+\sqrt{\frac{1}{2\pi\psi^{2}}}\widehat{B}_{k}$
$\displaystyle\qquad+(1+r_{k})\left(\frac{1}{2Q}\widehat{C}_{k}+\frac{1}{2Q}\widehat{D}_{k}+\frac{2}{3\lambda\psi}\widehat{E}_{k}\right),$

where $r_{k},$ $\widehat{A},$ $\widehat{B},$ and $\widehat{E}$ are as in Lemma
2.3, while

$\displaystyle\widehat{C}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left((\left|W\right|+\operatorname{\mathds{E}}\left|Z\right|)(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\,\big{|}\,Y\in\\{k-1,k\\}\right)$
$\displaystyle\text{and }\widehat{D}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|\Delta
W\right|\,\big{|}\,Y\in\\{k-1,k\\}\right).$

We now derive Theorem 2.4 using Lemmas 2.3 and 5.1. The proofs of these lemmas
are presented in Section 5.

###### Proof.

By Lemma 2.3 we have that for any $1$-Lipschitz function
$h:\mathds{R}\to\mathds{R}$

$\displaystyle\left|\operatorname{\mathds{E}}(h(W)-h(Z))\mathds{1}_{Y\in\\{k-1,k\\}}\right|$
$\displaystyle\leqslant\frac{2}{\psi}\left(\operatorname{\mathds{E}}|R_{1,-}|\mathds{1}_{Y=k}+\operatorname{\mathds{E}}|R_{1,+}|\mathds{1}_{Y=k-1}\right)$
(2.2)
$\displaystyle+\sqrt{\frac{2}{\pi\psi^{2}}}\left(\operatorname{\mathds{E}}|R_{2,-}|\mathds{1}_{Y=k}+\operatorname{\mathds{E}}|R_{2,+}|\mathds{1}_{Y=k-1}\right)$
$\displaystyle+\frac{2}{3\lambda\psi}\operatorname{\mathds{E}}\left|\Delta
W\right|^{3}\mathds{1}_{Y\in\\{k-1,k\\}}.$

On the other hand by Lemma 5.1 we have that for any such function $h$ and for
any $k$ such that $\operatorname{\mathds{P}}(Y=k)>0$ and
$\operatorname{\mathds{P}}(Y=k-1)>0$ we have that

$\displaystyle\left|\operatorname{\mathds{E}}(h(W)-h(Z))\left(\mathds{1}_{Y=k}-\mathds{1}_{Y=k-1}\right)\right|$
(2.3) $\displaystyle\leqslant\frac{1}{Q}\operatorname{\mathds{E}}\left(|\Delta
W|\cdot\mathds{1}_{Y\in\\{k-1,k\\}}\right)+\frac{1}{Q}\operatorname{\mathds{E}}\left((\left|W\right|+\left|Z\right|)(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\mathds{1}_{Y\in\\{k-1,k\\}}\right).$

Adding the inequalities from Lemma 2.3 to the one in Lemma 5.1 gives us that

$\displaystyle
2\cdot\left|\operatorname{\mathds{E}}(h(W)-h(Z))\mathds{1}_{Y=k}\right|$
$\displaystyle\leqslant\frac{2}{\psi}\left(\operatorname{\mathds{E}}|R_{1,-}|\mathds{1}_{Y=k}+\operatorname{\mathds{E}}|R_{1,+}|\mathds{1}_{Y=k-1}\right)$
$\displaystyle+\sqrt{\frac{2}{\pi\psi^{2}}}\left(\operatorname{\mathds{E}}|R_{2,-}|\mathds{1}_{Y=k}+\operatorname{\mathds{E}}|R_{2,+}|\mathds{1}_{Y=k-1}\right)$
$\displaystyle+\frac{2}{3\lambda\psi}\operatorname{\mathds{E}}\left(\left|\Delta
W\right|^{3}\mathds{1}_{Y\in\\{k-1,k\\}}\right)+\frac{1}{Q}\operatorname{\mathds{E}}\left(|\Delta
W|\cdot\mathds{1}_{Y\in\\{k-1,k\\}}\right)$
$\displaystyle+\frac{1}{Q}\operatorname{\mathds{E}}\left((\left|W\right|+\left|Z\right|)(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\mathds{1}_{Y\in\\{k-1,k\\}}\right).$

Dividing both sides of the inequality by $2p_{k}$ and recalling that
$r_{k}=\frac{p_{k-1}}{p_{k}}$ we derive the desired result. $\blacksquare$

One can see that Theorem 2.4 partially generalizes [31, Theorem 4.2]. While
our result allows for the dependence among random variables, it also requires
the third absolute moment to be finite (as in [6, Theorem 4]) and limits the
change in $Y$ to only $\\{-1,0,1\\}$. One can adapt our approach to models
with finite $(2+\delta)$ \- th moment, although it might involve some
technical computations. However, relaxing the assumption on the range of
$\Delta\\!Y$ is of particular interest. In case when
$\operatorname{\mathds{P}}(\Delta\\!Y\in\\{-1,0,1\\})$ is sufficiently large,
our techniques are still applicable but could yield a suboptimal rate of
convergence. For further discussion see Section 7.2.

######  Remark 2.5 (Explicit bound for the error terms with conditioning).

All of the error terms in Theorem 2.4 are of the form
$\operatorname{\mathds{E}}(\left|R\right|\mid Y=i)$ where $i\in\\{k-1,k\\}$.
One can bound those terms using Hölder inequality in the following way

$\displaystyle\operatorname{\mathds{E}}(\left|R\right|\mid Y=i)$
$\displaystyle=\operatorname{\mathds{P}}(Y=i)^{-1}\operatorname{\mathds{E}}(\left|R\right|\mathds{1}_{Y=i})\leqslant\frac{\left\|R\right\|_{p}}{\operatorname{\mathds{P}}(Y=i)^{1/p}}$

for some $p>1$. Provided that the random variable $R$ has $p^{\textrm{th}}$
moment and is of order $n^{-\alpha}$, _i.e.,_ for some constant $C(p)$
depending on $p$ we have $\left\|n^{\alpha}R\right\|_{p}\leqslant C(p)$, and
if $\operatorname{\mathds{P}}(Y=i)\approx~{}n^{-\beta/2}$, then

$\operatorname{\mathds{E}}(\left|R\right|\mid Y=i)\leqslant
C(p)n^{-\alpha+\frac{\beta}{2p}}.$

In our applications, we can take $p$ to be very large, so we will usually
write

$\operatorname{\mathds{E}}(\left|R\right|\mid Y=i)\lesssim
n^{-\alpha+\varepsilon}$

for some small $\varepsilon>0$.

The second aspect in which both Theorems 2.1 and 2.4 need improvement is that
one would want to extend it to the models with asymmetries concerning the
change in $Y$ of the form

$\displaystyle M_{1,\pm}(W,Y)=-\lambda\left(a_{\pm}\psi
W+b_{\pm}Y+R_{1,\pm}\right),$

and where the term $b_{\pm}Y$ is not be negligible. In other words, we would
like to apply this result to the models that satisfy Assumption IIIa instead
of Assumption III. One can do it by applying a change of variable presented in
the following proposition.

######  Proposition 2.6 (Univariate change of variable).

Suppose $X$ and $Y$ are random variables satisfying Assumptions I, II, IIIa
and IV. Assume that

$R_{0,\pm}=\mp\lambda a_{\pm}Y$

and define the change of variable

$\displaystyle W^{0}:=X+\lambda\,\psi\,\alpha
XY+\frac{\lambda\,\theta}{2}\left(Y^{2}-\operatorname{\mathds{E}}Y^{2}\right)+\frac{\lambda^{2}(\psi+1)\alpha\theta}{3}(Y^{3}-\operatorname{\mathds{E}}Y^{3}),$
(2.4)

where

$\alpha=\frac{a_{+}-a_{-}}{2Q}\quad\textrm{and}\quad\theta=\frac{b_{+}}{Q}.$

Let $W={W^{0}}/{\sigma_{W^{0}}}$. Then $\left(W,Y\right)$ satisfies
Assumptions I, II, III and IV with error terms $\widetilde{R}_{1,\pm}$ and
$\widetilde{R}_{2,\pm}$. Moreover, we have

$\displaystyle\widetilde{R}_{1,\pm}=\frac{\lambda\theta}{2}\left(1-\frac{\psi}{2}\right)\frac{\overline{Y^{2}}}{\sigma_{W^{0}}}+\frac{1}{\sigma_{W^{0}}}(\widetilde{\varepsilon}_{0,\pm}+\widetilde{\varepsilon}_{1,\pm}+\widetilde{\varepsilon}_{2,\pm}+\widetilde{\varepsilon}_{3,\pm}),$

where

$\displaystyle\widetilde{\varepsilon}_{0,\pm}$
$\displaystyle:=\lambda\psi^{2}\alpha a_{\pm}X(Y\pm
1)-\frac{\lambda\,\alpha\,\psi}{2}XY+R_{1,\pm}\biggl{(}1\pm\lambda\,\psi\,\alpha+\lambda\,\psi\,\alpha
Y\biggr{)},$ $\displaystyle\widetilde{\varepsilon}_{1,\pm}$
$\displaystyle:=\lambda\left(\pm\lambda
b_{\pm}\psi\alpha\mp\frac{a_{\pm}\theta}{2}+(\psi+1)\theta\alpha\left(Q-\frac{1}{3}\lambda
a_{\pm}\right)\right)Y,$ $\displaystyle\widetilde{\varepsilon}_{2,\pm}$
$\displaystyle:=\mp\lambda^{2}\theta(\psi+1)\alpha a_{\pm}Y^{2},$
$\displaystyle\text{and}\quad\widetilde{\varepsilon}_{3,\pm}$
$\displaystyle:=\frac{1}{3}\lambda\theta(\psi+1)\alpha
Q-\lambda^{2}\theta(\psi+1)\alpha
a_{\pm}Y^{3}-\frac{\lambda^{2}\psi(\psi+1)\alpha\theta}{6}\left(Y^{3}-\operatorname{\mathds{E}}Y^{3}\right),$

and for $p\geqslant 1$

$\displaystyle\left\|\widetilde{R}_{2,\pm}-\frac{R_{2,\pm}}{\sigma^{2}_{W^{0}}}\right\|_{2p}$
$\displaystyle\lesssim\lambda^{\nicefrac{{1}}{{2}}}\psi\left|\alpha\right|\left(\frac{\sigma_{X}}{\sigma_{W^{0}}}\sqrt{\left\|\lambda(1+R_{2,\pm}/\sigma^{2}_{X})\right\|_{2p}\left\|Y\right\|_{2p}}+\frac{\left\|X\right\|_{p}}{\sigma_{W^{0}}}\right)$
$\displaystyle\qquad+\lambda^{\nicefrac{{1}}{{2}}}\left|\theta\right|\cdot\frac{\left\|Y\right\|_{p}}{\sigma_{W^{0}}}+\lambda^{3/2}(\psi+1)\left|\alpha\theta\right|\cdot\frac{\left\|Y^{2}\right\|_{p}}{\sigma_{W^{0}}}.$

Assuming the particular form of $R_{0,\pm}$ one can see this change of
variable as the correction for the asymmetry created by the change of $Y$
(_i.e.,_ the $XY$ term) and the approximation of the conditional mean up to
the third order. Considering the examples where one can compute the exact
conditional mean, we notice that the change of variable is indeed very close
to the true value. We illustrate that in the Remarks 4.8 and 4.10.

Now we explain the intuition behind each term in the change of variable. One
needs the term $\lambda\,\psi\,\alpha XY$ to account for the asymmetry between
$a_{+}$ and $a_{-}$. Indeed, when $a_{+}=a_{-}$, we have that $\alpha=0$ and
this term is not present. In the computation of $M_{1,\pm}(W^{0},Y)$ it
produces the term $\mp\alpha QX$ that in combination with $a_{\pm}X$ gives us

$\displaystyle(a_{\pm}\mp\alpha
Q)X=\left(a_{\pm}\mp\frac{a_{+}-a_{-}}{2}\right)X=\frac{1}{2}X.$

The square term has the exact form to cancel out $b_{\pm}Y$ if it is non-
negligible, while the cubic term is present to cancel everything created by
the square term to match with the coefficient of
$\operatorname{\mathds{E}}Y^{2}$.

######  Remark 2.7 (Parameter $\psi$).

In the majority of the examples for which we expect Theorem 2.4 to be used,
one has $\psi=2$. When $\psi\neq 2$, we believe that one likely needs to use
the multivariate version as in Theorem 3.1, however, we presented the
statement for general $\psi$, in case one has sufficient control on the
quantity $\lambda\theta\sigma_{Y}$.

##  3 Main results: Multivariate Case

In this section, we present the extension of our main result to the
multivariate setting.

######  Theorem 3.1.

Let $\bm{W},Y$ be, respectively, a $\mathds{R}^{d}$-valued random vector and a
random variable satisfying Assumptions I, II, III, and IV. Let $k$ be such
that $p_{k}:=\operatorname{\mathds{P}}(Y=k)>0$ and
$p_{k-1}:=\operatorname{\mathds{P}}(Y=k-1)>0$. If
$\operatorname{\mathds{E}}\left|\bm{W}\right|^{4}<\infty$ then

$\displaystyle d_{\mathcal{W}}((\bm{W}\mid
Y=k),\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z})$
$\displaystyle\qquad\leqslant\frac{1}{1+r_{k}}\widehat{A}_{k}+\frac{1}{2(1+r_{k})}\left\|\Sigma^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{op}}\widehat{B}_{k}+\frac{1+r_{k}}{2Q}\left(\widehat{C}_{k}+\widehat{D}_{k}\right)$
$\displaystyle\qquad\qquad\qquad+(1+r_{k})\left\|\Sigma^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{op}}^{3/2}\sqrt{c_{3}\cdot\widehat{E}_{k}\cdot\widehat{F}_{k}},$

where $c_{3}=(2+8e^{-3/2})/\sqrt{2\pi}<2,$ $r_{k}=p_{k-1}/p_{k}$,

$\displaystyle\widehat{A}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|\Psi^{-1}\bm{R}_{1,-}\right|\mid
Y=k\right)+r_{k}\operatorname{\mathds{E}}\left(\left|\Psi^{-1}\bm{R}_{1,+}\right|\mid
Y=k-1\right),$ $\displaystyle\widehat{B}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left\|\Psi^{-1}\Gamma_{2,-}\right\|_{\operatorname{H.S.}}\mid
Y=k\right)+r_{k}\operatorname{\mathds{E}}\left(\left\|\Psi^{-1}\Gamma_{2,+}\right\|_{\operatorname{H.S.}}\mid
Y=k-1\right),$ $\displaystyle\widehat{C}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left(\left|\bm{W}\right|+\sqrt{\operatorname{Tr}(\Sigma)}\right)(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\,\big{|}\,Y\in\\{k-1,k\\}\right)$
$\displaystyle\widehat{D}_{k}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|\,\big{|}\,Y\in\\{k-1,k\\}\right)$
$\displaystyle\widehat{E}_{k}$
$\displaystyle={\operatorname{\mathds{E}}\left(\left|(\lambda\Psi)^{-1}\Delta\\!\bm{W}\right|\cdot\left|\Delta\\!\bm{W}\right|^{3}\,\big{|}\,Y\in\\{k-1,k\\}\right)},$
$\displaystyle\text{ and }\quad\widehat{F}_{k}$
$\displaystyle=\sqrt{\operatorname{Tr}(\Sigma)+\operatorname{\mathds{E}}\left(\left|\bm{W}\right|^{2}\,\big{|}\,Y\in\\{k-1,k\\}\right)}.$

In particular, if $\operatorname{Cov}(\bm{W})=\Sigma=I_{d}$ then the error
bound reduces to

$\displaystyle d_{\mathcal{W}}((\bm{W}\mid Y=k),\bm{Z})$
$\displaystyle\leqslant\frac{1}{1+r_{k}}\left(\widehat{A}_{k}+\frac{1}{2}\widehat{B}_{k}\right)+\frac{1+r_{k}}{2Q}\left(\widehat{C}_{k}+\widehat{D}_{k}\right)$
$\displaystyle\quad+(1+r_{k})\cdot(d+\operatorname{\mathds{E}}(\left|\bm{W}\right|^{2}\mid
Y\in\\{k,k-1\\}))^{\frac{1}{4}}\cdot\sqrt{\widehat{E}_{k}}.$

On the other hand if only
$\operatorname{\mathds{E}}\left|\bm{W}\right|^{3}<\infty$ then

$\displaystyle d_{\mathcal{W}}((\bm{W}\mid
Y=k),\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z})$
$\displaystyle\leqslant\frac{1}{1+r_{k}}\left(\widehat{A}_{k}+\frac{1}{2}\left\|\Sigma^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{op}}\widehat{B}_{k}\right)$
$\displaystyle\quad+\frac{1+r_{k}}{2Q}\left(\widehat{C}_{k}+\widehat{D}_{k}\right)+c_{2}(1+r_{k})\cdot\left\|\Sigma^{-1/2}\right\|_{\operatorname{op}}^{2}\widehat{E}_{k}^{\prime}\cdot\widehat{F}_{k}^{\prime},$

where $c_{2}=4/\sqrt{2\pi e}<1$,
$\widehat{A}_{k},\widehat{B}_{k},\widehat{C}_{k},\widehat{D}_{k}$ are as above
and

$\displaystyle\widehat{E}_{k}^{\prime}$
$\displaystyle=\operatorname{\mathds{E}}\left(\left|(\lambda\Psi)^{-1}\Delta\\!\bm{W}\right|\left|\Delta\\!\bm{W}\right|^{2}\,\big{|}\,Y\in\\{k-1,k\\}\right),$
$\displaystyle\text{and}\qquad\widehat{F}_{k}^{\prime}$
$\displaystyle=1+\left|\log\left(c_{2}\cdot\left\|\Sigma^{-1/2}\right\|_{\operatorname{op}}^{2}\cdot{\widehat{E}^{\prime}_{k}}/{\widehat{F}_{k}}\right)\right|.$

######  Remark 3.2.

The case when $\Sigma$ is the identity matrix, the proof of Theorem 2.4 can be
easily adapted to get a bound on $\left|\operatorname{\mathds{E}}\left(\Delta
f(\bm{W})-\bm{W}^{T}\nabla f(\bm{W})\right)\mathds{1}_{Y=k}\right|$. This
case, in a way, corresponds to the setting of [12]. However if $\Sigma$ is not
an identity matrix one has to change the function to an expression that
already resembles Taylor approximation and derive an upper bound to
$\left|\operatorname{\mathds{E}}\left(\nabla^{T}\Sigma\nabla
f(\bm{W})-\bm{W}^{T}\nabla f(\bm{W})\right)\mathds{1}_{Y=k}\right|$. This
generalization is done in the spirit of [23, 38, 39]. Moreover, in many
applications $\left\|\Psi^{-1}\right\|_{\operatorname{op}}$ is bounded by a
constant and thus $\left|\Psi^{-1}\Delta\\!\bm{W}\right|$ can be bounded by
some constant multiple of $\left|\Delta\\!\bm{W}\right|$.

The proof of Theorem 3.1 is analogous to the univariate case. We first
establish a CCLT for $(\bm{W}\mid Y\in\\{k-1,k\\})$ that we state in Lemma 5.2
and then combine it with the quantitative bound on the difference of
$(\bm{W}\mid Y=k)$ and $(\bm{W}\mid Y=k-1)$ as in Lemma 5.1. To derive the
bound in terms of Wasserstein distance, we follow the smoothing technique as
in [23, 38]. We present the proof of Theorem 3.1 in Section 5.3.

Similar to the univariate case, we introduce a change of variable that allows
one to pass from Assumption IIIa to Assumption III.

######  Proposition 3.3 (Multivariate change of variable).

Let $\bm{X},Y$ be, respectively, a $\mathds{R}^{d}$-valued random vector and a
random variable satisfying Assumptions I, II, IIIa, and IV. Define the
following change of variable

$\displaystyle\bm{W}^{0}:=\bm{X}+\lambda\mathrm{A}\bm{X}Y+\frac{\lambda\bm{\theta}}{2}\left(Y^{2}-\operatorname{\mathds{E}}Y^{2}\right)+\frac{\lambda^{2}(\mathrm{A}+\alpha)\bm{\theta}}{3}(Y^{3}-\operatorname{\mathds{E}}Y^{3}),$
(3.1)

where

$\mathrm{A}=\frac{\Psi_{+}-\Psi_{-}}{2Q},\quad\alpha=\frac{a_{+}-a_{-}}{2Q},\quad\textrm{and}\quad\bm{\theta}=\frac{\bm{b}_{+}}{Q}.$

Then vector
$\bm{W}:=\left(\bm{W}^{0}_{i}/\sigma_{\bm{W}^{0}_{i}}\right)_{1\leqslant
i\leqslant d}$ satisfies Assumptions I, II, III, and IV with error terms
$\widetilde{\bm{R}}_{1,\pm}$ and $\widetilde{\Gamma}_{2,\pm}$. In particular,
we have

$\displaystyle\widetilde{\bm{R}}_{1,\pm}=\Sigma^{-\nicefrac{{1}}{{2}}}_{W^{0}}(\widetilde{\bm{\varepsilon}}_{0,\pm}+\widetilde{\bm{\varepsilon}}_{1,\pm}+\widetilde{\bm{\varepsilon}}_{2,\pm}+\widetilde{\bm{\varepsilon}}_{3,\pm}),$

where

$\displaystyle\widetilde{\bm{\varepsilon}}_{0,\pm}$ $\displaystyle:=\lambda
a_{\pm}\Psi\mathrm{A}\bm{X}(Y\pm
1)-\frac{\lambda\,\Psi\,\mathrm{A}}{2}\bm{X}Y+\biggl{(}1\pm\lambda\,\mathrm{A}+\lambda\,\mathrm{A}Y\biggr{)}\bm{R}_{1,\pm},$
$\displaystyle\widetilde{\bm{\varepsilon}}_{1,\pm}$
$\displaystyle:=\lambda\left(\pm\lambda\mathrm{A}\bm{b}_{\pm}\mp\frac{a_{\pm}\bm{\theta}}{2}+(\mathrm{A}+\alpha)\bm{\theta}\left(Q-\frac{1}{3}\lambda
a_{\pm}\right)\right)Y,$ $\displaystyle\widetilde{\bm{\varepsilon}}_{2,\pm}$
$\displaystyle:=\mp\lambda^{2}a_{\pm}(\mathrm{A}+\alpha)\bm{\theta}Y^{2},$
$\displaystyle\text{and}\quad\widetilde{\bm{\varepsilon}}_{3,\pm}$
$\displaystyle:=\frac{1}{3}\lambda(\mathrm{A}+\alpha)\bm{\theta}Q-\lambda^{2}a_{\pm}(\mathrm{A}+\alpha)\bm{\theta}Y^{3}-\frac{\lambda^{2}\Psi(\mathrm{A}+\alpha)\bm{\theta}}{6}\left(Y^{3}-\operatorname{\mathds{E}}Y^{3}\right),$

and

$\displaystyle\left\|\widetilde{\Gamma}_{2,\pm}-\Sigma^{-\nicefrac{{1}}{{2}}}_{\bm{W}^{0}}\Gamma_{2,\pm}\Sigma^{-\nicefrac{{1}}{{2}}}_{\bm{W}^{0}}\right\|_{p-\operatorname{H.S.}}$
$\displaystyle\quad\lesssim\lambda^{\nicefrac{{1}}{{2}}}\left(\frac{\left\|\Sigma_{\bm{X}}\right\|_{\operatorname{H.S.}}}{\left\|\Sigma_{\bm{W}^{0}}\right\|_{\operatorname{H.S.}}}\sqrt{\left\|\lambda(\Psi+\Sigma_{\bm{X}}^{-\nicefrac{{1}}{{2}}}\Gamma_{2,\pm}\Sigma_{\bm{X}}^{-\nicefrac{{1}}{{2}}})\right\|_{p-\operatorname{H.S.}}\left\|Y\right\|_{2p}}+\left\|\Sigma_{\bm{X}}^{-\nicefrac{{1}}{{2}}}X\right\|_{p}\right)$
$\displaystyle\qquad+\lambda^{\nicefrac{{1}}{{2}}}\left\|\bm{\theta}\right\|_{p}\cdot\left\|\Sigma_{\bm{W}^{0}}^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{H.S.}}\left\|Y\right\|_{p}+\lambda^{3/2}\left\|\bm{\theta}\right\|_{p}\left\|\Sigma_{\bm{W}^{0}}^{-\nicefrac{{1}}{{2}}}\right\|_{\operatorname{H.S.}}\left\|Y^{2}\right\|_{p}.$

######  Remark 3.4.

Note that the change of variable (3.1) with $d=1$ agrees with univariate
change as in (2.4). The terms play analogous role as described in the
univariate case. From the Assumption IIIa with $d=1$ we have that
$\Psi_{\pm}=a_{\pm}\psi$ and hence
$\mathrm{A}=(\Psi_{+}-\Psi_{-})/2=\psi(a_{+}-a_{-})/2=\psi\alpha$ making the
$XY$ term of (2.4) match the $\bm{X}Y$ term of (3.1), while
$\mathrm{A}+\alpha=\psi\alpha+\alpha=(\psi+1)\alpha$ matches the cubic terms
of these changes of variables.

##  4 Applications

###  4.1 Classical methods in CCLT

In this section we present several derivation of CCLT using classical Stein’s
method. As we mentioned in Remark 1.5 to apply this technique to a random
vector $(X,Y)$ it is crucial to work with an exchangeable pair
$((X,Y),(X^{\prime},Y^{\prime}))$ such that $\operatorname{\mathds{P}}(\Delta
X\neq 0,\Delta\\!Y=0)>0.$

In each of the following subsections we first describe the model and then
state the relevant CCLT result.

####  4.1.1 Variant of an occupancy problem

Suppose there are three urns and $n$ many distinct balls. At time $i$ we put
the $i^{\textrm{th}}$ ball into an urn numbered $U_{i}$, where $U_{i}$’s are
i.i.d. random variables that are equal to $1$ with probability $p_{1}$, to $2$
with probability $p_{2}$, and to $3$ with probability $p_{3}:=1-p_{1}-p_{2}$.
Define

$\displaystyle V$ $\displaystyle:=\sum_{i=1}^{n}\mathds{1}_{U_{i}=2}\text{ and
}W:=n^{-\nicefrac{{1}}{{2}}}\sqrt{\frac{p_{1}p_{2}}{1-p_{2}}}\sum_{i=1}^{n}\left(\frac{1}{p_{1}}\mathds{1}_{U_{i}=1}-\frac{1}{p_{3}}\mathds{1}_{U_{i}=3}\right)$
(4.1)

as the number of balls in the second urn and the scaled difference between the
number of balls in the first and the third urn, respectively, at time $n$.
Notice that $\sigma_{V}^{2}=np_{2}(1-p_{2})$. We have the following CCLT
result with an explicit rate of convergence for $(W\mid V=k)$ when
$|k-np_{2}|\ll n^{\nicefrac{{1}}{{2}}}$.

######  Lemma 4.1.

Let $W$ and $Y$ be as defined in (4.1). For any $k\in\mathds{Z}$ with
$|k-np_{2}|\ll n^{\nicefrac{{1}}{{2}}}$, we have

$\displaystyle d_{\mathcal{W}}\left((W\mid V=k),\,Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

###### Proof.

Notice that $W$ is mean zero variance one random variable. Now conciser the
following Glauber dynamics Markov chain, for a given $(W,V)$ we pick index of
one of the balls uniformly at random, _i.e.,_
$I\sim\textrm{Uniform}\\{1,2,\ldots,n\\}$, and then re-sample its placing,
_i.e.,_ place $I^{\textrm{th}}$ ball into the urn $U_{I}$ where
$U_{I}\,{\buildrel d\over{=}}\,U_{1}$ and independent of everything else. Call
the result $(W^{\prime},V^{\prime})$. Clearly $(W,V)$ and
$(W^{\prime},V^{\prime})$ are equidistributed. Notice that, with
$\lambda=(1-p_{2})/n$, we have

$\displaystyle\operatorname{\mathds{P}}(V^{\prime}=V\mid
V,W)=\frac{1}{n}\left(p_{2}V+(1-p_{2})(n-V)\right)=1-p_{2}+(2p_{2}-1)\cdot\frac{V}{n},$
(4.2) $\displaystyle\operatorname{\mathds{E}}\left(\Delta
W\mathds{1}_{V^{\prime}=V}\mid\bm{U}\right)=-\lambda W,$ and
$\displaystyle\operatorname{\mathds{E}}\left(|\Delta
W|^{2}\mathds{1}_{V^{\prime}=V}\mid\bm{U}\right)=2\lambda\left(1+R_{2}\right),$

where $\bm{U}=(U_{1},U_{2},\ldots,U_{n})$ and

$R_{2}=\frac{p_{1}p_{3}}{n(1-p_{2})}\operatorname{\mathds{E}}\left(\sum_{i=1}^{n}p_{1}^{-2}(\mathds{1}_{U_{i}=1}-p_{1})+p_{3}^{-2}(\mathds{1}_{U_{i}=3}-p_{3})\
\bigl{|}\ \bm{U}\right).$

For any piece-wise three times differentiable function $F$ such that
$F^{\prime}=f\in\mathcal{A}$, the random variable
$(F(W^{\prime})-F(W))\mathds{1}_{V^{\prime}=V=k}$ has mean zero. Thus using
standard techniques we have

$\displaystyle\operatorname{\mathds{E}}\biggl{(}\bigl{(}\Delta W\cdot
f(W)+\frac{1}{2}\left|\Delta W\right|^{2}\cdot
f^{\prime}(W)+R\bigr{)}\mathds{1}_{V^{\prime}=V=k}\biggr{)}=0,$

where $R\leqslant\frac{\left|f\right|_{2}}{6}|\Delta W|^{3}$. Simplifying, we
arrive at

$\displaystyle\operatorname{\mathds{E}}\biggl{(}\left(-\lambda Wf(W)+\lambda
f^{\prime}(W)(1+R_{2})+R\right)\mathds{1}_{V^{\prime}=V}\mathds{1}_{V=k}\biggr{)}=0.$

Thus

$\displaystyle\operatorname{\mathds{E}}\left((f^{\prime}(W)-Wf(W))\mathds{1}_{V^{\prime}=V}\mid
V=k,W\right)$
$\displaystyle\quad\leqslant\left|f\right|_{1}\cdot\operatorname{\mathds{E}}\left(\left|R_{2}\right|\mathds{1}_{V^{\prime}=V}\mid
V=k,W\right)+\frac{\left|f\right|_{2}}{6\lambda}\cdot\operatorname{\mathds{E}}\left(|\Delta
W|^{3}\mathds{1}_{V^{\prime}=V}\mid V=k,W\right)\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

By (4.2) we have, $\operatorname{\mathds{P}}(V^{\prime}=V\mid V=k,W)\approx
1-p_{2}.$ Thus if $k$ is near the mean of $V$, more specifically if
$|k-np_{2}|\ll\sigma_{V}$ using relation (1.1) we conclude that

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid V=k),Z\bigr{)}$
$\displaystyle\lesssim n^{-\nicefrac{{1}}{{2}}}.$

This completes the proof. $\blacksquare$

####  4.1.2 Uniform darts given number of misses

Let $T\subset[0,1]^{2}$ be a set, called target, of area $q\in(0,1)$. Suppose
$U_{1},U_{2},\dots$ are i.i.d. uniform random vectors taking values in
$[0,1]^{2}$, called darts. In particular, a dart hits the target with
probability $\operatorname{\mathds{P}}(U_{i}\in T)=q$ and misses with
probability $\operatorname{\mathds{P}}(U_{i}\notin T)=1-q=p$. Let
$s:T\to\mathds{R}$ be a bounded non constant score function such that
$\operatorname{\mathds{E}}s(U_{1})\mathds{1}_{U_{1}\in T}=0$ and
$\operatorname{\mathds{E}}s(U_{1})^{2}\mathds{1}_{U_{1}\in T}=1$ .

Define

$Y:=\sum_{i}\mathds{1}_{U_{i}\notin T}-np\quad\text{ and }\quad
W:=n^{-\nicefrac{{1}}{{2}}}\sum_{i}^{n}s(U_{i})\mathds{1}_{U_{i}\in T},$

as the centered number of darts that missed the target and the total score,
respectively. Notice that $Y$ takes values in $\\{-np\\}+\mathds{Z}$ and that
$\sigma_{Y}^{2}=npq$.

######  Lemma 4.2.

For $W$ and $Y$ as above and any $k\in\\{np\\}+\mathds{Z}$ with $|k|\ll
n^{\nicefrac{{1}}{{2}}}$, we have that

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k),Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

###### Proof.

First, we notice that the $W$ and $Y$ are uncorrelated. As in Example 4.1, we
will consider Glauber dynamics conditioned on keeping the value of $Y$ to
remain the same. Namely at time $n$ we choose a dart
$I\sim\textrm{Uniform}\\{1,\ldots,n\\}$ and define

$W^{\prime}=W-n^{-\nicefrac{{1}}{{2}}}s(U_{I})\mathds{1}_{U_{I}\in
T}+n^{-\nicefrac{{1}}{{2}}}s(U^{\prime})\mathds{1}_{U^{\prime}\in T},$

where $U^{\prime}\sim\textrm{Uniform}\left([0,1]^{2}\right)$ and independent
of everything else. It is easy to see that resulting vectors $(W,Y)$ and
$(W^{\prime},Y^{\prime})$ are exchangeable, and with a positive probability,
the total score changes while the number of misses remains the same. Notice
that we utilize that the score function $s(u)$ is not constant on $T$;
otherwise, $Y^{\prime}=Y$ would have implied $W^{\prime}=W$. First we compute
that

$\displaystyle\operatorname{\mathds{E}}(\Delta
W\cdot\mathds{1}_{Y^{\prime}=Y}\mid\bm{U})$ $\displaystyle=-\frac{q}{n}W$
$\displaystyle\textrm{ and }\operatorname{\mathds{E}}(|\Delta
W|^{2}\cdot\mathds{1}_{Y^{\prime}=Y}\mid\bm{U})$
$\displaystyle=\frac{2q}{n}\left(1+R_{2}\right),$

where $\bm{U}=(U_{1},U_{2},\ldots,U_{n})$ and

$R_{2}:=-\frac{1}{2nq}Y+\frac{1}{2n}\operatorname{\mathds{E}}\left(\sum_{i=1}^{n}(s(U_{i})^{2}\mathds{1}_{U_{i}\in
T}-1)\ \biggl{|}\ W,Y\right).$

Since $s(x)$ is bounded we can bound $|\Delta
W|\leqslant\left\|s\right\|_{\infty}$. By application of standard technique,
we derive that for any $k\in\\{np\\}+\mathds{Z}$ with $|k|\ll
n^{\nicefrac{{1}}{{2}}}$ we have

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid Y=k),Z\bigr{)}$
$\displaystyle\leqslant\sup_{f\in\mathcal{A}}\left\\{\left|f\right|_{1}\cdot\operatorname{\mathds{E}}\left|R_{2}\right|+\frac{\left|f\right|_{2}}{6\lambda}\operatorname{\mathds{E}}\left(|\Delta
W|^{3}\mathds{1}_{Y^{\prime}=Y}\mid Y=k\right)\right\\}\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

This completes the proof. $\blacksquare$

####  4.1.3 Number of $01$’s given the number of $1$’s in a random binary
sequence

Let $(\omega_{1},\omega_{2},\ldots,\omega_{n})$ be a sequence of i.i.d.
Bernoulli$\left(p\right)$ random variables with $\omega_{n+1}=\omega_{1}$. Let
$V:=\sum_{i=1}^{n}\omega_{i}$ be the number of $1$’s in it and define

$\displaystyle
U:=\sum_{i=1}^{n}\mathds{1}_{\omega_{i}=0}\mathds{1}_{\omega_{i+1}}=\sum_{i=1}^{n}(1-\omega_{i})\omega_{i+1}$

be the number of times a zero is followed by a one. Define

$W^{0}:=U-\operatorname{\mathds{E}}\left(U\mid V=m\right)\text{ and
}W:={W^{0}}/{\sigma_{W^{0}}}.$

One can easily compute that

$\displaystyle\operatorname{\mathds{E}}(U\mid V=m)$
$\displaystyle=\frac{m(n-m)}{n-1}$ $\displaystyle\text{ and
}\sigma_{W_{0}}^{2}=\operatorname{Var}(U\mid V=m)$
$\displaystyle=\frac{\binom{m}{2}\binom{n-m}{2}}{(n-1)\binom{n-1}{2}}\approx
n\cdot(m/n)^{2}(1-m/n)^{2}.$

Moreover, we have the following result.

######  Lemma 4.3.

Let $W$ and $V$ be as above. For any $m\in\mathds{N}$ with
$m/n\in(\varepsilon,1-\varepsilon)$ for some
$\varepsilon\in(0,\nicefrac{{1}}{{2}})$, we have that

$\displaystyle d_{\mathcal{W}}\left((W\mid V=m),Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

###### Proof.

We will work with the random variable
$X:=V-U=\sum_{i=1}^{n}\omega_{i}\omega_{i+1}$. Consider the following
construction of an exchangeable pair. For a binary sequence
$\bm{\omega}=(\omega_{1},\omega_{2},\ldots,\omega_{n})$, pick two indices $I$
and $J$ uniformly at random from $\\{1,2,\ldots,n\\}$ and create a new binary
sequence by swapping the bits at those locations
$\bm{\omega}^{\prime}=(\omega_{1}^{\prime},\omega_{2}^{\prime},\ldots,\omega_{n}^{\prime})$
such that $\omega_{i}^{\prime}=\omega_{i}$ for all $i\notin\\{I,J\\}$,
$\omega_{I}^{\prime}=\omega_{J}$, and $\omega_{J}^{\prime}=\omega_{I}$. We
have

$\displaystyle\Delta
X=(\omega_{I}-\omega_{J})(\omega_{J+1}+\omega_{J-1}-\omega_{I+1}-\omega_{I-1})-(\omega_{I}-\omega_{J})^{2}\mathds{1}_{|I-J|=1}.$
(4.3)

One can easily check that $|\Delta X|\leqslant 2$ and

$\operatorname{\mathds{E}}(\Delta X\mid
V=m)=-\frac{4(n-1)}{n^{2}}\left(X-\frac{m(m-1)}{n-1}\right)$

This gives another proof of the fact that
$\operatorname{\mathds{E}}\left(X\mid V=m\right)=\frac{m(m-1)}{n-1}$. In
particular, we have

$\displaystyle\operatorname{\mathds{E}}(\Delta W\mid V=m)$
$\displaystyle=-\frac{4(n-1)}{n^{2}}W$ $\displaystyle\text{and
}\operatorname{\mathds{E}}(\left|\Delta W\right|^{2}\mid V=m)$
$\displaystyle=\frac{8(n-1)}{n^{2}}(1+R_{2}),$

where $R_{2}$ is a centered random variable with
$\operatorname{\mathds{E}}\left|R_{2}\right|\lesssim n^{-\nicefrac{{1}}{{2}}}$
that can be computed explicitly using (4.3). By a similar derivation as in the
Lemma 4.1 we have that

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid V=m),Z\bigr{)}$
$\displaystyle\leqslant\sup_{f\in\mathcal{A}}\left\\{\left|f\right|_{1}\operatorname{\mathds{E}}\left|R_{2}\right|+\frac{\left|f\right|_{2}}{6\lambda}\operatorname{\mathds{E}}\left(|\Delta
W|^{3}\mid
V=m\right)\right\\}\lesssim\frac{n}{n^{3/2}}=n^{-\nicefrac{{1}}{{2}}}.$

This completes the proof. $\blacksquare$

####  4.1.4 Number of wedges in a uniform graph with $m$ edges

Let $\mathcal{G}\sim G(n,m)$, a graph on $n$ vertices with $m$ edges chosen
uniformly at random. For Erdős–Rényi random graph $G_{n,p}$ the number of
edges $E$ is a sufficient statistic for the parameter $p$, thus the model
$(G_{n,p}\mid E=m)$ is equivalent to $G(n,m)$. In other words, deriving CCLT
in $G_{n,p}$ conditioned on the number of edges being $m$ can be converted
into deriving regular CLT in $G(n,m)$.

Let $d_{i}=\sum_{j}\mathds{1}_{i\sim j}$ be the degree of vertex $i$ in
$\mathcal{G}$, note that $\sum_{i}d_{i}=2m$ and
$\overline{d}_{i}:=d_{i}-\frac{2m}{n}$. The number of wedges
$U:=\sum\mathds{1}_{i\sim j}\mathds{1}_{j\sim\ell}$ and can be written as

$U=\frac{1}{2}\sum_{i}d_{i}(d_{i}-1)=\frac{1}{2}\sum_{i}d_{i}^{2}-m.$

######  Lemma 4.4.

We have $\operatorname{\mathds{E}}(U)=2m(m-1)/(n+1)$. Moreover, for
$m\in\mathds{N}$ with $m/N\in(\varepsilon,1-\varepsilon)$ for some
$\varepsilon\in(0,\nicefrac{{1}}{{2}})$, we have that

$\displaystyle
d_{\mathcal{W}}((U-\operatorname{\mathds{E}}U)/\sigma_{U},Z)\lesssim
n^{-\nicefrac{{1}}{{2}}}.$

###### Proof.

Define $W:=(U-\operatorname{\mathds{E}}U)/\sigma_{U}$ and
$X:=\frac{1}{2}\sum_{i}\overline{d}_{i}^{2}$. Notice that

$U=X+\frac{2m^{2}}{n}-m.$

Similar to the example in Section 4.1.3 we will consider the Markov Chain that
swaps two uniformly chosen edges to create an exchangeable pair preserving the
total amount of edges. Then

$\displaystyle\Delta
d_{i}=\begin{cases}+1&\textrm{w.p.~{}}\frac{1}{4N\left(N-1\right)}(n-1-d_{i})(m-d_{i})\\\
-1&\textrm{w.p.~{}}\frac{1}{4N\left(N-1\right)}d_{i}\left(N-m-(n-1-d_{i})\right)\\\
0&\textrm{otherwise}.\end{cases}$

Simple computations show that, for $i=1,2,\ldots,n$, we have

$\displaystyle\operatorname{\mathds{E}}\left(\Delta
d_{i}\mid\mathcal{G}\right)$
$\displaystyle=-\frac{1}{4\left(N-1\right)}\overline{d_{i}}\qquad\text{ and}$
$\displaystyle\operatorname{\mathds{E}}\left(|\Delta
d_{i}|^{2}\mid\mathcal{G}\right)$
$\displaystyle=\frac{1}{4\left(N-1\right)}\left(\frac{2(n-1)(n-2)}{n}\frac{m}{N}\left(1-\frac{m}{N}\right)+\frac{n-4}{n}\left(1-\frac{2m}{N}\right)\overline{d}_{i}+\frac{2\overline{d}_{i}^{2}}{N}\right).$

Therefore, using

$\displaystyle\Delta X=\frac{1}{2}\sum_{i=1}^{n}\Delta d_{i}\left(\Delta
d_{i}+2\overline{d}_{i}\right).$

we have that

$\displaystyle\operatorname{\mathds{E}}(\Delta X\mid\mathcal{G})$
$\displaystyle=-\frac{1}{2N}\left(X-\frac{n-1}{n+1}\cdot
m\left(1-\frac{m}{N}\right)\right).$

In particular, this implies that

$\operatorname{\mathds{E}}(X)=\frac{n-1}{n+1}\cdot
m\left(1-\frac{m}{N}\right)\text{ and
}\operatorname{\mathds{E}}(U)=\frac{2m(m-1)}{n+1}.$

So, after scaling by $\sigma_{U}\approx n^{3/2}$, we have

$\displaystyle\operatorname{\mathds{E}}\left(\Delta W\mid\mathcal{G}\right)$
$\displaystyle=-\frac{1}{2N}W$ $\displaystyle\text{and
}\operatorname{\mathds{E}}\left(\left|\Delta
W\right|^{2}\mid\mathcal{G}\right)$ $\displaystyle=\frac{1}{2N}2(1+R_{2}),$

where $R_{2}$ has mean zero and
$\operatorname{\mathds{E}}\left|R_{2}\right|\lesssim
n^{-\nicefrac{{1}}{{2}}}$. Letting $\lambda:=\frac{1}{2N}$. To derive CCLT it
remains to upper bound the error term
$\lambda^{-1}\operatorname{\mathds{E}}\left(|\Delta W|^{3}\mid E=m\right)$,
which we do as follows

$\displaystyle\lambda^{-1}\operatorname{\mathds{E}}\bigl{(}\left|\Delta
W\right|^{3}\bigr{)}$
$\displaystyle=\lambda^{-1}\operatorname{\mathds{E}}\left(|\Delta
W|\cdot\Delta W^{2}\right)\lesssim\lambda^{-1}n^{-\nicefrac{{1}}{{2}}}\cdot
2\lambda\approx n^{-\nicefrac{{1}}{{2}}},$

and get that

$\displaystyle
d_{\mathcal{W}}(W,Z)\leqslant\sqrt{\frac{2}{\pi}}\operatorname{\mathds{E}}\left|R_{2}\right|+\frac{2}{3\lambda}\operatorname{\mathds{E}}\left|\Delta
W\right|^{3}\lesssim n^{-\nicefrac{{1}}{{2}}}$

to complete the proof. $\blacksquare$

###  4.2 Applications of main results in one dimension

In this section, we present several applications of Theorem 2.4. In Section
4.2.1 we present a CCLT where due to inhomogeneity of the model, swapping the
Markov chain does not give an exchangeable pair, and hence full strength of
our main result is needed. In Sections 4.2.2 and 4.2.3 we explore the same
models as in Sections 4.1.3 and 4.1.4, respectively, but under with
exchangeable pair created by Glauber dynamics rather than the swapping Markov
chain. We bounded all of the error terms as described in Remark 2.5, and hence
we have the $\varepsilon$ in the exponent.

####  4.2.1 Difference between the number of $11$ patterns that start at odd
and even bits in a two-species binary sequence

Let $\bm{\omega}=(\omega_{1},\omega_{2},\ldots,\omega_{n})$ be a sequence of
independent Bernoulli$\left(p_{i}\right)$ random variables. We assume that $n$
is even and $\omega_{n+1}:=\omega_{1}$. Let $p_{i}$ be equal to $p$ if $i$ is
odd and equal to $q=1-p$ if $i$ is even. Consider the random variable
$V:=\sum_{i=1}^{n}\omega_{i}$, the number of $1$’s in the $\bm{\omega}$, and
$X:=\sum_{i=1}^{n}(-1)^{i}\omega_{i}\omega_{i+1}$, the difference between the
number of $11$’s that start at even and odd positions. Define
$Y:=V-\frac{n}{2}$, notice that $\operatorname{\mathds{E}}Y=0$ and
$\sigma_{Y}^{2}=npq$. Also, notice that $Y$ is not a sufficient statistic for
$p$, making this example particularly interesting. The random variable $X$ can
be rewritten as

$\displaystyle X$
$\displaystyle=\sum_{i=1}^{n}(-1)^{i}\omega_{i}\,\omega_{i+1}=\sum_{i=1}^{n}(-1)^{i}\overline{\omega}_{i}\,\overline{\omega}_{i+1}.$

This representation of $X$ is particularly convenient in computations for the
variance $\sigma_{X}^{2}=np^{2}(1-p)^{2}$ and a variety of terms in the
following lemma.

######  Lemma 4.5.

Let $X$ and $Y$ be as above, define $W:=\frac{X}{\sigma_{X}}$. For
$k\in\mathds{Z}$ with $|k|\ll n^{\nicefrac{{1}}{{2}}}$, we have that

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k)\,,\,Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

###### Proof.

Notice that $W$ and $Y$ are uncorrelated random variables,
$\sigma_{X}^{2}=np^{2}q^{2}$, and consider the following construction of an
exchangeable pair. Pick a position $I$ uniformly at random and replace it with
an independent $\omega_{I}^{\prime}\sim$ Bernoulli$(p_{I})$. It follows that
$(W,Y)$ satisfies Assumptions I, II, III and IV with $\lambda=\frac{1}{n}$ and
$\psi=2$ In particular,

$\displaystyle M_{1,\pm}(W,Y)$
$\displaystyle=-\frac{1}{n}(p+q)W=-\frac{1}{n}\frac{1}{2}\cdot 2W,$
$\displaystyle M_{2,\pm}(W,Y)$
$\displaystyle=\frac{1}{n}\left(2+R_{2,\pm}\right),$

where

$\displaystyle R_{2,+}$
$\displaystyle=-\sum_{i=1}^{n}p_{i}\overline{\omega}_{i-1}^{2}\overline{\omega}_{i}+p_{i}\overline{\omega}_{i+1}^{2}\overline{\omega}_{i}+2pq\overline{\omega}_{i-1}\overline{\omega}_{i+1}-2p_{i}\overline{\omega}_{i-1}\overline{\omega}_{i}\overline{\omega}_{i+1}$
$\displaystyle\text{and }R_{2,-}$
$\displaystyle=\sum_{i=1}^{n}p_{i}\overline{\omega}_{i-1}^{2}\overline{\omega}_{i}+p_{i}\overline{\omega}_{i+1}^{2}\overline{\omega}_{i}-2pq\overline{\omega}_{i-1}\overline{\omega}_{i+1}-2p_{i}\overline{\omega}_{i-1}\overline{\omega}_{i}\overline{\omega}_{i+1}.$

Notice that $R_{2,+}$ and $R_{2,-}$ have means equal to zero and variances of
order $n$.

For $\hat{k}\in\\{k-1,k\\}$ with $\left|k\right|\ll\sigma_{Y}$, by LLT we have

$\operatorname{\mathds{P}}(Y=\hat{k})\approx\sigma_{Y}^{-1}\approx
n^{-\nicefrac{{1}}{{2}}}.$

Thus the error terms from Theorem 2.4 can be upper bounded as follows

$\displaystyle\operatorname{\mathds{E}}(\left|R_{2,\pm}\right|\mid
Y=\hat{k})\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon},$
$\displaystyle\operatorname{\mathds{E}}(\left|W\right|\left|R_{0,\pm}\right|\mid
Y=\hat{k})\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon},$
$\displaystyle\operatorname{\mathds{E}}(\left|\Delta W\right|\mid
Y=\hat{k})\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon},$

and

$\left|\operatorname{\mathds{E}}\left(\left|\Delta W\right|^{3}\mid
Y\in\\{k-1,k\\}\right)\right|=\left|\operatorname{\mathds{E}}\left(|\Delta
W|\cdot\Delta W^{2}\mid Y\in\\{k-1,k\\}\right)\right|\lesssim\lambda
n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

In the last bound we used that $\left|\Delta W\right|\leqslant 2/\sigma_{X}$.
Thus by Theorem 2.4 we get that

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k)\,,\,Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}$

where the constant in the right hand side depends on $p$ and $\varepsilon$.
$\blacksquare$

######  Remark 4.6 (Change of variable and the conditional mean in Lemma 4.5).

In the lemma above, we do not use the change of variable because the model
already satisfies Assumptions I, III and IV. It is already symmetric due to
the choice of $p_{2i}=1-p_{2i+1}$, for general values of $p_{2i}$ and
$p_{2i+1}$ one would need to have the $\lambda\psi\alpha XY$ term as in (2.4).
However, the square and the cubic terms are not needed here because
$\operatorname{\mathds{E}}(W\mid Y=k)\approx 0$, which follows from the fact
that

$\operatorname{\mathds{E}}\left(\Delta W\mid W,Y\right)=-\frac{2}{n}W.$

####  4.2.2 Number of $01$’s given the number of $1$’s in a random binary
sequence

Similarly to the model in Section 4.1.3, let
$(\omega_{1},\omega_{2},\ldots,\omega_{n},\omega_{1})$ be a sequence of
independent Bernoulli$\left(p\right)$ random variables, with ends glued
together for simplicity. Let $V:=\sum_{i=1}^{n}\mathds{1}_{\omega_{i}=1}$ be
the number of $1$’s in it and define
$U:=\sum_{i=1}^{n}\mathds{1}_{\omega_{i}=0}\mathds{1}_{\omega_{i+1(\operatorname{mod}n)}=1}$
be the number of times zero is followed by a one. Define $Y:=V-np$ and
$X:=U-(1-2p)Y-npq$. Notice that $\operatorname{\mathds{E}}Y=0$,
$\sigma_{Y}^{2}=npq$ and $Y$ takes values in $\zeta+\mathds{Z}$ for
$\zeta:=\\{-np\\}$.

######  Lemma 4.7.

For random variables $X$ and $Y$ as above and $\alpha=\frac{2p-1}{2pq}$ define

$\displaystyle
W^{0}:=X+\frac{2\alpha}{n}XY+\frac{1}{n}\left(Y^{2}-\operatorname{\mathds{E}}Y^{2}\right)+\frac{2\alpha}{n^{2}}(Y^{3}-\operatorname{\mathds{E}}Y^{3})\quad\textrm{
and }\quad W=\frac{W^{0}}{\sigma_{W^{0}}}.$ (4.4)

For $k\in\zeta+\mathds{Z}$ with $|k|\ll\sigma_{Y}$ we have

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k),Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

###### Proof.

One can check that $X$ and $Y$ are mean zero uncorrelated random variables
satisfying Assumptions I, II, IIIa and IV with $Q=pq$, $\lambda=\frac{1}{n}$
and $\psi=2$. In particular, we have

$\displaystyle M_{0,+}(X,Y)=pq-\frac{1}{n}pY,$ $\displaystyle
M_{0,-}(X,Y)=pq+\frac{1}{n}qY,$ $\displaystyle
M_{1,+}(X,Y)=-\frac{1}{n}\left(2pX-2pqY\right)$ and $\displaystyle
M_{1,-}(X,Y)=-\frac{1}{n}\left(2qX+2pqY\right).$

Moreover,

$\displaystyle M_{2,+}(X,Y)$ $\displaystyle=\frac{1}{n}\left(2\cdot
np^{2}q^{2}+4(1-2p)pX+4pq(1-3p)Y-2p\operatorname{\mathds{E}}(\overline{\\#001}\mid
X,Y)\right)$ $\displaystyle\text{and }M_{2,-}(X,Y)$
$\displaystyle=\frac{1}{n}\left(2\cdot
np^{2}q^{2}-4(1-2p)qX+4pq(2-3p)Y-2q\operatorname{\mathds{E}}(\overline{\\#011}\mid
X,Y)\right),$

where $\overline{\\#011}$ and $\overline{\\#001}$ are centered random
variables that count the number of times the respective (consecutive) sub-
sequence appears in the sequence. We apply the change of variable (2.4) with
$\lambda=\frac{1}{n}$, $\psi=2$, $\alpha=\frac{2p-1}{2pq}$, and $\theta=2$ to
define the random variable $W^{0}$ and its scaled version $W$ as in the
statement of the Lemma 4.7.

For $i\in\\{k-1,k\\}$ with $\left|k\right|\ll\sigma_{Y}$, by LLT we have

$\operatorname{\mathds{P}}(Y=i)\approx\sigma_{Y}^{-1}\approx
n^{-\nicefrac{{1}}{{2}}}$

By Proposition 2.6, $(W,Y)$ satisfies Assumptions I, II, III and IV, in
particular

$\displaystyle M_{1,\pm}\left(W,Y\right)$
$\displaystyle=-\frac{1}{n}\biggl{(}\frac{1}{2}\cdot
2W+\widetilde{R}_{1,\pm}\biggr{)},\quad\textrm{where}\quad\operatorname{\mathds{E}}\left(|\widetilde{R}_{1,\pm}|\
\biggl{|}\ Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

and

$\displaystyle M_{2,\pm}\left(W,Y\right)$
$\displaystyle=\frac{1}{n}\left(2+\widetilde{R}_{2,\pm}\right),\quad\textrm{where}\quad\operatorname{\mathds{E}}\left(|\widetilde{R}_{2,\pm}|\
\biggl{|}\ Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

The remaining error terms can be bounded by

$\left|\operatorname{\mathds{E}}\left(\left|\Delta W\right|^{3}\mid
Y\in\\{k-1,k\\}\right)\right|=\left|\operatorname{\mathds{E}}\left(|\Delta
W|\cdot\Delta W^{2}\mid Y\in\\{k-1,k\\}\right)\right|\lesssim\lambda
n^{-\nicefrac{{1}}{{2}}-\varepsilon}.$

and

$\displaystyle\operatorname{\mathds{E}}\left(\left|W\right|\cdot\left|R_{0,\pm}\right|\mid
Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon},\quad\textrm{ and
}\quad\operatorname{\mathds{E}}\left(\left|\Delta W\right|\mid
Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

Thus by Theorem 2.4 for any number $k\in\zeta+\mathds{Z}$ such that
$|k|\ll\sqrt{n}$ we conclude that

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k),Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}$

and complete the proof. $\blacksquare$

######  Remark 4.8 (Change of variable and the conditional mean in Lemmas 4.7
and 4.3).

We define $m=np+k$, so that $\\{V=m\\}=\\{Y=k\\}$. With the notations as
above, using Lemma 4.3 one gets the exact formula for the conditional mean
given by

$\displaystyle\operatorname{\mathds{E}}\left(X\mid Y=k\right)$
$\displaystyle=\frac{(np+k)(nq-k)}{n-1}-(1-2p)k-npq$
$\displaystyle=\frac{npq}{n-1}+(1-2p)\frac{k}{n-1}-\frac{k^{2}}{n-1}=\frac{npq}{n-1}\left(1-\frac{2\alpha
k}{n}-\frac{k^{2}}{npq}\right),$

where $\alpha=\frac{2p-1}{2pq}$ is the same as $\alpha$ in the change of
variable (4.4). In particular, we have

$\displaystyle\operatorname{\mathds{E}}\left(X+\frac{2\alpha}{n}XY\ \biggl{|}\
Y=k\right)$
$\displaystyle=\operatorname{\mathds{E}}\left(\left(1+\frac{2\alpha
k}{n}\right)X\ \biggl{|}\ Y=k\right)$
$\displaystyle=\frac{npq}{n-1}\left(1-\frac{4\alpha^{2}k^{2}}{n^{2}}-\frac{k^{2}}{npq}-\frac{2\alpha
k^{3}}{n^{2}pq}\right)$ $\displaystyle=-\frac{k^{2}-npq}{n-1}-\frac{2\alpha
k^{3}}{n(n-1)}.$

This matches the $Y^{2}$ and $Y^{3}$ terms in (4.4) upto a small error caused
by dividing by $n-1$ instead of $n$.

####  4.2.3 number of wedges given the number of edges in a random graph

Let $G_{n,p}$ be the Erdős-Rényi random graph on $n$ vertices. Consider
$E:=\sum_{x<y}\omega_{xy}$, the number of edges in $G_{n,p}$ and its centered
version $Y:=E-\operatorname{\mathds{E}}E$. Notice that $Y$ takes values in
$\zeta+\mathds{Z}$, where $\zeta:=\\{-Np\\}$, and $\sigma_{Y}^{2}=Npq$. Let

$U:=\sum_{x<y,z\neq x,y}\omega_{xy}\omega_{yz}$

be the number of wedges in $G_{n,p}$ and

$X:=\sum_{x<y,z\neq
x,y}(\omega_{xy}-p)(\omega_{yz}-p)=U-2(n-2)pY-(n-2)Np^{2}.$ (4.5)

It is also straight forward to check that $X$ and $Y$ are uncorrelated
centered random variables with

$\displaystyle\sigma_{X}^{2}=\frac{1}{2}n(n-1)(n-2)p^{2}q^{2}.$

######  Lemma 4.9.

Let random variables $X$ and $Y$ as above and $\alpha=\frac{2p-1}{2pq}$ define

$\displaystyle
W^{0}:=X+\frac{2\alpha}{N}XY+\frac{n-2}{N}\left(Y^{2}-\operatorname{\mathds{E}}Y^{2}\right)+2\frac{n-2}{N^{2}}\alpha(Y^{3}-\operatorname{\mathds{E}}Y^{3})\textrm{
and }W=\frac{W^{0}}{\sigma_{W^{0}}}.$ (4.6)

For $k\in\zeta+\mathds{Z}$ with $|k|\ll n$ we have

$\displaystyle d_{\mathcal{W}}\left((W\mid Y=k)\,,\,Z\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

In the following proof we omit most of the computations, even though they are
typical for such applications, we present them in Appendix B.

###### Proof.

We first compute the following terms

$\displaystyle M_{0,+}(X,Y)$ $\displaystyle=pq-\lambda pY\quad\textrm{ and
}\quad M_{0,-}(X,Y)=pq+\lambda qY.$

Next we compute

$\displaystyle M_{1,+}(X,Y)$
$\displaystyle=-\frac{1}{N}\left(2pX-2(n-2)pqY\right)$ $\displaystyle
M_{1,-}(X,Y)$ $\displaystyle=-\frac{1}{N}\left(2qX+2(n-2)pqY\right)$
$\displaystyle M_{2,\pm}(X,Y)$
$\displaystyle=\frac{1}{N}\left(2\cdot\sigma_{X}^{2}+R_{2,\pm}\right),$

where using computations form Section B one can see that
$\left\|R_{2,\pm}\right\|_{p}\lesssim n^{5/2}$. We apply the change of
variable (2.4) with $\lambda=\frac{1}{N},\alpha=\frac{2p-1}{2pq}$, and
$\theta=2(n-2)$ to define the random variable $W^{0}$ and its scaled version
$W$ as in the statement of the Lemma 4.9. For all $i\in\zeta+\mathds{Z}$ with
$\left|i\right|\ll n$, by LLT
$\operatorname{\mathds{P}}(Y=i)\approx\sigma_{Y}^{-1}\approx n^{-1}$. By
Proposition 2.6 we have that

$\displaystyle M_{1,\pm}(W,Y)$
$\displaystyle=-\frac{1}{N}\biggl{(}\frac{1}{2}\cdot
2W+\widetilde{R}_{1,\pm}\biggr{)}\qquad\text{and}\qquad
M_{2,\pm}\left(W,Y\right)$
$\displaystyle=\frac{1}{N}\biggl{(}2+\widetilde{R}_{2,\pm}\biggr{)},$

where

$\displaystyle\operatorname{\mathds{E}}\left(|\widetilde{R}_{1,\pm}|\
\bigl{|}\ Y=i\right)\lesssim
n^{-\frac{3}{2}+\varepsilon}\qquad\text{and}\qquad\operatorname{\mathds{E}}\left(|\widetilde{R}_{2,\pm}|\
\bigl{|}\ Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

Thus $(W,Y)$ satisfies Assumptions I, II, III and IV with $Q=pq$,
$\lambda=\frac{1}{N}$ and $\psi=2$. The remaining terms can be bounded as
follows:

$\frac{1}{\lambda}\operatorname{\mathds{E}}\left(\left|\Delta W\right|^{3}\mid
Y\in\\{k-1,k\\}\right)\lesssim n^{-\frac{1}{2}+\varepsilon},$
$\displaystyle\operatorname{\mathds{E}}\left(\left|W\right|\left|R_{0,\pm}\right|\mid
Y=i\right)\lesssim n^{-2+\varepsilon}\quad\textrm{ and
}\quad\operatorname{\mathds{E}}\left(\left|\Delta W\right|\mid
Y=i\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

Thus, Theorem 2.4 for any $k\in\zeta+\mathds{Z}$ such that $|k|\ll n$ we
conclude that

$\displaystyle d_{\mathcal{W}}\bigl{(}(W\mid Y=k)\,,\,Z\bigr{)}\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon}$

for $\varepsilon>0$ small. $\blacksquare$

######  Remark 4.10 (Change of variable and the conditional mean in Lemma 4.9
and 4.4).

With the notations as above and $m=Np+k$, we have $\\{E=m\\}=\\{Y=k\\}$. Now,
using Lemma 4.4, one gets the exact conditional mean

$\displaystyle\operatorname{\mathds{E}}\left(X\mid Y=k\right)$
$\displaystyle=\frac{2m(m-1)}{n+1}-2(n-2)pk-(n-2)Np^{2}$
$\displaystyle=-2(1-2p)\frac{k}{n+1}+\frac{2k^{2}}{n+1}-\frac{2Npq}{n+1}$
$\displaystyle=-\frac{2Npq}{n+1}\left(1-\frac{2\alpha
k}{N}-\frac{k^{2}}{Npq}\right),$

where $\alpha=\frac{2p-1}{2pq}$ is the same as $\alpha$ in the change of
variable (4.6). In particular, we have

$\displaystyle\operatorname{\mathds{E}}$
$\displaystyle\left(X+\frac{2\alpha}{N}XY\ \biggl{|}\ Y=k\right)$
$\displaystyle=\operatorname{\mathds{E}}\left(\left(1+\frac{2\alpha
k}{N}\right)X\ \biggl{|}\ Y=k\right)$
$\displaystyle=-\frac{2Npq}{n+1}\left(1-\frac{4\alpha^{2}k^{2}}{N^{2}}-\frac{k^{2}}{Npq}\left(1+\frac{2\alpha}{N}k\right)\right)$
$\displaystyle=2\frac{k^{2}-Npq}{n+1}+\frac{4\alpha
k^{3}}{N\left(n+1\right)}-\frac{8pq\alpha^{2}k^{2}}{N(n+1)}$
$\displaystyle=\frac{N}{N-1}\left(\frac{n-2}{N}\cdot(k^{2}-Npq)+2\cdot\frac{(n-2)}{N^{2}}\cdot\alpha
k^{3}\right)-\frac{8pq\alpha^{2}k^{2}}{N(n+1)}.$

This matches $Y^{2}$ and $Y^{3}$ terms in (4.6) with a $1+O(1/N)$ factor.

###  4.3 Applications of main result in higher dimension

In this section, we present several applications of Theorem 3.1, the
multivariate result.

####  4.3.1 Multivariate version of darts model given number of misses

Similar to the model from Section 4.1.2, let $\\{S_{i}\\}$ be a sequence of
i.i.d. random variables with mean zero and unit variance uniformly bounded by
$s>0$. Let $\\{V_{i}\\}$ be a sequence of i.i.d.
Bernoulli$(\nicefrac{{1}}{{2}})$ random variables. While the following lemma
could be derived using classical methods analogous to the methods described in
Section 4.1, we use it as a toy example to illustrate an application of
Theorem 3.1.

######  Lemma 4.11.

Let $\bm{X}:=\left(\sum_{i}S_{i}\,\overline{V}_{i},\sum_{i}S_{i}\right)^{T}$
and $Y:=\sum_{i}\overline{V}_{i}$. Define

$\displaystyle\bm{W}^{0}=\bm{X}-\frac{1}{n}\begin{pmatrix}0&\nicefrac{{1}}{{2}}\\\
2&0\end{pmatrix}\bm{X}Y\quad\text{and
\quad}\bm{W}:=\left(W^{0}_{1}/\sigma_{W^{0}_{1}},W^{0}_{2}/\sigma_{W^{0}_{2}}\right)^{T}$

For any $k\in\\{\frac{n}{2}\\}+\mathds{Z}$ with $|k|\ll\sqrt{n}$ we have that

$\displaystyle d_{\mathcal{W}}\left((\bm{W}\mid Y=k),\bm{Z}\right)$
$\displaystyle\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

###### Proof.

Consider the following Markov Chain to generate an exchangeable pair. Let $I$
be chosen uniformly at random from $\\{1,2,\ldots,n\\}$. Replace both $S_{I}$
and $V_{I}$ with independent copies $S_{I}^{\prime}$ and $V^{\prime}_{I}$,
respectively. It is easy to check that

$\displaystyle
M_{1,\pm}(\bm{X},Y)=-\frac{1}{n}\begin{pmatrix}\frac{1}{4}&\mp\frac{1}{8}\\\
\mp\frac{1}{2}&\frac{1}{4}\end{pmatrix}\bm{X}$

and

$\displaystyle\operatorname{\mathds{E}}\left(\Delta\bm{X}\Delta\bm{X}^{T}\mathds{1}_{\Delta\\!Y=\pm
1}\mid\bm{X},Y\right)=\frac{1}{n}\left(\begin{pmatrix}\frac{1}{2}&0\\\
0&\frac{1}{2}\end{pmatrix}\begin{pmatrix}\frac{n}{4}&0\\\
0&n\end{pmatrix}+\Gamma_{2,\pm}\right).$

For $k\in\\{\frac{n}{2}\\}+\mathds{Z}$ with $|k|\ll\sqrt{n}$ we have
$\operatorname{\mathds{E}}\left(\left\|\Gamma_{2,\pm}\right\|_{\operatorname{H.S.}}\mid
Y=k\right)\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}$.

Define

$\displaystyle\Psi_{\pm}:=\begin{pmatrix}\frac{1}{4}&\mp\frac{1}{8}\\\
\mp\frac{1}{2}&\frac{1}{4}\end{pmatrix},$

and notice that

$\displaystyle\Psi=\Psi_{+}+\Psi_{-}=\begin{pmatrix}\frac{1}{2}&0\\\
0&\frac{1}{2}\end{pmatrix}.$

Since $\sum_{i}S_{i}\,\overline{V}_{i}$ and $\sum_{i}S_{i}$ are uncorrelated,
it follows $\bm{X}$ satisfies Assumptions I, II, IIIa (with $\bm{b}_{\pm}=0$),
and IV with variance-covariance matrix $\begin{pmatrix}n/4&0\\\
0&n\end{pmatrix}.$ Using the change of variable (3.1) and Proposition 3.3 we
get that for

$\displaystyle\bm{W}^{0}:=\bm{X}-\frac{1}{n}\begin{pmatrix}0&\frac{1}{2}\\\
2&0\end{pmatrix}\bm{X}Y\quad\text{and
\quad}\bm{W}:=\left(W^{0}_{1}/\sigma_{W^{0}_{1}},W^{0}_{2}/\sigma_{W^{0}_{2}}\right)^{T}$

$(\bm{W},Y)$ satisfies Assumptions I, II, III, and IV. Furthermore, notice
that $|\Delta W_{i}|\leqslant 4s/\sqrt{n}$ thus for all $|k|\ll\sqrt{n}$

$\displaystyle\frac{1}{\lambda}\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|^{4}\mid
Y=k\right)$ $\displaystyle\lesssim\frac{s^{2}}{\lambda
n}\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|^{2}\mid
Y=k\right)\lesssim n^{-1+2\varepsilon}.$

Finally, using Theorem 3.1 with
$\operatorname{\mathds{E}}\left|\bm{W}\right|^{4}<\infty$ we have that for any
number $k\in\\{\frac{n}{2}\\}+\mathds{Z}$ with $|k|\ll\sqrt{n}$ the following
bound holds

$\displaystyle d_{\mathcal{W}}\left((\bm{W}\mid Y=k),\bm{Z}\right)$
$\displaystyle\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}$

for some $\varepsilon>0$. $\blacksquare$

####  4.3.2 Number of $($triangles, wedges$)$ given the number of edges in a
random graph

As before, let $G_{n,p}$ be the Erdős–Rényi random graph and denote
$\omega_{xy}:=\mathds{1}_{x\sim y}$.

Define

$E:=\sum_{x<y}\omega_{xy},\quad U:=\sum_{x<y,z\neq
x,y}\omega_{xy}\omega_{yz},\quad\text{and}\quad
T:=\sum_{x<y<z}\omega_{xy}\omega_{yz}\omega_{zx},$

the number of edges, wedges, and triangles, respectively, in $G_{n,p}$. It is
straight forward to check that, letting $\lambda=\frac{1}{N}$, we get

$\displaystyle M_{1,+}(U,E)=-\lambda\left(2pU-2p(n-2)E\right)$ $\displaystyle
M_{1,-}(U,E)=-\lambda 2qU$ $\displaystyle M_{1,+}(T,E)=-\lambda(3pT-pU)$
$\displaystyle M_{1,-}(T,E)=-\lambda 3qT.$

Define $Y:=E-\operatorname{\mathds{E}}E$ and notice that
$\operatorname{\mathds{E}}Y=0$, $\sigma_{Y}^{2}=Npq$, and it takes values in
$\zeta+\mathds{Z}$, where $\zeta:=\\{-Np\\}$. Moreover,

$\displaystyle M_{0,+}(U,T,Y)=pq-\lambda pY\quad\textrm{ and }\quad
M_{0,-}(U,T,Y)=pq+\lambda qY.$

Considering the following representation of our random variables allows us to
pass to uncorrelated random variables in a natural way,

$\displaystyle\widetilde{T}$
$\displaystyle=\sum_{i<j<k}(\omega_{ij}-p)(\omega_{jk}-p)(\omega_{ki}-p)=T-p(U-\operatorname{\mathds{E}}U)+p^{2}(n-2)Y-\binom{n}{3}p^{3}$
(4.7) $\displaystyle\widetilde{U}$ $\displaystyle=\sum_{j<k,i\neq
j,k}(\omega_{ij}-p)(\omega_{ik}-p)=U-2p(n-2)Y+\frac{n(n-1)(n-2)}{2}p^{2}.$
(4.8)

Notice that $\widetilde{U}=X$ as in (4.5) from Section 4.2.3.

######  Lemma 4.12.

Let $\widetilde{T}$, $\widetilde{U}$, and $Y$ be as above. Define
$\bm{X}=\left(\widetilde{T},\widetilde{U}\right)^{T}$ and

$\displaystyle\bm{W}^{0}:=\bm{X}+\lambda\mathrm{A}\bm{X}Y+\frac{\lambda\bm{\theta}}{2}\left(Y^{2}-\operatorname{\mathds{E}}Y^{2}\right)+\frac{\lambda^{2}(\mathrm{A}+\alpha)\bm{\theta}}{3}(Y^{3}-\operatorname{\mathds{E}}Y^{3}),$
(4.9)

where

$\mathrm{A}=\frac{1}{2Q}\begin{pmatrix}3(2p-1)&0\\\
-2pq&(2p-1)\end{pmatrix},\quad\alpha=\frac{2p-1}{2pq},\quad\text{and}\quad\bm{\theta}=-\begin{pmatrix}0\\\
-2(n-2)\end{pmatrix}.$

Define the random vector

$\bm{W}:=\begin{pmatrix}\widehat{T}\\\
\widehat{U}\end{pmatrix}:=\begin{pmatrix}W^{0}_{1}/\sigma_{W^{0}_{1}}\\\
W^{0}_{2}/\sigma_{W^{0}_{2}}\end{pmatrix}.$ (4.10)

For any $k\in\zeta+\mathds{Z}$ with $|k|\ll n$ we have that

$\displaystyle d_{\mathcal{W}}\left((\bm{W}\mid Y=k),\bm{Z}\right)$
$\displaystyle\lesssim{n}^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

###### Proof.

Computing $M_{1,\pm}$ terms yields that

$\displaystyle M_{1,+}\left(\bm{X},Y\right)$
$\displaystyle=-\frac{1}{N}\left(\begin{pmatrix}3p&-2pq\\\
0&2p\end{pmatrix}\bm{X}-\begin{pmatrix}0\\\ 2(n-2)pq\end{pmatrix}Y\right)$

and

$\displaystyle M_{1,+}\left(\bm{X},Y\right)$
$\displaystyle=-\frac{1}{N}\left(\begin{pmatrix}3q&2pq\\\
0&2q\end{pmatrix}\bm{X}+\begin{pmatrix}0\\\ 2(n-2)pq\end{pmatrix}Y\right).$

Computing the second order terms yields

$\displaystyle\operatorname{\mathds{E}}\left(\begin{pmatrix}\Delta\widetilde{T}^{2}&\Delta\widetilde{T}\Delta\widetilde{V}\\\
\Delta\widetilde{T}\Delta\widetilde{V}&\Delta\widetilde{V}^{2}\end{pmatrix}\mathds{1}_{\Delta\\!Y=\pm
1}\ \biggl{|}\
\widetilde{T},\widetilde{V},Y\right)=\frac{1}{N}\left(\begin{pmatrix}3&0\\\
0&2\end{pmatrix}\begin{pmatrix}\sigma^{2}_{\widetilde{T}}&0\\\
0&\sigma^{2}_{\widetilde{V}}\end{pmatrix}+\Gamma_{2,\pm}\right),$

where $\left\|\Gamma_{2,\pm}\right\|_{\operatorname{H.S.}}\lesssim n^{5/2}$.
Define $\lambda=\frac{1}{N}$, $\Psi=\begin{pmatrix}3&0\\\ 0&2\end{pmatrix}$,
and $\bm{b}_{\pm}=\begin{pmatrix}0\\\ \mp 2(n-2)pq\end{pmatrix}$. Notice that
the random vector $(\bm{X},Y)=\left(\begin{pmatrix}\widetilde{T}\\\
\widetilde{V}\end{pmatrix},Y\right)$ satisfies Assumptions I, II, IIIa, and
IV. Using the change of variable (3.1) define the random vector $\bm{W}$ as in
the statement of the Lemma 4.12.

By Proposition 3.3 we get that the random vector $(\bm{W},Y)$ satisfies
Assumptions I, II, III, and IV; and for $k\in\zeta+\mathds{Z}$ with
$\left|k\right|\ll n$, we can bound the error terms $\widehat{A}_{k}$ and
$\widehat{B}_{k}$ using the following inequalities for $\hat{k}\in\\{k-1,k\\}$

$\displaystyle\operatorname{\mathds{E}}\left(\left|\widetilde{\bm{R}}_{1,\pm}\right|\mid
Y=\hat{k}\right)\lesssim n^{-3/2+\varepsilon}\textrm{ and
}\operatorname{\mathds{E}}\left(\left\|\widetilde{\Gamma}_{2,\pm}\right\|_{\operatorname{H.S.}}\mid
Y=\hat{k}\right)\lesssim n^{-1/2+\varepsilon},$

similarly the terms $\widehat{C}_{k}$, $\widehat{D}_{k}$, $\widehat{E}_{k}$,
and $\widehat{F}_{k}$ can be bounded by using the following inequalities for
$\hat{k}\in\\{k-1,k\\}$

$\displaystyle\operatorname{\mathds{E}}(\left|\bm{W}\right|\left(\left|R_{0,+}\right|+\left|R_{0,-}\right|\right)\mid{Y=\hat{k}})\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon},$
$\displaystyle\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|\mid{Y=\hat{k}}\right)\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon},$ and
$\displaystyle\sqrt{\frac{1}{\lambda}\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|^{4}\mid
Y=\hat{k}\right)}\lesssim n^{-\nicefrac{{1}}{{2}}+\varepsilon}.$

Thus by Theorem 3.1 with
$\operatorname{\mathds{E}}\left|\bm{W}\right|^{4}<\infty$ for
$k\in\zeta+\mathds{Z}$ with $\left|k\right|\ll n$ we have that

$\displaystyle d_{\mathcal{W}}\left((\bm{W}\mid
Y=k),\bm{Z}\right)\lesssim{n}^{-\nicefrac{{1}}{{2}}+\varepsilon}$

for some $\varepsilon>0$. $\blacksquare$

###  4.4 General subgraph count given the number of edges

Stein’s method for normal approximation and Stein–Chen’s method for Poisson
convergence were contextualized to random graphs by Barbour in [2]. The
techniques for proving Poisson convergence described in [2] were used shortly
after in many results, such as [33] where many distributional convergence
theorems were established in different regimes of Erdős–Rényi random graph.
Due to technical difficulties, this method for normal approximation in the
context of random graphs was limited to particular examples until the
following general theorem was shown in [4]. The original result in [4] is
stated in terms of the Fortet–Mourier distance. However, the proof can be
adopted to derive analogous statement in Wasserstein distance using standard
machinery.

######  Theorem 4.13 ([4, Theorem 2]).

Let $\mathcal{H}$ be a graph on $v$ vertices with $m$ edges, $H$ be the number
of its copies in $G_{n,p}$, then

$\displaystyle
d_{\mathcal{W}}\left((H-\operatorname{\mathds{E}}H)/\sigma_{H},Z\right)=k_{\mathcal{H}}\cdot\begin{cases}r(n,p)^{-\nicefrac{{1}}{{2}}}&p\geqslant\nicefrac{{1}}{{2}}\\\
n^{-1}(1-p)^{-\nicefrac{{1}}{{2}}}&p<\nicefrac{{1}}{{2}},\end{cases}$

where $k_{\mathcal{H}}$ is a constant depending on $\mathcal{H}$,

$r(n,p):=\min_{\mathcal{H}^{\prime}\subseteq\mathcal{H},e(\mathcal{H}^{\prime})>0}\left\\{n^{v(\mathcal{H}^{\prime})}p^{e(\mathcal{H}^{\prime})}\right\\},$

and $v(\mathcal{H}^{\prime})$, $e(\mathcal{H}^{\prime})$ denote the number of
vertices and edges in a graph $\mathcal{H}^{\prime}$, respectively.

######  Corollary 4.14 ([4, Remark 1 on p.133]).

For fixed $p\in(0,1)$ we have

$d_{\mathcal{W}}\left((H-\operatorname{\mathds{E}}H)/\sigma_{H},Z\right)\lesssim
n^{-1}.$

It is important to notice that this result is based on the dependency graph
approach. In this section, we will derive an analogous CCLT as a consequence
of Theorem 3.1 and Lemma 4.12.

From the applications in Section 4.3.2 and the decomposition in (4.7) and
(4.8), it is natural to expect that in order to derive CCLT for a graph
$\mathcal{H}$ given the number of edges, one would have to do it for a vector
containing all possible sub-graphs of $\mathcal{H}$. Surprisingly it is not
the case, as illustrated by the following lemma.

######  Lemma 4.15.

Let $\mathcal{H}$ be a graph on $v$ vertices with $m$ edges, $H$ be the number
of its copies in $G_{n,p}$ and $E$ be the number of edges, then

$\displaystyle\operatorname{Var}{(H)}\approx n^{2v-2}\quad\text{ and
}\quad\operatorname{Var}{\left(H-\sigma_{H,E}/{\sigma_{E}^{2}}\cdot
E\right)}\approx n^{2v-3}.$

###### Proof.

Let $\bm{s}$ denote a subset of edges in the complete graph $\mathcal{K}_{n}$
on $n$ vertices that forms an isomorphic copy of $\mathcal{H}$ and
$\mathcal{S}=\mathcal{S}_{n}(H)$ denote the collection of all such $\bm{s}$’s.
Define $|\mathcal{S}|$ to be the size of the collection $\mathcal{S}$. This
allows us to rewrite the sub-graph count as

$\displaystyle
H=\sum_{\bm{s}\in\mathcal{S}}\prod_{e\in\bm{s}}\omega_{e}=\sum_{\bm{s}\in\mathcal{S}}\omega_{\bm{s}},$

where $\omega_{\bm{s}}:=\prod_{e\in\bm{s}}\omega_{e}$. It is easy to check
that

$\displaystyle\sigma_{H,E}:=\operatorname{Cov}(H,E)=mp^{m}q\cdot|\mathcal{S}|.$

In particular we can write

$\displaystyle\widehat{H}$
$\displaystyle:=H-\frac{\sigma_{H,E}}{\sigma_{E}^{2}}E=\sum_{\bm{s}\in\mathcal{S}}\omega_{\bm{s}}-\frac{m}{N}p^{m-1}|\mathcal{S}|\cdot
E.$ (4.11)

We rewrite $\omega_{\bm{s}}$ as

$\displaystyle\omega_{\bm{s}}=\prod_{e\in\bm{s}}\omega_{e}=\prod_{e\in\mathcal{S}}(\overline{\omega}_{e}+p)=\sum_{\ell=0}^{m}p^{m-\ell}\sum_{\bm{s}^{\prime}\subseteq\bm{s},|\bm{s}^{\prime}|=\ell}\widetilde{\omega}_{\bm{s}^{\prime}}$

where
$\widetilde{\omega}_{\bm{s}^{\prime}}:=\prod_{e\in\bm{s}^{\prime}}\overline{\omega}_{e}$.
Given an edge-set $\bm{s}^{\prime}$, we define

$\displaystyle\mathcal{S}_{\bm{s}^{\prime}}:=\\{\bm{s}\in\mathcal{S}\mid\bm{s}^{\prime}\subseteq\bm{s}\\}.$

Given an edge $e$, size of the set $\\{\bm{s}\in\mathcal{S}\mid e\in\bm{s}\\}$
is independent of $e$ and thus by symmetry the common size is given by
$\frac{m}{N}|\mathcal{S}|$. In particular,
$\sum_{\bm{s}\in\mathcal{S}}\sum_{e\in\bm{s}}\overline{\omega}_{e}=\frac{m}{N}|\mathcal{S}|\cdot\overline{E}$
and from (4.11) we get

$\displaystyle\widehat{H}-\operatorname{\mathds{E}}\widehat{H}$
$\displaystyle=\sum_{\ell=2}^{m}p^{m-\ell}\sum_{\bm{s}^{\prime}:|\bm{s}^{\prime}|=\ell}\widetilde{\omega}_{\bm{s}^{\prime}}\cdot|\mathcal{S}_{\bm{s}^{\prime}}|.$
(4.12)

It is easy to see that $\widetilde{\omega}_{\bm{s}}$ and
$\widetilde{\omega}_{\bm{s}^{\prime}}$ are uncorrelated whenever
$\bm{s}\neq\bm{s}^{\prime}$. Let $v^{\prime}$ be the number of vertices of a
graph whose edges form $\bm{s}^{\prime}$. Recall that $v=|V(\mathcal{H})|$.
Thus it remains to estimate the following quantity for $\ell\geqslant 2$,

$\displaystyle\operatorname{Var}\left(\sum_{\bm{s}^{\prime}:|\bm{s}^{\prime}|=\ell}\widetilde{\omega}_{\bm{s}^{\prime}}\cdot|\mathcal{S}_{\bm{s}^{\prime}}|\right)$
$\displaystyle=\sum_{|\bm{s}^{\prime}|=\ell}|\mathcal{S}_{\bm{s}^{\prime}}|^{2}\cdot(pq)^{\ell}$
$\displaystyle\approx n^{2(v-v^{\prime})}n^{v^{\prime}}\approx n^{2v-3},$

where in the second equality we used the fact that
$|\mathcal{S}_{\bm{s}^{\prime}}|\approx n^{v-v^{\prime}}$ for
$\bm{s}^{\prime}\subseteq\bm{s}$,
$|\\{\bm{s}^{\prime}:|\bm{s}^{\prime}|=\ell\\}|\approx n^{v^{\prime}}$; and in
the last equality we used the fact that $\ell\geqslant 2$ implies
$v^{\prime}\geqslant 3$. $\blacksquare$

######  Definition 4.16 (Extension function).

Let $\mathcal{K}_{n}$ be the complete graph on $n$ vertices, and
$\mathcal{H}^{\prime}$ be a sub-graph of $\mathcal{K}_{n}$. For any fixed
graph $\mathcal{H}$, we define
$\mathrm{ext}_{n}(\mathcal{H}^{\prime},\mathcal{H})$ to be the number of ways
to extend the given graph $\mathcal{H}^{\prime}$ to an isomorphic copy of
$\mathcal{H}$ inside of $\mathcal{K}_{n}$.

For example if $\mathcal{T}$ is the triangle and $\mathcal{K}_{4}$ is the
complete graph on four vertices then
$\mathrm{ext}_{n}(\mathcal{T},\mathcal{K}_{4})=n-3$, while if $\mathcal{V}$ is
the wedge graph and $\mathcal{P}_{4}$ is the path with four vertices then
$\mathrm{ext}_{n}(\mathcal{V},\mathcal{P}_{4})=2(n-3)$. As a consequence of
Lemma 4.15 and a bit more analysis, we have the following lemma.

Let $\widetilde{T}$ and $\widetilde{U}$ are centered edge counts for triangles
and wedges as in (4.7) and (4.8) respectively.

######  Lemma 4.17.

Let $\mathcal{H}$ be a graph on $v$ vertices with $m$ edges, let $\mathcal{T}$
be the triangle and $\mathcal{U}$ be the wedge graphs. One can represent the
random variable $\widehat{H}$, defined in (4.11), in the following way

$\displaystyle\widehat{H}-\operatorname{\mathds{E}}\widehat{H}=\mathrm{ext}_{n}(\mathcal{T},\mathcal{H})\cdot\widetilde{T}+\mathrm{ext}_{n}(\mathcal{U},\mathcal{H})\cdot\widetilde{U}+R_{H},$
(4.13)

Moreover,
$\operatorname{Var}\bigl{(}\widetilde{T}\bigr{)}\approx\operatorname{Var}\bigl{(}\widetilde{U}\bigr{)}\approx
n^{3}$,
$\mathrm{ext}_{n}(\mathcal{T},\mathcal{H})\approx\mathrm{ext}_{n}(\mathcal{U},\mathcal{H})\approx
n^{2v-6}$ and

$\displaystyle\operatorname{\mathds{E}}R_{H}=0,\quad\operatorname{\mathds{E}}\left|R_{H}\right|^{2\theta}=O\bigl{(}\sigma_{\widehat{H}}^{2\theta}\cdot
n^{-\theta}\bigr{)}\quad\text{ for }\quad\theta\geqslant 1.$

###### Proof.

Everything besides the statement about
$\operatorname{\mathds{E}}|R_{H}|^{\theta}$ follows directly from the
representation of $\widehat{H}-\operatorname{\mathds{E}}\widehat{H}$ in
(4.12), the fact that the only connected graphs on three vertices are the
triangle and the wedge graphs, and the computations of
$|\mathcal{S}_{\bm{s}^{\prime}}|$. Notice that if $\bm{s}^{\prime}$ induces
the graph $\mathcal{H}^{\prime}$ then
$|\mathcal{S}_{\bm{s}^{\prime}}|=\mathrm{ext}_{n}(\mathcal{H}^{\prime},\mathcal{H})$.

Thus it remains to compute $\operatorname{\mathds{E}}|R_{H}|^{2\theta}$ for an
integer $\theta\geqslant 1$. Let $\bm{s}^{\prime}$ denote a subset of edges in
the complete graph $\mathcal{K}_{n}$ on $n$ vertices that forms an isomorphic
copy of $\mathcal{H}^{\prime}$, such that
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ and
$|V(\bm{s}^{\prime})|:=|V(\mathcal{H}^{\prime})|\geqslant 4$. Then

$\displaystyle\operatorname{\mathds{E}}\left|R_{H}\right|^{2\theta}$
$\displaystyle=\sum_{\bm{s}_{1},\bm{s}_{2},\ldots,\bm{s}_{2\theta}}\prod_{i=1}^{2\theta}\widetilde{\omega}_{\bm{s}_{i}}|\mathcal{S}_{\bm{s}_{i}}|\approx
n^{2\theta
v-\sum_{i=1}^{2\theta}V(\bm{s}_{i})+|\cup_{i=1}^{2\theta}V(\bm{s}_{i})|}.$

Notice that
$\operatorname{\mathds{E}}\omega_{\bm{s}_{1}}\omega_{\bm{s}_{1}}\cdots\omega_{\bm{s}_{2\theta}}\neq
0$ if there is and edge $e\in\cup_{i=1}^{2\theta}\bm{s}_{i}$ that appears in
this product only once. So in contributing terms each vertex appears at least
twice and thus
$|\cup_{i=1}^{2\theta}V(\bm{s}_{i})|\leqslant\frac{1}{2}\sum_{i=1}^{2\theta}V(\bm{s}_{i}).$
Now since $V(\bm{s}_{i})\geqslant 4$ and $\sigma_{\widehat{H}}\approx
n^{2v-3}$ we conclude that

$\displaystyle\operatorname{\mathds{E}}\left|R_{H}\right|^{2\theta}\lesssim
n^{2\theta v-4\theta}\approx\sigma_{\widehat{H}}^{2\theta}n^{-\theta}.$

This completes the proof. $\blacksquare$

The decomposition from Lemma 4.17 yields that the terms involving
$\widetilde{U}$ and $\widetilde{T}$ are both of order $n^{2v-3}$. After
dividing both sides of (4.13) by $\sigma_{\widehat{H}}$ by multivariate CLT
[5, Theorem 2.1] right hand side is asymptotically Gaussian with the same rate
of convergence as the left hand side. However to derive CCLT simply stating
that $R_{H}$ is of the smaller order is not enough as it could be significant
after multiplication by $p_{k}^{-1}=\operatorname{\mathds{P}}(Y=k)^{-1}\approx
n$. Thus for an appropriate function $h$ we need to bound the following
expression

$\displaystyle\operatorname{\mathds{E}}\left(\left|h\bigl{(}\widehat{H}-R_{H}\bigr{)}-h\bigl{(}\widehat{H}\bigr{)}\right|\big{|}Y=k\right)$
$\displaystyle\leqslant\left|h\right|_{1}\cdot
p_{k}^{-1}\operatorname{\mathds{E}}(|R_{H}|\cdot\mathds{1}_{Y=k})$
$\displaystyle\lesssim
p_{k}^{-1}\cdot(\operatorname{\mathds{E}}|R_{H}|^{2\theta})^{\frac{1}{2\theta}}\cdot
p_{k}^{1-\frac{1}{2\theta}}$ $\displaystyle\lesssim\sigma_{\widehat{H}}\cdot
n^{-(\theta-1)/(2\theta)},$ (4.14)

for all $\theta>1$. Hence by taking $\theta$ to infinity and scaling by
$\sigma_{\widehat{H}}$ the right hand side goes to $0$ at the rate of
$n^{-\nicefrac{{1}}{{2}}+\varepsilon}$. Let

$\displaystyle\rho_{1}:=\lim_{n\to\infty}\frac{\mathrm{ext}_{n}(\mathcal{T},\mathcal{H})\cdot\sigma_{\widetilde{T}}}{\sigma_{\widehat{H}}}\quad\text{
and
}\quad\rho_{2}:=\lim_{n\to\infty}\frac{\mathrm{ext}_{n}(\mathcal{V},\mathcal{H})\cdot\sigma_{\widetilde{U}}}{\sigma_{\widehat{H}}}.$

Recall that in Lemma 4.12 we applied a change of variables to
$(\widetilde{T},\widetilde{U})^{T}$ as in (4.9). After appropriate scaling we
defined a random vector $(\widehat{T},\widehat{U})^{T}$ in (4.10) and derived
CCLT given the number of edges for this random vector. Lemma 4.12 together
with Lemma 4.17 gives the following general result.

######  Theorem 4.18.

Let $\mathcal{H}$ be a finite graph, $H$ be the number of times $\mathcal{H}$
appears in $G_{n,p}$, $\widehat{H}:=H-\frac{\sigma_{H,E}}{\sigma_{E}^{2}}E$,
$\widetilde{T}$ and $\widetilde{U}$, and $Y$ be the centered edge counts of
triangles, wedges, and edges, respectively. Let $(\widehat{T},\widehat{U})$ be
the scaled random vector defined in (4.10). For any $k\in\\{-Np\\}+\mathds{Z}$
with $|k|\ll n$ we have

$\displaystyle
d_{\mathcal{W}}\biggl{(}\left(\left((\widehat{H}-\operatorname{\mathds{E}}\widehat{H})/\sigma_{\widehat{H}},{\widehat{T}},{\widehat{U}}\right)\,\big{|}\,Y=k\right),\left(\rho_{1}Z_{1}+\rho_{2}Z_{2},Z_{1},Z_{2}\right)\biggr{)}\lesssim
n^{-\nicefrac{{1}}{{2}}+\varepsilon},$

where $Z_{1}$ and $Z_{2}$ are independent standard normal random variables and
$\varepsilon>0$.

There are several reasons why the upper bound of the rate of convergence in
this theorem is slower than that in Corollary 4.14. First, it might be due to
the limitation of exchangeable pairs in the context of random graphs. As we
saw before in Lemma 4.4, the upper bound on the rate of convergence can be
slower than $n^{-1}$ even with classical techniques. Another possibility is
that it is caused by our technique. At the end of the proof of Theorem 2.4,
one can see when we invoke the Lipschitz property; our upper bound cannot be
better than $|\Delta W|/\sigma_{W}$, which in this case is of order
$n^{-\nicefrac{{1}}{{2}}}$. This naturally leads to Question 4 in Section 7.

##  5 Proofs of Main Results

As we mentioned above, one of the proofs of Theorem 2.4 and Theorem 3.1 have
two main components. One is to derive a CCLT for $(W\mid Y\in\\{k-1,k\\})$
which we do in Lemma 2.3 and Lemma 5.2 for the univariate case and
multivariate case respectively. The other step is to quantitatively bound the
difference between $(W\mid Y=k)$ and $(W\mid Y=k-1)$, which we do in the next
lemma.

######  Lemma 5.1.

For any $d\geqslant 1$. Suppose $\bm{W}$ is a $d$-dimensional random vector
such that $(\bm{W},Y)$ satisfy Assumptions I and II, then for any
$1$-Lipschitz function $h:\mathds{R}^{d}\to\mathds{R}$ and for any $k$ such
that $\operatorname{\mathds{P}}(Y=k)>0$ and
$\operatorname{\mathds{P}}(Y=k-1)>0$ we have that

$\displaystyle\left|\operatorname{\mathds{E}}(h(\bm{W})-h(\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z}))\left(\mathds{1}_{Y=k}-\mathds{1}_{Y=k-1}\right)\right|$
$\displaystyle\qquad\leqslant\frac{1}{Q}\operatorname{\mathds{E}}\left(|\Delta\bm{W}|\cdot\mathds{1}_{Y\in\\{k-1,k\\}}\right)+\frac{1}{Q}\operatorname{\mathds{E}}\left((\left|\bm{W}\right|+\sqrt{\operatorname{Tr}(\Sigma)})(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\mathds{1}_{Y\in\\{k-1,k\\}}\right),$

where $\bm{Z}$ is a $d$-dimensional standard normal random vector that is
independent of everything else.

###### Proof.

Without loss of generality we may assume that
$\operatorname{\mathds{E}}h(\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z})=0$. Assumption
II implies that

$Q=\operatorname{\mathds{E}}(\mathds{1}_{\Delta\\!Y=-1}\mid\bm{W},Y)-R_{0,-}.$

Hence,

$\displaystyle\operatorname{\mathds{E}}\left(h(\bm{W})\mathds{1}_{Y=k}\right)$
$\displaystyle=\frac{1}{Q}\operatorname{\mathds{E}}\left(h(\bm{W})\mathds{1}_{Y=k}\mathds{1}_{\Delta\\!Y=-1}\right)-\frac{1}{Q}\operatorname{\mathds{E}}\left(h(\bm{W})\mathds{1}_{Y=k}R_{0,-}\right)$
$\displaystyle=\frac{1}{Q}\operatorname{\mathds{E}}\left(h(\bm{W})\mathds{1}_{Y=k}\mathds{1}_{Y^{\prime}=k-1}\right)-\frac{1}{Q}\operatorname{\mathds{E}}\left(h(\bm{W})R_{0,-}\mathds{1}_{Y=k}\right).$

Similarly using the fact that
$Q=\operatorname{\mathds{E}}(\mathds{1}_{\Delta\\!Y=1}\mid\bm{W},Y)-R_{0,+}$
we get that

$\displaystyle\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)\mathds{1}_{Y=k-1}\right)$
$\displaystyle=\frac{1}{Q}\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)\mathds{1}_{Y^{\prime}=k}\mathds{1}_{Y=k-1}\right)-\frac{1}{Q}\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)R_{0,+}\mathds{1}_{Y=k-1}\right).$

Moreover, exchangeability of $(\bm{W},Y)$ and $(\bm{W}^{\prime}.Y^{\prime})$
implies

$\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)\mathds{1}_{Y=k-1}\mathds{1}_{Y^{\prime}=k}\right)=\operatorname{\mathds{E}}\left(h\left(\bm{W}^{\prime}\right)\mathds{1}_{Y^{\prime}=k-1}\mathds{1}_{Y=k}\right).$

In particular, since $h(\bm{w})$ is $1$-Lipschitz and
$\operatorname{\mathds{E}}h(\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z})=0$ it follow
that

$\displaystyle\left|\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)\mathds{1}_{Y=k}\right)-\operatorname{\mathds{E}}\left(h\left(\bm{W}\right)\mathds{1}_{Y=k-1}\right)\right|$
$\displaystyle\quad\leqslant\frac{1}{Q}\operatorname{\mathds{E}}\left(\left|\Delta\\!\bm{W}\right|\cdot\mathds{1}_{Y\in\\{k-1,k\\}}\right)$
$\displaystyle\qquad\quad+\frac{1}{Q}\operatorname{\mathds{E}}\left((\left|\bm{W}\right|+\operatorname{\mathds{E}}\left|\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z}\right|)(\left|R_{0,+}\right|+\left|R_{0,-}\right|)\mathds{1}_{Y\in\\{k-1,k\\}}\right),$

where $Z\sim N(0,1)$ and is independent of everything else. Recalling the fact
that
$\operatorname{\mathds{E}}\left|\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z}\right|\leqslant\sqrt{\operatorname{\mathds{E}}(|\Sigma^{\nicefrac{{1}}{{2}}}\bm{Z}|^{2})}=\sqrt{\operatorname{Tr}(\Sigma)}$
completes the proof. $\blacksquare$

###  5.1 Proof of Theorem 2.1

Fix $k\in\zeta+\mathds{Z}$ with $p_{k}:=\operatorname{\mathds{P}}(Y=k)>0$. We
define

$\displaystyle g(y):=\left(-1\right)^{y}\cdot\mathds{1}_{y\leqslant 0}\text{
for }y\in\mathds{Z}.$ (5.1)

Note that

$g(y)+g(y+1)\equiv\mathds{1}_{y=0}\text{ for all }y.$

Recall from equation (1.11), the following mean zero random variable

$\displaystyle\Theta_{f}(W,Y)$
$\displaystyle:=\operatorname{\mathds{E}}\left((F(W^{\prime})-F(W))\cdot(g(Y^{\prime}-k)\cdot\mathds{1}_{\Delta\\!Y=1}+g(Y-k)\cdot\mathds{1}_{\Delta\\!Y=-1})\mid
W,Y\right),$

where $F(w)$ is a three times differentiable function. Denote, the first
derivative of $F$ by $f$. We will use

$\left|f\right|_{i}:=\left\|f^{(i)}\right\|_{\infty},$

where $f^{(i)}$ is the $i^{\textrm{th}}$ derivative of $f$. Using Taylor
approximation upto the third order we have

$\displaystyle\Theta_{f}(W,Y)$
$\displaystyle=f(W)\cdot\hat{g}_{1}+\frac{1}{2}f^{\prime}(W)\cdot\hat{g}_{2}+\frac{1}{6}\left|f\right|_{2}\cdot\text{Err}$

where

$\displaystyle\hat{g}_{i}:=\operatorname{\mathds{E}}\left((\Delta
W)^{i}\left(g(Y-k+1)\mathds{1}_{\\{\Delta\\!Y=1\\}}+g(Y-k)\mathds{1}_{\\{\Delta\\!Y=-1\\}}\right)\mid
W,Y\right),$

for $i=1,2$ and

$\displaystyle\left|\text{Err}\right|\leqslant\operatorname{\mathds{E}}\left(|\Delta
W|^{3}\cdot(\left|g(Y-k+1)\right|\mathds{1}_{\Delta\\!Y=1}+\left|g(Y-k)\right|\mathds{1}_{\Delta\\!Y=-1})\mid
W,Y\right).$

Now we plug in (5.1) for $g(\cdot)$ and notice that

$\displaystyle\hat{g}_{i}=M_{i,-}\mathds{1}_{Y=k}+\bigl{(}M_{i,+}-M_{i,-}\bigr{)}g(Y-k+1),\text{
for }i=1,2.$

By grouping the terms based on the indicator and the order of the $M$ terms to
get the following

$\displaystyle\Theta_{f}(W,Y)$
$\displaystyle=\bigl{(}f(W)M_{1,-}+\frac{1}{2}f^{\prime}(W)M_{2,-}\bigr{)}\mathds{1}_{Y=k}$
$\displaystyle\quad+\sum_{i=1}^{2}\frac{1}{i!}f^{(i-1)}(W)\cdot\bigl{(}M_{i,+}-M_{i,-}\bigr{)}\cdot
g(Y-k+1)+\frac{1}{6}\left|f\right|_{2}\cdot\text{Err}.$

By using Assumptions III, IV, the fact that
$\operatorname{\mathds{E}}\Theta_{f}(W,Y)=0$ and
$\left\|g\right\|_{\infty}\leqslant 1$, we can write

$\displaystyle\frac{1}{2}\lambda\left|\operatorname{\mathds{E}}\bigr{(}f^{\prime}(W)(\psi+R_{2,-})-f(W)(\psi
W+2R_{1,-})\bigl{)}\mathds{1}_{Y=k}\right|$
$\displaystyle\qquad\leqslant\sum_{i=1}^{2}\frac{1}{i!}\left|f\right|_{i-1}\cdot\operatorname{\mathds{E}}\left|M_{i,+}-M_{i,-}\right|+\frac{1}{6}\left|f\right|_{2}\cdot\operatorname{\mathds{E}}\left|\text{Err}\right|.$

By moving the error terms to the right hand side and dividing both sides of
the inequality by $\lambda\psi/2$ we get

$\displaystyle\left|\operatorname{\mathds{E}}(f^{\prime}(W)-f(W)W)\mathds{1}_{Y=k}\right|$
$\displaystyle\quad\leqslant\frac{2\left|f\right|_{0}}{\psi}\cdot\operatorname{\mathds{E}}|R_{1,-}|\mathds{1}_{Y=k}+\frac{\left|f\right|_{1}}{\psi}\cdot\operatorname{\mathds{E}}|R_{2,-}|\mathds{1}_{Y=k}+\frac{\left|f\right|_{2}}{3\lambda\psi}\cdot\operatorname{\mathds{E}}\left|\text{Err}\right|$
$\displaystyle\qquad+\frac{2\left|f\right|_{0}}{\psi}\cdot\operatorname{\mathds{E}}|R_{1,+}-R_{1,-}|+\frac{\left|f\right|_{1}}{\psi}\cdot\operatorname{\mathds{E}}|R_{2,+}-R_{2,-}|.$

In the last line, each term would have appeared with $\mathds{1}_{Y\leqslant
k-1}$; however, since $\\{Y\leqslant k-1\\}$ is a constant order event, we
upper-bounded it by $1$. Recall that using the relation (1.1) bounding
$\left|\operatorname{\mathds{E}}(f^{\prime}(W)-Wf(W))\mathds{1}_{Y=k}\right|$
for $f\in\mathcal{A}$ allows us to bound the Wasserstein distance between
$W\mathds{1}_{Y=k}$ and the standard normal random variable $Z$. Dividing both
sides by

$p_{k}=\operatorname{\mathds{P}}(Y=k)>0$

we get the desired bound

$\displaystyle\left|\operatorname{\mathds{E}}\left(h\left(W)\mid
Y=k\right)-h\left(Z\right)\right)\right|\leqslant\frac{2}{\psi}\left(A_{k}+\frac{1}{p_{k}}C\right)+\sqrt{\frac{2}{\pi\psi^{2}}}\left(B_{k}+\frac{1}{p_{k}}D\right)+\frac{2}{3\lambda\psi
p_{k}}E.$

This completes the proof. $\blacksquare$

###  5.2 Proof of Lemma 2.3

By the same argument as in the Proof of Theorem 2.1 but with
$g(y)=\mathds{1}_{y=0}$ we get that

$\displaystyle\Theta_{f}(W,Y)$
$\displaystyle=\bigl{(}f(W)M_{1,-}+\frac{1}{2}f^{\prime}(W)M_{2,-}\bigr{)}\mathds{1}_{Y=k}+\bigl{(}f(W)M_{1,+}+\frac{1}{2}f^{\prime}(W)M_{2,+}\bigr{)}\mathds{1}_{Y=k-1}$
$\displaystyle\quad+\frac{1}{6}f^{\prime\prime}(W)\cdot\text{Err}\cdot\mathds{1}_{Y\in\\{k-1,k\\}},$

where

$\displaystyle\left|\text{Err}\right|\leqslant\operatorname{\mathds{E}}\left(|\Delta
W|^{3}\mid W,Y\right).$

Using Assumptions III, IV, and the fact that
$\operatorname{\mathds{E}}\Theta_{f}(W,Y)=0$ and
$\left\|g\right\|_{\infty}\leqslant 1$, we derive that

$\displaystyle\left|\operatorname{\mathds{E}}(f^{\prime}(W)-f(W)W)\mathds{1}_{Y\in\\{k-1,k\\}}\right|$
$\displaystyle\leqslant\frac{2\left|f\right|_{0}}{\psi}\cdot\operatorname{\mathds{E}}|R_{1,-}|\mathds{1}_{Y=k}+\frac{\left|f\right|_{1}}{\psi}\cdot\operatorname{\mathds{E}}|R_{2,-}|\mathds{1}_{Y=k}$
$\displaystyle\qquad+\frac{2\left|f\right|_{0}}{\psi}\cdot\operatorname{\mathds{E}}|R_{1,+}|\mathds{1}_{Y=k-1}+\frac{\left|f\right|_{1}}{\psi}\cdot\operatorname{\mathds{E}}|R_{2,+}|\mathds{1}_{Y=k-1}+\frac{\left|f\right|_{2}}{3\lambda\psi}\operatorname{\mathds{E}}\left|\textrm{Err}\right|\mathds{1}_{Y\in\\{k-1,k\\}}.$

Recall that as defined in Assumption II we have that for $k$ such that
$p_{k}>0$ and $p_{k-1}>0$ the ratio

$r_{k}:=\frac{p_{k-1}}{p_{k}}\in(0,\infty),$

which implies that

$\frac{p_{k}}{p_{k}+p_{k-1}}=\frac{1}{1+r_{k}}\quad\text{and}\quad\frac{p_{k-1}}{p_{k}+p_{k-1}}=\frac{r_{k}}{1+r_{k}}.$

The standard application of the relation (1.1) as well as dividing by
$p_{k}+p_{k-1}$ now yields the desired bound

$\displaystyle d_{\mathcal{W}}((W\mid Y\in\\{k-1,k\\}),Z)$
$\displaystyle\quad\leqslant\frac{2}{\psi(1+r_{k})}\left(\operatorname{\mathds{E}}(|R_{1,-}|\mid{Y=k})+r_{k}\operatorname{\mathds{E}}(|R_{1,+}|\mid{Y=k-1})\right)$
$\displaystyle\qquad+\frac{\sqrt{2/\pi}}{\psi(1+r_{k})}\left(\operatorname{\mathds{E}}(|R_{2,-}|\mid{Y=k})+r_{k}\operatorname{\mathds{E}}(|R_{2,+}|\mid{Y=k-1})\right)$
$\displaystyle\qquad+\frac{2}{3\lambda\psi}\operatorname{\mathds{E}}(\left|\Delta
W\right|^{3}\mid Y\in\\{k-1,k\\}).$

The proof is now complete. $\blacksquare$

###  5.3 Proof of Theorem 3.1

Since Lemma 5.1 is applicable in multivariate case, hence to mimic the
univariate argument it is enough to derive an equivalent of Lemma 2.3 in
multivariate case. We first derive a bound for the operator

$\displaystyle\mathscr{S}f(\bm{x}):=\langle\Sigma,\operatorname{Hess}f(\bm{x})\rangle_{\operatorname{H.S.}}-\langle\bm{x},\nabla
f(\bm{x})\rangle,$

where $f$ is three times differentiable function. This is equivalent to
deriving a CCLT with explicit rate of convergence in the metric with smooth
test functions. From that we derive the bound in terms of Wasserstein distance
by following the argument of [23, Theorem 1.1] that builds up on the
previously established techniques for exchangeable pair to the multivariate
setting such as [8, 38, 39].

We now introduce the notations needed for the arguments in this section. For
further details on them we refer to [38, Section 5] and [23, Section 1]. For
$r$-times differentiable function $f:\mathds{R}^{d}\to\mathds{R}$, we denote
by $\nabla^{r}f(x)$ the $r^{\textrm{th}}$ derivative of $f$ at
$x\in\mathds{R}^{d}$.

The value of $\nabla^{r}f(x)$ evaluated at $u_{1},...,u_{r}\in\mathds{R}^{d}$
is defined to be

$\langle\nabla^{r}f(x),u_{1}\otimes u_{2}\cdots\otimes
u_{r}\rangle:=\sum_{j_{1},j_{2},\ldots,j_{r}=1}^{d}\partial_{j_{1},j_{2},\ldots,j_{r}}f(x)u_{1,j_{1}}\cdots
u_{r,j_{r}}.$

We define the injective norm of an $r$-linear form $T$ on $\mathds{R}^{d}$ by

$\left|T\right|_{\vee}:=\sup_{\left|u_{1}\right|\vee\cdots\vee\left|u_{r}\right|\leqslant
1}\left|\langle T,u_{1}\otimes u_{2}\cdots\otimes u_{r}\rangle\right|.$

Then for an $(r-1)$-times differentiable function
$h:\mathds{R}^{d}\to\mathds{R}$, we define the operator

$M_{r}(h):=\sup_{x\neq
y}\frac{\left|\nabla^{r-1}h(x)-\nabla^{r-1}h(y)\right|_{\vee}}{\left|x-y\right|}.$
(5.2)

Notice that in the denominator of (5.2) $\left|\cdot\right|$ is the Euclidean
$\ell_{2}$ norm. Furthermore, if $h$ is $r$-times differentiable then
$M_{r}(h)=\sup_{x\in\mathds{R}^{d}}\left|\nabla^{r}h(x)\right|_{\vee}$.

######  Lemma 5.2.

Under assumptions of Theorem 3.1, for any third order differentiable function
$f$ such that the following terms make sense and for any $k$ such that
$\operatorname{\mathds{P}}(Y=k)>0$ and $\operatorname{\mathds{P}}(Y=k-1)>0$
and we have that

$\displaystyle\operatorname{\mathds{E}}\biggl{(}\mathscr{S}f(\bm{W})\cdot\mathds{1}_{Y\in\\{k-1,k\\}}\biggr{)}$
$\displaystyle\quad\leqslant