Concentration inequalities using approximate zero bias couplings with applications to Hoeffding’s statistic under the Ewens distribution

Stein’s method was first introduced by Charles Stein in his seminal paper (Stein (1972)) and is best known for obtaining non-asymptotic bounds on various distances for distributional approximations, see the text (Chen et al. (2011)) and the introductory notes (Ross (2011)). Thus far, many applications in several areas such as combinatorics, statistics, statistical physics and applied sciences have been developed using this method. Meanwhile, some researchers have used Stein’s method for non-distributional approximation contexts. Chatterjee (2007) introduced a version of Stein’s method for deriving concentration of measure inequalities.

The name ‘concentration of measure’ was first used in Talagrand (1995) when the author aimed to derive deviation bounds of the form $P(|X-\mathbb{E}X|\geq x)$ in the situations where the exact evaluation is impossible or is hard to obtain. A bound of this form is considered ‘good’ if it decays sufficiently rapidly in $x$. For instance, most of the works in the literature seek for bounds that are decreasing at exponential rate.

Now we only restrict our attention to concentration inequalities using Stein’s method. Laipaporn and Neammanee (2006) and Rattanawong (2013) obtained non-uniform concentration inequalities for randomized orthogonal array sampling designs and random permutation sum, respectively, however, they are not in the form that we focus on. Chatterjee (2007) used exchangeable pairs technique to provide concentration of measure for functions of dependent random variables, including the Hoeffding’s statistic when the random permutation has the uniform distribution and the net magnetization in the Curie-Weiss model. Once the connection between Stein’s method and concentration inequalities was uncovered, many results have been obtained using various techniques related to Stein’s method. Concentration bounds using bounded size bias couplings was introduced in Ghosh and Goldstein (2011b) and Ghosh and Goldstein (2011a) with examples including the number of relatively ordered subsequences of a random permutation, sliding window statistics, the lightbulb process, and etc. The same type of results with the help of bounded zero bias couplings occurred in Goldstein and Işlak (2014) with applications to the Hoeffding’s statistic where the random permutation has either the uniform distribution or one which is constant over permutations with the same cycle type and having no fixed points. The bounded size bias technique was strengthened in Arratia and Baxendale (2015) and the bounded assumption was relaxed by Cook et al. (2018) with applications to Erdös-Rényi graphs and permutation models.

In this work, we generalize the results in Goldstein and Işlak (2014) with zero bias couplings replaced by approximate zero bias couplings, first appeared in Wiroonsri (2017). This coupling is constructed by adding a remainder term to the construction of the zero bias coupling generated by a $\lambda$-Stein pair (see Goldstein and Reinert (1997) or Section 4.4 of Chen et al. (2011)). Here we provide brief detail, presented in Wiroonsri (2017), of the construction of approximate zero bias couplings generated by approximate $\lambda,R$-Stein pairs. Recall that we call a pair of random variables $(Y^{\prime},Y^{\prime\prime})$, an approximate $\lambda,R$-Stein pair if it is exchangeable and satisfies

$\displaystyle\mathbb{E}Y^{\prime}=0,\quad\mathrm{Var}(Y^{\prime})=\sigma^{2}$

(1)

with $\sigma^{2}\in(0,\infty)$, and

$\displaystyle\mathbb{E}(Y^{\prime\prime}|Y^{\prime})=(1-\lambda)Y^{\prime}+R,$

(2)

for some $0<\lambda<1$ and $R=R(Y^{\prime})$.

Now we state the following lemma proved in Wiroonsri (2017) which is the generalized version of the result in Goldstein and Reinert (1997) with a $\lambda$-Stein pair replaced by an approximate $\lambda,R$-Stein pair. We call $Y^{*}$ that satisfies (3), an approximate $Y^{\prime}$-zero bias variable.

The core idea of Stein’s method is based on the fact that a mean zero random variable $W$ is normal if and only if $\mathbb{E}[Wf(W)]=\sigma^{2}\mathbb{E}[f^{\prime}(W)]$ for all absolutely continuous function. Therefore if $Y^{\prime}$ and $Y^{*}$ can be closely coupled by using Lemma 1.1 satisfying (3) with some small remainder term $R$ then we expect that the behavior of $Y^{\prime}$, including the decay of its tail probabilities, may be simlar to that of the normal. Wiroonsri (2017) obtained $L^{1}$ and $L^{\infty}$ bounds between $Y^{\prime}/\sigma$ and the standard normal in term of the difference $|Y^{\prime}-Y^{*}|$ and the remainder term $R$. Here we focus on the concentration bounds on the same setting.

We also apply our result to the Hoeffding’s statistic (Hoeffding (1951)) where the random permutation has the Ewens distribution. That is, we study the distribution of

$\displaystyle Y=\sum_{i=1}^{n}a_{i,\pi(i)}$

(4)

where $A\in\mathbb{R}^{n\times n}$ is a given real matrix with components $\{a_{i,j}\}_{i,j=1}^{n}$ and $\pi\in\mathcal{S}_{n}$ has the Ewens distribution where $\mathcal{S}_{n}$ denotes the symmetric group. We note that the distribution of $Y$ is of interest as it has a connection to nonparametric tests in statistics. Wiroonsri (2017) has succeeded in providing $L^{1}$ and $L^{\infty}$ bounds of order $\sigma^{-1}$ between $Y$ and the normal by constructing an approximate $Y$-zero bias coupling and deriving the bounds based on the coupling. In the present work, we follow the construction there and apply the following main results to obtain concentration inequalities.

We now state the main theorem and then add a remark comparing the results here to the ones in Goldstein and Işlak (2014).

Part (b) shows that the respective asymptotic orders as $t\rightarrow\infty$ of $\exp(-t/(2c))$ and $\exp(-t/c)$ of the bounds (5) and (6) can be improved to $\exp(-t\log t/(2c))$.

Stein’s method has been used with Ewens distribution recently in Gan and Ross (2021) where they obtained an upper bound on the total variabtion distance between the random partition generated by Ewens Sampling Formula and the Poisson-Dirichlet distribution. Ewens distribution has also attracted attention in other fields of mathematics for a while (see Johnson et al. (1997), Arratia et al. (2003), Crane (2016) and da Silva et al. (2020) for instance.)

The remainder of this work is organized as follows. We present an application to the Hoeffding’s statistic where the random permutation has the Ewens distribution in Section 2. A few simulation experiments are then performed in Section 3. Finally, we devote the last section for the proof of our main theorem.

As introduced in the first section, we study the distribution of

$\displaystyle Y=\sum_{i=1}^{n}a_{i,\pi(i)}$

(8)

where $A\in\mathbb{R}^{n\times n}$ is a given real matrix with components $\{a_{i,j}\}_{i,j=1}^{n}$ and $\pi\in\mathcal{S}_{n}$ has the Ewens distribution. The original work (Hoeffding (1951)) studied the asymptotic normality of $Y$ when $\pi\in\mathcal{S}_{n}$ has a uniform distribution. We note that, in this section, we consider the symbols $\pi$ and $Y$ interchageable with $\pi^{\prime}$ and $Y^{\prime}$, respectively.

We first briefly describe the Ewens distribution and state some important properties. The Ewens distribution ${\cal E}_{\theta}$ on the symmetric group ${\cal S}_{n}$ with parameter $\theta>0$, was first introduced in Ewens (1972) and used in population genetics to describe the probabilities associated with the number of times that different alleles are observed in the sample; see also Arratia et al. (2003) for the description in mathematical context. Let $\mathbb{N}_{k}=[k,\infty)\cap\mathbb{Z}$. In the following, for $x\in\mathbb{R}$ and $n\in\mathbb{N}_{1}$, we use the notations

$\displaystyle x^{(n)}=x(x+1)\cdots(x+n-1)\text{ \ \ and \ \ }x_{(n)}=x(x-1)\cdots(x-n+1).$

For a permutation $\pi\in\mathcal{S}_{n}$, the Ewens measure is given by

$\displaystyle P_{\theta}(\pi)=\frac{\theta^{\#(\pi)}}{\theta^{(n)}},$

(9)

where $\#(\pi)$ denotes the number of cycles of $\pi$. We note that ${\cal E}_{\theta}$ specializes to the uniform distribution over all permutations when $\theta=1$.

A permutation $\pi_{n}\in\mathcal{S}_{n}$ with the distribution ${\cal E}_{\theta}$ can be constructed by the “so called” the Chinese restaurant process (see e.g. Aldous (1985) and Pitman (1996)), as follows. For $n=1$, $\pi_{1}$ is the unique permutation that maps $1$ to $1$ in $\mathcal{S}_{1}$. For $n\geq 2$, we construct $\pi_{n}$ from $\pi_{n-1}$ by either adding $n$ as a fixed point with probability $\theta/(\theta+n-1)$, or by inserting $n$ uniformly into one of $n-1$ locations inside a cycle of $\pi_{n-1}$, so each with probability $1/(\theta+n-1)$. Following this construction, for $i,j,k,l\in[n]$ where $[n]=\{1,2,\ldots,n\}$ such that $i\neq j$ and $k\neq l$, we have

$\displaystyle P_{\theta}(\pi(i)=k)=\begin{cases}\frac{1}{\theta+n-1}\text{ \ if \ }k\neq i,\\ \frac{\theta}{\theta+n-1}\text{ \ if \ }k=i\end{cases}.$

(10)

A distribution on $\mathcal{S}_{n}$ is said to be constant on cycle type if the probability of any permutation $\pi\in{\cal S}_{n}$ depends only on the cycle type $(c_{1},\ldots,c_{n})$ where $c_{q}(\pi)$ is the number of $q$ cycles of $\pi$ and we write $c_{q}$ for $c_{q}(\pi)$ for simplicity. Concentration inequalities of $Y$ where $\pi\in\mathcal{S}_{n}$ has either a uniform distribution or one which is constant over permutations with the same cycle type and having no fixed points were obtained in Goldstein and Işlak (2014) by using zero bias couplings. It follows from (9) directly that the Ewens distribution is constant on cycle type and allows fixed point. Due to the difference, the zero biasing technique does not work here and thus we use approximate zero biasing as discussed in the first section instead. We first follow the construction of approximate $Y$-zero bias couplings presented in Wiroonsri (2017) and then apply Theorem 1.2 to obtain concentration bounds. It is interesting to study the robustness and the sensitivity of the tail probabilities when the controlled assumptions have changed.

We begin with stating the definitions, notations and assumptions used in Wiroonsri (2017). Letting

$\displaystyle a_{\bullet,\bullet}=\frac{1}{n(\theta+n-1)}\left(\theta\sum_{i=1}^{n}a_{i,i}+\sum_{i\neq j}a_{ij}\right),$

(11)

by (10), we have

$\displaystyle\mathbb{E}Y=na_{\bullet,\bullet}.$

(12)

Letting

$\displaystyle\widehat{a}_{i,j}=a_{i,j}-a_{\bullet,\bullet},$

and using (12), we have

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{n}\widehat{a}_{i,\pi(i)}\right]=\mathbb{E}\left[\sum_{i=1}^{n}(a_{i,\pi(i)}-a_{\bullet,\bullet})\right]=\mathbb{E}\left[\sum_{i=1}^{n}a_{i,\pi(i)}-na_{\bullet,\bullet}\right]=0.$

As a consequence, replacing $a_{i,j}$ by $\widehat{a}_{i,j}$, we assume without loss of generality that

$\displaystyle\mathbb{E}Y=0\text{ \ and \ }a_{\bullet,\bullet}=0,$

(13)

and for simplicity, we consider only the symmetric case, that is, $a_{i,j}=a_{j,i}$ for all $i,j$. Also, to rule out trivial cases, we assume in what follows that $\sigma^{2}>0$. The explicit form of $\sigma^{2}$ was calculated in Lemma 4.8 of Wiroonsri (2017) and as discussed in Remark 4.9 of Wiroonsri (2017), $\sigma^{2}$ is of order $n$ when the elements of $A$ are well chosen so that they do not depend on $n$ and most of the elements are not the same number. In this case, there exists $N\in\mathbb{N}_{1}$ such that $\sigma^{2}>0$ for $n>N$.

The following theorem presents concentration inequalities for $Y$.

As mentioned earlier in Remark 1.3, the bounds arised in Theorem 2.1, are effective for $t\geq 2B_{1}$ where $B_{1}$ depends on the remainder term of the approximate $\lambda,R$-Stein pair and the bounds are trivial outside this range. Hence if $2B_{1}$ is out of the support of $Y-\mathbb{E}Y$, then the bound will not be useful. The best possible bound of $B_{1}$ that we can obtain in general is $(6n+4.8\theta)M$ which depends on $n$, nevertheless, it becomes $\theta M(3.6n+2.4\theta-3)/(\theta+n-1)+\theta^{2}nM/(2(\theta+n-1)_{(2)})$ which is of constant order in the case that $|R|$ and and $e^{sY}$ are negatively correlated for $0<s<\alpha$.

To prove Theorem 2.1, we apply Theorem 1.2 from the introduction. That is, we have to construct an approximate $Y$-zero bias coupling $Y^{*}$ from an approximate $\lambda,R$-Stein pair $(Y,Y^{\prime\prime})$ by using Lemma 1.1 in such a way that $|Y^{*}-Y|$ and $\mathbb{E}[R|Y]$ are bounded and that $|\mathbb{E}(YR)|<\infty$. For this purpose, we state the following two lemmas. The first, Lemma 2.2 proved in Wiroonsri (2017), constructs an approximate $4/n,R$-Stein pair $(Y^{\prime},Y^{\prime\prime})$ for $n\geq 6$ where $Y^{\prime}$ is given by (8) with $\pi^{\prime}$ replacing $\pi$. The bounds related to the remainder term $R$ are then obtained in Lemma 2.3. Below, for $i,j\in[n]$, we write $i\sim j$ if $i$ and $j$ are in the same cycle, let $|i|$ be the length of the cycle containing $i$ and let $\tau_{i,j}$, $i,j\in[n]$ be the permutation that transposes $i$ and $j$.

Now we have all ingredients to prove Theorem 2.1.

In this section, we perform 4 simulation experiments. $A$ is generated by first randomly choosing $X$ from $N(1,0.2)$ and $N(-1,0.2)$ equally and then letting $B=X+X^{T}$ and $A=B-b_{\bullet,\bullet}$ where $b_{\bullet,\bullet}$ is defined similarly to (11). We intentionally select $X$ such that $\mathrm{Cov}(|R|,e^{sY})<0$ for all $0<s<\alpha$ with $\alpha$ as defined in Theorem 1.2 so that the negative correlation assumption there is satisfied. To generate Ewens permutations with $\theta\neq 1$, we apply the accept-reject algorithm (see Robert and Casella (2013)). Recall that the discrete version of the accept-reject algorithm is stated as follow.

In our case, $Y$ and $V$ are $\mathcal{E}_{\theta}$ with $\theta\neq 1$ and uniform, respectively, with common support be all possible permutations $\pi\in\mathcal{S}_{n}$. Recall that the probability mass functions of $Y$ and $V$ are

$\displaystyle f_{Y}(\pi)=\frac{\theta^{\#(\pi)}}{\theta^{(n)}}\text{ \ and \ }f_{V}(\pi)=\frac{1}{n!},$

where $\#(\pi)$ denotes the number of cycles of $\pi$. It is easy to see that

$\displaystyle C=\begin{cases}\frac{n!\theta}{\theta^{(n)}}\text{ \ if \ }\theta<1\\ \frac{n!\theta^{n}}{\theta^{(n)}}\text{ \ if \ }\theta>1\\ \end{cases}.$

In this section, we follow the same technique as in Goldstein and Işlak (2014) but handle a few extra terms that include $R$.

(a) If $m(s)$ exists in an open interval containing $s$ we may interchange expectation and differentiation at $s$ to obtain

	$\displaystyle m^{\prime}(s)$	$\displaystyle=$	$\displaystyle\mathbb{E}[Ye^{sY}]=\sigma^{2}\mathbb{E}[se^{sY^{*}}]-\frac{\mathbb{E}YR}{\lambda}\mathbb{E}[se^{sY^{*}}]+\frac{\mathbb{E}[Re^{sY}]}{\lambda}$		(22)
		$\displaystyle=$	$\displaystyle\sigma^{2}sm^{*}(s)-\frac{\mathbb{E}YR}{\lambda}sm^{*}(s)+\frac{\mathbb{E}[Re^{sY}]}{\lambda},$

where we have used the approximate zero bias relation in the second equality.

For $\alpha\in(0,1/c)$ and $0\leq s\leq\alpha$, using $e^{x}\leq 1/(1-x)$ for $x\in[0,1)$ we have

$\displaystyle m^{*}(s)\leq e^{cs}m(s)\leq\frac{1}{1-sc}m(s).$

(23)

Using (22) and applying (23), we have

	$\displaystyle m^{\prime}(s)$	$\displaystyle\leq$	$\displaystyle\frac{\sigma^{2}s}{1-sc}m(s)+\frac{|\mathbb{E}(YR)|}{\lambda}\frac{s}{1-sc}m(s)+\frac{|\mathbb{E}(Re^{sY})|}{\lambda}$		(24)
		$\displaystyle=$	$\displaystyle\frac{\sigma^{2}s}{1-sc}m(s)+\frac{|\mathbb{E}(YR)|}{\lambda}\frac{s}{1-sc}m(s)+\frac{|\mathbb{E}[e^{sY}\mathbb{E}[R|Y]]|}{\lambda}$
		$\displaystyle\leq$	$\displaystyle\frac{(\sigma^{2}+|\mathbb{E}(YR)|/\lambda)s}{1-sc}m(s)+\frac{\mathbb{E}[e^{sY}|\mathbb{E}[R|Y]|]}{\lambda}.$

Recalling from the statement of the theorem that $B_{1}=\mathbb{E}|R|/\lambda$ if $|R|$ and and $e^{sY}$ are negatively correlated for $0<s<\alpha$ and $B_{1}=\mathrm{ess}\ \mathrm{sup}|\mathbb{E}[R|Y]|/\lambda$ otherwise and $B_{2}=|\mathbb{E}(YR)|/\lambda$, it follows from the last expression that

$\displaystyle m^{\prime}(s)\leq\frac{(\sigma^{2}+B_{2})s}{1-sc}m(s)+B_{1}m(s).$

Dividing both sides by $m(s)$, integrating over $[0,\alpha]$ and using that $m(0)=1$ yield

$\displaystyle\log(m(\alpha))=\int_{0}^{\alpha}\frac{m^{\prime}(s)}{m(s)}ds\leq\frac{\sigma^{2}+B_{2}}{1-\alpha c}\int_{0}^{\alpha}sds+B_{1}\int_{0}^{\alpha}1ds=\frac{(\sigma^{2}+B_{2})\alpha^{2}}{2(1-\alpha c)}+B_{1}\alpha,$

and therefore

$\displaystyle m(\alpha)\leq\exp\left(\frac{(\sigma^{2}+B_{2})\alpha^{2}}{2(1-\alpha c)}+B_{1}\alpha\right).$

We note that the claim for $t=0$ is clear as the right hand side of (5) is one. Applying Markov’s inequality for $t>0$, we obtain

$\displaystyle P(Y\geq t)=P(e^{\alpha Y}\geq e^{\alpha t})\leq e^{-\alpha t}m(\alpha)\leq\exp\left(-\alpha(t-B_{1})+\frac{(\sigma^{2}+B_{2})\alpha^{2}}{2(1-\alpha c)}\right).$

Letting $\alpha=t/(\sigma^{2}+B_{2}+ct)$ that lies in $(0,1/c)$, (5) holds. The result for the left tail when $Y-Y^{*}\leq c$ follows immediately from the same proof by letting $X=-Y$ and the fact that $X^{*}=-Y^{*}$ has the approximate $X$-zero bias distribution with $R$ replaced by $-R$. We also note that the results for the left tail in the other cases below follow by the same argument so it suffices to prove only the results for the right tail.