\sc\MakeUppercase{Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics}
\sc Xiao Fang
\sc Adrian R\"ollin
We provide a new general theorem for multivariate normal approximation on convex sets. The theorem is formulated in terms of a multivariate extension of Stein couplings. We apply the results to a homogeneity test in dense random graphs and to prove multivariate asymptotic normality for certain doubly indexed permutation statistics.
1206.6586.tex
\documentclass[11pt,a4paper]{article}

\usepackage{amsmath,amsthm,amssymb,color}
\usepackage[authoryear]{natbib}
\usepackage{booktabs}
\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}

\usepackage{bbm}
\usepackage{mathrsfs}
\usepackage[breaklinks=true]{hyperref}

\numberwithin{equation}{section}
\allowdisplaybreaks[4]

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}[definition]{Example}
\newtheorem{remark}[definition]{Remark}
\newtheorem{case}[definition]{Case}
\newtheorem{condition}[definition]{Condition}


\makeatletter

\newcount\minute
\newcount\hour
\newcount\hourMins
\def\now{%
\minute=\time%
\hour=\time \divide \hour by 60%
\hourMins=\hour \multiply\hourMins by 60%
\advance\minute by -\hourMins%
\zeroPadTwo{\the\hour}:\zeroPadTwo{\the\minute}%
}
\def\zeroPadTwo#1{\ifnum #1<10 0\fi#1}

\def\note#1{\par\smallskip%
\noindent%
\llap{$\boldsymbol\Longrightarrow$}%
\fbox{\vtop{\hsize=0.98\hsize\parindent=0cm\small\rm #1}}%
\rlap{$\boldsymbol\Longleftarrow$}%
\par\smallskip}

\renewcommand{\cite}{\citet}

\def\^#1{\ifmmode {\mathaccent"705E #1} \else {\accent94 #1} \fi}
\def\~#1{\ifmmode {\mathaccent"707E #1} \else {\accent"7E #1} \fi}

\def\*#1{#1^\ast}
\edef\-#1{\noexpand\ifmmode {\noexpand\bar{#1}} \noexpand\else \-#1\noexpand\fi}
\def\>#1{\vec{#1}}
\def\.#1{\dot{#1}}
\def\wh#1{\widehat{#1}}
\def\wt#1{\widetilde{#1}}
\def\atop{\@@atop}
% \def\%#1{\mathcal{#1}}
\def\*#1{\mathscr{#1}}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\phi}{\varphi}
\newcommand{\eps}{\varepsilon}
\renewcommand{\eps}{\varepsilon}
\newcommand{\D}{\Delta}
\newcommand{\eq}{\eqref}

\newcommand{\dtv}{\mathop{d_{\mathrm{TV}}}}
\newcommand{\dloc}{\mathop{d_{\mathrm{loc}}}}
\newcommand{\dw}{\mathop{d_{\mathrm{W}}}}
\newcommand{\dk}{\mathop{d_{\mathrm{K}}}}

\newcommand\indep{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}

\def\endo{\mathop{\mathrm{end}}}
\newcommand{\ER}{Erd\H{o}s-R\'enyi}
\newcommand{\Des}{\mathop{\mathrm{Des}}}
\newcommand{\Inv}{\mathop{\mathrm{Inv}}}

\newcommand{\bigo}{\mathrm{O}}
\newcommand{\lito}{\mathrm{o}}
\newcommand{\hence}{\Rightarrow}

\def\tsfrac#1#2{{\textstyle\frac{#1}{#2}}}
\newcommand{\toinf}{\to\infty}
\newcommand{\tozero}{\to0}
\newcommand{\longto}{\longrightarrow}

\def\t#1{\tilde{#1}}
\def\tt#1{\tilde{\tilde{#1}}}

\newcommand{\diag}{{\mathop{\mathrm{diag}}}}

\newcommand{\Po}{\mathop{\mathrm{Po}}}
\newcommand{\cPo}{\mathop{\widehat{\mathrm{Po}}}}
\newcommand{\TP}{\mathop{\mathrm{TP}}}
\newcommand{\TCP}{\mathop{\mathrm{TCP}}}
\newcommand{\CP}{\mathop{\mathrm{CP}}}
\newcommand{\Bi}{\mathop{\mathrm{Bi}}}
\newcommand{\cBi}{\mathop{\widehat{\mathrm{Bi}}}}
\newcommand{\Pa}{\mathop{\mathrm{Pa}}}
\newcommand{\Exp}{\mathop{\mathrm{Exp}}}
\newcommand{\Ge}{\mathop{\mathrm{Ge}}\nolimits}
\newcommand{\MVN}{\mathrm{MVN}}
\newcommand{\Be}{\mathop{\mathrm{Be}}}
\newcommand{\N}{\mathrm{N}}
\newcommand{\NE}{\mathop{\mathrm{NE}}}
\newcommand{\Hyp}{\mathop{\mathrm{Hyp}}}
\newcommand{\U}{\mathrm{U}}
\newcommand{\IE}{\mathbbm{E}}
\newcommand{\IP}{\mathbbm{P}}
\newcommand{\Var}{\mathop{\mathrm{Var}}\nolimits}
\newcommand{\Cov}{\mathop{\mathrm{Cov}}}
\newcommand{\Cor}{\mathop{\mathrm{Cor}}}
\newcommand{\Vol}{\mathop{\mathrm{Vol}}}
\newcommand{\e}{{\mathrm{e}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}
\newcommand{\sgn}{\mathop{\mathrm{sgn}}}
\newcommand{\law}{\mathscr{L}}
\newcommand{\eqlaw}{\stackrel{\mathscr{D}}{=}}
\newcommand{\esssup}{\mathop{\mathrm{ess\,sup}}}
\newcommand{\IN}{\mathbbm{N}}
\newcommand{\IZ}{\mathbbm{Z}}
\newcommand{\IR}{\mathbbm{R}}
\newcommand{\IS}{\mathbbm{S}}
\newcommand{\IC}{\mathbbm{C}}
\newcommand{\II}{\mathbbm{I}}
\newcommand{\Id}{\mathrm{Id}}
\newcommand{\ahalf}{{\textstyle\frac{1}{2}}}
\newcommand{\athird}{{\textstyle\frac{1}{3}}}
\newcommand{\aforth}{{\textstyle\frac{1}{4}}}
\newcommand{\afifth}{{\textstyle\frac{1}{5}}}
\newcommand{\asixth}{{\textstyle\frac{1}{6}}}
\newcommand{\anth}{{\textstyle\frac{1}{n}}}
\newcommand{\bahalf}{{\displaystyle\frac{1}{2}}}
\newcommand{\bathird}{{\displaystyle\frac{1}{3}}}
\newcommand{\baforth}{{\displaystyle\frac{1}{4}}}
\newcommand{\bafifth}{{\displaystyle\frac{1}{5}}}
\newcommand{\basixth}{{\displaystyle\frac{1}{6}}}

\def\be#1{\begin{equation*}#1\end{equation*}}
\def\ben#1{\begin{equation}#1\end{equation}}
\def\bes#1{\begin{equation*}\begin{split}#1\end{split}\end{equation*}}
\def\besn#1{\begin{equation}\begin{split}#1\end{split}\end{equation}}
\def\bg#1{\begin{gather*}#1\end{gather*}}
\def\bgn#1{\begin{gather}#1\end{gather}}
\def\bm#1{\begin{multline*}#1\end{multline*}}
\def\bmn#1{\begin{multline}#1\end{multline}}
\def\ba#1{\begin{align*}#1\end{align*}}
\def\ban#1{\begin{align}#1\end{align}}

\def\klr#1{(#1)}
\def\bklr#1{\bigl(#1\bigr)}
\def\bbklr#1{\Bigl(#1\Bigr)}
\def\bbbklr#1{\biggl(#1\biggr)}
\def\bbbbklr#1{\Biggl(#1\Biggr)}

\def\klrl{(}
\def\bklrl{\bigl(}
\def\bbklrl{\Bigl(}
\def\bbbklrl{\biggl(}
\def\bbbbklrl{\Biggl(}

\def\klrr{)}
\def\bklrr{\bigr)}
\def\bbklrr{\Bigr)}
\def\bbbklrr{\biggr)}
\def\bbbbklrr{\Biggr)}

\def\kle#1{[#1]}
\def\bkle#1{\bigl[#1\bigr]}
\def\bbkle#1{\Bigl[#1\Bigr]}
\def\bbbkle#1{\biggl[#1\biggr]}
\def\bbbbkle#1{\Biggl[#1\Biggr]}

\def\klel{[}
\def\bklel{\bigl[}
\def\bbklel{\Bigl[}
\def\bbbklel{\biggl[}
\def\bbbbklel{\Biggl[}

\def\kler{]}
\def\bkler{\bigr]}
\def\bbkler{\Bigr]}
\def\bbbkler{\biggr]}
\def\bbbbkler{\Biggr]}

\def\klg#1{\{#1\}}
\def\bklg#1{\bigl\{#1\bigr\}}
\def\bbklg#1{\Bigl\{#1\Bigr\}}
\def\bbbklg#1{\biggl\{#1\biggr\}}
\def\bbbbklg#1{\Biggl\{#1\Biggr\}}

\def\klgl{\{}
\def\bklgl{\bigl\{}
\def\bbklgl{\Bigl\{}
\def\bbbklgl{\biggl\{}
\def\bbbbklgl{\Biggl\{}

\def\klgr{\}}
\def\bklgr{\bigr\}}
\def\bbklgr{\Bigr\}}
\def\bbbklgr{\biggr\}}
\def\bbbbklgr{\Biggr\}}

\def\norm#1{\Vert#1\Vert}
\def\bnorm#1{\bigl\Vert#1\bigr\Vert}
\def\bbnorm#1{\Bigl\Vert#1\Bigr\Vert}
\def\bbbnorm#1{\biggl\Vert#1\biggr\Vert}
\def\bbbbnorm#1{\Biggl\Vert#1\Biggr\Vert}

\def\supnorm#1{\Vert#1\Vert_\infty}
\def\bsupnorm#1{\bigl\Vert#1\bigr\Vert_\infty}
\def\bbsupnorm#1{\Bigl\Vert#1\Bigr\Vert_\infty}
\def\bbbsupnorm#1{\biggl\Vert#1\biggr\Vert_\infty}
\def\bbbbsupnorm#1{\Biggl\Vert#1\Biggr\Vert_\infty}

\def\abs#1{\vert#1\vert}
\def\babs#1{\bigl\vert#1\bigr\vert}
\def\bbabs#1{\Bigl\vert#1\Bigr\vert}
\def\bbbabs#1{\biggl\vert#1\biggr\vert}
\def\bbbbabs#1{\Biggl\vert#1\Biggr\vert}

\def\absl{\vert}
\def\babsl{\bigl\vert}
\def\bbabsl{\Bigl\vert}
\def\bbbabsl{\biggl\vert}
\def\bbbbabsl{\Biggl\vert}

\def\absr{\vert}
\def\babsr{\bigr\vert}
\def\bbabsr{\Bigr\vert}
\def\bbbabsr{\biggr\vert}
\def\bbbbabsr{\Biggr\vert}

\def\mid{\vert}
\def\bmid{\!\bigm\vert\!}
\def\bbmid{\Bigm\vert}
\def\bbbmid{\biggm\vert}
\def\bbbbmid{\Biggm\vert}

\def\floor#1{{\lfloor#1\rfloor}}
\def\bfloor#1{{\bigl\lfloor#1\bigr\rfloor}}
\def\bbfloor#1{{\Bigl\lfloor#1\Bigr\rfloor}}
\def\bbbfloor#1{{\biggl\lfloor#1\biggr\rfloor}}
\def\bbbbfloor#1{{\Biggl\lfloor#1\Biggr\rfloor}}

\def\ceil#1{{\lceil#1\rceil}}
\def\bceil#1{{\bigl\lceil#1\bigr\rceil}}
\def\bbceil#1{{\Bigl\lceil#1\Bigr\rceil}}
\def\bbbceil#1{{\biggl\lceil#1\biggr\rceil}}
\def\bbbbceil#1{{\Biggl\lceil#1\Biggr\rceil}}

\def\angle#1{{\langle#1\rangle}}
\def\bangle#1{{\bigl\langle#1\bigr\rangle}}
\def\bbangle#1{{\Bigl\langle#1\Bigr\rangle}}
\def\bbbangle#1{{\biggl\langle#1\biggr\rangle}}
\def\bbbbangle#1{{\Biggl\langle#1\Biggr\rangle}}

\def\Id{\mathbbm{I}}


\def\beqn#1\eeqn{\begin{align}#1\end{align}}
\def\beq#1\eeq{\begin{align*}#1\end{align*}}

\newcommand{\ds}{\displaystyle}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{epsf,amsmath}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\argsup}{argsup}
%\def\qed{{\hfill $\Box$\medskip}}
\def\E{{\IE}}
\def\N{{\rm N}}
\def\P{{\IP}}
\def\Ave{{\rm Ave}}
\def\Std{{\rm Std}}
\def\min{{\rm min}}
\def\I{{\rm I}}
\def\mK{\mathcal{K}}
\def\mE{\mathcal{E}}
\def\mV{\mathcal{V}}

\newcommand{\bl}{\big\{}
\newcommand{\br}{\big\}}
% \newcommand{\ba}{\big|}
\newcommand{\mh}{\mathbf}
\newcommand{\mr}{\IR^d}
\newcommand{\w}{\omega}
\newcommand{\hs}{\mathbf{s}}
\newcommand{\hw}{\mathbf{w}}
\newcommand{\hx}{\mathbf{x}}
\newcommand{\hy}{\mathbf{y}}
\newcommand{\hv}{\mathbf{v}}
\newcommand{\hu}{\mathbf{u}}
\newcommand{\g}{\gamma}
\newcommand{\as}{\stackrel{\text{a.s.}}{\longrightarrow}}
\newcommand{\p}{\stackrel{p}{\longrightarrow}}
\newcommand{\dis}{\stackrel{d}{\longrightarrow}}
\newcommand{\ic}{{\it c}}
\newcommand{\ta}{r}
\newcommand{\si}{\sigma}

\renewcommand\section{\@startsection {section}{1}{\z@}%
{-3.5ex \@plus -1ex \@minus -.2ex}%
{1.3ex \@plus.2ex}%
{\center\small\sc\mathversion{bold}\MakeUppercase}}

\def\subsection#1{\@startsection {subsection}{2}{0pt}%
{-3.5ex \@plus -1ex \@minus -.2ex}%
{1ex \@plus.2ex}%
{\bf\mathversion{bold}}{#1}}

\def\subsubsection#1{\@startsection{subsubsection}{3}{0pt}%
{\medskipamount}%
{-10pt}%
{\normalsize\itshape}{\kern-2.2ex. #1.}}


\def\blfootnote{\xdef\@thefnmark{}\@footnotetext}

\makeatother


\begin{document}

\title{\sc\bf\large\MakeUppercase{Rates of convergence for multivariate
normal approximation with applications to dense graphs and
doubly indexed permutation statistics}}
\author{\sc Xiao Fang \and \sc Adrian R\"ollin}
\date{\it National University of Singapore}%\\[2ex]  \today, \now}
\maketitle

\begin{abstract} We provide a new general theorem for multivariate normal
approximation on convex sets. The theorem is formulated in terms of a
multivariate extension of Stein couplings. We apply the results to a homogeneity
test in dense random graphs and to prove multivariate asymptotic normality
for certain doubly indexed permutation statistics.
\end{abstract}


\section{Introduction} \label{sec1}

Let $W$ and $Z$ be $d$-dimensional random vectors, $d\geq 1$, where $Z$
has standard $d$-dimensional Gaussian distribution. We are concerned with
bounding the
quantity
\ben{\label{1}
  d_{c}\bklr{\law (W), \law (Z)}
   =\sup_{A\in \mathcal{A}}|\P (W\in A)-\P (Z \in A)|,
}
where $\mathcal{A}$ denotes the collection of all the convex sets in $\IR^d$. 

Our main tool is Stein's method for the multivariate normal
distribution, which has already been used to obtain bounds on~\eq{1}, the two
main contributions coming from \cite{Goetze1991} for sums of independent random
vectors (see also \cite{Bhattacharya2010}), and \cite{Rinott1996} for sums of
dependent random vectors that allow for a certain decomposition. Most other
contributions on multivariate normal approximation via Stein's method have
focused on smooth functions; see e.g.\ \cite{Goldstein1996}, \cite{Raic2004} and
\cite{Reinert2009}.

The main aim of this article is to improve the results of \cite{Rinott1996} in
two important ways. Firstly, we remove a logarithmic factor in the error
bound of \cite{Rinott1996}. The techniques that allow us to do this are
taken from \cite{Fang2012} and will yield optimal rates of
convergence in some applications. Secondly, the
assumptions made on the dependence by \cite{Rinott1996} do not cover the
applications we will discuss here. Instead, we will use a multivariate
generalisation of Stein couplings to achieve the necessary generality. Stein
couplings, introduced by \cite{Chen2010b}, capture the minimal structural
assumption necessary to use Stein's method for normal approximation. 

We will also keep the dependence of the
constants on the dimensionality explicit and as small as possible without
blowing up the proofs, but we do not pursue optimality in that respect. 

The remainder of this article is organised as follows. In Section~\ref{sec2} we
will state our main abstract theorem, but we will postpone the (rather
technical) proof to Section~\ref{sec4}. In Section~\ref{sec3}, we will discuss
two main applications, one involving permutation statistics and the other a new
test for heterogeneity in dense graphs. In Section~\ref{sec5}, we will present
some standard multivariate Stein couplings for reference. 


\section{Main results} \label{sec2}

Stein couplings were introduced by \cite{Chen2010b} in order to unify many of
the approaches developed around Stein's method for normal approximation, such
as local approach, size biasing and exchangeable pairs, to name but a few. In
the spirit of \cite{Chen2010b} we give a multivariate definition of Stein
couplings. 

\begin{definition}\label{def1}
A triple of square integrable $d$-dimensional random vectors $(W, W', G)$ is
called a \emph{$d$-dimensional Stein coupling} if
\ben{\label{4}
  \E\bklg{G^t  F(W') -G^t F(W)}=\E\bklg{W^t F(W)}
}
for all $F: \IR^d\rightarrow \IR^d$ for which the expectations exist.
\end{definition}

\begin{remark}\label{rem1} By choosing $F(w) = e_i$, where $e_i$ is the $i$th
unit vector, it follows from \eq{4} that $\IE W_i = 0$. Therefore, $\IE W = 0$
is a necessary condition for a Stein coupling. Choosing $F(w) = w_j e_i$, it
follows that
\be{
   \IE\bklg{G(W'-W)^t} = \Cov(W).
}
\end{remark}

Throughout this article, $\abs{x}$ denotes the Euclidean norm of $x\in\IR^d$,
and $\Id_d$ denotes the $d$-dimensional identity matrix.
With this, we can formulate our main result.

\begin{theorem}\label{thm1} Let $(W,W',G)$ be a $d$-dimensional Stein
coupling. Assume that $\Cov(W)=\Id_d$. With $D=W'-W$, 
suppose that there are positive constants $\alpha$ and $\beta$ such that
\ben{\label{5}
|G|\leq \alpha,\quad |D|\leq \beta.
}
Then there is a universal constant $C$ such that
\besn{\label{6}
  &d_c\bklr{\law (W), \law (Z)}\\
    & \quad\leq C\bbklr{ d^{7/4} \alpha \E|D|^2+d^{1/4} \beta
      +d^{7/8}\alpha^{1/2} B_1^{1/2} +d^{3/8} B_2      
      +d^{1/8}B_3^{1/2}},
}
where $Z$ is a $d$-dimensional standard Gaussian random vector and
\bg{
  B_1  = \sqrt{\Var \E^W|D|^2}, \qquad
  B_2  = \sum_{i,j=1}^d\sqrt{\Var \E^W (G_i D_j)},\\
  B_3  = \sum_{i,j,k=1}^d\sqrt{\Var \E^W (G_i D_j D_k)}.
}

 
\end{theorem}

As usual, we can upper bound $\Var \IE^W(\cdot)$ by
$\Var\IE^{\mathcal{F}}(\cdot)$ for any $\sigma$-algebra $\mathcal{F}\supset
\sigma(W)$. This is a standard trick in Stein's method and will be used in the
applications without further mention.

Note that, if $(W,W',G)$ is a $d$-dimensional Stein coupling
and  $A$ is a $m\times d$ matrix, $m\geq 1$, then $(AW,AW',AG)$ is an
$m$-dimensional Stein coupling. In this light, assuming that $\Cov(W) = \Id_d$
is a matter of convenience rather than a real restriction. Note however, that
the dependence on the dimension will be affected. If $A$ is a
$d\times d$ matrix, denote by $\norm{A}_2$ its operator norm with respect
to the Euclidean norm and denote by $\norm{A}_{\infty}$ its element-wise
supremum norm. Noticing that $d_c$ is invariant under linear transformations, we
have the following immediate consequence of Theorem~\ref{thm1}. 

\begin{corollary}\label{cor1} Under the conditions of Theorem~\ref{thm1}, but
now allowing
$\Cov(W) = \Sigma$ for any positive definite $\Sigma$, there is a constant
$C_d$ depending only on the dimension such that
\besn{ \label{7}
  &d_c(\law (\Sigma^{-1/2} W), \law (Z))
      = d_c(\law ( W), \law (\Sigma^{1/2}Z))\\
  & \qquad\leq C_d \bbklr{ \alpha s_2^2\E|D|^2+
    s_2\beta + s_\infty \alpha^{1/2} B_4^{1/2} + s^2_\infty B_2
    +s^{3/2}_\infty B_3^{1/2}},
}
where $s_2 = \norm{\Sigma^{-1/2}}_2$, $s_\infty =
\norm{\Sigma^{-1/2}}_\infty$ and
\be{
  B_4 = \sum_{i=1}^d\sqrt{\Var
    \E^W D_i^2}.
}
\end{corollary}

Note that the corollary cannot be expected to be informative if $\Sigma$
is singular or close to singular. In particular, the $W_i$ need to be
standardized so that $\Var W_i$, $1\leq i\leq d$, are all of the same order.


\begin{remark}\label{rem2} If $(W,W')$ is an exchangeable pair of
$d$-dimensional vectors and 
\be{   
  \IE^W(W'-W) = -\Lambda W
}
for some invertible $d\times d$-matrix $\Lambda$, then
$\bklr{W,W',\ahalf\Lambda^{-1}(W'-W)}$ is a Stein coupling.
\cite{Reinert2009} showed that, under the very special condition that
\ben{\label{8}
  \IE^W(W'-W) = -\lambda W
}
for some $0<\lambda<1$, one only needs that $\law(W) = \law(W')$ without
exchangeability for their results to hold. The situation for our
Theorem~\ref{thm1} is the same. If $W$ and $W'$ have the same marginal
distribution and satisfy \eq{8}, then \eq{6} holds if $\Cov(W)=\Id_d$ 
(respectively, \eq{7} holds if $\Cov(W)=\Sigma$) with
$G=\ahalf\lambda^{-1}(W'-W)$. A sketch of the
proof will be given in Section~\ref{sec4}.  

\end{remark}

\section{Applications} \label{sec3}


\subsection{A confidence interval for dense homogeneous random graphs}

A basic problem in the analysis of graphs is to test whether
a given graph of size $n$ is compatible with the assumption that it is a
realisation of an \ER\ random graph $G(n,p)$ with edge probability $p$. Many
test statistics have been proposed, such as diameter, maximal degree, number of
triangles, etc.; see e.g.\ \cite{Pao2011}. Here we
propose and justify a new test that is based on the theory of dense graph
limits. We will only introduce the parts of the theory necessary for our
application; see \cite{Borgs2008,Borgs2012} for a thorough introduction; see
also \cite{Diaconis2008}, who make a connection with earlier work of
\cite{Aldous1981}.

Denote by $\endo(F,G)$ the set
of injective graph homomorphisms from $F$ into~$G$. If $F$ has $k$ vertices,
then it is clear that $\abs{\endo(F,G)}\leq (n)_k:=
n(n-1)\cdots(n-k+1)$. Define 
\be{
  t(F,G) = \frac{\abs{\endo(F,G)}}{(n)_k},
}
the ``density of $F$ in $G$''. Let $(G_n)$ be a sequence of graphs (where $n\geq
n_0$ for some unspecified $n_0$) and for convenience assume that $G_n$ has $n$
vertices. The sequence is called a \emph{dense graph sequence} if the number of
edges is of order~$n^2$. It is clear that if the sequence $(G_n)$ is not dense
then $\lim_{n\toinf} t(F,G_n) = 0$ for any $F$ containing at least one edge.

Let now $\kappa:[0,1]^2\to[0,1]$ be a measurable, symmetric function; we shall
call any such function a \emph{standard kernel}. For any finite graph $F$ with
$k$ vertices, let us define the ``density of $F$ in $\kappa$'' as
\be{
  t(F,\kappa) = \int_{0}^1\dots\int_0^1 \prod_{\{i,j\}\subset
  E(F)}\kappa(x_i,x_j) \,d x_1\cdots d x_k,
}
where $E(F)$ denotes the edge set of graph $F$.

The corner stone of dense graph theory is that if $t(F,G_n)$ converges for every
$F$, then there is a standard kernel $\kappa$ such that $\lim t(F,G_n) =
t(F,\kappa)$. We can therefore say that \emph{$\kappa$ is the limit of the graph
sequence $(G_n)$}. Note, however, that $\kappa$ is usually not unique; we refer
again to \cite{Borgs2008,Borgs2012} on how to characterise the equivalence
classes of standard kernels representing the same graph limits.

Let now $K_n$ be the complete graph of size $n$, and let $C_n$ be the cycle
graph of size $n$. \cite{Chung1989} proved the surprising result that if 
\be{
  t(K_2,G_n) \to p\quad\text{and}\quad t(C_4,G_n) \to p^4
}
for some $0<p\leq 1$, then 
\be{
  t(F,G_n) \to p^{e(F)}
}
for \emph{any} graph $F$ where $e(F)$ is the number of edges in $F$. That is,
in the dense case, the limiting densities of edges and $4$-cycles determine
whether the limit is an (infinite) homogeneous \ER\ random graph. In other
words, $\kappa\equiv p$ is the only standard kernel with $t(K_2,\kappa) =
p$ and $t(C_4,\kappa)= p^4$; see
\cite{Lovasz2011} for generalisations of these findings. This suggests that we
may use the number of edges and $4$-cycles in a finite graph as test
statistics.

However, some care is needed. It is known that for a homogenous \ER\
random graph, the number of edges and the number of $4$-cycles are linearly
dependent in the limit; see \cite{Janson1991}.
Thus, we cannot use these values
directly to construct our test.

Following \cite{Janson1991}, we can instead consider the density of $4$-cycles
\emph{corrected} by the edge density (this is essentially the first non-leading
term in a Hoeffding-type decomposition for the $4$-cycle
count). To this end, if $G_n$ is a given graph of size $n$, define the two
statistics
\be{
  T_1(G_n) = \frac{\abs{\endo(K_2,G_n)}}{2},
  \qquad T_2(G_n) = \frac{\abs{\endo(C_4,G_n)}}{8}.
}
The factors $2$ and $8$, respectively, are the sizes of the automorphism
groups of $K_2$ and $C_4$, respectively. Therefore, $T_1$ is just the number of
edges in $G_n$ and $T_2$ is the number of $4$-cycles in $G_n$. Define now the
normalised edge counts
\be{
  W_1(p,G_n) = \frac{T_1(G_n) - {n\choose 2}p }{\sigma_1},\qquad
   \text{with}\quad \sigma_1^2 = {n\choose 2}p(1-p),
}
and the corrected and normalised $4$-cycle count
\be{
  W_2(p,G_n) = \frac{T_2(G_n) - 2{n-2 \choose 2}p^3T_1(G_n) + 9{n\choose
4}p^4}{\sigma_2}
}
with
\bes{
  \sigma_2^2 & = 3{n\choose 4}\bbbklr{p^4(1-4p^3+3p^4) +
(4(n-4)+2)p^6(1-2p+p^2)}\\
      & =n_{(4)}(n-3)\frac{p^6+p^8-2p^7}{2}+n_{(4)}\frac{p^4+p^8-2p^6}{8}.
}

Note that \cite{Barbour1989} use Stein's method to prove univariate normal
approximations of subgraph counts and related statistics. However, for
statistics such as $W_2$, they resort to the method of
moments. The reason that $W_2$ is more difficult to handle is
that it is a degenerate incomplete $U$-statistic of the edges (see \eq{10}
below), whereas simple subgraph counts are non-degenerate. Corresponding
multivariate results where obtained by \cite{Janson1991} in great
generality using Hoeffding-type decompositions and the methods of moments. For
the degenerate statistics they
state that ``Stein's method does not seem to work in that case''.
Our next result shows that it is nevertheless possible.
 
\begin{theorem}\label{thm2} Let $G_n$ be a realisation of an
\ER\ random graph on $n$ vertices and edge probability $p$. Let $W =
\bklr{W_1(p,G_n),W_2(p,G_n)}$ and
let $Z$ be a standard bi-variate normal random variable. There is a
universal constant $C$ intependent of $p$ and $n$ such that
\be{
  d_c(\law (W), \law (Z))\leq \frac{C}{p^9(1-p)^3\sqrt{n}}.
}
\end{theorem}


Theorem~\ref{thm2} justifies the following procedure to construct a confidence
set for the family of \ER\ random graphs. Let $G_n$ be a simple,
unlabeled graph of size $n$. For some $0<\alpha<1$, define the $1-\alpha$
confidence set as
\be{
  C_{1-\alpha}(G_n) = \bklg{0<p<1\,:\, W_1^2(p,G_n)+W_2^2(p,G_n)\leq
q_{1-\alpha}},
}
where $q_{1-\alpha}$ is the $1-\alpha$ quantile of the $\chi^2$-distribution
with $2$ degrees of freedom. $C_{1-\alpha}(G_n)$ is the set of those $p$ for
which $G_n$ is compatible with the model $G(n,p)$. If $C_{1-\alpha}(G_n)$ is
empty, then $G_n$ is not compatible with any homogeneous \ER\ random graph
model (at significance level $\alpha$).

\begin{corollary} For any given $0<p_l < p_u < 1$,
\be{
   \IP[p\not\in C_{1-\alpha}(G(n,p))] =  \alpha 
 + \bigo\bklr{n^{-1/2}}
}
uniformly in $p\in[p_l,p_u]$ as $n\toinf$. Furthermore, for any
non-constant standard kernel $\kappa$, 
\ben{\label{9}
  \IP[C_{1-\alpha}(G(n,\kappa))=\emptyset] \to 1
}
as $n\toinf$.
\end{corollary}

Note that the second part of the corollary follows from standard concentration
results; see e.g.\ \cite{Borgs2008}.

\begin{remark} Note that \eq{9} essentially says that the test will
eventually detect any non-homogeneity as $n\toinf$. This is no longer true if
$4$-cycles were to be replaced by triangles; see e.g.\ \cite[p.~361]{Chung1989}
for an example where the edge and triangle densities of a heterogeneous \ER\
random graph is indistinguishable from that of a homogeneous one.
\end{remark}
 
\begin{remark} If one is interested in testing 
\be{
  H_0\,:\, \text{$G_n \sim G(n,p)$ for some $0< p < 1$}
}
against
\be{
  H_1\,:\, \text{$G_n\sim G(n,\kappa)$ with $\kappa\not\equiv p$ for all 
            $0< p< 1$},
}
then one can consider the test
\bes{
  \phi(G_n) & =\I\bkle{C_{1-\alpha}(G_n)=\emptyset} \\ 
         & = \I\bbkle{\,\inf_{0<p<1}
\bklr{W_1^2(p,G_n)+W_2^2(p,G_n)} > q_{1-\alpha}}.
}
Note, however, that this test will have significance level less
than $\alpha$ and can therefore only be considered as a
conservative test for homogeneity of a dense graph.
\end{remark}
  
Before we prove Theorem~\ref{thm2} we need some technical lemmas. For each
$(i,j,k,l)$ define
\be{
  \eta_{ijkl}=I_{ij} I_{jk} I_{kl} I_{il}-p^3\bklr{
            I_{ij}+I_{jk}+I_{kl}+ I_{il}}+3p^4,
}
where $I_{ij} = I_{ji}$ is the indicator of the event that there is an edge
connecting
$i$ and~$j$. It is straightforward to verify that 
\ben{\label{10}    
  \E \klr{\eta_{ijkl}\mid I_{uv}}=0
}
for any $(i,j,k,l)$ and any $(u,v)$. From \eq{10}, we have the following lemma.
\begin{lemma}\label{lem1} For any $(i,j,k,l)$ and $(u,v,w,m)$ we
have
\be{
  \E(\eta_{ijkl} I_{uv})=0
}
and, if $|\{i,j,k,l\} \cap \{u,v,w,m\}|\leq 2$,
\ben{\label{11}
  \E(\eta_{ijkl} \eta_{uvwm})=0.
}
\end{lemma}

In what
follows we will always assume that $k$-tuples $(i_1,\dots,i_k)\in
\{1,\dots,n\}^k$
are ordered as $i_1<i_2<\dots<i_k$. 
With $\iota = (i,j,k,l)$, define
\ba{
  X_{1,\iota} & = I_{ij}+I_{ik}+I_{il}+I_{jk}+I_{jl}+I_{kl} - 6p,\\
  X_{2,\iota} & = \eta_{ijkl} + \eta_{ijlk} + \eta_{ikjl},
}
and $X_\iota=(X_{1,\iota}, X_{2,\iota})^t$. Now we can represent $W$ as a sum of
locally dependent random vectors, namely
\ben{\label{12}
  W = \bbbklr{\frac{1}{{n-2 \choose 2}\sigma_1}\sum_{\iota} X_{1,\iota},
      \frac{1}{\sigma_2}\sum_{\iota} X_{2,\iota}}^t,
}
where the sum ranges over all $\iota = (i,j,k,l)$, again with $i<j<k<l$. To see
that \eq{12} is the same as in Theorem~\ref{thm2}, note that each ordered
tuple $(i,j,k,l)$ corresponds uniquely to three possible $4$-cycles.
Furthermore, in the first sum in \eq{12}, each edge $I_{ij}$ is
over-counted ${n-2\choose 2}$ times. It is straightforward to check that
\be{
  \E W=0,\qquad  \IE(WW^t) = \Id_2.
}

Since $X_\iota$ is independent of $X_\kappa$ if $\iota$ and $\kappa$ share at
most one vertex, we can choose, for each $\iota$, the neighbourhood
$A_\iota:=\{\kappa\,: \,|\kappa\cap \iota|\geq 2\}$ and we have that, for given
$\iota$, the collection $(X_\kappa)_{\kappa\not\in A_\iota}$ is independent of
$X_\iota$. Therefore, if $I$ is uniformly distributed over all $\iota=(i,j,k,l)$
with $i<j<k<l$, 
\ben{\label{13}
  (W,W',G):=\bbbklr{W, W-\sum_{\kappa\in A_I} X_\kappa, -{n \choose 4}X_I }
}
is a Stein coupling (c.f.\ Section~\ref{sec5}).

\begin{proof}[Proof of Theorem~\ref{thm2}]
We apply Theorem~\ref{thm1} for the Stein coupling \eq{13}. Let as usual
$D=W'-W$. In what follows, $C$ denotes a positive constant independent of
$p$ and $n$, possibly different from line to line. Note first that
\be{
  \sigma_1^2\geq Cn^2p(1-p),
  \qquad \sigma_2^2 \geq C n^5p^6(1-p)^2.
}
Hence,
\be{
  |X_\iota|\leq C\bbbklr{\frac{1}{n^2\sigma_1}+\frac{1}{\sigma_2}}\leq
      \frac{C}{n^{5/2}p^3(1-p)}
}
and $|A_\iota|\leq Cn^2$, and we obtain the upper bounds 
\ben{\label{14}
  |G|\leq \frac{Cn^{3/2}}{p^3(1-p)} =: \alpha, 
    \quad |D|\leq \frac{C}{p^3(1-p)n^{1/2}} =: \beta.
}
The second moment of $|D|$ can be calculated as follows. Noting that
$|\kappa\cap \kappa'|\leq 2$ implies $\IE(X_{2,\kappa} X_{2,\kappa'})=0$, which
follows from \eq{11}, we have
\besn{\label{15}
  \E |D|^2 
  & = \E D_1^2+\E D_2^2\\
  & = \frac{1}{{n \choose 4}}\sum_{\iota}\sum_{\kappa,\kappa'\in
      A_\iota}\IE(X_{1,\kappa}X_{1,\kappa'})
        +\frac{1}{{n \choose 4}}\sum_{\iota}\sum_{\kappa,\kappa'\in
        A_\iota}\IE(X_{2,\kappa} X_{2,\kappa'})\\
  & \leq Cn^2\times n^2 \times \frac{1}{n^4 \sigma_1^2}+Cn^2 \times n\times
        \frac{1}{\sigma_2^2} 
  \leq \frac{C}{n^2 p^6 (1-p)^2}.
}
Define the $\sigma$-field $\mathcal{F} = \sigma(G_n)$. Clearly, $\mathcal{F}
\supset \sigma(W)$. In the following, we calculate the variances of the
conditional expectations in the bound \eq{6}. The key ingredient is
Lemma~\ref{lem1}. 

First,
\bes{
  \Var (\E^\mathcal{F} G_1 D_1)
  & \leq \Var \bbbklr{\sum_\iota X_{1,\iota} \sum_{\kappa\in A_\iota}
      X_{1,\iota}}\\
  & = \sum_{\iota, \iota'} \sum_{\kappa\in A_\iota, \kappa'\in
  A_{\iota'}}\Cov(X_{1,\iota}X_{1,\kappa}, X_{1,\iota'} X_{1,\kappa'}) \leq 
  \frac{Cn^{10}}{n^8 \sigma_1^4},
}
where the last inequality is because $\Cov(X_{1,\iota}X_{1,\kappa},
X_{1,\iota'} X_{1,\kappa'})=0$ if $(\iota,\kappa)$ and $(\iota',\kappa')$ share
at most one vertex. By the same argument, 
\be{
  \Var (\E^\mathcal{F} G_1 D_2)
  \leq \sum_{\iota, \iota'} \sum_{\kappa\in A_\iota,
    \kappa'\in A_{\iota'}}\Cov(X_{1,\iota}X_{2,\kappa}, X_{1,\iota'}
    X_{2,\kappa'})
  \leq \frac{Cn^{10}}{n^4 \sigma_1^2 \sigma_2^2}
}
and
\be{
  \Var (\E^\mathcal{F} G_2 D_1)\leq \frac{Cn^{10}}{n^4 \sigma_1^2 \sigma_2^2};
}
furthermore, from \eq{11},
\be{
  \Var (\E^\mathcal{F} G_2 D_2)\leq \frac{Cn^{9}}{\sigma_2^4}.
}
Therefore, 
\be{
  B_2\leq \frac{C}{n^{1/2}p^{6}(1-p)^2}.
}
By similar arguments,
\be{
  \Var\E^\mathcal{F} (D_1^2)\leq \frac{C}{n^2 \sigma_1^4},\quad
  \Var \E^\mathcal{F} (D_2^2)\leq \frac{Cn^5}{\sigma_2^4},
}
and, hence,
\be{
  B_1\leq \frac{C}{n^{5/2}p^{6}(1-p)^2}.
}
Finally, using Lemma~\ref{lem1}, we obtain
\be{
  \Var\E^\mathcal{F} (G_1 D_1^2)\leq \frac{Cn^{14}}{n^{12} \sigma_1^6},\quad
  \Var\E^\mathcal{F}
  (G_1 D_1 D_2)\leq \frac{Cn^{14}}{n^8 \sigma_1^4 \sigma_2^2},
}
\be{
  \Var\E^\mathcal{F} (G_1 D_2^2)\leq \frac{Cn^{13}}{n^4 \sigma_1^2
  \sigma_2^4},\quad
  \Var\E^\mathcal{F} (G_2 D_1^2)\leq \frac{Cn^{14}}{n^8 \sigma_1^4 \sigma_2^2},
}
\be{
  \Var \E^\mathcal{F} (G_2 D_1 D_2)\leq \frac{Cn^{13}}{n^4 \sigma_1^2
  \sigma_2^4},\quad
  \Var \E^\mathcal{F} (G_2 D_2^2)\leq \frac{Cn^{13}}{\sigma_2^6},
}
and therefore
\be{
  B_3 \leq \frac{C}{np^9(1-p)^{3}}.
}
Collecting the bounds on $B_1$, $B_2$ and~$B_3$, in combination with
\eq{14} and~\eq{15}, yields the final estimate via~\eq{6}.
\end{proof}

\subsection{Joint normality of certain permutation statistics}

Let $M$ be a real $n\times n$ matrices and assume that $M$ is anti-symmetric,
that is, for each $i\neq j$ we have
\be{
  M_{ij} = - M_{ji}.
}
Let $\pi$ be a permutation of size $n$, chosen uniformly at random, and
consider the statistic
\ben{\label{16}
  W = \sum_{i<j} M_{\pi(i)\pi(j)}.
}
This type of permutation statistics was considered by \cite{Fulman2004} and it
is a special case of doubly-indexed permutation statistics
\ben{\label{17}
  \sum_{i,j} a\bklr{i,j,\pi(i),\pi(j)}
}
with 
\be{
  a(i,j,k,l) = \I[i<j] M_{kl}.
}
The reason to study \eq{16} is that two important properties of permutations,
the number of descents and inversions, can be readily represented in this form. 
Choosing $M_{i,i+1}=-1$ and $M_{ij} = 0$ for all other $j>i$ (for
$j<i$, $M_{ij}$ is defined via anti-symmetry), \eq{16} becomes
$2\Des(\pi^{-1})-(n-1)$, where $\Des(\pi)$ is the number of descents of~$\pi$,
and with $M_{ij} = -1$ for all $i<j$, \eq{16}
becomes $2\Inv(\pi^{-1}) - {n\choose 2}$, where $\Inv(\pi)$ is the number of
inversions of~$\pi$. 

Using Stein's method, \cite{Zhao1997} prove a general Berry-Esseen type theorem
for sums of the form~\eq{17}, but their results do not apply to the number of
descents $\Des(\pi)$, which seems to be ``too sparse''. In contrast, using a
special exchangeable pair, \cite{Fulman2004} was able to obtain a rate of
converegence of $n^{-1/2}$ for the Kolmogorov metric for both, the number of
descents and inversions. 

We shall extend Fulman's results to the multivariate setting. Furthermore, 
we are able to remove a certain conditon on $M$ (present in Fulman's work), 
arising from the requirement of exchangeability; c.f.\ Remark~\ref{rem2}.

Let $M^1,\dots,M^d$ be a sequence of real $n\times n$ matrices and assume that
each matrix is anti-symmetric.  
For each $r$, define $W_r=\sum_{i<j} M^r_{\pi(i), \pi(j)}$. As in
\cite{Fulman2004}, define 
\be{
  A_i^r=\sum_{j>i} M^r_{ij}, \qquad B^r_i=\sum_{j<i} M^r_{ji}.
}
The mean and
covariances of $W=(W_1,\dots,W_d)$ are given in the following lemma.
\begin{lemma}\label{lem2}
We have $\E W=0$ and
\be{
  \Cov(W_r, W_s)=\frac{1}{3}\bbbklr{ \sum_{i<j} M^r_{ij}
                  M^s_{ij} +\sum_{i}
                  (A^r_i-B^r_i)(A^s_i-B^s_i)}
}
\end{lemma}
\begin{proof}
The proof is similar to that of \cite[Lemma 4.3.1]{Fulman2004}. For each $r$
define
\be{
  X^r_{ij}(\pi)=
  \begin{cases}
    M^r_{ij}, & \text{if $\pi^{-1}(i)<\pi^{-1}(j)$,}\\
    M^r_{ji}, & \text{if $\pi^{-1}(j)<\pi^{-1}(i)$.}
  \end{cases}
}
Then
\be{
  W_r =\sum_{i<j}   
  M^r_{\pi(i)\pi(j)}=\sum_{\pi^{-1}(i)\atop\quad
  <\pi^{-1}(j)}M^r_{ij}=\sum_{i<j}  X^r_{ij}(\pi). 
}
Since $\E X^r_{ij}=0$, we have $\E W_r=0$. To avoid over-use of brackets in
what follows, expressions such as ``$\E X^{r}_{i,j}(\pi) X^{s}_{i,j}(\pi)$'' are
to be understood as ``$\E\bklg{X^{r}_{i,j}(\pi) X^{s}_{i,j}(\pi)}$''. Recalling
that $M^r$ is
anti-symmetric, $\Cov(W_{r}, W_{s})$ can be calculated as
\bes{
  &\Cov(W_{r}, W_{s})\\
  &\quad= \sum_{i<j} \E X^{r}_{i,j}(\pi) X^{s}_{i,j}(\pi)\\
  &\qquad+\sum_{i}\sum_{j\ne l: j,l>i } \E X^{r}_{i,j}(\pi)
    X^{s}_{i,l}(\pi)+\sum_{j}\sum_{i\ne k: i,k<j} \E X^{r}_{i,j}(\pi)
    X^{s}_{k,j}(\pi)\\
  &\qquad+\sum_{i<j<l} \E X^{r}_{i,j}(\pi) X^{s}_{j, l}(\pi)+\sum_{k<i<j}
    \E X^{r}_{i,j}(\pi) X^{s}_{k,i}(\pi)\\
  &\quad= \sum_{i<j} M^{r}_{i,j} M^{s}_{i,j}+\sum_{i}\sum_{j\ne l:
    j,l>i}\frac{M^{r}_{i,j} M^{s}_{i,l}}{3}+\sum_{j}\sum_{i\ne k:
    i,k<j }\frac{M^{r}_{i,j} M^{s}_{k,j}}{3}\\
  &\qquad-\sum_{i<j<l} \frac{M^{r}_{i,j}
    M^{s}_{j,l}}{3}-\sum_{k<i<j}\frac{M^{r}_{i,j}
    M^{s}_{k,i}}{3}\\
  &\quad=\sum_{i<j} M^{r}_{i,j} M^{s}_{i,j}+\sum_{i}\frac{1}{3}(
    A^{r}_i A^{s}_i-\sum_{j: j>i}M^{r}_{i,j} M^{s}_{i,j})\\
  &\qquad +\sum_{i}\frac{1}{3}( B^{r}_i B^{s}_i-\sum_{j:
    j<i}M^{r}_{i,j} M^{s}_{i,j}  )
    -\frac{1}{3}\sum_i B^{r}_i A^{s}_i - \frac{1}{3}A^{r}_i
    B^{s}_i\\
  &\quad=\frac13 \sum_{i<j} M^{r}_{i,j} M^{s}_{i,j} +\frac13\sum_{i}
    (A^{r}_i-B^{r}_i)(A^{s}_i-B^{s}_i).\qedhere
}
\end{proof}
Without loss of generality, in the following we assume that $\Var(W_r)=1$
for each $r$. With $W=(W_1,\dots, W_d)^t$, we have the following result.

\begin{theorem}\label{thm3}
Let be $W$ as above and let
\ben{\label{18}
  \beta=\sup_{r, i} \sum_{j=1}^n |M^r_{ij}|.
}
Then, with $\Sigma=\Cov(W)$, there is a positive constant $C_d$ depending only
on~$d$, such that
\be{
  d_c(\law ( W), \law(\Sigma^{1/2} Z))\leq 
  C_d(\norm{\Sigma^{-1/2}}_2^2+\norm{\Sigma^{-1/2}}_\infty^2)n\beta^3.
}

\end{theorem}
As a corollary of Theorem~\ref{thm3}, we prove the joint asymptotic
normality of the number of descents and inversions of $\pi$; the rate obtained
is best possible.

\begin{corollary}\label{cor2}
Let $\Des(\pi)$ and $\Inv(\pi)$ be the number of descents and inversions of
$\pi$, and let
\be{
  W=(W_1,W_2)^t=\bbbbklr{\frac{\Des(\pi)-\frac{n-1}{2}}{\sqrt{\frac{n+1}{12}}},
  \frac{\Inv(\pi)-\ahalf{n \choose 2}}{\sqrt{\frac{n(n-1)(2n+5)}{72}}}}^t
}
Then
\be{
  d_c(\law ( W), \law( Z) )\leq \frac{C}{\sqrt{n}}
}
for some absolute constant $C$, where $Z$ is a $2$-dimensional standard Gaussian
vector.
\end{corollary}

\begin{proof}
Set
\be{
  M^1_{ij}=
  \sqrt{\frac{3}{n+1}}
  \times 
  \begin{cases}
  - 1& \text{if $j=i+1$,}\\
  + 1& \text{if $j=i-1$,}\\
  0 & \text{otherwise,}
  \end{cases}
}
and set
\be{
  M^2_{ij}=
  \sqrt{\frac{18}{n(n-1)(2n+5)}}
  \times
  \begin{cases}
  -1& \text{if $j>i$,}\\
  +1& \text{if $j<i$,}\\
  0 & \text{otherwise.}
  \end{cases}
}
It can be easily verified that $W_1=\sum_{i<j} M^1_{\pi(i)\pi(j)}$ and
$W_2=\sum_{i<j} M^2_{\pi(i)\pi(j)}$. From Lemma~\ref{lem2},
$\Var(W_1)=\Var(W_2)=1$ and $|\Cov(W_1,W_2)|\leq C/n$. Moreover, $\beta$ as
defined in \eq{18} is smaller than $C/\sqrt{n}$. Therefore, the corollary is
proved by applying Theorem~\ref{thm3}.
\end{proof}

To prove Theorem~\ref{thm3}, we need the following lemma, the proof of
which is straightforward and therefore omitted. 

\begin{lemma}\label{lem3}
For $1\leq r, s, t \leq d$ and $\beta$ defined in \eq{18}, we
have
\bgn{
\label{19}
  \sum_{i_1,\dots,i_6}|M^{r}_{i_1i_2}M^{s}_{i_1,i_3}M^{
  r}_{i_4i_5}M^{s}_{i_4i_6}|\leq n^2\beta^4,\\
\label{20}
  \sum_{\abs{\{i_1,\dots,i_6\}}\leq
  5}|M^{r}_{i_1 i_2}M^{s}_{i_1i_3}M^{r}_{i_4i_5}M^{s}_{i_4i_6}|\leq n \beta^4,\\
\label{21}
  \sum_{i_1,\dots,i_8}|M^{r}_{i_1i_2}M^{s}_{i_1i_3}
  M^{t}_{i_1i_4}M^{r}_{i_5i_6}M^{s}_{i_5i_7}M^{t}_{i_5i_8}|\leq n^2\beta^6,\\
\label{22}
  \sum_{\abs{\{i_1,\dots,i_8\}}\leq7}|M^{r}_{i_1i_2}M^{s}_{i_1i_3}
  M^{t}_{i_1i_4}M^{r}_{i_5i_6}M^{s}_{i_5i_7}M^{t}_{i_5i_8}|\leq n \beta^6,
}
where $\sum_{\abs{\{i_1,\dots,i_k\}}\leq k-1}$ stands for summation over all
tuples $(i_1,\dots,i_k)$ for which at least two components are equal.
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{thm3}]
We adopt the construction of $W'$ from \cite{Fulman2004}. Let $I$ be uniformly
chosen from $\{1,\dots,n\}$ and independently of $\pi$. Given $I$, we define
$\pi'$ as
$\pi\circ (I,I+1,\dots, n)$ where $(I,I+1,\dots, n)$ denotes the mapping
$I\mapsto I+1 \mapsto \dots \mapsto n\mapsto I$, while keeping the rest
identical. As $\pi$ and $\pi'$ both are uniformly distributed, $W$ and $W'$ have
the same marginal distribution (but are not necessarily exchangeable).
\cite{Fulman2004} showed that with $\lambda=2/n$
\be{
  \E^{\pi} (W'-W)=-\lambda W.
}
Following Remark~\ref{rem2}, the bound \eq{7} holds with $D=W'-W$
and $G=\ahalf \lambda^{-1}D$ (c.f.\ Section~\ref{sec5}).
From the construction of $W'$ and the definition of $\beta$ in \eq{18}, we have
\ben{\label{23}
  |G|\le C_d n \beta, \quad |D|\le C_d \beta.
}
We first prove that
\ben{\label{24}
  \Var \E^\pi( D_{r} D_{s})\leq \frac{C_d\beta^4}{n}.
}
From the construction of $W'$,
\bes{
  &\Var \E^\pi (D_{r} D_{s})\\
  &\quad=  \Var \bbbklr{ \frac{4}{n}\sum_{i=1}^n
    \sum_{j_1,j_2>i}M^{r}_{\pi(i),
    \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)}}\\
  &\quad=\frac{16}{n^2}\Var \bbbklr{ \sum_{i=1}^n\sum_{j>i} M^{r}_{\pi(i),
    \pi(j)}M^{s}_{\pi(i),\pi(j)}+\sum_{i=1}^n \sum_{j_1,j_2>i \atop j_1\neq j_2}
    M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)} }.
}
As the first double sum in the last line is constant, we only
need to show that, for each $i$,
\be{
  \sum_{i<j_1<j_2} \Var\bklr{M^{r}_{\pi(i),
      \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)}}\leq C_d n\beta^4
}
and
\ben{\label{25}
  \sum_{i<j_1<j_2, k<l_1<l_2 \atop (i,j_1,j_2)\ne
  (k,l_1,l_2)}\Cov\bklr{M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)},
  M^{r}_{\pi(k), \pi(l_1)}M^{s}_{\pi(k),\pi(l_2)}}\leq C_d n\beta^4.
}
From \eq{20},
\bes{
  \sum_{i<j_1<j_2} \Var\bklr{M^{r}_{\pi(i),
\pi(j_1)}M^{s}_{\pi(i),\pi(j_2)}} &\leq
  \sum_{i<j_1<j_2} \E\bklr{M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)}}^2\\
  & = \sum_{i<j_1<j_2} \frac{1}{(n)_3} \sum_{\abs{\{k,l,m\}}=3}
  \bklr{M^{r}_{k,l}M^{s}_{k,m}}^2\\
  & \leq C_d n\beta^4.
}
To prove \eq{25}, we consider the following three cases where
$|\{i,j_1,j_2,k,l_1,l_2\}|$ is either $4$, $5$ or $6$. We will, for the
remainder of this proof, use the simplified notation
\be{
  \sum_4\kern1em := \sum_{i<j_1<j_2, k<l_1<l_2 \atop |\{i,j_1,j_2,
    k,l_1,l_2\}|=4}
}
and analogously for the cases $5$ and $6$. Let $\t{\pi}$ be an independent copy
of $\pi$.
\bes{
  &\bbbabs{\sum_4\Cov\bklr{M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)},
    M^{r}_{\pi(k), \pi(l_1)}M^{s}_{\pi(k),\pi(l_2)}} }\\
  &\quad\leq \sum_4 \babs{
    \E M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)} M^{r}_{\pi(k),
    \pi(l_1)}M^{s}_{\pi(k),\pi(l_2)}  }\\
  &\qquad + \sum_4  \babs{\E
    M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)} M^{r}_{\t{\pi}(k),
    \t{\pi}(l_1)}M^{s}_{\t{\pi}(k),\t{\pi}(l_2)}}\\
  &\quad\leq C_d n^4 \bbbklr{\frac{1}{n^4} n \beta^4+\frac{1}{n^6} n^2
    \beta^4}\leq C_d   n \beta^4,
}
where in the second inequality, we used \eq{19} and~\eq{20}.
Similarly,
\be{
  \bbbabs{\sum_5\Cov\bklr{M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)},
  M^{r}_{\pi(k), \pi(l_1)}M^{s}_{\pi(k),\pi(l_2)}}} \leq C_d n \beta^4.
}
Lastly,
\bes{
  &\bbbabs{\sum_6\Cov\bklr{M^{r}_{\pi(i), \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)},
    M^{r}_{\pi(k), \pi(l_1)}M^{s}_{\pi(k),\pi(l_2)}} } \\
  &\quad\leq \bbbabs{
    \sum_6 \E M^{r}_{\pi(i),
    \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)} M^{r}_{\pi(k),
    \pi(l_1)}M^{s}_{\pi(k), \pi(l_2)}\\
  &\kern6em \times \bklr{1-\P\bkle{|\{\pi(i), \pi(j_1), \pi(j_2), \t{\pi}(k),
    \t{\pi}(l_1),\t{\pi}(l_2)\}|= 6 }} } \\
  &\qquad+\bbbabs{ \sum_6 \E M^{r}_{\pi(i),
    \pi(j_1)}M^{s}_{\pi(i),\pi(j_2)} M^{r}_{\t{\pi}(k),
    \t{\pi}(l_1)}M^{s}_{\t{\pi}(k), \t{\pi}(l_2)} \\
  &\kern6em \times\I\bkle{|\{\pi(i), \pi(j_1), \pi(j_2), \t{\pi}(k),
\t{\pi}(l_1),
    \t{\pi}(l_2)\}|\leq 5  }}\\
  &\quad\leq C_d n \beta^4,
}
where we used \eq{19} and \eq{20} in the last step. Therefore, we have
proved
\eq{25}, and thus \eq{24}. By the same argument as in proving \eq{24}, and using
the
bounds \eq{21} and \eq{22}, we can prove
\ben{\label{26}
  \Var \E^\pi (D_{r} D_{s} D_{t})\leq \frac{ C_d \beta^6}{n}.
}
Applying the bounds \eq{23}, \eq{24} and \eq{26} in \eq{7} and observing that
$\beta \leq C_d n \beta^3$ proves the theorem.
\end{proof}

\section{Proof of main theorem} \label{sec4}

For given test function $h$, we consider the Stein equation
\ben{   \label{27}
  \D f(w)-w^t\nabla f(w)=h(w)-\E h(Z),\qquad w\in \IR^d,
}
where $\D$ denotes the Laplacian operator and $\nabla$ the gradient operator.
If $h$ is not continuous (like the indicator function of a convex set), then $f$
is not smooth enough to apply Taylor expansion to the necessary degree, so
more refined techniques are necessary. 

We follow the smoothing technique of \cite{Bentkus2003}. Recall that
$\mathcal{A}$ is the collection of all convex sets in $\IR^d$. For
$A\in\mathcal{A}$, let $h_A(x)=I_A(x)$, and define the
smoothed function
\ben{   \label{28}
  h_{A,\eps}(w) = \psi\bbbklr{\frac{d(w, A)}{\eps}},
}
where $d(w,A) = \inf_{v\in A}\abs{w-v}$ and
\ben{
  \psi(x)=
  \begin{cases}
    1, & x<0,\\
    1-2x^2, & 0\leq x<\frac{1}{2},\\
    2(1-x)^2, & \frac{1}{2} \leq x <1,\\
    0, & 1\leq x.
\end{cases}
}
Define also 
\be{
  A^\eps = \{x\in\IR^d\,:\, d(x,A)\leq \eps\},\qquad
  A^{-\eps} = \{x\in A\,:\, d(x,\IR^d\setminus A) > \eps\}
}
(note that in general $(A^{-\eps})^\eps \neq A$).

\begin{lemma}[\cite{Bentkus2003}] The
function $h_{A,\eps}$ as defined above
has the following properties:
\ban{   
  (i)&\enskip\text{$h_{A,\eps}(w)=1$ for all $w\in A$,}\label{29}\\
  (ii)&\enskip\text{$h_{A,\eps}(w)=0$ for all
                    $w\in\IR^d\setminus A^\eps$,}\label{30}\\
  (iii)&\enskip \text{$0\leq h_{A,\eps}(w) \leq 1$ for all
                     $w\in A^\eps\setminus A$,}\label{31}\\
 (iv)&\enskip \text{$|\nabla h_{A,\eps} (w)|\leq 2\eps^{-1}$ for all
                   $w\in \IR^d$,}\label{32}\\
 (v) &\enskip \text{$|\nabla h_{A,\eps}
    (v)-\nabla h_{A,\eps} (w)|\leq 8|v-w|\eps^{-2}$ for all
$v,w\in \mr$}.\label{33}
}
\end{lemma}

\begin{lemma}\label{lem4}
For any $d$-dimensional random vector $W$,
\ben{\label{34}
  d_c(\law (W), \law (Z)) \leq 4d^{1/4}\eps +
    \sup_{A\in\mathcal{A}}\babs{\E h_{A,\eps}(W)-\E h_{A,\eps}(Z)}.
}
\end{lemma}

\begin{proof}A standard argument yields that, for any $\eps>0$,
\bes{                 
  d_c(\law (W), \law (Z))
   &\leq \sup_{A\in\mathcal{A}}|\E h_{A,\eps}(W)-\E h_{A,\eps}(Z)| \\
   &\quad +\sup_{A\in \mathcal{A}} \max\{\P (Z\in A^\eps\setminus A),\P
      (Z\in A\setminus A^{-\eps})\}.
}
From \cite{Ball1993} and \cite{Bentkus2003} we have
\ben{\label{35}
  \sup_{A\in \mathcal{A}}\max \{\P (Z\in A^\eps\setminus A),\P (Z\in
    A\setminus A^{-\eps})\}
    \leq 4d^{1/4} \eps.
}
(the dependence on $d$ in \eq{34} is optimal; see \cite{Bentkus2003}).
\end{proof}


Fix now $\eps$ and a convex $A\subset \IR^d$. It can be verified directly
that
\bes{ 
  & f_{A,\eps}(w) \\
    &\quad = -\frac{1}{2}
    \int_0^1 \frac{1}{1-s} \int_{\IR^d}
    \bkle{h_{A,\eps}(\sqrt{1-s}w+\sqrt{s}z)-\E h_{A,\eps} (Z)}\phi(z)dz ds
}
is a solution to \eq{27}, where $\phi$ is the density function of the
$d$-dimensional standard normal
distribution. In what follows, we keep the dependence on $A$ and $\eps$
implicit and write $f=f_{A,\eps}$. For real-valued functions on $\IR^d$ we
will write $f_i(x)$ for $\partial f(x)/\partial x_i$, $f_{ij}(x)$ for
$\partial^2 f(x)/(\partial x_i\partial x_j)$ and so forth. 

Using this notation, we have for $1\leq i,j\leq d$ that
\besn{   \label{36}
  f_{ij} (w) & =
    -\frac{1}{2}\int_{\eps^2}^1 \frac{1}{s}
        \int_{\IR^d} h (\sqrt{1-s}w+\sqrt{s}z) \phi_{ij} (z) dzds \\
   &\quad +\frac{1}{2} \int_0^{\eps^2} \frac{1}{\sqrt{s}} \int_{\IR^d}
     h_j(\sqrt{1-s}w+\sqrt{s}z) \phi_i (z) dz ds.
}

\begin{proof}[Proof of Theorem~\ref{thm1}]
Fix $A\in\mathcal{A}$ and $\eps>0$ (to be chosen
later) and let $f=f_{A,\eps}$ be the solution to the Stein equation \eq{27}
with respect to $h=h_{A,\eps}$ as defined by \eq{28}. Let
\be{
  \kappa := d_c(\law(W),\law(Z)).
}
Adding and subtracting the corresponding terms, we have
\bes{
  &\E \bklg{\Delta f(W)- W^t\nabla f(W)} \\
  &\quad=  \E \bklg{G^t \nabla f(W')-G^t \nabla f(W)-W^t \nabla f(W)} \\
  &\qquad +\sum_{i,j=1}^d \E\bklg{(\delta_{ij}- G_{i}D_{j})f_{ij}(W)} \\
  &\qquad -\E \bbbklg{\sum_{i=1}^d G_{i} f_i(W')-\sum_{i=1}^d
  G_{i}f_i(W)-\sum_{i,j=1}^d G_{i}D_{j} f_{ij}(W)}\\
  &\quad=: R_0 + R_1 - R_2.
}
As $(W,W',G)$ is a Stein coupling, clearly $R_0=0$. 
Using \eq{36}, and the fact
that $\int_{\mr} \phi_{ij}(z)dz=0$, we have
\bes{
  R_1& =\sum_{i,j=1}^d \E \int_{\eps^2} ^1 \bbbklr{-\frac{1}{2s}} \int_{\mr} 
      \bkle{\E
    ^W (\delta_{ij} -G_i D_{j})} \\
  &\kern6em \times \bkle{h \bklr{\sqrt{1-s}W+\sqrt{s}z}-h
      \bklr{\sqrt{1-s}W}}
    \phi_{ij}(z)dzds \\
  &\quad + \sum_{i,j=1}^d \E \int_0^{\eps^2} \frac{1}{2\sqrt{s}} \int_{\mr}
    \bkle{\E^W (\delta_{ij}-G_i D_{j})} h_j \bklr{\sqrt{1-s}
    W+\sqrt{s}z} \phi_i(z) dzds.
}
Form the definition of $\kappa$ and the concentration inequality of the standard
$d$-dimensional Gaussian distribution (c.f. \eq{35}), we have
\bes{
   &\E\bklg{h \bklr{\sqrt{1-s}W+\sqrt{s}z}-h \bklr{\sqrt{1-s} W}}^2\\
  &\qquad\leq \E\bklg{ \I\bkle{d\bklr{\sqrt{1-s}W, A^\eps\setminus A}\leq
    \sqrt{s} |z|}}\\
  & \qquad\leq 4d^{1/4} \bbbklr{\frac{\eps}{\sqrt{1-s}} +
    2\sqrt{\frac{s}{1-s}}|z|} +2\kappa.
}
Using Cauchy-Schwartz's inequality, the bound \eq{32},
the simple inequality $\sqrt{a_1+a_2+a_3}\leq \sqrt{a_1}+\sqrt{a_2}+\sqrt{a_3}$
for $a_1,a_2,a_3\ge
0$, and $\int_{\mr} |z|^{1/2}|\phi_{ij}(z)|dz\leq C d^{1/4}$, we have
\bes{ 
  |R_1|
  &\leq \sum_{i,j=1}^d \sqrt{\Var \E^W (G_i D_{j})} \\
  &\qquad\times \bbbbkle{ \int_{\eps^2} ^1 \frac{1}{s} \int_{\mr}
  \bbbklr{d^{1/4}\frac{\eps}{\sqrt{1-s}}+2d^{1/4}\sqrt{\frac{s}{1-s}}|z|+\frac{
  \kappa}{2}}^{1/2}|\phi_{ij}(z)| dz ds+2 } \\
  &\leq C B_2 \bklr{
    d^{1/8}
  \eps^{1/2} |\log \eps| +d^{3/8} + \kappa^{1/2} |\log \eps| }.
}
In order to estimate $R_2$, let $U$ and $V$ be independent random
variable distributed uniformly on $[0,1]$. Using
the integration by parts formula, 
\def\thsp{\kern13em}
\ba{ 
  R_2 
  &= \sum_{i,j=1}^d \E \int_{\eps^2}^1 \bbbklr{-\frac{1}{2s}} \int_{\mr} 
  \bkle{ h\bklr{\sqrt{1-s}(W+UD)+\sqrt{s}z}\\
  &\thsp -h \bklr{\sqrt{1-s}W+\sqrt{s}z}} G_i D_{j} \phi_{ij}(z)dzds\\
  &\quad+  \sum_{i,j=1}^d \E \int_0^{\eps^2} \frac{1}{2\sqrt{s}} \int_{\mr}
  \bkle{h_j \bklr{\sqrt{1-s}(W+UD)+\sqrt{s}z}\\
  &\thsp -h_j\bklr{\sqrt{1-s}W+\sqrt{s}z}} G_i D_{j}
  \phi_i(z)dzds \\
  &= \sum_{i,j,k=1}^d \E \int_{\eps^2} ^1 \frac{\sqrt{1-s}}{2s^{3/2}}
  \int_{\mr} h \bklr{\sqrt{1-s}W +\sqrt{s}z+\sqrt{1-s} UVD }\\
  &\thsp \times UG_i D_{j} D_{k} \phi_{ijk}(z) dzds\\
  &\quad +\sum_{i,j,k=1}^d \E \int_0^{\eps^2} \frac{\sqrt{1-s}}{2s^{1/2}}
  \int_{\mr}   h_{jk} \bklr{\sqrt{1-s}W +\sqrt{s}z+\sqrt{1-s} UVD }\\
  &\thsp  \times UG_i D_{j} D_{k} \phi_i(z) dzds\\
  &=: R_{2,1}+R_{2,2}.
}
We can rewrite $R_{2,1}$ as
\def\thsp{\kern9em}
\bes{
  R_{2,1}
  &=\sum_{i,j,k=1}^d \E \int_{\eps^2}^1
  \frac{\sqrt{1-s}}{2s^{3/2}} \int_{\mr}
  \bkle{h\bklr{\sqrt{1-s}W +\sqrt{s}z+\sqrt{1-s} UVD}\\
  &\thsp  -h\bklr{\sqrt{1-s}W+\sqrt{s}z}}
  UG_i D_{j} D_{k} \phi_{ijk} (z)dzds\\
  &\quad+\sum_{i,j,k=1}^d \E \int_{\eps^2}^1
  \frac{\sqrt{1-s}}{2s^{3/2}} \int_{\mr}
  h\bklr{\sqrt{1-s}W+\sqrt{s}z}\\
  &\thsp \times
  U\bkle{\E^W(G_{i}D_{j}D_{k})-\E(G_{i}D_{j}D_{k})}\phi_{ijk} 
  (z)dzds\\
  &\quad+\sum_{i,j,k=1}^d \E \int_{\eps^2}^1
  \frac{\sqrt{1-s}}{2s^{3/2}} \int_{\mr}
  \bkle{h\bklr{\sqrt{1-s}W+\sqrt{s}z}\\
  & \thsp -h\bklr{\sqrt{1-s}Z+\sqrt{s}z}}
  U\E(G_{i}D_{j}D_{k}) \phi_{ijk}(z)dzds\\
  &\quad+\sum_{i,j,k=1}^d \E \int_{\eps^2}^1
  \frac{\sqrt{1-s}}{2s^{3/2}} \int_{\mr}
  h\bklr{\sqrt{1-s}Z+\sqrt{s}z}\\
  &\thsp\times U\E(G_{i}D_{j}D_{k}) \phi_{ijk} (z)dzds\\
  &=: R_{2,1,1}+R_{2,1,2}+R_{2,1,3}+R_{2,1,4}.
}
Now, it is straightforward to verify that for any $u,v,w,z\in \IR^d$
\besn{\label{37}
 & \sum_{i,j,k=1}^d u_i v_j w_k \phi_{ijk}(z) \\
 &\qquad = -u^t z\, v^tz\, w^tz\, \phi(z) 
        +(u^tv\, w^tz + u^tw \, v^tz + v^tw \,u^tz)\phi(z).
}
From \eq{37} and the boundedness condition \eq{5},
\def\thsp{\kern9em}
\ba{
  |R_{2,1,1}|
  &\leq  \E  \int_{\eps^2}^1 \frac{\sqrt{1-s}}{2s^{3/2}} \int_{\mr}
  \I\bkle{d\bklr{\sqrt{1-s}W+\sqrt{s}z ,A^\eps\setminus A}\leq \sqrt{1-s}
        \beta} \\
  &\thsp \times  U\bbbabs{\sum_{i,j,k=1}^d G_i D_{j} D_{k}\phi_{ijk}(z)}
  dzds \\
  &\leq \alpha \int_{\eps^2}^1 \frac{\sqrt{1-s}}{4s^{3/2}}\int_{\mr} \P
  \bkle{d\bklr{\sqrt{1-s}W+\sqrt{s}z, A^\eps \setminus A}\leq \sqrt{1-s}\beta}
    \\
  &\thsp \times \E |D|^2\bklr{3|z|+|z|^3}\phi(z)dzds\\
  &\quad +\alpha \int_{\eps^2}^1 \frac{\sqrt{1-s}}{4s^{3/2}}\int_{\mr} 
  \E\bklg{ \I
  \bkle{d\bklr{\sqrt{1-s}W+\sqrt{s}z, A^\eps \setminus A}\leq \sqrt{1-s}\beta}\\
  &\thsp \times \bklr{\E^W |D|^2-\E |D|^2}}(3|z|+|z|^3)\phi(z)dzds\\
  &\leq C d^{3/2}\alpha \E|D|^2 \eps^{-1} \bklr{\kappa +d^{1/4}
  (\beta+\eps)}+Cd^{3/2}\eps^{-1} \alpha \sqrt{\Var\E^W |D|^2}.
}
From the fact that $\sup_{i,j,k}\int_{\mr} | \phi_{ijk}(z)|dz\leq C$,
\bes{
  |R_{2,1,2}|
    &\leq C\eps^{-1} \sum_{i,j,k=1}^d \sqrt{\Var\E^W (G_{i}D_{j}D_{k})}.
}
From \eq{37},
\bes{
  |R_{2,1,3}|
    &\leq C\bklr{\kappa \eps^{-1}+d^{1/4}} \E\bklr{|G||D|^2}.
}
For $R_{2,1,4}$, applying the integration by parts formula,
\def\thsp{\kern13em}
\bes{
  R_{2,1,4}
  &= \sum_{i,j,k=1}^d \E \int_{\eps^2}^1
  \frac{-\sqrt{1-s}}{2} \int_{\mr}
   h_{ijk}(\sqrt{1-s}Z+\sqrt{s}z)\\
  &\thsp\times U\E(G_{i}D_{j}D_{k})  \phi (z)dzds\\
  &=\sum_{i,j,k=1}^d  \int_{\eps^2}^1
  \frac{-\sqrt{1-s}}{2} \int_{\mr}
   h_{ijk}(z)
  U\E(G_{i}D_{j}D_{k})  \phi (z)dzds\\
  &=\sum_{i,j,k=1}^d  \int_{\eps^2}^1
  \frac{\sqrt{1-s}}{2} \int_{\mr}
  h(z)
  U\E(G_{i}D_{j}D_{k})   \phi_{ijk} (z)dzds
}
where we pretended that the third partial derivatives of $h$ exist. This is
not a problem because we can first smooth $h$ to have third derivatives
then take the limit. Now with
\eq{37},
\be{
  |R_{2,1,4}|\leq C \E\bklr{|G||D|^2}.
}
From \eq{33} and $|\sum_{i=1}^d G_i \phi_i(z)|\leq \alpha |z|\phi(z)$,
\def\thsp{\kern13em}
\ba{
  |R_{2,2}|&\leq\frac{8}{\eps^2} \E \int_0^{\eps^2}
  \frac{\sqrt{1-s}}{2s^{1/2}} \int_{\mr} \I\bkle{d\bklr{\sqrt{1-s}W +\sqrt{s}z,
  A^\eps\setminus A}\leq \sqrt{1-s} \beta } \\
  &\thsp \times |D|^2 \bbbabs{\sum_{i=1}^d G_i  \phi_i(z)} dzds \\
  &\leq  \frac{8\alpha}{\eps^2}\int_0^{\eps^2}
  \frac{\sqrt{1-s}}{2s^{1/2}}\int_{\mr}\P\bkle{d\bklr{\sqrt{1-s}W+\sqrt{s}z,
  A^\eps  \setminus A}\leq
  \sqrt{1-s}\beta}\\
  &\thsp\times \E|D|^2 |z|\phi(z)dzds\\
  &\quad + \frac{8\alpha}{\eps^2}\int_0^{\eps^2}
  \frac{\sqrt{1-s}}{2s^{1/2}}\int_{\mr}\E
    \bklg{\I\bkle{d\bklr{\sqrt{1-s}W+\sqrt{s}z, A^\eps
  \setminus A}\leq
  \sqrt{1-s}\beta}\\
  &\thsp \times (\E^W|D|^2- \E|D|^2)} |z|\phi(z)dzds\\
  &\leq Cd^{1/2}\alpha\bbbklr{
  \E|D|^2 \bklr{\kappa \eps^{-1}+d^{1/4}\beta\eps^{-1}+d^{1/4}}+ \eps^{-1}
  \sqrt{\Var \E^W |D|^2}}.
}
Therefore,
\bes{
  |R_2|&\leq C \bbklr{d^{3/2}\alpha \E|D|^2 \eps^{-1} \bklr{\kappa
+d^{1/4}
  (\beta+\eps)}+ d^{3/2} \eps^{-1} \alpha B_1
  + \eps^{-1} B_3}.
}
Collecting the bounds and using the smoothing inequality \eq{34}, we
obtain the following recursive inequality
\besn{\label{38}
  \kappa
  &\leq C \bklg{ d^{3/2}\alpha \E|D|^2 \eps^{-1} \bklr{\kappa
    +d^{1/4} (\beta+\eps)}+d^{3/2} \eps^{-1} \alpha B_1 \\
  &\quad+ \eps^{-1} B_3 + B_2 \bklr{d^{3/8}
    +d^{1/8} \eps^{1/2} |\log \eps|+ \sqrt{\kappa} |\log \eps|}} +4d^{1/4} \eps.
}
Let
\be{
  \eps= 2C d^{3/2} \alpha \E|D|^2+\beta +d^{5/8} \alpha^{1/2} B_1^{1/2}
  +d^{1/8} B_2 +d^{-1/8}B_3^{1/2}
}
with the same constant $C$ as in \eq{38}. The theorem is proved by solving
the recursive inequality for $\kappa$ and observing that
as long as $\eps$ is smaller than an absolute constant, $\eps^{1/2}
|\log \eps| \leq C$ and $\kappa ^{1/2} |\log \eps| \leq C d^{1/8}$.
\end{proof}

\begin{proof}[Sketch of the proof for Remark~\ref{rem2}] Let $U$ and $V$ be
uniform on $[0,1]$, independent of each other and all else. Under the
conditions of Remark~\ref{rem2}, we have from Taylor expansion that
\bes{
  0 & = \lambda^{-1}\IE\bklg{f(W')-f(W)} \\
  & = \lambda^{-1}\IE\sum_{i=1}^d (W_i'-W_i) f_i(W) + 
    \lambda^{-1}\IE\sum_{i,j=1}^d U D_iD_j f_{ij} (W+UVD)\\
  & = -\IE\sum_{i=1}^d W_i f_i(W) + 
    \IE\sum_{i,j=1}^d G_iD_j f_{ij} (W)\\
  & \quad - 2\,\IE\sum_{i,j=1}^d U G_iD_j \bklr{f_{ij}(W)-f_{ij} (W+UVD)}.
}
Therefore,
\bes{
  &\E \bklg{\Delta f(W)- W^t\nabla f(W)} \\
  &\quad= \sum_{i,j=1}^d \E\bklg{(\delta_{ij}- G_{i}D_{j})f_{ij}(W)} \\
  &\qquad +2\,\IE\sum_{i,j=1}^d U G_iD_j \bklr{f_{ij}(W)-f_{ij} (W+UVD)}
  =: R'_1 - R'_2.
}
The quantity $R'_1$ is the same as $R_1$ in the proof of Theorem~\ref{thm1}.
The quantity $R'_2$ contains an additional integration step as compared to
$R_2$ of Theorem~\ref{thm1}, but can be bounded in very much the same way (up to
different constants).
\end{proof}

\section{Some Stein couplings} \label{sec5}

In this section, we describe some known coupling constructions as
multivariate Stein couplings for reference.

\subsection{Multivariate exchangeable pairs} \label{sec6}

\cite{Chatterjee2008a} and \cite{Reinert2009} introduced the exchangeable
pairs method for random vectors. These are particular Stein couplings as we
will now show. Assume
that
$(W, W')$ is an exchangeable pair of
$d$-dimensional random vectors such that 
\beqn\label{39}
  \E ^W (W'-W) = -\Lambda W
\eeqn
for some invertible $(d\times d)$-matrix $\Lambda$. It is straightforward to
check that
\be{
  (W,W',G) = \bklr{W,W',\ahalf\Lambda^{-1}(W'-W)}
}
is a Stein coupling. 

Assume $\Var(W) = \Sigma$ is positive definite. Let $\Sigma^{1/2}$ be the
unique positive-definite root of $\Sigma$, and let $\Sigma^{-1/2}$ its
corresponding unique inverse. It was shown by \cite{Reinert2009} that
exchangeability of $(W,W')$ implies symmetry of $\^\Lambda =
\Sigma^{-1/2}\Lambda\Sigma^{1/2}$. Let therefore $O$ be an orthonormal matrix
and let $L$ be a positive diagonal matrix such that $\^\Lambda = OLO^t$.
Define $\^W = O\Sigma^{-1/2}W$, $\^W' = O\Sigma^{-1/2}W'$. It follows from
\eq{39} that
\be{
  \E^{\^W} (\^W'-\^W) = -L\^W.
}
We could therefore---in principle---restrict ourselves to $(W,W')$ that are
uncorrelated with \eq{39} being true for diagonal $\Lambda$. However, it is in
practice often much easier to work with the unstandardized $W$ as
$\Sigma^{-1/2}$ and $O$ are typically  difficult calculate. 


\subsection{Multivariate size bias couplings} \label{sec7}

This coupling was considered by \cite{Goldstein1996}. Let $Y$ be a non-negative
$d$-dimensional random vector with mean $\mu$ and covariance matrix $\Sigma$.
For each $i=\{1,\ldots,d\}$, let $Y^i$ be defined in the same probability space
as $Y$ and have $Y$-size biased distribution in direction $i$, i.e.,
\be{
  \E\bklg{Y_i f(Y)}=\mu_i\E  f(Y^i)
}
for all functions $f$ such that the expectations exist. Let $K$ be uniformly
distributed over $\{1,2,\ldots,d\}$ and let $e_K$ be the $d$-dimensional unit
vector in direction $K$. Then
\be{
  (W,W',G)
%   =(\Sigma^{-1/2}(Y-\mu),\Sigma^{-1/2}(Y^{K}-\mu),\Sigma^{-1/2}\mu_{K}e_K)
  =\bklr{Y-\mu,Y^{K}-\mu,\mu_{K}e_K}
}
is a Stein coupling.

\subsection{Local dependence}\label{sec8}

A refined version of this dependence was considered by \cite{Rinott1996}. Let
$(X_i)_{i\in\mathcal{I}}$ be a collection of centered $d$-dimensional random
vectors for some finite index set $\mathcal{I}$. For each $i\in\mathcal{I}$,
assume there is a set $A_i\subset\mathcal{I}$ such that $X_i$ is independent of
$(X_j)_{i\in A^c_i}$. Let $I$ be uniformly distributed on~$\mathcal{I}$. Then
\be{
  (W,W',G) = \bbbklr{\sum_{i\in\mathcal{I}} X_i, \sum_{i\in\mathcal{I}\setminus
A_I} X_i, -nX_I}
}
is a Stein coupling. Note that our Theorem~\ref{thm1} can yield informative
bounds if the random vectors are locally dependent, but uncorrelated, in cases
where the general theorem of \cite{Rinott1996} would not yield informative
bounds. 

\section*{Acknowledgments}

We are grateful to Louis Chen for fruitful discussions that lead to this
research. We also thank Persi Diaconis for the suggestion to study the
joint distribution of inversions and descents in random permutations. 

XF was supported by NUS Research Grants C-389-000-010-101 and C-389-000-012-101.
AR was partially supported by NUS Research Grant R-155-000-098-133.

\setlength{\bibsep}{0.5ex}
\def\bibfont{\small}

% \bibliographystyle{mynatbib}
% \bibliography{literatur}

\begin{thebibliography}{22}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Aldous(1981)]{Aldous1981}
D.~J. Aldous (1981).
\newblock Representations for partially exchangeable arrays of random
  variables.
\newblock \emph{J. Multivariate Anal.} \textbf{11}, \penalty0 581--598.

\bibitem[Ball(1993)]{Ball1993}
K.~Ball (1993).
\newblock The reverse isoperimetric problem for {G}aussian measure.
\newblock \emph{Discrete Comput. Geom.} \textbf{10}, \penalty0 411--420.

\bibitem[Barbour et~al.(1989)Barbour, Karo{\'n}ski, and
  Ruci{\'n}ski]{Barbour1989}
A.~D. Barbour, M.~Karo{\'n}ski, and A.~Ruci{\'n}ski (1989).
\newblock A central limit theorem for decomposable random variables with
  applications to random graphs.
\newblock \emph{J.~Combin. Theory Ser.~B} \textbf{47}, \penalty0 125--145.

\bibitem[Bentkus(2003)]{Bentkus2003}
V.~Bentkus (2003).
\newblock On the dependence of the {B}erry-{E}sseen bound on dimension.
\newblock \emph{J. Statist. Plann. Inference} \textbf{113}, \penalty0 385--402.

\bibitem[Bhattacharya and Holmes(2010)]{Bhattacharya2010}
R.~N. Bhattacharya and S.~Holmes (2010).
\newblock An exposition of {G\"o}tze's estimation of the rate of convergence in
  the multivariate central limit theorem.
\newblock Available at \url{arxiv.org/abs/1003.4254}.

\bibitem[Borgs et~al.(2008)Borgs, Chayes, Lov{\'a}sz, S{\'o}s, and
  Vesztergombi]{Borgs2008}
C.~Borgs, J.T. Chayes, L.~Lov{\'a}sz, V.T. S{\'o}s, and K.~Vesztergombi (2008).
\newblock {Convergent sequences of dense graphs I: Subgraph frequencies, metric
  properties and testing}.
\newblock \emph{Advances in Mathematics} \textbf{219}, \penalty0 1801--1851.

\bibitem[Borgs et~al.(2012)Borgs, Chayes, Lov{\'a}sz, S{\'o}s, and
  Vesztergombi]{Borgs2012}
C.~Borgs, JT~Chayes, L.~Lov{\'a}sz, VT~S{\'o}s, and K.~Vesztergombi (2012).
\newblock {Convergent sequences of dense graphs II: Multiway cuts and
  statistical physics}.
\newblock \emph{Ann. Math.} \textbf{176}, \penalty0 151--219.

\bibitem[Chatterjee and Meckes(2008)]{Chatterjee2008a}
S.~Chatterjee and E.~Meckes (2008).
\newblock Multivariate normal approximation using exchangeable pairs.
\newblock \emph{ALEA Lat. Am. J. Probab. Math. Stat.} \textbf{4}, \penalty0
  257--283.

\bibitem[Chen and R\"ollin(2010)]{Chen2010b}
L.~H.~Y. Chen and A.~R\"ollin (2010).
\newblock Stein couplings for normal approximation.
\newblock \emph{Preprint}.
\newblock Available at \url{http://arxiv.org/abs/1003.6039}.

\bibitem[Chung et~al.(1989)Chung, Graham, and Wilson]{Chung1989}
F.~R.~K. Chung, R.~L. Graham, and R.~M. Wilson (1989).
\newblock Quasi-random graphs.
\newblock \emph{Combinatorica} \textbf{9}, \penalty0 345--362.

\bibitem[Diaconis and Janson(2008)]{Diaconis2008}
P.~Diaconis and S.~Janson (2008).
\newblock Graph limits and exchangeable random graphs.
\newblock \emph{Rend. Mat. Appl. (7)} \textbf{28}, \penalty0 33--61.

\bibitem[Fang(2012)]{Fang2012}
X.~Fang (2012).
\newblock \emph{Multivariate, combinatorial and discretized normal
  approximations by Stein's method}.
\newblock PhD thesis, National University of Singapore.

\bibitem[Fulman(2004)]{Fulman2004}
J.~Fulman (2004).
\newblock Stein's method and non-reversible {M}arkov chains.
\newblock In \emph{Stein's method: expository lectures and applications},
  volume~46 of \emph{IMS Lecture Notes Monogr. Ser.}, pages 69--77. Inst. Math.
  Statist., Beachwood, OH.

\bibitem[Goldstein and Rinott(1996)]{Goldstein1996}
L.~Goldstein and Y.~Rinott (1996).
\newblock Multivariate normal approximations by {S}tein's method and size bias
  couplings.
\newblock \emph{J.~Appl. Probab.} \textbf{33}, \penalty0 1--17.

\bibitem[G{\"o}tze(1991)]{Goetze1991}
F.~G{\"o}tze (1991).
\newblock On the rate of convergence in the multivariate {CLT}.
\newblock \emph{Ann. Probab.} \textbf{19}, \penalty0 724--739.

\bibitem[Janson and Nowicki(1991)]{Janson1991}
S.~Janson and K.~Nowicki (1991).
\newblock The asymptotic distributions of generalized {$U$}-statistics with
  applications to random graphs.
\newblock \emph{Probab. Theory Related Fields} \textbf{90}, \penalty0 341--375.

\bibitem[Lov{\'a}sz and Szegedy(2011)]{Lovasz2011}
L.~Lov{\'a}sz and B.~Szegedy (2011).
\newblock Finitely forcible graphons.
\newblock \emph{Journal of Combinatorial Theory, Series B} \textbf{101},
  \penalty0 269 -- 301.

\bibitem[Pao et~al.(2011)Pao, Coppersmith, and Priebe]{Pao2011}
H.~Pao, G.~A. Coppersmith, and C.~E. Priebe (2011).
\newblock Statistical inference on random graphs: Comparative power analyses
  via monte carlo.
\newblock \emph{Journal of Computational and Graphical Statistics} \textbf{20},
  \penalty0 395--416.

\bibitem[Rai{\v{c}}(2004)]{Raic2004}
M.~Rai{\v{c}} (2004).
\newblock A multivariate {CLT} for decomposable random vectors with finite
  second moments.
\newblock \emph{J. Theoret. Probab.} \textbf{17}, \penalty0 573--603.

\bibitem[Reinert and R{\"o}llin(2009)]{Reinert2009}
G.~Reinert and A.~R{\"o}llin (2009).
\newblock Multivariate normal approximation with {S}tein's method of
  exchangeable pairs under a general linearity condition.
\newblock \emph{Ann. Probab.} \textbf{37}, \penalty0 2150--2173.

\bibitem[Rinott and Rotar{$'$}(1996)]{Rinott1996}
Y.~Rinott and V.~Rotar{$'$} (1996).
\newblock A multivariate {CLT} for local dependence with {$n\sp {-1/2}\log n$}
  rate and applications to multivariate graph related statistics.
\newblock \emph{J. Multivariate Anal.} \textbf{56}, \penalty0 333--350.

\bibitem[Zhao et~al.(1997)Zhao, Bai, Chao, and Liang]{Zhao1997}
L.~Zhao, Z.~Bai, C.-C. Chao, and W.-Q. Liang (1997).
\newblock Error bound in a central limit theorem of double-indexed permutation
  statistics.
\newblock \emph{Ann. Statist.} \textbf{25}, \penalty0 2210--2227.

\end{thebibliography}


\end{document}

1206.6586.extracted_bib
\begin{thebibliography}{22}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Aldous(1981)]{Aldous1981}
D.~J. Aldous (1981).
\newblock Representations for partially exchangeable arrays of random
  variables.
\newblock \emph{J. Multivariate Anal.} \textbf{11}, \penalty0 581--598.

\bibitem[Ball(1993)]{Ball1993}
K.~Ball (1993).
\newblock The reverse isoperimetric problem for {G}aussian measure.
\newblock \emph{Discrete Comput. Geom.} \textbf{10}, \penalty0 411--420.

\bibitem[Barbour et~al.(1989)Barbour, Karo{\'n}ski, and
  Ruci{\'n}ski]{Barbour1989}
A.~D. Barbour, M.~Karo{\'n}ski, and A.~Ruci{\'n}ski (1989).
\newblock A central limit theorem for decomposable random variables with
  applications to random graphs.
\newblock \emph{J.~Combin. Theory Ser.~B} \textbf{47}, \penalty0 125--145.

\bibitem[Bentkus(2003)]{Bentkus2003}
V.~Bentkus (2003).
\newblock On the dependence of the {B}erry-{E}sseen bound on dimension.
\newblock \emph{J. Statist. Plann. Inference} \textbf{113}, \penalty0 385--402.

\bibitem[Bhattacharya and Holmes(2010)]{Bhattacharya2010}
R.~N. Bhattacharya and S.~Holmes (2010).
\newblock An exposition of {G\"o}tze's estimation of the rate of convergence in
  the multivariate central limit theorem.
\newblock Available at \url{arxiv.org/abs/1003.4254}.

\bibitem[Borgs et~al.(2008)Borgs, Chayes, Lov{\'a}sz, S{\'o}s, and
  Vesztergombi]{Borgs2008}
C.~Borgs, J.T. Chayes, L.~Lov{\'a}sz, V.T. S{\'o}s, and K.~Vesztergombi (2008).
\newblock {Convergent sequences of dense graphs I: Subgraph frequencies, metric
  properties and testing}.
\newblock \emph{Advances in Mathematics} \textbf{219}, \penalty0 1801--1851.

\bibitem[Borgs et~al.(2012)Borgs, Chayes, Lov{\'a}sz, S{\'o}s, and
  Vesztergombi]{Borgs2012}
C.~Borgs, JT~Chayes, L.~Lov{\'a}sz, VT~S{\'o}s, and K.~Vesztergombi (2012).
\newblock {Convergent sequences of dense graphs II: Multiway cuts and
  statistical physics}.
\newblock \emph{Ann. Math.} \textbf{176}, \penalty0 151--219.

\bibitem[Chatterjee and Meckes(2008)]{Chatterjee2008a}
S.~Chatterjee and E.~Meckes (2008).
\newblock Multivariate normal approximation using exchangeable pairs.
\newblock \emph{ALEA Lat. Am. J. Probab. Math. Stat.} \textbf{4}, \penalty0
  257--283.

\bibitem[Chen and R\"ollin(2010)]{Chen2010b}
L.~H.~Y. Chen and A.~R\"ollin (2010).
\newblock Stein couplings for normal approximation.
\newblock \emph{Preprint}.
\newblock Available at \url{http://arxiv.org/abs/1003.6039}.

\bibitem[Chung et~al.(1989)Chung, Graham, and Wilson]{Chung1989}
F.~R.~K. Chung, R.~L. Graham, and R.~M. Wilson (1989).
\newblock Quasi-random graphs.
\newblock \emph{Combinatorica} \textbf{9}, \penalty0 345--362.

\bibitem[Diaconis and Janson(2008)]{Diaconis2008}
P.~Diaconis and S.~Janson (2008).
\newblock Graph limits and exchangeable random graphs.
\newblock \emph{Rend. Mat. Appl. (7)} \textbf{28}, \penalty0 33--61.

\bibitem[Fang(2012)]{Fang2012}
X.~Fang (2012).
\newblock \emph{Multivariate, combinatorial and discretized normal
  approximations by Stein's method}.
\newblock PhD thesis, National University of Singapore.

\bibitem[Fulman(2004)]{Fulman2004}
J.~Fulman (2004).
\newblock Stein's method and non-reversible {M}arkov chains.
\newblock In \emph{Stein's method: expository lectures and applications},
  volume~46 of \emph{IMS Lecture Notes Monogr. Ser.}, pages 69--77. Inst. Math.
  Statist., Beachwood, OH.

\bibitem[Goldstein and Rinott(1996)]{Goldstein1996}
L.~Goldstein and Y.~Rinott (1996).
\newblock Multivariate normal approximations by {S}tein's method and size bias
  couplings.
\newblock \emph{J.~Appl. Probab.} \textbf{33}, \penalty0 1--17.

\bibitem[G{\"o}tze(1991)]{Goetze1991}
F.~G{\"o}tze (1991).
\newblock On the rate of convergence in the multivariate {CLT}.
\newblock \emph{Ann. Probab.} \textbf{19}, \penalty0 724--739.

\bibitem[Janson and Nowicki(1991)]{Janson1991}
S.~Janson and K.~Nowicki (1991).
\newblock The asymptotic distributions of generalized {$U$}-statistics with
  applications to random graphs.
\newblock \emph{Probab. Theory Related Fields} \textbf{90}, \penalty0 341--375.

\bibitem[Lov{\'a}sz and Szegedy(2011)]{Lovasz2011}
L.~Lov{\'a}sz and B.~Szegedy (2011).
\newblock Finitely forcible graphons.
\newblock \emph{Journal of Combinatorial Theory, Series B} \textbf{101},
  \penalty0 269 -- 301.

\bibitem[Pao et~al.(2011)Pao, Coppersmith, and Priebe]{Pao2011}
H.~Pao, G.~A. Coppersmith, and C.~E. Priebe (2011).
\newblock Statistical inference on random graphs: Comparative power analyses
  via monte carlo.
\newblock \emph{Journal of Computational and Graphical Statistics} \textbf{20},
  \penalty0 395--416.

\bibitem[Rai{\v{c}}(2004)]{Raic2004}
M.~Rai{\v{c}} (2004).
\newblock A multivariate {CLT} for decomposable random vectors with finite
  second moments.
\newblock \emph{J. Theoret. Probab.} \textbf{17}, \penalty0 573--603.

\bibitem[Reinert and R{\"o}llin(2009)]{Reinert2009}
G.~Reinert and A.~R{\"o}llin (2009).
\newblock Multivariate normal approximation with {S}tein's method of
  exchangeable pairs under a general linearity condition.
\newblock \emph{Ann. Probab.} \textbf{37}, \penalty0 2150--2173.

\bibitem[Rinott and Rotar{$'$}(1996)]{Rinott1996}
Y.~Rinott and V.~Rotar{$'$} (1996).
\newblock A multivariate {CLT} for local dependence with {$n\sp {-1/2}\log n$}
  rate and applications to multivariate graph related statistics.
\newblock \emph{J. Multivariate Anal.} \textbf{56}, \penalty0 333--350.

\bibitem[Zhao et~al.(1997)Zhao, Bai, Chao, and Liang]{Zhao1997}
L.~Zhao, Z.~Bai, C.-C. Chao, and W.-Q. Liang (1997).
\newblock Error bound in a central limit theorem of double-indexed permutation
  statistics.
\newblock \emph{Ann. Statist.} \textbf{25}, \penalty0 2210--2227.

\end{thebibliography}