text:
\section{Introduction and motivation}
\label{sct:intro}

This article presents concentration inequalities for randomly permuted sums defined by
$Z_n=\sum_{i=1}^{n} a_{i,\ensuremath{{\Pi_n}}(i)},$ where $\ac{a_{i,j}}_{1\leq i,j\leq n}$ are real numbers, and $\ensuremath{{\Pi_n}}$ is a uniformly distributed random permutation of the set $\ac{1,\dots,n}$. Initially motivated by hypothesis testing in the non-parametric framework (see \cite{WaldWolfowitz1944} for instance), such sums have been largely studied from an asymptotic point of view in the literature.
A first combinatorial central limit theorem is proved by Wald and Wolfowitz in \cite{WaldWolfowitz1944}, in the particular case when the real numbers $a_{i,j}$ are of a product form $b_i \times c_j$, under strong assumptions that have been released for instance by Noether \cite{Noether1949}.
Then, Hoeffding obtains stronger results in such product case, and generalizes those results to not necessarily product type real terms $a_{i,j}$ in \cite{Hoeffding1951}. More precisely, he considers
\begin{equation}
\label{eq:def_dij}
d_{i,j} = a_{i,j} - \frac{1}{n} \sum_{k=1}^n a_{k,j} -\frac{1}{n} \sum_{l=1}^n a_{i,l} + \frac{1}{n^2} \sum_{k,l=1}^n a_{k,l}.
\end{equation}
In particular, $\var{Z_n} = \frac{1}{n-1}\sum_{i=1}^n d_{i,j}^2$.
Then he proves (see \cite[Theorem 3]{Hoeffding1951}) that, if
\begin{equation}
\label{eq:cond_Hoeffding-mieux}
\lim_{n\to+\infty} \frac{\frac{1}{n}\sum_{1\leq i,j \leq n} d_{i,j}^r}{\pa{\frac{1}{n}\sum_{i,j=1}^n d_{i,j}^2}^{r/2}} = 0, \quad \mbox{for some }r>2,
\end{equation}
then the distribution of $Z_n = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$ is asymptotically normal, that is, for all $x$ in $\ensuremath{\mathds{R}}$,
$$ \lim_{n\to +\infty} \proba{Z_n - \esp{Z_n} \leq x \sqrt{\var{Z_n}}} = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^x e^{-\frac{y^2}{2}} dy.$$
He also considers a stronger (in the sense that it implies \eqref{eq:cond_Hoeffding-mieux}), but simpler condition in \cite[Theorem 3]{Hoeffding1951}, precisely
\begin{equation}
\label{eq:cond_Hoeffding-pareil}
\frac{\max_{1\leq i,j\leq n} \ac{\abs{d_{i,j}}}}{\sqrt{\frac{1}{n} \sum_{i,j=1}^n d_{i,j}^2}}\cv{n\to+\infty} 0,
\end{equation}
under which such an asymptotic Gaussian limit holds.
Similar results have been obtained later, for instance by Motoo \cite{Motoo1956}, under the following Lindeberg-type condition that is for all $\varepsilon >0$,
\begin{equation}
\label{eq:cond_Lindeberg}
\lim_{n\to+\infty} \sum_{1\leq i,j\leq n} \pa{\frac{d_{i,j}}{d}}^2 \1{\abs{\frac{d_{i,j}}{d}}>\varepsilon} = 0,
\end{equation}
where $d^2 = n^{-1} \sum_{1\leq i,j\leq n} d_{i,j}^2$.
In particular, he proves in \cite{Motoo1956} that such Lindeberg-type condition is weaker than Hoeffding's ones in the sense that \eqref{eq:cond_Lindeberg} is implied by \eqref{eq:cond_Hoeffding-mieux} (and thus by \eqref{eq:cond_Hoeffding-pareil}). A few years later, Hájek \cite{Hajek1961} proves in the product case, that the condition \eqref{eq:cond_Lindeberg} is in fact necessary.
A simpler proof of the sufficiency of the Lindeberg-type condition is given by Schneller \cite{Schneller1988} based on Stein's method.

Afterwards, the next step was to study the convergence of the conditional distribution when the terms $a_{i,j}$ in the general case, or $b_i\times c_j$ in the product case, are random. Notably, Dwass studies in \cite{Dwass1955} the limit of the randomly permuted sum in the product case, where only the $c_j$'s are random, and proves that the conditional distribution given the $c_j$'s converges almost surely (a.s.) to a Gaussian distribution. Then, Shapiro and Hubert \cite{ShapiroHubert1979} generalized this study to weighted $U$-statistics of the form $\sum_{i\neq j}b_{i,j} h(X_i,X_j)$ where the $X_i$'s are independent and identically distributed (i.i.d.) random variables. In a first time, they show some a.s. asymptotic normality of this statistic. In a second time, they complete Jogdeo's \cite{Jogdeo1968} work in the deterministic case, proving asymptotic normality of permuted statistics based on the previous weighted $U$-statistic. More precisely, they consider the rank statistic $\sum_{i\neq j}b_{i,j} h(X_{R_i},X_{R_j})$, where $R_i$ is the rank of $V_i$ in a sample $V_1,\dots,V_n$ of i.i.d. random variables with a continuous distribution function. In particular, notice that considering such rank statistics is equivalent to considering uniformly permuted statistics.
In \cite{AlbertBouretFromontReynaud2015}, the previous combinatorial central limit theorems is generalized to permuted sums of non-i.i.d. random variables $\sum_{i=1}^n Y_{i,\ensuremath{{\Pi_n}}(i)}$, for particular forms of random variables $Y_{i,j}$
The main difference with the previous results comes from the fact that the random variables $Y_{i,j}$ are not necessarily exchangeable.

Hence, the asymptotic behavior of permuted sums have been vastly investigated in the literature, allowing to deduce good properties for permutation tests based on such statistics, like the asymptotic size, or the power (see for instance \cite{Romano1989} or \cite{AlbertBouretFromontReynaud2015}). Yet, such results are purely asymptotic, while, in many application fields, such as neurosciences for instance as described in \cite{AlbertBouretFromontReynaud2015}, few exploitable data are available. Hence, such asymptotic results may not be sufficient. This is why a non-asymptotic approach is preferred here, leading to concentration inequalities.

\paragraph{}
Concentration inequalities have been vastly investigated in the literature, and the interested reader can refer to the books of Ledoux \cite{Ledoux2005}, Massart \cite{Massart2007}, or the more recent one of Boucheron, Lugosi, and Massart \cite{BoucheronLugosiMassart2013} for some overall reviews. Yet in many cases, they provide precise tail bounds for well-behaved functions or sums of independent random variables. For instance, let us recall the classical Bernstein inequality stated for instance in \cite[Proposition 2.9 and Corollary 2.10]{Massart2007}.
\begin{thm}[Bernstein's inequality, Massart 2007]
\label{thm:Bernstein_ineq_Massart07}
Let $X_1,\dots,X_n$ be independent real valued random variables. Assume that there exists some positive numbers $v$ and $c$ such that
$$
\sum_{i=1}^n \esp{X_i^2}\leq v,
$$
and for all integers $k\geq 3$,
$$
\sum_{i=1}^n \esp{{(X_i)}_+^k} \leq \frac{k!}{2} vc^{k-2},
$$
where $(\cdot)_+=\max\{\cdot,0\}$ denotes the positive part.

Let $S =\sum_{i=1}^n (X_i-\esp{X_i})$, then for every positive $x$,
\begin{equation}
\label{eq:ineq_Bernstein_stat}
\proba{S\geq \sqrt{2vx} + cx} \leq e^{-x}.
\end{equation}
Moreover, for any positive $x$,
\begin{equation}
\label{eq:ineq_Bernstein_proba}
\proba{S\geq x} \leq \exp\pa{-\frac{x^2}{2(v+cx)}}.
\end{equation}
\end{thm}
Notice that both forms of Bernstein's inequality appear in the literature. Yet, due to its form, \eqref{eq:ineq_Bernstein_stat} is rather preferred in statistics, even though \eqref{eq:ineq_Bernstein_proba} is more classical.

The work in this article is based on the pioneering work of Talagrand (see \cite{Talagrand1995} for a review) who investigates the concentration of measure phenomenon for product measures. Of main interest here, he proved the following inequality for random permutations in \cite[Theorem~5.1]{Talagrand1995}.
\begin{thm}[Talagrand, 1995]
\label{thm:Talagrand}
Denote by $\Sn{n}$ the set of all permutations of $\ac{1,\dots,n}$. Define for any subset $A\subset \Sn{n}$, and permutation $\ensuremath{{\pi_n}}\in\Sn{n}$,
$$U_A(\ensuremath{{\pi_n}}) = \ac{s \in \{0,1\}^n \ ;\ \exists \tau \in A \mbox{ such that } \forall 1\leq i\leq n,\ s_i=0 \implies \tau(i)=\ensuremath{{\pi_n}}(i)}.$$
Then, consider $V_A(\ensuremath{{\pi_n}})=\operatorname{ConvexHull}\pa{U_A(\ensuremath{{\pi_n}})}$, and
$$f(A,\ensuremath{{\pi_n}}) = \min\ac{\sum_{i=1}^n v_i^2\ ;\ v=\pa{v_i}_{1\leq i\leq n}\in V_A(\ensuremath{{\pi_n}})}.$$

Then, if $P_n$ denotes the uniform distribution on $\Sn{n}$,
$$\int_{\Sn{n}} e^{\frac{1}{16} f(A,\ensuremath{{\pi_n}})}dP_n(\ensuremath{{\pi_n}}) \leq \frac{1}{P_n(A)}.$$

Therefore, by Markov's inequality, for all $t>0$,
\begin{equation}
\label{eq:Talagrand-Markov}
P_n\pa{\ensuremath{{\pi_n}}\ ;\ f(A,\ensuremath{{\pi_n}}) \geq t^2} \leq \frac{e^{-t^2/16}}{P_n(A)}.
\end{equation}
\end{thm}

This result on random permutations is fundamental, and is a key point to many other non-asymptotic works on random permutations.
Among them emerges McDiarmid's article \cite{McDiarmid2002} in which he derives from Talagrand's inequality, exponential concentration inequalities around the median for randomly permuted functions of the observation under Lipschitz-type conditions and applied to randomized methods for graph coloring.
More recently, Adamczak et al. obtained in \cite{AdamczakChafaiWolff2014} some concentration inequality under convex-Lipschitz conditions when studying the empirical spectral distribution of random matrices.
In particular, they prove the following Theorem (precisely \cite[Theorem 3.1]{AdamczakChafaiWolff2014}).
\begin{thm}[Adamczak, Chafai and Wolff, 2014]
\label{thm:AdamczakChafaiWolff}
Consider $x_1,\ldots,x_n$ in $[0,1]$ and let $\varphi:[0,1]^n \to \ensuremath{\mathds{R}}$ be an $L$-Lipschitz convex function. Let $\ensuremath{{\Pi_n}}$ be a random uniform permutation of the set $\ac{1,\dots,n}$ and denote $Y=\varphi\!\pa{x_{\ensuremath{{\Pi_n}}(1)},\dots, x_{\ensuremath{{\Pi_n}}(n)}}$.
Then, there exists some positive absolute constant $c$ such that, for all $t>0$,
$$\proba{Y-\esp{Y}\geq t} \leq 2\exp\pa{-\frac{ct^2}{L^2}}.$$
\end{thm}

Yet, the Lispchitz assumptions may be very restrictive and may not be satisfied by the functions considered in the application fields (see Section \ref{sct:motivstat} for instance).
Hence, the idea is to exploit the attractive form of a sum.
Based on Stein's method, initially introduced to study the Gaussian behavior of sums of dependent random variables, Chatterjee studies permuted sums of non-negative numbers in \cite{Chatterjee2007}. He obtains in \cite[Proposition 1.1]{Chatterjee2007} the following first Bernstein-type concentration inequality for non-negative terms around the mean.
\begin{thm}[Chatterjee, 2007]
\label{thm:Chatterjee2007}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be a collection of numbers from $[0,1]$.
Let $Z_n = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$, where $\ensuremath{{\Pi_n}}$ is drawn from the uniform distribution over the set of all permutations of $\ac{1,\dots,n}$. Then, for any $t\geq 0$,
\begin{equation}
\label{eq:Chatterjee2007}
\proba{\abs{Z_n-\esp{Z_n}}\geq t} \leq 2 \exp\pa{-\frac{t^2}{4\esp{Z_n} + 2t}}.
\end{equation}
\end{thm}
Notice that because of the expectation term in the right-hand side of \eqref{eq:Chatterjee2007}, the link with Hoeffding's combinatorial central limit theorem (for instance) is not so clear. \\

In \cite[Theorem 4.3]{BercuDelyonRio2015}, this result is sharpened in the sense that this expectation term is replaced by a variance term, allowing us to provide a non-asymptotic version of such combinatorial central limit theorem. This result is moreover generalized to any real numbers (not necessarily non-negative).
More precisely, based on martingale theory, they prove the following result.

\begin{thm}[Bercu, Delyon and Rio, 2015]
\label{thm:BercuDelyonRio2015}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be an array of real numbers from $[-m_a,m_a]$.
Let $Z_n = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$, where $\ensuremath{{\Pi_n}}$ is drawn from the uniform distribution over the set of all permutations of $\ac{1,\dots,n}$. Then, for any $t> 0$,
\begin{equation}
\label{eq:BercuDelyonRio2015}
\proba{\abs{Z_n-\esp{Z_n}}\geq t} \leq 4 \exp\pa{-\frac{t^2}{16(\theta \frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2 + m_a t/3)}},
\end{equation}
where $\displaystyle\theta=\frac{5}{2} \ln(3) - \frac{2}{3}.$
\end{thm}
In this work, we obtain a similar result (up to constants) but based on a completely different approach. Moreover, this approach provides a direct proof for a concentration inequality of a permuted sum around its median.

\paragraph{}
The present work is organized as follows. In Section \ref{sct:conc_ineq} are formulated the main results.
Section \ref{sct:sum_pos_case} is devoted to the permuted sums of non-negative numbers. Based on Talagrand's result, a first rough concentration inequality for the square root of permuted sum is obtained in Lemma \ref{lm:concRac}. Then by iterating the previous analysis and plugging this first inequality, a general concentration of permuted sums around their median is obtained in Proposition \ref{prop:concPosMed}. Finally, the concentration inequality of Proposition \ref{prop:concPosMoy} around the mean is deduced. In Section \ref{sct:sum_general_case}, the previous inequalities are generalized to general permuted sums of not necessarily non-negative terms in Theorem \ref{thm:concQcqMoy}.
Section \ref{sct:applitestindep} presents an application to the study of non-asymptotic properties of a permutation independence test in Statistics. In particular, a sharp control of the critical value of the test is deduced from the main result.
The proofs are detailed in Section \ref{sct:proofs}.
Finally, Appendix~\ref{sct:cond_Chebychev_Hoeffding_gen} contains technical results for the non-asymptotic control of the second kind error rate of the permutation test introduced in Section \ref{sct:applitestindep}.

\section{Bernstein-type concentration inequalities for permuted sums}
\label{sct:conc_ineq}

Let us first introduce some general notation.
In the sequel, denote by $\Sn{n}$ the set of permutations of $\ac{1,2,\ldots,n}$.
For all collection of real numbers $\ac{a_{i,j}}_{1\leq i,j\leq n}$, and for each $\ensuremath{{\pi_n}}$ in $\Sn{n}$, consider the permuted sum
$$Z_n(\ensuremath{{\pi_n}})=\sum_{i=1}^n a_{i,\ensuremath{{\pi_n}}(i)}.$$

Let $\ensuremath{{\Pi_n}}$ be a random uniform permutation in $\Sn{n}$, and $Z_n:=Z_n(\ensuremath{{\Pi_n}})$.
Denote $\med{Z_n}$ its median, that is which satisfies
$$\proba{Z_n\geq \med{Z_n}} \geq 1/2\quad \mbox{and}\quad \proba{Z_n\leq \med{Z_n}}\geq 1/2. $$

This study is divided in two steps. The first one is restrained to non-negative terms. The second one extends the previous results to general terms, based on a trick involving both non-negative and negative parts.

\subsection{Concentration of permuted sums of non-negative numbers}
\label{sct:sum_pos_case}

In the present section, the collection of numbers $\ac{a_{i,j}}_{1\leq i,j\leq n}$ is assumed to be non-negative.
The proof of the concentration inequality around the median in Proposition \ref{prop:concPosMed} needs a preliminary step which is presented in Lemma \ref{lm:concRac}.
It provides concentration inequality for the square root of the sum.
It allows us then by iterating the same argument, and plugging the obtained inequality to the square root of the sum of the squares, namely $\sqrt{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}$, to be able to sharpen Chatterjee's concentration inequality \eqref{eq:Chatterjee2007}.

\begin{lm}
\label{lm:concRac}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be a collection of non-negative numbers, and $\ensuremath{{\Pi_n}}$ be a random uniform permutation in $\Sn{n}$. Consider $Z_n=\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$.
Then, for all $t>0$,
\begin{equation}
\label{eq:concRac+}
\proba{\sqrt{Z_n} \geq \sqrt{\med{Z_n}} + t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 2 e^{-t^2/16},
\end{equation}
and
\begin{equation}
\label{eq:concRac-}
\proba{\sqrt{Z_n} \leq \sqrt{\med{Z_n}} - t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 2 e^{-t^2/16}.
\end{equation}
In particular, one obtains the following two-sided concentration for the square root of a randomly permuted sum of non-negative numbers,
$$\proba{\abs{\sqrt{Z_n} - \sqrt{\med{Z_n}}} > t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 4 e^{-t^2/16}.$$
\end{lm}

The idea of the proof is the same that the one of Adamczak et al. in \cite[Theorem 3.1]{AdamczakChafaiWolff2014}, but with a sum instead of a convex Lipschitz function.
In a similar way, it is based on Talagrand's inequality for random permutations recalled in Theorem \ref{thm:Talagrand}.

\paragraph{}
In the following are presented two concentration inequalities in the non-negative case; the first one around the median, and the second one around the mean. It is well known that both are equivalent up to constants, but here, both are detailed in order to give the order of magnitude of the constants. The transition from the median to the mean can be obtained thanks to Ledoux' trick in the proof of \cite[Proposition 1.8]{Ledoux2005} allowing to reduce exponential concentration inequalities around any constant $m$ (corresponding in our case to $\med{Z_n}$) to similar inequalities around the mean. This trick consists in using the exponentially fast decrease around $m$ to upper bound the difference between $m$ and the mean. Yet, this approach leads to drastic multiplicative constants (of the order $8e^{16\pi}$ as shown in \cite{Albert2015PhD}). Better constants can be deduced from the following lemma.
\begin{lm}
\label{lm:ineqEspMedVar}
For any real valued random variable $X$,
$$\abs{\esp{X}-\med{X}} \leq \sqrt{\var{X}}.$$
\end{lm}

In particular, we obtain the following result.
\begin{prop}
\label{prop:concPosMed}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be a collection of non-negative numbers and $\ensuremath{{\Pi_n}}$ be a random uniform permutation in $\Sn{n}$. Consider $Z_n=\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$.
Then, for all $x>0$,
\begin{equation}
\label{eq:concPosMed}
\proba{\abs{Z_n - \med{Z_n}} > \sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}x} + x\max_{1\leq i,j\leq n}\ac{a_{i,j}}}\leq 8 \exp\pa{\frac{-x}{16}}.
\end{equation}
\end{prop}

Since in many applications, the concentration around the mean is more adapted, the following proposition shows that one may obtain a similar behavior around the mean, at the cost of higher constants.

\begin{prop}
\label{prop:concPosMoy}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be a collection of non-negative numbers, and $\ensuremath{{\Pi_n}}$ be a random uniform permutation in $\Sn{n}$. Consider $Z_n=\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$.

Then, for all $x>0$,
\begin{equation}
\label{eq:concPosMoy}
\proba{\abs{Z_n-\esp{Z_n}}\geq 2\sqrt{\pa{\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2}x} + \max_{1\leq i,j\leq n} \ac{a_{i,j}} x}\leq 8e^{1/16} \exp\pa{-\frac{x}{16}}.
\end{equation}
\end{prop}

This concentration inequality is called a Bernstein-type inequality restricted to non-negative sums, due to its resemblance to the standard Bernstein inequality, as recalled in Theorem \ref{thm:Bernstein_ineq_Massart07}. The main difference here lies in the fact that the random variables in the sum are not independent.
Moreover, this inequality implies a more popular form of Bernstein's inequality stated in Corollary \ref{coro:concPosMoy}.
\begin{coro}
\label{coro:concPosMoy}
With the same notation and assumptions as in Proposition \ref{prop:concPosMoy}, for all $t>0$,
\begin{equation}
\label{eq:concPosMoy2}
\proba{\abs{Z_n-\esp{Z_n}}\geq t}\leq 8e^{1/16} \exp\pa{\frac{-t^2}{16\pa{4\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2 + 2\max_{1\leq i,j\leq n} \ac{a_{i,j}} t}}}.
\end{equation}
\end{coro}

\emph{Comment:}
Recall Chatterjee's result in \cite[Proposition 2.1]{Chatterjee2007}, quoted in Theorem \ref{thm:Chatterjee2007}, which can easily be rewritten with our notation, and for a collection of non-negative numbers not necessarily in $[0,1]$, by
$$\forall t>0, \quad \proba{\abs{Z_n-\esp{Z_n}}\geq t}\leq 2\exp\pa{\frac{-t^2}{4M_a\frac{1}{n}\sum_{i,j=1}^n a_{i,j} + 2M_a t}},$$
where $M_a$ denotes the maximum $\max_{1\leq i,j\leq n} \ac{a_{i,j}}$.
As mentioned in \cite{BercuDelyonRio2015}, the inequality in \eqref{eq:concPosMoy2} is sharper up to constants, thanks to the quadratic term since $\sum_{i,j=1}^n a_{i,j}^2 \leq M_a \sum_{i,j=1}^n a_{i,j}$ always holds.

\subsection{Concentration of permuted sums in the general case}
\label{sct:sum_general_case}

In this section, the collection of numbers $\ac{a_{i,j}}_{1\leq i,j\leq n}$ is no longer assumed to be non-negative. The following general concentration inequality for randomly permuted sums directly derives from Proposition \ref{prop:concPosMoy}.
\begin{thm}
\label{thm:concQcqMoy}
Let $\ac{a_{i,j}}_{1\leq i,j\leq n}$ be a collection of any real numbers, and $\ensuremath{{\Pi_n}}$ be a random uniform permutation in $\Sn{n}$. Consider $Z_n=\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}$.
Then, for all $x>0$,
\begin{equation}
\proba{\abs{Z_n-\esp{Z_n}}\geq 2\sqrt{2\pa{\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2}x} + 2\max_{1\leq i,j\leq n} \ac{\abs{a_{i,j}}} x}\leq 16e^{1/16} \exp\pa{-\frac{x}{16}}.
\end{equation}
\end{thm}

Once again, the obtained inequality is a Bernstein-type inequality.
Moreover, it is also possible to obtain a more popular form of Bernstein-type inequalities applying the same trick based on the non-negative and the negative parts from Corollary \ref{coro:concPosMoy}.
\begin{coro}
\label{coro:concQcqMoy}
With the same notation as in Theorem \ref{thm:concQcqMoy}, for all $t>0$,
\begin{equation*}
\proba{\abs{Z_n-\esp{Z_n}}\geq t}\leq 16e^{1/16} \exp\pa{\frac{-t^2}{256\pa{\var{Z_n} + \max_{1\leq i,j\leq n} \ac{\abs{a_{i,j}}} t}}}.
\end{equation*}
\end{coro}

\emph{Comments:} One recovers a Gaussian behavior of the centered permuted sum obtained by Hoeffding in \cite[Theorem 3]{Hoeffding1951} under the same assumptions.
Indeed, in the proof of Corollary \ref{coro:concQcqMoy}, one obtains the following intermediate result (see \eqref{eq:concQcqMoyHoeffding}), that is
$$\proba{\abs{Z_n-\esp{Z_n}}\geq t}\leq 16e^{1/16} \exp\pa{\frac{-t^2}{64\pa{4\frac{1}{n}\sum_{i,j=1}^n d_{i,j}^2 + \max_{1\leq i,j\leq n} \ac{\abs{d_{i,j}}} t}}},$$
where the $d_{i,j}$'s are defined in \eqref{eq:def_dij}.
Yet, $\var{Z_n}=\frac{1}{n-1}\sum_{i,j=1}^n d_{i,j}^2$ (see \cite[Theorem 2]{Hoeffding1951}).
Hence, applying this inequality to $t=x\sqrt{\var{Z_n}} \geq x\sqrt{n^{-1}\sum_{i,j=1}^n d_{i,j}^2}$ for $x>0$ leads to
\begin{equation*}
\proba{\abs{Z_n-\esp{Z_n}}\geq x\sqrt{\var{Z_n}}}\leq 16e^{1/16} \exp\pa{\frac{-x^2}{256 \pa{1 + \frac{\max_{1\leq i,j\leq n} \ac{\abs{d_{i,j}}}}{\sqrt{\frac{1}{n} \sum_{i,j=1}^n d_{i,j}^2}} x}}},
\end{equation*}
Hence, under Hoeffding's simpler condition \eqref{eq:cond_Hoeffding-pareil}, namely
$$\lim_{n\to+\infty} \frac{\max_{1\leq i,j \leq n} d_{i,j}^2}{\frac{1}{n}\sum_{i,j=1}^n d_{i,j}^2} = 0, $$
one recovers,
$$\lim_{n\to+\infty} \proba{\abs{Z_n-\esp{Z_n}}\geq x\sqrt{\var{Z_n}}} \leq 16e^{1/16} e^{-x^2/256},$$
which is a Gaussian tail that is, up to constants, close in spirit to the one obtained by Hoeffding in \cite[Theorem 3]{Hoeffding1951}.

\section{Application to independence testing}
\label{sct:applitestindep}
\subsection{Statistical motivation}
\label{sct:motivstat}

Let $\ensuremath{\mathcal{X}}$ represent a separable set.
Given an i.i.d. $n$-sample $\ensuremath{\mathds{X}}_n = (X_1,\dots,X_n)$, where each $X_i$ is a couple $(X_i^1,X_i^2)$ in $\ensuremath{\mathcal{X}}^2$ with distribution $P$ of marginals $P^1$ and $P^2$, we aim at testing
\begin{center}
the null hypothesis $(\ensuremath{\mathcal{H}}_0)$ "$P=P^1\otimes P^2$" against the alternative $(\ensuremath{\mathcal{H}}_1)$ "$P\neq P^1\otimes P^2$".
\end{center}
The considered test statistic is defined by
\begin{equation}
\label{eq:def_stat_T}
T_\delta(\ensuremath{\mathds{X}}_n) = \frac{1}{n-1} \pa{\sum_{i=1}^n \varphi_\delta (X_i^1,X_i^2) -\frac{1}{n} \sum_{i,j=1}^n \varphi_\delta (X_i^1,X_j^2)},
\end{equation}
where $\varphi_\delta$ is a measurable real-valued function on $\ensuremath{\mathcal{X}}^2$ potentially depending on some unknown parameter $\delta$.
Denoting for any real-valued measurable function $g$ on $\ensuremath{\mathcal{X}}^2$,
\begin{equation}
\label{eq:not_esps_general_indep}
\esps{P}{g} = \int_{\ensuremath{\mathcal{X}}^2} g\!\pa{x^1,x^2}dP\!\pa{x^1,x^2}\quad \mbox{and}\quad \esps{\ensuremath{\perp\!\!\!\perp}}{g} = \int_{\ensuremath{\mathcal{X}}^2} g\!\pa{x^1,x^2}dP^1\!\pa{x^1} dP^2\!\pa{x^2},
\end{equation}
one may notice that, $T_\delta(\ensuremath{\mathds{X}}_n)$ is an unbiased estimator of
$$
\esp{T_\delta(\ensuremath{\mathds{X}}_n)}=\esps{P}{\varphi_\delta} - \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta},
$$
which is equal to $0$ under $(\ensuremath{\mathcal{H}}_0)$.
For more details on the choice of the test statistic, the interested reader can refer to \cite{AlbertBouretFromontReynaud2015} (motivated by synchrony detection in neuroscience for instance). The particular case where $\ensuremath{\mathcal{X}}=[0,1]$ and the $\varphi_\delta$ are Haar wavelets is studied in \cite[Chaper 4]{Albert2015PhD}. Notice that in this case, the Lispchitz assumptions of Adamczak et al (see Theorem \ref{thm:AdamczakChafaiWolff}) are not satisfied, since the Haar wavelet functions are not even continuous.

\paragraph{}
The critical value of the test is obtained from the permutation approach, inspired by Hoeffding \cite{Hoeffding1952}, and Romano \cite{Romano1989}.
Let $\ensuremath{{\Pi_n}}$ be a uniformly distributed random permutation of $\ac{1,\dots,n}$ independent of $\ensuremath{\mathds{X}}_n$ and consider the permuted sample
$$\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}} = (X_1^{\ensuremath{{\Pi_n}}}, \dots X_n^{\ensuremath{{\Pi_n}}}), \quad \mbox{where}\quad X_i^{\ensuremath{{\Pi_n}}}=(X_i^1,X_{\ensuremath{{\Pi_n}}(i)}^2) \ \forall 1\leq i\leq n,$$
obtained from permuting only the second coordinates.
Then, under $\ensuremath{\mathcal{H}}_0$, the original sample $\ensuremath{\mathds{X}}_n$ and the permuted one $\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}}$ have the same distribution.
Hence, the critical value of the upper-tailed test, denoted by $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$, is the $(1-\alpha)$-quantile of the conditional distribution of the permuted statistic $T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}})$ given the sample $\ensuremath{\mathds{X}}_n$,
where the permuted test statistic is equal to
\begin{equation*}
T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}}) = \frac{1}{n-1} \pa{\sum_{i=1}^n \varphi_\delta (X_i^1,X_{\ensuremath{{\Pi_n}}(i)}^2) -\frac{1}{n} \sum_{i,j=1}^n \varphi_\delta (X_i^1,X_j^2)},
\end{equation*}
More precisely, given $\ensuremath{\mathds{X}}_n$, if
$$T_\delta^{(1)}(\ensuremath{\mathds{X}}_n)\leq T_\delta^{(2)}(\ensuremath{\mathds{X}}_n)\leq \dots \leq T_\delta^{(n!)}(\ensuremath{\mathds{X}}_n)$$
denote the ordered values of all the permuted test statistic $T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\pi_n}}})$, when $\ensuremath{{\pi_n}}$ describes the set of all permutations of $\ac{1,\dots,n}$, then the critical value is equal to
\begin{equation}
\label{eq:def_crit_valq}
q_{1-\alpha}(\ensuremath{\mathds{X}}_n) = T_\delta^{(n!-\lfloor n!\alpha \rfloor)}(\ensuremath{\mathds{X}}_n).
\end{equation}
The corresponding test rejects the null hypothesis when $T_\delta(\ensuremath{\mathds{X}}_n) > q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$, here denoted by
\begin{equation}
\label{eq:def_test_chap_conc}
\Delta_\alpha(\ensuremath{\mathds{X}}_n) = \1{T_\delta(\ensuremath{\mathds{X}}_n) > q_{1-\alpha}(\ensuremath{\mathds{X}}_n)}.
\end{equation}

\paragraph{}
In \cite{AlbertBouretFromontReynaud2015}, the asymptotic properties of such test are studied. Based on a combinatorial central limit theorem in a non-i.i.d. case, the test is proved to be, under mild conditions, asymptotically of prescribed size, and power equal to one under any reasonable alternatives.
Yet, as explained above, such purely asymptotic properties may be insufficient when applying these tests in neuroscience for instance. Moreover, the delicate choice of the parameter $\delta$ is a real question, especially, in neuroscience, where it has some biological meaning, as mentioned in \cite{AlbertBouretFromontReynaud2015} and \cite{AlbertBouretFromontReynaud2016}.
A possible approach to overcome this issue is to aggregate several tests for different parameters $\delta$, and reject independence if at least one of them does. In particular, this approach should give us information on how to choose this parameter. Yet, to do so, non-asymptotic controls are necessary.

\paragraph{}
From a non-asymptotic point of view, since the test is non-asymptotically of prescribed level by construction, remains the non-asymptotic control of the second kind error rate, that is the probability of wrongly accepting the null hypothesis.
In the spirit of \cite{FromontLaurentReynaud2011,FromontLaurentReynaud2013,SansonnetTuleau2015}, the idea is to study the uniform separation rates, in order to study the optimality in the minimax sense (see \cite{Baraud2002}).

From now on, consider an alternative $P$ satisfying $(\ensuremath{\mathcal{H}}_1)$, and an i.i.d. sample $\ensuremath{\mathds{X}}_n$ from such distribution $P$.
Assume moreover that the alternative satisfies $\esps{P}{\varphi_\delta}>\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta}$, that is $\esp{T_\delta(\ensuremath{\mathds{X}}_n)} > 0$.
The initial step is to find some condition on $P$ guaranteeing the control of the second kind error rate, namely $\proba{\Delta_\alpha(\ensuremath{\mathds{X}}_n) = 0}$, by a prescribed value $\beta>0$.
Intuitively, since the expectation of the test statistic $\esp{T_\delta(\ensuremath{\mathds{X}}_n)}$ is equal to zero under the null hypothesis, the test should be more efficient in rejecting $(\ensuremath{\mathcal{H}}_0)$ for large values of this expectation.
So, the aim is to find conditions of the form $\esp{T_\delta(\ensuremath{\mathds{X}}_n)}\geq s$ for some threshold $s$ to be determined.
Yet, one of the main difficulties here comes from the randomness of the critical value.
The idea, as in \cite{FromontLaurentReynaud2011}, is thus to introduce $q^\alpha_{1-\beta/2}$ the $(1-\beta/2)$-quantile of the critical value $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$ and deduce from Chebychev's inequality (see Appendix \ref{sct:cond_Chebychev}), that the second kind error rate is controlled by $\beta$ as soon as
\begin{equation}
\label{eq:cond_simple_tchebychev}
\esp{T_\delta(\ensuremath{\mathds{X}}_n)} \geq q^\alpha_{1-\beta/2} + \sqrt{\frac{2}{\beta} \var{T_\delta(\ensuremath{\mathds{X}}_n)}}.
\end{equation}
Usually, the goal in general minimax approaches is to express, for well-chosen functions $\varphi_\delta$, some distance between the alternative $P$ and the null hypothesis $(\ensuremath{\mathcal{H}}_0)$ thanks to $\esp{T_\delta(\ensuremath{\mathds{X}}_n)}$ for which minimax lower-bounds are known (see for instance \cite{FromontLaurentReynaud2011,FromontLaurentReynaud2013}).
The objective is then to control, up to a constant, such distance (and in particular each term in the right-hand side of \eqref{eq:cond_simple_tchebychev}) by the minimax rate of independence testing with respect to such distance on well-chosen regularity subspaces of alternatives, in order to prove the optimality of the method from a theoretical point of view.
The interested reader could refer to the thesis \cite[Chapter 4]{Albert2015PhD} for more details about this kind of development in the density case.
It is not in the scope of the present article to develop such minimax theory in the general case, but to provide some general tools providing some sharp control of each term in the right-hand side of \eqref{eq:cond_simple_tchebychev} which consists in a very first step of this approach.
Some technical computations imply that the variance term can be upper bounded, up to a multiplicative constant, by $n^{-1} (\esp{\varphi_\delta^2(X_1^1,X_1^2)} + \esp{\varphi_\delta^2(X_1^1,X_2^2)})$ (see Lemma~\ref{lm:calcul_variance}).
Hence, the challenging part relies in the quantile term. At this point, several ideas have been explored.

\subsection{Why concentration inequalities are necessary}
\label{sct:motivconc}

A first idea to control the conditional quantile of the permuted test statistic is based on the non-asymptotic control of the critical value obtained in Appendix \ref{sct:control_quantile_cond} (see equation \eqref{eq:maj_quantile_Hoeffding}), following Hoeffding's idea (see \cite[Theorem 2.1]{Hoeffding1952}), that leads to the condition
\begin{equation}
\label{eq:cond_Hoeffding}
\esp{T_\delta(\ensuremath{\mathds{X}}_n)} \geq \frac{4}{\sqrt{\alpha}}\sqrt{\frac{2}{\beta}\frac{\esp{\varphi_\delta(X_1^1,X_1^2)^2} + \esp{\varphi_\delta(X_1^1,X_2^2)^2}}{n}}.
\end{equation}
The proof of this result is detailed in Appendix \ref{sct:cond_Hoeffding52}.
Yet, this result may not be sharp enough, especially in $\alpha$. Indeed, as explained above, the next step consists in aggregating several tests for different values of the parameter $\delta$ in a purpose of adaptivity.
Generally, when aggregating tests, as in multiple testing methods, the multiplicity of the tests has to be taken into account. In particular, the single prescribed level of each individual test should be corrected.
Several corrections exist, such as the Bonferroni one, which consists in dividing the global desired level $\alpha$ by the number of tests $M$. Yet, for such correction, the lower-bound in \eqref{eq:cond_Hoeffding} comes with a cost in $\sqrt{M}$, which is too large to provide optimal rates. Even with more sophisticated corrections than the Bonferroni one (see, e.g., \cite{FromontLaurentReynaud2011,FromontLaurentReynaud2013,SansonnetTuleau2015}),
the control by a term of order $\alpha^{-1/2}$ is too large, since classically in the literature, the dependence in $\alpha$ should be of the order of $\sqrt{\ln(1/\alpha)}$.
Hence, the bound ensuing from this first track being not sharp enough, the next idea was to investigate other non-asymptotic approaches for permuted sums.

\paragraph{}
Such approaches have also been studied in the literature.
For instance, Ho and Chen \cite{HoChen1978} obtain non-asymptotic Berry-Esseen type bounds in the $\L^p$-distance between the cumulative distribution function (c.d.f.) of the standardized permuted sum of i.i.d. random variables and the c.d.f. of the normal distribution, based on Stein's method. In particular, they obtain the rate of convergence to a normal distribution in $\L^p$-distance under Lindeberg-type conditions. Then, Bolthausen \cite{Bolthausen1984} considers a different approach, also based on Stein's method allowing to extend Ho and Chen's results in the non-identically distributed case. More precisely, he obtains bounds in the $\L^\infty$-distance in the non-random case.
In particular, in the deterministic case (which can easily be generalized to random cases), considering the notation introduced above, he obtains the following non-asymptotic bound:
\begin{equation*}
\sup_{x\in\ensuremath{\mathds{R}}} \abs{\proba{Z_n -\esp{Z_n} \leq x\sqrt{\var{Z_n}}} - \Phi_{0,1}(x)} \leq \frac{C}{n\sqrt{\var{Z_n}}^3}\sum_{i,j=1}^n\abs{d_{i,j}}^3,
\end{equation*}
where $C$ is an absolute constant, and $\Phi_{0,1}$ denotes the standard normal distribution function.
In particular, when applying this result to answer our motivation by considering random variables $\varphi_\delta(X_i^1,X_j^2)$ instead of the deterministic terms $a_{i,j}$, and working conditionally on the sample $\ensuremath{\mathds{X}}_n$, the permuted statistic $T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}})$ corresponds to $(n-1)^{-1}(Z_n-\esp{Z_n})$.
Therefore, the previous inequality implies that, for all $t$ in $\ensuremath{\mathds{R}}$,
\begin{align}
\label{eq:cond_appl_Bolthausen}
\proba{T_\delta\!\pa{\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}}} > t \middle| \ensuremath{\mathds{X}}_n} \leq &\cro{1 - \Phi_{0,1}\pa{\frac{t}{\sqrt{\var{T_\delta\!\pa{\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}}} \middle| \ensuremath{\mathds{X}}_n}}}}} \nonumber\\
& +\quad \frac{C}{n(n-1)^{2/3}\sqrt{\var{T_\delta\!\pa{\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}}} \middle| \ensuremath{\mathds{X}}_n}}^3}\sum_{i,j}\abs{D_{i,j}}^3,
\end{align}
where $D_{i,j}$ denotes
$$\varphi_\delta(X_i^1,X_j^2) -\frac{1}{n}\sum_{l=1}^n \varphi_\delta(X_i^1,X_l^2) -\frac{1}{n}\sum_{k=1}^n \varphi_\delta(X_k^1,X_j^2) + \frac{1}{n^2}\sum_{k,l=1}^n \varphi_\delta(X_k^1,X_l^2).$$
Yet, by definition of conditional quantiles, the critical value $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$ is the smallest value of $t$ such that $\proba{T_\delta(\ensuremath{\mathds{X}}_n) > t \middle| \ensuremath{\mathds{X}}_n} \leq \alpha$.
Hence, considering \eqref{eq:cond_appl_Bolthausen}, one can easily make the first term of the sum in the right-hand side of the inequality as small as one wants by choosing $t$ large enough.
However, the second term being fixed, nothing guarantees that the upper-bound in \eqref{eq:cond_appl_Bolthausen} can be constrained to be smaller than $\alpha$. Thus, this result cannot be applied in order to control non-asymptotically the critical value.
Concentration inequalities seem thus to be adequate here, as they provide sharp non-asymptotic results, with usually exponentially small controls which leads to the desired logarithmic dependency in $\alpha$, as mentioned above.

\subsection{A sharp control of the conditional quantile and a new condition guaranteeing a control of the second kind error rate}
\label{sct:quantcontr}

Sharp controls of the quantiles are provided in the following proposition.
\begin{prop}
\label{prop:control_quantile}
Consider the same notation as in Section \ref{sct:motivstat} and let $q_{1-\beta/2}^{\alpha}$ be the $(1-\beta/2)$-quantile of the conditional quantile $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$.
Then, there exists two universal positive constants $C'$ and $c_0$ such that
\begin{equation}
\label{eq:control_conditional_quantile}
q_{1-\alpha}(\ensuremath{\mathds{X}}_n) \leq \frac{C'}{n-1} \ac{\sqrt{\frac{1}{n} \sum_{i,j=1}^n\varphi_\delta^2(X_i^1,X_j^2)} \sqrt{\ln\pa{\frac{c_0}{\alpha}}} + \norm{\varphi_\delta}_{\infty}\ln\pa{\frac{c_0}{\alpha}}}.
\end{equation}

As a consequence, there exists a universal positive constants $C$ such that
\begin{equation}
\label{eq:control_quantile}
q_{1-\beta/2}^\alpha \leq C \ac{\sqrt{\frac{2}{\beta}\ln\pa{\frac{c_0}{\alpha}}}\pa{\frac{\sqrt{\esps{P}{\varphi_\delta^2}}}{n} + \frac{\sqrt{\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}}{\sqrt{n}}}  + \frac{\norm{\varphi_\delta}_\infty}{n}\ln\pa{\frac{c_0}{\alpha}}}.
\end{equation}
\end{prop}

Moreover, a control of the variance term is obtained in the following lemma based on the Cauchy-Schwartz inequality.
\begin{lm}
\label{lm:calcul_variance}
Let $n\geq 4$ and $\ensuremath{\mathds{X}}_n$ be a sample of $n$ i.i.d. random variables with distribution $P$ and marginals $P^1$ and $P^2$. Let $T_\delta$ be the test statistic defined in \eqref{eq:def_stat_T}, and $\esps{P}{\cdot}$ and $\esps{\ensuremath{\perp\!\!\!\perp}}{\cdot}$ be notation introduced in \eqref{eq:not_esps_general_indep}. Then, if both $\esps{P}{\varphi_\delta^2}<+\infty$ and $\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}<+\infty$,
$$\var{T_\delta(\ensuremath{\mathds{X}}_n)} \leq \frac{1}{n} \pa{\sqrt{\esps{P}{\varphi_\delta^2}} + 2 \sqrt{\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}}^2.$$
\end{lm}

Proposition~\ref{prop:control_quantile} and Lemma \ref{lm:calcul_variance} both imply that the right-hand side of \eqref{eq:cond_simple_tchebychev} is upper bounded by
\begin{equation}
\label{eq:upper_bound}
C''\ac{\sqrt{\frac{2}{\beta}\cro{\ln\pa{\frac{c_0}{\alpha}}+1}\frac{\pa{\esps{P}{\varphi_\delta^2} + \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}}{n}} + \frac{\norm{\varphi_\delta}_\infty}{n}\ln\pa{\frac{c_0}{\alpha}}},
\end{equation}
where $C''$ is a universal constant.

Indeed, the control of $q_{1-\beta/2}^\alpha$ is implied by \eqref{eq:control_quantile} combined with the concavity property of the square-root function.
Lemma \ref{lm:calcul_variance} directly implies that the variance term satisfies
$$
\var{T_\delta(\ensuremath{\mathds{X}}_n)} \leq \frac{8}{n} \pa{\esps{P}{\varphi_\delta^2} + \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}},
$$

Finally, if $\esp{T_\delta(\ensuremath{\mathds{X}}_n)}$ is larger than the quantity in \eqref{eq:upper_bound}, then condition \eqref{eq:cond_simple_tchebychev} is satisfied which directly provides that $\proba{\Delta_{\delta,\alpha}(\ensuremath{\mathds{X}}_n) = 0} \leq \beta$, that is the second kind error rate of the test $\Delta_{\delta,\alpha}$ is less than or equal to the prescribed value $\beta$.
One may notice that this time, the dependence in $\alpha$ is, as expected, of the order of $\sqrt{\ln(1/\alpha)}$.

\section{Proofs}
\label{sct:proofs}

\subsection{Proof of Lemma \ref{lm:concRac}}
\label{sct:lmConcRac}

\paragraph{Sketch of proof.} From now on, fix $t>0$.
Recall the notation introduced by Talagrand in Theorem \ref{thm:Talagrand}. The main purpose of these notation is to introduce some notion of distance between a permutation $\ensuremath{{\pi_n}}$ in $\Sn{n}$ and a subset $A$ of $\Sn{n}$. To do so, the idea is to reduce the set of interest to a simpler one, that is $[0,1]^n$, by considering $$U_A(\ensuremath{{\pi_n}}) = \ac{s \in \{0,1\}^n \ ;\ \exists \tau \in A \mbox{ such that } \forall 1\leq i\leq n,\ s_i=0 \implies \tau(i)=\ensuremath{{\pi_n}}(i)}.$$
One may notice that the permutation $\ensuremath{{\pi_n}}$ belongs to $A$ if and only if $0$ belongs to the set $U_A(\ensuremath{{\pi_n}})$.
Hence, the corresponding distance between the permutation $\ensuremath{{\pi_n}}$ and the set $A$ is coded by the distance between $0$ and the set $U_A(\ensuremath{{\pi_n}})$ and thus defined by
$$f(A,\ensuremath{{\pi_n}}) = \min\ac{\sum_{i=1}^n v_i^2\ ;\ v=\pa{v_i}_{1\leq i\leq n}\in V_A(\ensuremath{{\pi_n}})},$$
where $V_A(\ensuremath{{\pi_n}})=\operatorname{ConvexHull}\pa{U_A(\ensuremath{{\pi_n}})}$.
One may notice in particular that $A$ contains $\ensuremath{{\pi_n}}$ if and only if the distance $f(A,\ensuremath{{\pi_n}})=0$.

The global frame of the proof of Lemma \ref{lm:concRac} (and also Proposition \ref{prop:concPosMed}) relies on the following steps.
The first step consists in proving that
\begin{equation}
\label{eq:1step}
\proba{\sqrt{Z}\geq\sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}} \leq \frac{e^{-t^2/16}}{\proba{Z\in A}},
\end{equation}
for some subset $A$ of $\Sn{n}$ of the shape $A=\ac{\tau\in\Sn{n} ; Z(\tau)\leq C_A}$ for some constant $C_A$ to be chosen later.
For this purpose, since Talagrand's inequality for random permutations (see Theorem \ref{thm:Talagrand}) provides that
$$\proba{f(A,\ensuremath{{\Pi_n}}) \geq t^2} \leq \frac{e^{-t^2/16}}{\proba{\ensuremath{{\Pi_n}} \in A}},$$
it is sufficient to prove that
$$\proba{f(A,\ensuremath{{\Pi_n}}) \geq t^2}\geq \proba{\sqrt{Z}\geq\sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}},$$ to obtain \eqref{eq:1step}.
To do so, the idea, as in \cite{AdamczakChafaiWolff2014}, is to show that the assertion $f(A,\ensuremath{{\Pi_n}}) < t^2$ implies that $\sqrt{Z}< \sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}$, and to conclude by contraposition.

Then, the two following steps consist in choosing appropriate constants $C_A$ in \eqref{eq:1step} depending on the median of $Z$, such that both $\proba{\sqrt{Z}\geq\sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}$ and $\proba{Z\in A}$ are greater than $1/2$, in order to control both probabilities
$$\proba{\sqrt{Z} \geq \sqrt{\med{Z}} + t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\mbox{ and }\proba{\sqrt{Z} \leq \sqrt{\med{Z}} - t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}$$ respectively in \eqref{eq:concRac+} and \eqref{eq:concRac-}.

\paragraph{First step: preliminary study.}
Assume $f(A,\ensuremath{{\Pi_n}})<t^2$. Then, by definition of the distance $f$, there exists some $s^1,\dots,s^m$ in $U_A(\ensuremath{{\Pi_n}})$, and some non-negative weights $p_1,\dots,p_m $ satisfying $\sum_{j=1}^m p_j=1$ such that
$$\sum_{i=1}^n \cro{\pa{\sum_{j=1}^m p_j s_i^j}^2} < t^2.$$
For each $1\leq j\leq m$, since $s^j$ belongs to $U_A(\ensuremath{{\Pi_n}})$, one may consider a permutation $\tau_j$ in $A$ associated to $s^j$ (that is satisfying $s_i^j=0 \implies \tau_j(i)=\ensuremath{{\Pi_n}}(i)$).
Then, since the $a_{i,j}$ are non-negative, and from the Cauchy-Schwartz inequality,
\begin{eqnarray*}
Z-\sum_{j=1}^m p_j Z(\tau_j) &=& \sum_{i=1}^n \sum_{j=1}^m p_j \pa{a_{i,\ensuremath{{\Pi_n}}(i)}-a_{i,\tau_j(i)}}\\
&=& \sum_{i=1}^n \sum_{j=1}^m p_j \pa{a_{i,\ensuremath{{\Pi_n}}(i)}-a_{i,\tau_j(i)}}s_i^j\\
&\leq & \sum_{i=1}^n \cro{\pa{\sum_{j=1}^m p_j s_i^j} a_{i,\ensuremath{{\Pi_n}}(i)}} \\
&\leq & \sqrt{\sum_{i=1}^n \pa{\sum_{j=1}^m p_j s_i^j}^2} \sqrt{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}\\
&< & t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}} \sqrt{Z}.
\end{eqnarray*}
Thus, as the $\tau_j$ are in $A=\ac{\tau ; Z(\tau)\leq C_A}$,
$$ Z < C_A + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}} \sqrt{Z}.$$

Therefore, by solving the second-order polynomial in $\sqrt{Z}$ above, one obtains
$$ \sqrt{Z} < \frac{t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}} + \sqrt{t^2\max_{1\leq i,j\leq n}\ac{a_{i,j}}+4C_A}}{2}\leq t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}} + \sqrt{C_A}. $$

Finally, by contraposition,
$$\proba{\sqrt{Z}\geq\sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}} \leq \proba{f(A,\ensuremath{{\Pi_n}})\geq t^2},$$
which, combined with \eqref{eq:Talagrand-Markov} of Theorem \ref{thm:Talagrand} provides \eqref{eq:1step}.

\paragraph{Second step: proof of \eqref{eq:concRac+}.}
Taking $C_A=\med{Z}$ guarantees $\proba{Z\in A}\geq 1/2$ and thus, \eqref{eq:1step} provides \eqref{eq:concRac+}.

\paragraph{Third step: proof of \eqref{eq:concRac-}.}
Taking $C_A = \pa{\sqrt{\med{Z}} - t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}^2$ implies
$$\proba{\sqrt{Z}\geq \sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}} = \proba{\sqrt{Z}\geq\sqrt{\med{Z}}}=\proba{Z\geq\med{Z}} \geq \frac{1}{2}.$$

So finally, again by \eqref{eq:1step},
\begin{eqnarray*}
\proba{\sqrt{Z} \leq \sqrt{\med{Z}} - t\sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}
& = & \proba{Z\in A} \\
&\leq & \frac{e^{-t^2/16}}{\proba{\sqrt{Z}\geq \sqrt{C_A} + t \sqrt{\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}}\\
&\leq & 2 e^{-t^2/16},
\end{eqnarray*}
which ends the proof of the Lemma.

\subsection{Proof of Proposition \ref{prop:concPosMed}}
\label{sct:propConcPosMed}

From now on, fix $x>0$, and consider $t=x^2$.
This proof is again based on Talagrand's inequality for random permutations, combined with \eqref{eq:concRac+} in Lemma \ref{lm:concRac}. It follows exactly the same progression as in the proof of Lemma \ref{lm:concRac};
the preliminary step consists in working with subsets $A\subset \Sn{n}$ of the form $A=\ac{\tau\in\Sn{n}\ ;\ Z(\tau)\leq C_A}$ for some constant $C_A$, in order to obtain for all $v>0$,
\begin{equation}
\label{eq:1stepPos}
\proba{Z \geq C_A + t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}}}\leq \frac{e^{-t^2/16}}{\proba{Z\in A}} + 2 e^{-v^2/16}.
\end{equation}
The second and third step consist in picking up a well-chosen constant $C_A$ and a well-chosen $v>0$ in order to obtain respectively
\begin{equation}
\label{eq:concPosMed+}
\proba{Z \geq \med{Z} + t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + (t\vee C_0) \max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 4 e^{-t^2/16},
\end{equation}
and
\begin{equation}
\label{eq:concPosMed-}
\proba{Z \leq \med{Z} - t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + (t\vee C_0) \max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 4 e^{-t^2/16},
\end{equation}
where $C_0 = 4\sqrt{\ln(8)}$.
The final step combines \eqref{eq:concPosMed+} and \eqref{eq:concPosMed-} in order to prove \eqref{eq:concPosMed}.

\paragraph{First step: preliminary study.}
Let $A=\ac{\tau\in\Sn{n}\ ;\ Z(\tau)\leq C_A}$ with $C_A$ a general constant, and fix $v>0$.
Assume, this time, that both
\begin{equation}
\label{eq:hypPos}
f(A,\ensuremath{{\Pi_n}})<t^2 \quad\mbox{ and }\quad
\sqrt{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2} < \sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}.
\end{equation}
Then, as in the preliminary study of the proof of Lemma \ref{lm:concRac}, from the first assumption in \eqref{eq:hypPos}, there exists some $s^1,\dots,s^m$ in $U_A(\ensuremath{{\Pi_n}})$, and some non-negative weights $p_1,\dots,p_m$ satisfying $\sum_{j=1}^m p_j=1$ such that
$$\sum_{i=1}^n \cro{\pa{\sum_{j=1}^m p_j s_i^j}^2} < t^2.$$
For each $1\leq j\leq m$, consider $\tau_j$ in $A$ associated to $s^j$, that is a permutation $\tau_j$ in $A$ satisfying $s_i^j=0 \implies \tau_j(i)=\ensuremath{{\Pi_n}}(i)$.
Then, combining the Cauchy-Shwartz inequality with the second assumption in \eqref{eq:hypPos} leads to
\begin{eqnarray*}
Z-\sum_{j=1}^m p_j Z(\tau_j) &=& \sum_{i=1}^n \sum_{j=1}^m p_j \pa{a_{i,\ensuremath{{\Pi_n}}(i)}-a_{i,\tau_j(i)}}s_i^j\\
&\leq & \sum_{i=1}^n \cro{\pa{\sum_{j=1}^m p_j s_i^j} a_{i,\ensuremath{{\Pi_n}}(i)}} \\
&\leq & \sqrt{\sum_{i=1}^n \pa{\sum_{j=1}^m p_j s_i^j}^2} \sqrt{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}\\
&< & t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}}.
\end{eqnarray*}
Notice that here, the reasoning begins exactly as in the proof of Lemma \ref{lm:concRac}. Yet, the second assumption in \eqref{eq:hypPos}, which can be controlled thanks to that lemma, allows us to sharpen the inequality.
Thus, as the $\tau_j$ are in $A=\ac{\tau ; Z(\tau)\leq C_A}$,
\begin{equation}
\label{eq:csqPos}
Z < C_A + t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}}.
\end{equation}
Hence, by contraposition of \eqref{eq:hypPos} $\implies$ \eqref{eq:csqPos},  one obtains
\begin{multline*}
\proba{Z \geq C_A + t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}}} \\
\leq \proba{f(A,\ensuremath{{\Pi_n}})\geq t^2} + \proba{\sqrt{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2} \geq \sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}},
\end{multline*}
and \eqref{eq:1stepPos} follows from Theorem \ref{thm:Talagrand} and \eqref{eq:concRac+} in Lemma \ref{lm:concRac}.

\paragraph{Second step: proof of \eqref{eq:concPosMed+}.}
Consider $C_A=\med{Z}$ so that $\proba{Z\in A}\geq 1/2$.
Thus, if $v=t$ in \eqref{eq:1stepPos}
\begin{align*}
\ensuremath{\mathds{P}}\Bigg(Z \geq \med{Z} &+ t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + (t\vee C_0) \max_{1\leq i,j\leq n}
\ac{a_{i,j}}}\Bigg)\\
&\leq \proba{Z \geq \med{Z} + t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + t \max_{1\leq i,j\leq n}
\ac{a_{i,j}}}}\\
&\leq 4 e^{-t^2/16}
\end{align*}
Notice that the maximum with the constant in $(t\vee C_0)$ is not necessary in the case only a control of the right-tail is wanted.

\paragraph{Third step: proof of \eqref{eq:concPosMed-}.}
Consider now $$C_A = \med{Z} - t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}},$$
so that
$$\proba{Z \geq C_A + t \pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + v\max_{1\leq i,j \leq n}\ac{a_{i,j}}}}
= \proba{Z\geq \med{Z}} \geq \frac{1}{2}.$$
Hence, on the one hand, from \eqref{eq:1stepPos},
$$\proba{Z\in A} \leq \frac{e^{-t^2/16}}{\pa{\frac{1}{2} - 2 e^{-v^2/16}}}.$$
Thus, if $v=C_0=4\sqrt{\ln(8)}$, then $\pa{\frac{1}{2} - 2 e^{-v^2/16}} = \frac{1}{4}$, and $\proba{Z\in A} \leq 4 e^{-t^2/16}.$

On the other hand, as $(t\vee C_0) \geq C_0=v$,
$$\proba{Z\in A} \geq \proba{Z \leq \med{Z} - t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + (t\vee C_0) \max_{1\leq i,j\leq n}\ac{a_{i,j}}}},$$
which ends the proof of \eqref{eq:concPosMed-}.

\paragraph{Fourth step: proof of \eqref{eq:concPosMed}.}
Both \eqref{eq:concPosMed+} and \eqref{eq:concPosMed-} lead to
$$\proba{\abs{Z - \med{Z}} > t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + (t\vee C_0) \max_{1\leq i,j\leq n}\ac{a_{i,j}}}}\leq 8 e^{-t^2/16}.$$
Thus, on the one hand, if $t\geq C_0$, that is $t\vee C_0 = t$, and \eqref{eq:concPosMed} holds. \\
On the other hand, if $t < C_0$,
\begin{multline*}
\proba{\abs{Z - \med{Z}} > t\pa{\sqrt{\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}} + t\max_{1\leq i,j\leq n}\ac{a_{i,j}}}}
\leq  1\\
\leq  e^{C_0^2/16 - t^2/16} = 8 e^{-t^2/16},
\end{multline*}
which ends the proof of the Proposition by taking $x=\sqrt{t}$.

\subsection{Proof of Lemma \ref{lm:ineqEspMedVar}}
\label{sct:lmineqEspMedVar}

Let $X$ be any real random variable.
Recall that $$\med{X} \in \operatornamewithlimits{argmin}_{m\in\ensuremath{\mathds{R}}} \esp{\abs{X-m}}. $$
In particular, thanks to Jensen's inequality,
\begin{eqnarray}
\abs{\esp{X}-\med{X}} &\leq & \esp{\abs{X-\med{X}}} \nonumber \\
&\leq & \esp{\abs{X-\esp{X}}} \nonumber\\
&\leq & \sqrt{\esp{\pa{X-\esp{X}}^2}} \nonumber\\
&\leq & \sqrt{\var{X}} \label{eq:majdiffmoymed}.
\end{eqnarray}

\subsection{Proof of Proposition \ref{prop:concPosMoy}}
\label{sct:propConcPosMoy}

First, for a better readability, let
$$M=\max_{1\leq i,j\leq n} \ac{a_{i,j}}\quad \mbox{ and }\quad V=\esp{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2}=\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2.$$
Then, $\med{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^2} \leq 2V$ since by Markov's inequality, for all non-negative random variable X, $\med{X}\leq 2\esp{X}$.
Indeed,
$$\frac{1}{2} \leq \proba{X \geq \med{X}} \leq \frac{\esp{X}}{\med{X}}. $$

Thus, by Proposition \ref{prop:concPosMed}, one obtains that, for all $x>0$,
\begin{equation}
\label{eq:tradconcMedMV}
\proba{\abs{Z-\med{Z}}\geq \sqrt{2Vx} + Mx } \leq 8 e^{-x/16}.
\end{equation}

The following is based on Lemma \ref{lm:ineqEspMedVar}, and provides an upper-bound of the difference between the expectation and the median of $Z$.

\begin{lm}
\label{lm:majdiffmoymed}
With the notation defined above,
$$
\abs{\esp{Z}-\med{Z}} \leq \sqrt{2 V}.
$$
\end{lm}

\begin{proof}[Proof of Lemma \ref{lm:majdiffmoymed}]
Lemma \ref{lm:ineqEspMedVar} implies that
$$
\abs{\esp{Z}-\med{Z}} \leq \sqrt{\var{Z}}.
$$
Let us prove that
\begin{equation}
\label{eq:majvar}
\var{Z} \leq 2V.
\end{equation}

Indeed,
\begin{eqnarray*}
\var{Z} &=& \esp{\pa{\sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)} - \frac{1}{n}\sum_{i,j=1}^n a_{i,j}}^2} \\
&=& \esp{\pa{\sum_{i,j=1}^n a_{i,j}\pa{\1{\ensuremath{{\Pi_n}}(i)=j}-\frac{1}{n}}}^2} \\
&=& \sum_{i,j=1}^n \sum_{k,l=1}^n a_{i,j} a_{k,l} E_{i,j,k,l},
\end{eqnarray*}
where $$E_{i,j,k,l}=\esp{\pa{\1{\ensuremath{{\Pi_n}}(i)=j}-\frac{1}{n}}\pa{\1{\ensuremath{{\Pi_n}}(k)=l}-\frac{1}{n}}} = \esp{\1{\ensuremath{{\Pi_n}}(i)=j}\1{\ensuremath{{\Pi_n}}(k)=l}} - \frac{1}{n^2}.$$
In particular,
\begin{equation*}
E_{i,j,k,l} = \left\{ \begin{array}{ll}
\displaystyle\frac{1}{n}-\frac{1}{n^2} \leq \frac{1}{n} & \mbox{if } i=k \mbox{ and } j=l, \\ \\
\displaystyle\frac{-1}{n^2}\leq 0 & \mbox{if } i=k \mbox{ and } j\neq l \mbox{ or } i\neq k \mbox{ and } j=l, \\ \\
\displaystyle\frac{1}{n(n-1)} - \frac{1}{n^2} = \frac{1}{n^2(n-1)} & \mbox{if } i\neq k \mbox{ and } j\neq l.
\end{array}\right.
\end{equation*}
Therefore, from the Cauchy-Schwarz inequality applied to the second sum bellow (of $n^2(n-1)^2$ terms), one obtains
\begin{eqnarray*}
\var{Z} &\leq & \frac{1}{n} \sum_{i,j=1}^n a_{i,j}^2 + \frac{1}{n^2(n-1)} \sum_{i\neq k} \sum_{j\neq l} a_{i,j} a_{k,l} \\
&\leq & V + \frac{\sqrt{n^2(n-1)^2}}{n^2(n-1)} \sqrt{\sum_{i\neq k}\sum_{j\neq l} a_{i,j}^2 a_{k,l}^2} \\
&\leq & V + \frac{1}{n} \sqrt{\sum_{i,j} a_{i,j}^2\sum_{k,l}a_{k,l}^2} \\
&=& 2V.
\end{eqnarray*}
Finally, combining \eqref{eq:majdiffmoymed} and \eqref{eq:majvar} ends the proof of Lemma \ref{lm:majdiffmoymed}.
\end{proof}

Therefore, one deduces from Lemma \ref{lm:majdiffmoymed} and Equation \eqref{eq:tradconcMedMV} that for all $x>0$,
\begin{equation}
\label{eq:concMoyPlusEta}
\proba{\abs{Z-\esp{Z}} \geq \sqrt{2 V} + \sqrt{2 V x} + M x} \leq 8e^{-x/16}.
\end{equation}

Now, as in \cite[Corollary 2.11]{BoucheronLugosiMassart2013}, introduce $h_1 : u\in\ensuremath{\mathds{R}}^+ \mapsto 1+u-\sqrt{1+2u}$. Then, in particular, $h_1$ is non-decreasing, convex, one to one function on $\ensuremath{\mathds{R}}^+$ with inverse function $h_1^{-1} : v\in\ensuremath{\mathds{R}}^+ \mapsto v+\sqrt{2v}.$
Indeed,
\begin{eqnarray*}
h_1\pa{h_1^{-1}(v)} &=& 1+v+\sqrt{2v} - \sqrt{1+2v+2\sqrt{2v}} \\
&=& 1 + v +\sqrt{2v} - \sqrt{\pa{1+\sqrt{2v}}^2} =v,
\end{eqnarray*}
and
\begin{eqnarray*}
h_1^{-1}\pa{h_1(u)} &=& 1+u-\sqrt{1+2u} + \sqrt{2 + 2u-2\sqrt{1+2u}} \\
&=& u + 1-\sqrt{1+2u} + \sqrt{1 -2\sqrt{1+2u} + 1+2u} \\
&=& 1+u-\sqrt{1+2u} + \sqrt{\pa{1-\sqrt{1+2u}}^2} = u. \\
\end{eqnarray*}

Consider $\ensuremath{\mfk{a}}$ and $\ensuremath{\mfk{c}}$ defined by $\ensuremath{\mfk{a}} = V/M$ and $\ensuremath{\mfk{c}} = M^2/V$, such that $\ensuremath{\mfk{a}} \ensuremath{\mfk{c}} = M $ and $\ensuremath{\mfk{a}}^2 \ensuremath{\mfk{c}} = V$ and thus
$$\sqrt{2 V x} + M x  = \ensuremath{\mfk{a}} h_1^{-1}(\ensuremath{\mfk{c}} x).$$

Then, from \eqref{eq:concMoyPlusEta},
$$\proba{\abs{Z-\esp{Z}}\geq \sqrt{2\ensuremath{\mfk{a}}^2 \ensuremath{\mfk{c}}} + \ensuremath{\mfk{a}} h_1^{-1}(\ensuremath{\mfk{c}} x)}\leq 8 e^{-x/16}.$$

\medskip
Let $t>0$, and consider the two following cases.

\paragraph{1st case:} if $t \geq \sqrt{2V} = \sqrt{2\ensuremath{\mfk{a}}^2 \ensuremath{\mfk{c}}}$,
then define $\displaystyle x=\frac{1}{\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{\ensuremath{\mfk{a}}}-\sqrt{2\ensuremath{\mfk{c}}}}$ such that $t = \sqrt{2\ensuremath{\mfk{a}}^2 \ensuremath{\mfk{c}}}+\ensuremath{\mfk{a}} h_1^{-1}(\ensuremath{\mfk{c}} x)$. Then,
$$\proba{\abs{Z-\esp{Z}}\geq t} \leq 8 \exp\pa{-\frac{1}{16\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{\ensuremath{\mfk{a}}}-\sqrt{2\ensuremath{\mfk{c}}}}}. $$
Yet, by convexity of $h_1$,
$$h_1\pa{\frac{t}{\ensuremath{\mfk{a}}}-\sqrt{2\ensuremath{\mfk{c}}}} \geq 2 h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}} - h_1\pa{\sqrt{2\ensuremath{\mfk{c}}}}.$$
Hence,
$$\proba{\abs{Z-\esp{Z}}\geq t} \leq 8 \exp\pa{\frac{1}{16\ensuremath{\mfk{c}}}h_1\pa{\sqrt{2\ensuremath{\mfk{c}}}}}\exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}.$$

Moreover,
$\sqrt{2\ensuremath{\mfk{c}}} \leq \ensuremath{\mfk{c}} + \sqrt{2\ensuremath{\mfk{c}}} = h_1^{-1} \pa{\ensuremath{\mfk{c}}},$
hence $$\frac{1}{16\ensuremath{\mfk{c}}}h_1\pa{\sqrt{2\ensuremath{\mfk{c}}}}\leq \frac{1}{16}.$$
So finally in this case,
\begin{equation}
\label{eq:grandst}
\proba{\abs{Z-\esp{Z}}\geq t} \leq 8 e^{1/16}\exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}.
\end{equation}

\paragraph{2nd case:} if $t < \sqrt{2V} = \sqrt{2\ensuremath{\mfk{a}}^2 \ensuremath{\mfk{c}}}$,
\begin{equation*}
\proba{\abs{Z-\esp{Z}}\geq t} \quad\leq\quad 1
\quad = \quad  \exp\pa{\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}\exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}
\end{equation*}

Moreover, in this case, since $\sqrt{2\ensuremath{\mfk{c}}}/2 \leq h_1^{-1}(\ensuremath{\mfk{c}}/4)$, hence
$$\frac{1}{8\ensuremath{\mfk{c}}} h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}} \leq \frac{1}{8\ensuremath{\mfk{c}}} h_1\pa{\frac{\sqrt{2\ensuremath{\mfk{c}}}}{2}}\leq \frac{1}{32},$$
and thus
\begin{equation}
\label{eq:petitst}
\proba{\abs{Z-\esp{Z}}\geq t} \leq  e^{1/32}\exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}.
\end{equation}

\medskip

\paragraph{}
Finally, combining \eqref{eq:grandst} and \eqref{eq:petitst} leads, in all cases, to
\begin{equation}
\label{eq:toust}
\proba{\abs{Z-\esp{Z}}\geq t} \leq 8e^{1/16} \exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}}.
\end{equation}

Now, in order to obtain the Bernstein-type inequality, let $\displaystyle x = \frac{2}{\ensuremath{\mfk{c}}}h_1\!\pa{\frac{t}{2\ensuremath{\mfk{a}}}}$, then
$$t = 2\ensuremath{\mfk{a}} h_1^{-1}\pa{\frac{\ensuremath{\mfk{c}} x}{2}} = \ensuremath{\mfk{a}}\ensuremath{\mfk{c}} x + 2\sqrt{\ensuremath{\mfk{a}}^2\ensuremath{\mfk{c}} x} = 2\sqrt{V x} + Mx,$$
and thus for all $x>0$,
\begin{equation}
\proba{\abs{Z-\esp{Z}}\geq 2\sqrt{V x} + M x}\leq 8e^{1/16} \exp\pa{-\frac{x}{16}},
\end{equation}
which ends the proof of the Proposition.

\subsection{Proof of Corollary \ref{coro:concPosMoy}}
\label{sct:coroConcPosMoy}

Consider the same notation as in both Proposition \ref{prop:concPosMoy} and its proof.
This proof follows the one of \cite[Corollary 2.10]{Massart2007}.
Notice that for all $u\geq 0$,
$$h_1(u)\geq \frac{u^2}{2(1+u)}.$$
Hence, from \eqref{eq:toust} in the proof of Proposition \ref{prop:concPosMoy}, for all $t \geq 0$,
\begin{eqnarray*}
\proba{\abs{Z-\esp{Z}}\geq t} &\leq & 8e^{1/16} \exp\pa{-\frac{1}{8\ensuremath{\mfk{c}}}h_1\pa{\frac{t}{2\ensuremath{\mfk{a}}}}} \\
&\leq & 8e^{1/16} \exp\pa{-\frac{t^2}{64\ensuremath{\mfk{a}}^2\ensuremath{\mfk{c}}\pa{1+t/2\ensuremath{\mfk{a}}}}} \\
&=& 8e^{1/16} \exp\pa{-\frac{t^2}{32\pa{2\ensuremath{\mfk{a}}^2\ensuremath{\mfk{c}}+\ensuremath{\mfk{a}}\ensuremath{\mfk{c}} t}}} \\
&=& 8e^{1/16} \exp\pa{-\frac{t^2}{32\pa{V+M t}}}.
\end{eqnarray*}
which ends the proof of the Corollary.

\subsection{Proof of Theorem \ref{thm:concQcqMoy}}
\label{sct:thmConcQcqMoy}

For a better readability, introduce
$a_{i,j}^+ = a_{i,j}\1{a_{i,j}\geq 0}$ (respectively $a_{i,j}^- = -a_{i,j}\1{a_{i,j} < 0}$), and
denote $Z^+ = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^+$ (respectively $Z^- = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)}^-$).
Then $$Z = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)} = Z^+ - Z^-.$$

Moreover, if $v$ (respectively $v^+$ and $v^-$) denotes $\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2$ (respectively $\frac{1}{n}\sum_{i,j=1}^n (a_{i,j}^+)^2$ and $\frac{1}{n}\sum_{i,j=1}^n (a_{i,j}^-)^2$), then $v=v^+ + v^-$ and, from the concavity property of the square root function,
$$\sqrt{2v}\geq \sqrt{v^+} + \sqrt{v^-}.$$

Furthermore, if $M^+$ (respectively $M^-$) denotes $\max_{1\leq i,j\leq n}\{a_{i,j}^+\}$ (respectively $\max_{1\leq i,j\leq n}\{a_{i,j}^-\}$), then $2M=2\max_{1\leq i,j\leq n}\ac{|a_{i,j}|} \geq M^+ + M^-$.

Finally, applying Proposition \ref{prop:concPosMoy} to $Z^+$ and $Z^-$ which are both sums of non-negative numbers leads to
\begin{eqnarray*}
\ensuremath{\mathds{P}}\Big(|Z \!\! &-&\!\! \esp{Z}| \ \geq\ 2\sqrt{2vx}\ +\ 2Mx\Big) \\
&\leq & \proba{\abs{Z^+ -\esp{Z^+}} + \abs{Z^- -\esp{Z^-}} \geq 2\sqrt{v^+ x} + M^+ x + 2\sqrt{v^- x} + M^- x} \\
&\leq &\proba{\abs{Z^+ -\esp{Z^+}} \geq 2\sqrt{v^+ x} + M^+ x} +\ \proba{\abs{Z^- -\esp{Z^-}} \geq 2\sqrt{v^- x} + M^- x} \\
&\leq & 16e^{1/16} \exp\pa{-\frac{x}{16}},
\end{eqnarray*}
which ends the proof of the Theorem.

\subsection{Proof of Corollary \ref{coro:concQcqMoy}}
\label{sct:thmConcQcqMoy}

Consider the same notation as in the proof of Theorem \ref{thm:concQcqMoy}, and let $t>0$.
Let $M$ denote the maximum $\max_{1\leq i,j\leq n}\ac{|a_{i,j}|}$. On the one hand, $M^+ \leq M$ and $M^- \leq M$, and on the other hand, $v^+\leq v$ and $v^- \leq v$.
Therefore, applying Corollary \ref{coro:concPosMoy}, one obtains
\begin{eqnarray*}
\proba{\abs{Z-\esp{Z}}\geq t}
&\leq & \proba{\abs{Z^+ -\esp{Z^+}} + \abs{Z^- -\esp{Z^-}}\geq t} \\
&\leq & \proba{\abs{Z^+ -\esp{Z^+}}\geq t/2} + \proba{\abs{Z^- -\esp{Z^-}}\geq t/2} \\
&\leq & 8 e^{1/16} \exp\pa{\frac{-(t/2)^2}{16\pa{4v^+ + 2M^+ t/2}}} + 8 e^{1/16}\exp\pa{\frac{-(t/2)^2}{16\pa{4v^- + 2M^- t/2}}} \\
&\leq & 16e^{1/16} \exp\pa{\frac{-t^2}{64\pa{4 v + M t}}},
\end{eqnarray*}
which leads to the following intermediate result
\begin{equation}
\label{eq:concQcqMoyInter}
\proba{\abs{Z-\esp{Z}}\geq t}\leq 16e^{1/16} \exp\pa{\frac{-t^2}{64\pa{4\frac{1}{n}\sum_{i,j=1}^n a_{i,j}^2 + \max_{1\leq i,j\leq n} \ac{\abs{a_{i,j}}} t}}}.
\end{equation}

In order to make the variance appear, consider Hoeffding's centering trick recalled in \eqref{eq:def_dij} and introduce
$$d_{i,j} = a_{i,j} - \frac{1}{n} \sum_{k=1}^n a_{k,j} -\frac{1}{n} \sum_{l=1}^n a_{i,l} + \frac{1}{n^2} \sum_{k,l=1}^n a_{k,l}
=\frac{1}{n^2} \sum_{k,l=1}^n \pa{a_{i,j}-a_{k,j}-a_{i,l}+a_{k,l}}.$$
One may easily verify that for all $i_0$ and $j_0$, $\sum_{i=1}^n d_{i,j_0} = \sum_{j=1}^n d_{i_0,j} = 0$.
Moreover,
$$\sum_{i=1}^n d_{i,\ensuremath{{\Pi_n}}(i)} = \sum_{i=1}^n a_{i,\ensuremath{{\Pi_n}}(i)} - \frac{1}{n} \sum_{i,j=1}^n a_{i,j}=Z-\esp{Z} \quad \mbox{and}\quad \esp{\sum_{i=1}^n d_{i,\ensuremath{{\Pi_n}}(i)}} = \frac{1}{n}\sum_{i,j=1}^n d_{i,j} = 0.$$
In particular, applying equation \eqref{eq:concQcqMoyInter} to the permuted sum of the $d_{i,j}$'s leads to
\begin{equation}
\label{eq:concQcqMoyHoeffding}
\proba{\abs{Z-\esp{Z}}\geq t}\leq 16e^{1/16} \exp\pa{\frac{-t^2}{64\pa{4\frac{1}{n}\sum_{i,j=1}^n d_{i,j}^2 + \max_{1\leq i,j\leq n} \ac{\abs{d_{i,j}}} t}}}.
\end{equation}
Then, it is sufficient to notice that, on the one hand,  from \cite[Theorem 2]{Hoeffding1951},
$$\var{Z}=(n-1)^{-1}\sum_{i,j=1}^n d_{i,j}^2\geq n^{-1}\sum_{i,j=1}^n d_{i,j}^2,$$ and on the other hand, $$\max_{1\leq i,j\leq n} \ac{\abs{d_{i,j}}} \leq 4 \max_{1\leq i,j\leq n} \ac{\abs{a_{i,j}}}, $$
to end the proof of Corollary \ref{coro:concQcqMoy}.

\subsection{Proof of Proposition~\ref{prop:control_quantile}}
\label{sect:proof_prop_control_var_quantile}

The proof of Proof of Proposition~\ref{prop:control_quantile} is divided into two steps. The first step consists in controlling the conditional quantile $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$ and the second step provides an upper-bound for $q_{1-\beta/2}^\alpha$.

\begin{description}
\item[1st step.] Let us prove \eqref{eq:control_conditional_quantile}, that is
$$
q_{1-\alpha}(\ensuremath{\mathds{X}}_n) \leq \frac{C'}{n-1} \ac{\sqrt{\frac{1}{n} \sum_{i,j=1}^n\varphi_\delta^2(X_i^1,X_j^2)} \sqrt{\ln\pa{\frac{c_0}{\alpha}}} + \norm{\varphi_\delta}_{\infty}\ln\pa{\frac{c_0}{\alpha}}}.
$$
Introduce $\tilde Z(\ensuremath{\mathds{X}}_n) = \sum_{i=1}^n \varphi_\delta (X_i^1,X_{\ensuremath{{\Pi_n}}(i)}^2)$. Then, notice that
\begin{equation}
\label{eq:writing_stat}
T_\delta^\ensuremath{{\Pi_n}} (\ensuremath{\mathds{X}}_n) = \frac{1}{n-1}\pa{\tilde Z(\ensuremath{\mathds{X}}_n) - \esp{\tilde Z(\ensuremath{\mathds{X}}_n)\middle| \ensuremath{\mathds{X}}_n}}.
\end{equation}
Therefore, applying Theorem~\ref{thm:concQcqMoy} to the conditional probability given $\ensuremath{\mathds{X}}_n$, one obtains that there exist universal positive constants $c_0$ and $c_1$ such that, for all $x>0$,
\begin{multline*}
\proba{\abs{\tilde Z(\ensuremath{\mathds{X}}_n)-\esp{\tilde Z(\ensuremath{\mathds{X}}_n)\middle| \ensuremath{\mathds{X}}_n}} \geq  2\sqrt{2\pa{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2)}x} + 2\norm{\varphi_\delta}_\infty x\middle|\ensuremath{\mathds{X}}_n} \\
\leq c_0 \exp\pa{-c_1 x}.
\end{multline*}
In particular, from \eqref{eq:writing_stat}, one obtains
\begin{multline*}
\proba{\abs{T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}})} \geq  \frac{2}{n-1}\pa{\sqrt{2\pa{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2)}x} + \norm{\varphi_\delta}_\infty x}\middle| \ensuremath{\mathds{X}}_n} \\
\leq c_0 \exp\pa{- c_1 x}.
\end{multline*}

Yet, by definition of the quantile, $q_{1-\alpha}(\ensuremath{\mathds{X}}_n)$ is the smallest $u$ such that
$$\proba{\abs{T_\delta(\ensuremath{\mathds{X}}_n^{\ensuremath{{\Pi_n}}})} \geq u\middle|\ensuremath{\mathds{X}}_n} \leq \alpha.$$
Thus taking $x$ such that $c_0 \exp\pa{-c_1 x}=\alpha$ , that is $x=c_1^{-1} \ln\pa{c_0/\alpha}$, one obtains \eqref{eq:control_conditional_quantile} with $C' = 2 \max\ac{\sqrt{2/c_1}, 1/c_1}$ which is a universal positive constant.

\item[2nd step.] Let us now control the quantile $q_{1-\beta/2}^{\alpha}$.
Since \eqref{eq:control_conditional_quantile} is always true, by definition of $q_{1-\beta/2}^\alpha$, one has that $q_{1-\beta/2}^\alpha$ is upper bounded by the $(1-\beta/2)$-quantile of the right-hand side of \eqref{eq:control_conditional_quantile}.
Yet, the only randomness left in the right-hand side of \eqref{eq:control_conditional_quantile} comes from the randomness of $\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2)$, and thus it is sufficient to control its $(1-\beta/2)$-quantile.

Besides, applying Markov's inequality, one obtains for all $x>0$,
$$\proba{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2) \geq x} \leq \frac{\esp{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2) }}{x}, $$
with $\esp{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2) } = \esps{P}{\varphi_\delta^2} + (n-1) \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}$, and thus, taking $$x=\frac{2}{\beta}\pa{\esps{P}{\varphi_\delta^2} + (n-1) \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}},$$
one has that the $(1-\beta/2)$-quantile of $\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2)$ is upper bounded by $x$, and thus, the  $(1-\beta/2)$-quantile of $\sqrt{\frac{1}{n}\sum_{i,j=1}^n \varphi_\delta^2(X_i^1,X_j^2)}$ is itself upper bounded by
$$\sqrt{\frac{2}{\beta}}\pa{\sqrt{\esps{P}{\varphi_\delta^2}} + \sqrt{n}\sqrt{\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}}.$$
Finally,
\begin{eqnarray*}
q_{1-\beta/2}^\alpha &\leq & \frac{2C'}{n} \ac{\sqrt{\frac{2}{\beta}}\pa{\sqrt{\esps{P}{\varphi_\delta^2}} + \sqrt{n}\sqrt{\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}} \sqrt{\ln\pa{\frac{c_0}{\alpha}}} + \norm{\varphi_\delta}_{\infty}\ln\pa{\frac{c_0}{\alpha}}}
\end{eqnarray*}
which is exactly \eqref{eq:control_quantile} for any constant $C\geq 2C'$.
\end{description}

\section{Proof of Lemma~\ref{lm:calcul_variance}}
\label{sct:proof_lm_calcul_variance}

Let us now prove Lemma \ref{lm:calcul_variance}.
Let $n\geq 4$ and $\ensuremath{\mathds{X}}_n$ be an i.i.d. sample with distribution $P$.
First notice that one can write
$$T_\delta(\ensuremath{\mathds{X}}_n) = \frac{1}{n(n-1)} \sum_{i\neq j} \pa{\varphi_\delta (X_i^1,X_i^2) - \varphi_\delta(X_i^1,X_j^2)}.$$
In particular, one recovers that $\esp{T_\delta(\ensuremath{\mathds{X}}_n)} = \esps{P}{\varphi_\delta}-\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta}$.

For a better readability, let us introduce for all $i\neq j$ in \ac{1,2,\ldots,n},
$$Y_i = \varphi_\delta(X_i^1,X_i^2)-\esps{P}{\varphi_\delta} \quad \mbox{and}\quad Z_{i,j} = \varphi_\delta(X_i^1,X_j^2)-\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta}.$$ Then,
\begin{equation}
\label{eq:propYZ}
\esp{Y_i} = \esp{Z_{i,j}} = 0,\quad \mbox{and} \quad
\left\{\begin{array}{l}
\displaystyle \esp{Y_i^2} = \vars{P}{\varphi_\delta}\leq \esps{P}{\varphi_\delta^2},\\
\displaystyle \esp{Z_{i,j}^2} = \vars{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta}\leq \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}.
\end{array}\right.
\end{equation}

One can write $$T_\delta(\ensuremath{\mathds{X}}_n) - \esp{T_\delta(\ensuremath{\mathds{X}}_n)} = \frac{1}{n(n-1)} \sum_{i\neq j} \pa{Y_i - Z_{i,j}},$$ and thus,
\begin{eqnarray*}
\var{T_\delta(\ensuremath{\mathds{X}}_n)} &=& \esp{\pa{\frac{1}{n(n-1)} \sum_{i\neq j} \pa{Y_i - Z_{i,j}}}^2} \\
&=& \frac{1}{n^2(n-1)^2} \sum_{i\neq j} \sum_{k\neq l} \esp{\pa{Y_i-Z_{i,j}}\pa{Y_k - Z_{k,l}}} \\
&=& A_n - 2 B_n + C_n, \\
\end{eqnarray*}
with
$$A_n = \frac{1}{n^2} \sum_{i,k=1}^n \esp{Y_i Y_k},$$
$$B_n = \frac{1}{n^2(n-1)} \sum_{i=1}^n\sum_{k\neq l} \esp{Y_i Z_{k,l}},$$
$$C_n = \frac{1}{n^2(n-1)^2} \sum_{i\neq j} \sum_{k\neq l} \esp{Z_{i,j} Z_{k,l}},$$
where each sum is taken for indexes contained in $\ac{1,2,\ldots,n}$.
In particular, since just an upper-bound of the variance is needed, it is sufficient to write
\begin{equation}
\label{eq:control_variance1}
\var{T_\delta(\ensuremath{\mathds{X}}_n)} \leq |A_n| + 2 |B_n| + |C_n|,
\end{equation}
and to study each term separately.

\paragraph{Study of $A_n$.} Since by construction, the $Y_i$'s are centered, and independent (as the $X_i$'s are),
\begin{eqnarray*}
A_n &=& \frac{1}{n^2} \pa{ \sum_{i} \esp{Y_i^2} + \sum_{i\neq k} \esp{Y_i}\esp{Y_k}} \\
&=& \frac{1}{n} \esp{Y_1^2}, \\
\end{eqnarray*}
and in particular, from \eqref{eq:propYZ},
\begin{equation}
\label{eq:control_A}
\abs{A_n} \leq \frac{1}{n} \esps{P}{\varphi_\delta^2}.
\end{equation}

\paragraph{Study of $B_n$.} If $i$, $k$ and $l$ are all different, using once again the independence of the $X_i$'s and a centering argument, then $\esp{Y_{i}Z_{k,l}} = \esp{Y_{i}}\esp{Z_{k,l}} = 0$. Thus
\begin{eqnarray*}
B_n &=& \frac{1}{n^2 (n-1)} \sum_{i\neq k} \pa{ \esp{Y_i Z_{i,k}} + \esp{Y_i Z_{k,i}} } \\
&=& \frac{1}{n} \pa{\esp{Y_1 Z_{1,2}} + \esp{Y_1 Z_{2,1}}}.
\end{eqnarray*}
In particular, applying the Cauchy-Schwartz inequality, and from \eqref{eq:propYZ}, one obtains
\begin{equation}
\label{eq:control_B}
\abs{B_n} \leq  \frac{2}{n}\sqrt{\esp{Y_1^2} \esp{Z_{1,2}^2}}
\leq  \frac{2}{n}\sqrt{\esps{P}{\varphi_\delta^2} \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}.
\end{equation}

\paragraph{Study of $C_n$.} Still by an independence and a centering argument, if $i$, $j$, $k$ and $l$ are all different,
$\esp{Z_{i,j} Z_{k,l}} = \esp{Z_{i,j}}\esp{Z_{k,l}} = 0$. Thus, if $I_n^{[3]}$ denotes the set of triplets $(i,j,k)$ in $\ac{1,\dots,n}^3$ which are all different, one obtains
\begin{eqnarray*}
C_n &=& \frac{1}{n^2 (n-1)^2} \Bigg\{ \sum_{(i,j,k) \in I_n^{[3]}} \Big( \esp{Z_{i,j} Z_{i,k}} + 2 \esp{Z_{i,j} Z_{k,i}} +  \esp{Z_{j,i} Z_{k,i}} \Big) \\
&& \quad\quad\quad\quad\quad\quad +\ \sum_{i\neq j} \Big( \esp{Z_{i,j}^2} + \esp{Z_{i,j} Z_{j,i} }\Big) \Bigg\} \\
&=& \frac{n-2}{n(n-1)} \pa{\esp{Z_{1,2} Z_{1,3}} + 2 \esp{Z_{1,2} Z_{3,1}} + \esp{Z_{2,1} Z_{3,1}} }  \\
&& +\ \frac{1}{n(n-1)}\pa{\esp{Z_{1,2}^2} + \esp{Z_{1,2} Z_{2,1} }}.
\end{eqnarray*}
In particular, applying the Cauchy-Schwartz inequality, and using \eqref{eq:propYZ}, each expectation in the previous equation satisfies
$\esp{Z_{i,j} Z_{k,l}}\leq \esp{Z_{1,2}^2} \leq \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}$, and thus

\begin{equation}
\label{eq:control_C}
\abs{C_n} \leq  \pa{\frac{4(n-2)}{n(n-1)} + \frac{2}{n(n-1)}}\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}
\leq  \frac{4}{n} \esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}.
\end{equation}

Finally, combining \eqref{eq:control_variance1}, \eqref{eq:control_A}, \eqref{eq:control_B}, and \eqref{eq:control_C} leads to
$$\var{T_\delta(\ensuremath{\mathds{X}}_n)} \leq \frac{1}{n}\pa{\sqrt{\esps{P}{\varphi_\delta^2}} + 2 \sqrt{\esps{\ensuremath{\perp\!\!\!\perp}}{\varphi_\delta^2}}}^2, $$
which ends the proof of the Lemma.

redpajama_set_name: RedPajamaArXiv


The set includes 2 cut-out sheets for a total of 84 antiquarian book covers in various sizes.
Balsa wood profile strips for 4 mm, 6 mm and 8 mm wide spines and a Pritt glue stick are additionally included as working materials.
Balsa wood profile strips for 4 mm, 6 mm and 8 mm wide spines and a Pritt glue stick are additionally included as working material.


text:
About The DN
Lincoln, NE (68508)
Sunshine and clouds mixed. High 43F. Winds WNW at 15 to 25 mph. Higher wind gusts possible..
A clear sky. Low 23F. Winds SW at 10 to 15 mph.
Other Husker Sports
Sports Feature
Fighting the Footprint
Let's talk: Campus Speech
Saving the Greek System
Shrinking Rural Nebraska: Map of Nowhere
Marijuana Legalization Challenges
Keystone Pipeline: Should we build?
Visiting UNL
Curious Cornhuskers
Art by Grace Orwen
BEACH: Electoral College gives some Nebraskans privilege of voting third party without consequence
The opinion of Brian Beach
Brian Beach
Despite its consistent unpopularity, the Electoral College has survived another election cycle and will determine the next President this November.
A majority of Americans want this traditional method of electing the President to be replaced, including 81% of Democrats and those who lean Democrat who say the Constitution should be amended so the candidate who receives the most votes nationwide wins the election, according to Pew Research.
While it is too late to amend the Electoral College in this election cycle, some of the more frustrating aspects of the system may actually free up your Presidential vote in 2020.
It is easy to see the unfairness of the Electoral College when considering that California's electors represent 3.18 times more voters than Wyoming's. In other words, a vote in Wyoming is worth over three times more than a vote in California.
But if Wyoming's individual voters have more power than in any other state, why isn't Wyoming a popular campaign stop for candidates? Apart from its small population, Wyoming is consistently conservative. The state has not voted for a Democratic presidential candidate since 1964 and no Democrat candidate has even amassed one-third of the state's vote since 2000.
If you're a Democrat in Wyoming, your Presidential vote doesn't matter much at all. If you're a Republican in Wyoming, your vote doesn't really affect the outcome either. Even in a close national election, Wyoming votes only matter in Wyoming, and there has not been a close election there in 20 years.
The same dilemma applies in pretty much every strong Democrat and Republican state from New York to most of Nebraska.
Nebraska is one of two states, along with Maine, which allocates its electoral votes by congressional district. The winner of each district receives one electoral vote, while the statewide winner receives two additional electoral votes. While Nebraska is a conservative stronghold statewide, one congressional district is shaping up to be a close race.
If you are voting in Nebraska's 2nd Congressional District, which includes most of the Omaha metropolitan area, you should vote for either Donald Trump or Joe Biden. Even if you consider that choice to be the lesser of two evils, this is your best chance to have the biggest impact with your vote. According to FiveThirtyEight, Biden has a 76% chance of winning the district, though Trump is within striking distance and has a history of winning elections despite the polls giving him unfavorable chances.
Whether you are a Trump or Biden supporter, tolerator, or just hate one of them a smidge more than the other, voting for one of these two is the best way to make your voice heard in the Omaha area. The New York Times even wrote that the district could be the deciding factor in a tight national election. If you live in NE-02, a third party vote is foolish and would essentially be throwing your vote away.
If you live outside of the 2nd District in Nebraska or in any other solidly red or blue state, thanks to the Electoral College, your Presidential vote has pretty much been thrown away already. But that does not mean you should skip your trip to the polls altogether.
Not only are there plenty of down ballot elections to consider, but you have a special opportunity to vote for a more ideal candidate regardless of their chance of winning without the pressure of the nation's fate resting in your ballot box.
As the ACLU Nebraska billboards across Omaha and Lincoln have said, "Every vote is a protest."
In the case of Omaha, your vote for Trump or Biden is either a protest of Trump's administration or Biden's proposed policies. Everywhere else, your vote can serve as a protest of the two-party system that made two septuagenarians with sexual assault allegations who have both struggled to string together coherent sentences as the only two viable candidates in this year's election.
You can still vote for Biden or Trump if you believe that they are truly the best options to lead the nation. But in uncompetitive areas, your list of potential candidates is greater than two.
Want a $20 minimum wage and a candidate who actually supports the Green New Deal without reservation? Vote for the Green Party's Howie Hawkins.
Pro-life and anti-death penalty? Vote for Brian Carroll, the American Solidarity Party nominee.
Big rap fan and in favor of getting a million dollar check when you have a baby? Vote for Kanye West of the Birthday Pa – yeah, that's probably throwing away your vote no matter where you live.
Still, a vote for Kanye in an uncompetitive state is not consequential for either of the two major candidates, so unless you are voting in a swing state or swing district, a vote for Kanye is not necessarily a vote for Trump, despite what some left-leaning sites may say.
None of these candidates have a chance of winning even one electoral vote in this year's election, but your vote has the potential to send a message. Third party ideas are sometimes adopted by major party candidates, including women's suffrage, the direct election of senators and even the abolition of slavery.
Is voting third-party a privilege? Absolutely. A white privilege perhaps? Considering that most states with a vast majority of white people are GOP strongholds, you could even make that argument. But that does not make it a bad thing. After all, for people living in more competitive districts, actually getting a chance to elect the President seems like a privilege in itself.
It is still possible for Biden to win Nebraska, Kansas and other traditionally conservative states, just as Trump could win Minnesota, Colorado and other traditionally liberal states. If you are a staunch Republican or Democrat, a map showing these states in your preferred color may be cool to see on election night, but they will not be the deciding factor, as close elections in these states are a sure sign of a landslide win in swing states.
In other words, even if third party votes keep Biden from eking out a victory in Nebraska's 1st Congressional District — a Republican leaning district which includes Lincoln — they will probably not cost Biden from ultimately winning the Presidency.
So remember, this election, you can go to the polls or your nearest mailbox, and vote for your favorite candidate, free of the responsibility of actually picking the next President of the United States, just as our founding fathers intended.
And you can do it all with a clean conscience, knowing your vote for one candidate is not just a vote for one of two major party candidates in disguise.*
*Offer only available in select markets. Void where prohibited (including NE-02).
Brian Beach is a sophomore journalism major. Reach him at brianbeach@dailynebraskan.com
Follow Brian Beach
Subscribe to our newsletter, The Husk
Nebraska volleyball team prepares for spring season after a year without competition
Nebraska head coach Fred Hoiberg tests positive for COVID-19
Huskers upset undefeated No. 15 Ohio State 63-55
No. 5 Nebraska Wrestling defeats No. 13 Minnesota in season opener
No. 5 Nebraska wrestling dominated by No. 1 Iowa
Nebraska women's gymnastics drops season opener against Illinois
Chancellor Green clarifies spring protocols, saliva testing to begin Jan. 19
Pre-1966 Archives
dailynebraskan.com
Email: dn@unl.edu
© Copyright 2021, The Daily Nebraskan, P.O. Box 880448 Lincoln, NE

redpajama_set_name: RedPajamaCommonCrawl


text:
package com.buession.httpclient.conn;

import com.buession.httpclient.core.Configuration;

/**
 * 连接管理器
 *
 * @author Yong.Teng
 */
public interface ConnectionManager<O> {

    /**
     * 获取连接对象
     *
     * @return 连接对象
     */
    Configuration getConfiguration();

    /**
     * 设置连接对象
     *
     * @param configuration
     *         连接对象
     */
    void setConfiguration(Configuration configuration);

    /**
     * 获取驱动连接管理器
     *
     * @return 连接管理器
     */
    O getClientConnectionManager();

    /**
     * 设置连接管理器
     *
     * @param clientConnectionManager
     *         连接管理器
     */
    void setClientConnectionManager(O clientConnectionManager);

    /**
     * 创建驱动默认连接管理器
     *
     * @return 连接管理器
     */
    O createDefaultClientConnectionManager();

}

redpajama_set_name: RedPajamaGithub


text:
Sweet 'Dreams' Are Made of Twisted Pine Covering Blondie's "Heart of Glass" (premiere)
Michael Bialas
Photo courtesy of the artist
Four musicians from various parts of the country with varied influences found a common bond in Boston as Twisted Pine, and take on some heavy hitters as they release a seven-song EP full of spark, light and irresistible force.
Twisted Pine
Heralded as an unconventional Americana string quartet based in Boston, the four versatile members of Twisted Pine have emerged from underneath the covers to reveal their love for the Beatles, Scissor Sisters, the Cranberries and, yes, disco-era Blondie.
The result is a charming, refreshing take on oldies but goodies by the figurative twisted sisters and brothers who all lend their voices to this band that includes lead vocalists Kathleen Parks (fiddle) and Rachel Sumner (guitar), mandolinist Dan Bui and bassist Chris Sartori.
As they prepare for the Friday (June 8) release of Dreams (via Signature Sounds), their EP of seven wildly innovative covers of songs including "Lucy in the Sky With Diamonds", "I Don't Feel Like Dancin'", and the title cut, the fearless foursome present the music video premiere of Blondie's "Heart of Glass" today (June 5) at PopMatters.
Twisted Pine came down with disco fever on their new EP. / Photo by Hannah Cohen
The song written by new wave wonder woman Debbie Harry and her musical partner Chris Stein launched Blondie and their third album, 1978's Parallel Lines, into the pop culture stratosphere with her sexy vocals and the band's propulsive disco beat.
Twisted Pine's Parks elevates the new music video with breathy vocals, fiddlelicious fury and smooth dancehall moves during a spirited performance under the direction of her best friend, videographer Zoe Mitchell, who shot it during a sunny and breezy afternoon on the first day of May in an alleyway of Boston's North End.
"Zoe and I have known each other for almost six years now; we met during our first semester at Berklee College of Music [in Boston] and have always connected in a very special and unique way that I've truly cherished," Parks wrote in a series of email responses for this article that accompanies the premiere. "She is the water to my fire, and we make each other laugh — a lot."
With Mitchell and Bui, the three put together the video concept that includes, Parks said, "The modern twist of showing the band on the road performing in different clubs and venues through a cellphone because isn't that how we find out most information about each other anyway? We wanted to give a nod to the '80s with the leather jacket, sunglasses, black and white alleyway footage and feel-good vibes while still sticking with the times."
So to celebrate the 40th anniversary of Blondie's Parallel Lines, and the impending release of Twisted Pine's sweet Dreams, check out "Heart of Glass", then continue reading to learn more about the cover, the video, the album and the band ahead of their tour through the Midwest and Northeast this summer.
"Since I was a kid, this song has made me want to dance whether it was in the car or rocking down the street with headphones," Parks said when asked how she found her inner Debbie Harry to groove through the video. "I knew dance had to be a part of this because it's part of disco culture. When I mentioned it to Zoe on the day of filming, she immediately agreed and encouraged me to really rock out. While we were filming, if ever she could tell I was feeling unsure or shy, she would call out 'vogue!' or 'energy, energy!' and I would burst into a smile. She made me feel awesome!"
Though the band members have connected through college, bluegrass and roots instruments, they brought jazz, funk, R&B, pop and British ballad sensibilities to the mix while exploring their musical identities. Parks, Sumner and Bui met at Berklee, while Sartori went to UMass-Amherst but studied jazz at Berklee.
Twisted Pine, a band competition winner (FreshGrass in 2014) and runner-up (RockyGrass in 2015) at prestigious music festivals, released their self-titled full-length debut album of 11 original songs on July 14, 2017.
Dreams by Twisted Pine
The decision to next record and produce an EP of covers, including a respectfully rip-roaring rendition of Joni Mitchell's "Raised on Robbery" and the fitting finale of "Dreams", sounding more poignant following the January death of Cranberries lead singer Dolores O'Riordan, was an easy one, according to Parks.
"We first started learning and playing these songs because our renditions and mashups came very naturally to us," she said. "For example, 'El Chepe/The One I Love Is Gone', came out while making a set list for a bluegrass gig. Vulfpeck's 'El Chepe' had just come out, and Chris was laying it down on the bass; Rachel was writing out a set list asking us if we wanted to play 'The One I Love Is Gone' (Bill Monroe's minor waltz), and all of a sudden the vocal phrasing just came out of me, like a moment in a musical. Others such as 'I Don't Feel Like Dancin' ' came from our love of disco bass lines, Scissor Sisters, and Elton John. We wanted to get those grooves in our hands. Rachel absolutely slays the vocal — turning it into a honky-tonk, contemporary affair."
For a band that triumphantly covers a lot of ground in a short period, Twisted Pine surely knows these reboots are made for walking on sunshine.
When playing covers, Twisted Pine's approach is "to keep the music fresh in any way we can," said fiddler Kathleen Parks. / Photo courtesy of the artist
TWISTED PINE'S KATHLEEN PARKS TAKES A POPMATTERS POP QUIZ
There's no extra credit, but Kathleen Parks, the fiddler who shares lead vocals with Rachel Sumner, also agreed to fill in the blanks of her life and answer a few more questions. Get to know the musician who was 18 when she moved to Boston to study violin performance and songwriting at Berklee College of Music before graduating last spring.
Family members: "My father Eric played the trumpet and was the leader of West Point Military's Jazz Knights and the Grammy-award winning Jimmy Sturr Orchestra for about 30 years. My mother was a dancer and took me to violin and dance lessons. She drove many late nights and long distances to get me and my brother Conor back and forth from Irish step-dancing lessons when were teens. My brother played upright bass in high school and likes to burst into a wedding reception with his Justin Timberlake dance moves. He and I share that in common. He and my sister-in-law Jodi practice medicine in Long Island."
Status: "I'm currently in a very happy and loving relationship. Living in Salem, Massachusetts, and loving Witch City. Everybody in this town is funky, and it's so easy to get to the beach. Currently, don't have any tattoos or piercings; if I get them, I'm going to wait until I'm old and all my skin sags so that the image doesn't droop from years of aging."
Hobbies: "Some of my best songs have come to me when I've been away from my instrument doing chores of some kind, or while taking a walk. I'm a big fan of Jazzercise, exclaiming 'We're gonna boogie down!' in a man voice, and squishing cats, dogs and people big or small."
1. What's your favorite cover to cover live?
Kathleen Parks: "That's so tough to answer! I guess I would have to say 'El Chepe/The One I Love Is Gone' because the way we play it live is different every time. Recently, Chris has been opening the song with a super free-improvised bass solo where sometimes he'll be playing in a different key or time signature and make it land into the song's groove perfectly. It leaves goosebumps on my arms. Other reasons to love the song is the weaving in and out of melody and harmony singing with Rachel, and space jamming with Dan. The freedom we give this song has extended into all of the other covers we perform live. We really try to keep the music fresh in any way we can. You have to be on your toes the whole time, and that's what's so much fun about playing in this band."
2. Have you heard from Debbie Harry or anyone else from Blondie regarding your cover or music video for "Heart of Glass"?
Parks: "Not yet! I know Debbie and the band are on tour right now. It would be a dream come true if we ever heard from any of them, maybe after June 8th!"
3. Who's the biggest disco fan of the group, and why?
Parks: "Hmmmmmmm, that's probably a competition between Chris and I. I'm known to bust out the disco in the van and play the Bee Gees, Pointer Sisters or a disco-fever playlist. Meanwhile, Chris can just bust out the bass and play you some Jamiroquai, he's so good!"
4. Who's the biggest disco hater of the group, and why?
Parks: "Aw man, we actually all love it. As soon as someone puts it on, we're all bobbing our heads."
5. Who's the party animal of the group and what led to that distinction?
Parks: "Dan! We call him Fireball Bui for more than just his fast mandolin licks."
6. Assuming you had other possible choices, which cover was the most painful to leave off the EP?
Parks: "We ended up getting all the covers we wanted onto the EP, including the Cranberries' 'Dreams,' which we recorded two months after the original six. Now, we sometimes do a nice rendition of [Bob] Dylan's 'Simple Twist of Fate,' which Rachel really shines on."
7. Since your EP is titled Dreams, what recurring dream do you have about Twisted Pine's future?
Parks: "We really want to keep growing and writing. Take our sound as far as we possibly can, and continue to use our influences to keep inspiring us along the way. A dream of ours is to play NPR's Tiny Desk Concert; that would be so great for us."
Michael Bialas is a journalist and photographer who enjoys writing about entertainment and sports for a number of online publications, including PopMatters and No Depression. Follow him on Twitter: @mjbialas
Twisted Pine (@TwistedPineBand) | Twitter ›
Twisted Pine ›
Twisted Pine - Home | Facebook ›
twisted pine signature sounds music video folk bluegrass blondie americana interview premiere


Charlie Neese's eye for detail and extensive knowledge of Middle Tennessee serves him well as a Realtor for Zeitlin Sotheby's International Realty. It also helped him win two Emmys while working as a television meteorologist here in Nashville. Charlie says attention to detail helps whether you're looking for a new home or trying to sell.
It's also a focus on the details of customer service and knowing the market.
Quite simply, whether you're selling your home or in the market for one, it's is a big deal.
A native Nashvillian, Charlie loves helping people find just what they want here in Middle Tennessee.
Charlie has watched Nashville's rapid growth through the years but says some things about the area never change.
Most of all, Charlie says it's the people.


RCW 28A.230.097: Career and technical high school course equivalencies.
Career and technical high school course equivalencies.
(1) Each high school or school district board of directors shall adopt course equivalencies for career and technical high school courses offered to students in high schools and skill centers. A career and technical course equivalency may be for whole or partial credit. Each school district board of directors shall develop a course equivalency approval procedure. Boards of directors must approve AP computer science courses as equivalent to high school mathematics or science, and must denote on a student's transcript that AP computer science qualifies as a math-based quantitative course for students who take the course in their senior year. Beginning no later than the 2015-16 school year, a school district board of directors must, at a minimum, grant academic course equivalency in mathematics or science for a high school career and technical course from the list of courses approved by the superintendent of public instruction under RCW 28A.700.070, but is not limited to the courses on the list. If the list of courses is revised after the 2015-16 school year, the school district board of directors must grant academic course equivalency based on the revised list beginning with the school year immediately following the revision.
(2) Career and technical courses determined to be equivalent to academic core courses, in full or in part, by the high school or school district shall be accepted as meeting core requirements, including graduation requirements, if the courses are recorded on the student's transcript using the equivalent academic high school department designation and title. Full or partial credit shall be recorded as appropriate. The high school or school district shall also issue and keep record of course completion certificates that demonstrate that the career and technical courses were successfully completed as needed for industry certification, college credit, or preapprenticeship, as applicable. The certificate shall be part of the student's high school and beyond plan. The office of the superintendent of public instruction shall develop and make available electronic samples of certificates of course completion.
Reviser's note: This section was amended by 2018 c 73 § 1 and by 2018 c 177 § 301, each without reference to the other. Both amendments are incorporated in the publication of this section under RCW 1.12.025(2). For rule of construction, see RCW 1.12.025(1).
(f) Strategies are needed to support additional opportunities for Washington students to have careers in the innovative, technology-based or technology-enhanced industries located in our state.
Finding—Intent—2006 c 114: "(1) The legislature finds that Washington's performance-based education system should seek to provide fundamental academic knowledge and skills for all students, and to provide the opportunity for students to acquire knowledge and skills likely to contribute to their own economic well-being and that of their families and communities.
(2) The legislature recognizes that career and technical options are available for students.
(3) High schools or school districts should take advantage of their opportunity to offer course credits, including credits toward graduation requirements, for knowledge and skills in fundamental academic content areas that students gain in career and technical education courses.


My original score for this dance piece featured 4-channel sound, spread throughout a reclaimed warehouse. Audiences were seated in one of three performance areas while simultaneous dances could be glimpsed through gaps. Three times, audiences switched areas and the repeating dance was witnessed from a new perspective and with new music.
Linda Austin and I reconfigured the solo from this performance as a video and sound installation called Circus Me (A Round).