Concentration inequality for maximum permuted sums

Question

Let $\{A_i\}_{i=1}^n$ and $\{B_i\}_{i=1}^n$ be two sets of i.i.d. random variables (say Bernoulli's or sub-Gaussian). Assume that $\{A_i\}_{i=1}^n$ and $\{B_i\}_{i=1}^n$ are statistically independent as well. Consider the sum $$ S_n = \max_{\pi\in\Pi_n}\sum_{i=1}^nA_iB_{\pi(i)}, $$ where $\pi$ is a permutation over $\{1,2,\ldots,n\}$ and $\Pi_n$ is the set of all possible permutations. I am interested in "good" upper bounds on the tail probability, i.e., $\Pr(S_n>t) $, for $t\in\mathbb{R}$.

One way to approach this is to use the union bound over $\Pi_n$, namely, $$ \Pr(S_n>t)\leq n!\Pr\left(\sum_{i=1}^nA_iB_i>t\right), $$ and then the probability term above can be easily upper bounded using the distributional assumptions on $\{A_i\}_{i=1}^n$ and $\{B_i\}_{i=1}^n$.

The question is whether there is an elegant way to deal this maximum other than just by applying a union bound.

Answer 1

For any event $\omega\in \Omega$, according to the rearrangement inequality $$\sum_{i=1}^n A_i(\omega)B_i( \omega) \le \sum_{i=1}^n A_{(i)}(\omega)B_{(i)}( \omega)$$ where $(A_{(i)})_{i=1,...,n}$ and $(B_{(i)})_{i=1,...,n}$ are the order statistic of $(A_{i})_{i=1,...,n}$ and $(B_{i})_{i=1,...,n}$. In order words, the sum $\sum_{i=1}^n A_i(\omega)B_i( \omega)$ reaches its maximum when $(A_{i})_{i=1,...,n}$ and $(B_{i})_{i=1,...,n}$ in the same order.

So, we have

$$\color{red}{S_n=\sum_{i=1}^n A_{(i)}B_{(i)}} \tag{1}$$

---

Case 1: For the distribution like Bernoulli as in the question, I assume that these iid random variables $A_i$ and $B_i$ follow the distribution of the random variable $X$ with non-negative support. We will apply the Markov's inequality to $S_n$, given the assumption that these $A_i, B_i$ have non-negative support. $$\mathbb{P}(S_n>t) \le\frac{\mathbb{E}(S_n)}{t}=\frac{\sum_{i=1}^n\mathbb{E}(A_{(i)}B_{(i)})}{t}= \frac{\sum_{i=1}^n\mathbb{E}^2(A_{(i)})}{t} \tag{2}$$

For any $i \in \{1,2,...,n \}$, according to this result, the density function of $A_{(i)}$ and $B_{(i)}$ are $$f_{(i)}(x)=\frac{n!}{i!(n-i)!}f_X(x)F^{i-1}(x) (1-F(x))^{n-i}$$

Then, applying the Cauchy-Schwazt inequality (at the step 3-4), we have:

$$\begin{align} \mathbb{E}^2(A_{(i)}) &= \left(\int_{0}^{+\infty} x f_{(i)}(x)dx\right)^2 \\ &=\left(\frac{n!}{i!(n-i)!}\right)^2\left(\int_{0}^{+\infty} x f_X(x)F^{i-1}(x) (1-F(x))^{n-i}dx\right)^2 \\ &=\left(\frac{n!}{i!(n-i)!}\right)^2\left(\int_{0}^{+\infty} (x \sqrt{f_X(x)})\sqrt{f_X(x)}F^{i-1}(x) (1-F(x))^{n-i}dx\right)^2 \\ & \le \left(\frac{n!}{i!(n-i)!}\right)^2 \left(\int_{0}^{+\infty} x^2 f_X(x)\right)\left(\int_{0}^{+\infty} f_X(x)F^{2i-2}(x) (1-F(x))^{2n-2i}dx\right)\\ & = \left(\frac{n!}{i!(n-i)!}\right)^2 (\mathbb{V}(X) + \mathbb{E}^2(X))\left(\int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du\right)\\ \end{align}$$

Then $$\sum_{i=1}^n\mathbb{E}^2(A_{(i)}) \le (\mathbb{V}(X) + \mathbb{E}^2(X)) \sum_{i=1}^n \left( \left(\frac{n!}{i!(n-i)!}\right)^2 \int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du \right) \tag{3}$$

From $(2),(3)$, we deduce that

$$\mathbb{P}(S_n>t) \le \frac{1}{t}(\mathbb{V}(X) + \mathbb{E}^2(X))\color{red}{\sum_{i=1}^n \left( \left(\frac{n!}{i!(n-i)!}\right)^2 \int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du \right)} \tag{4}$$

The RHS of $(4)$ is a known function of $n$ and variance of $X$. We can make it a more elegant (but less tighter) by remarking that

$$\frac{n!}{i!(n-i)!} \le \frac{n!}{\left(\frac{n}{2} \right)!^2}$$

Then, the red term of $(4)$ is smaller than $$ \le \frac{n!}{\left(\frac{n}{2} \right)!^2}\sum_{i=1}^n \left(\frac{n!}{i!(n-i)!} \int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du \right) \le \frac{n!}{\left(\frac{n}{2} \right)!^2} \int_{0}^{1} (u^2 + (1-u)^2)^n du$$

So, a more elegant bound of $(4)$ is $$\color{red}{\mathbb{P}(S_n>t) \le \frac{1}{t}(\mathbb{V}(X) + \mathbb{E}^2(X))\frac{n!}{\left(\frac{n}{2} \right)!^2} \int_{0}^{1} (u^2 + (1-u)^2)^n du }\tag{5}$$

---

Case 2: For distribution of type sub-Gaussian (that includes the Gaussian distribution)

Applying the Chernoff's inequality, we have: $$\mathbb{P}(S_n >t) \le \inf_{s\ge 0}\frac{\mathbb{E}(e^{sS_n})}{e^{st}} \tag{6}$$

With $(1)$, we compute $\mathbb{E}(sS_n)$ $$\begin{align} \mathbb{E}(e^{sS_n}) &= \mathbb{E}(e^{s\sum_{i=1}^n A_{(i)}B_{(i)}})\\ &= \prod_{i=1}^n \mathbb{E}\left(e^{s A_{(i)}B_{(i)}}\right)\\ &\le \prod_{i=1}^n \mathbb{E}\left(e^{\frac{s}{2} (A_{(i)}^2 +B_{(i)}^2)}\right) = \prod_{i=1}^n \mathbb{E}^2\left(e^{\frac{s}{2} A_{(i)}^2}\right) \tag{7}\\ \end{align}$$

We have, for $i=1,...,n$, applying the Cauchy-Schwazt inequality (at the step 3-4) as in the case 1: $$\begin{align} \mathbb{E}^2\left(e^{\frac{s}{2} A_{(i)}^2}\right) &= \left(\int_{0}^{+\infty} e^{\frac{sx^2}{2}} f_{(i)}(x)dx\right)^2 \\ &=\left(\frac{n!}{i!(n-i)!}\right)^2\left(\int_{0}^{+\infty} x f_X(x)F^{i-1}(x) (1-F(x))^{n-i}dx\right)^2 \\ &=\left(\frac{n!}{i!(n-i)!}\right)^2\left(\int_{0}^{+\infty} (e^{\frac{sx^2}{2}} \sqrt{f_X(x)})\sqrt{f_X(x)}F^{i-1}(x) (1-F(x))^{n-i}dx\right)^2 \\ & \le \left(\frac{n!}{i!(n-i)!}\right)^2 \left(\int_{0}^{+\infty} e^{sx^2} f_X(x)dx\right)\left(\int_{0}^{+\infty} f_X(x)F^{2i-2}(x) (1-F(x))^{2n-2i}dx\right)\\ & = \mathbb{E}\left(e^{sX^2} \right) \left(\frac{n!}{i!(n-i)!}\right)^2 \left(\int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du\right)\\ \end{align}$$

As $X$ follows the sub-Gaussian distribution, there exists a $\delta <+\infty$ such that $\mathbb{E}\left(e^{\delta X^2} \right)<+\infty$, then, for all $0\le s \le \delta$, $\mathbb{E}\left(e^{s X^2} \right)<+\infty$.

Remark: If $X$ follows the Gaussian distribution, $\delta$ can be $\frac{1}{2\sigma^2}$ where $\sigma^2$ is the variance of $X$.

Return back to $(7)$, we have for all $0\le s \le \delta$ : $$\begin{align} \mathbb{E}(e^{sS_n}) &= \prod_{i=1}^n \mathbb{E}^2\left(e^{\frac{s}{2} A_{(i)}^2}\right) \le \mathbb{E}^n\left(e^{sX^2} \right) \underbrace{\prod_{i=1}^n \left(\left(\frac{n!}{i!(n-i)!}\right)^2 \int_{0}^{1} u^{2i-2} (1-u)^{2n-2i}du\right)}_{\text{Let denote this term by } M}\\ \end{align}$$

From $(6)$, we have $$\mathbb{P}(S_n >t) \le M\cdot \inf_{0 \le s \le \delta} \frac{\mathbb{E}^n\left(e^{sX^2} \right) }{e^{st}} \tag{8}$$

If the exact distribution of the sub-Gaussian variable $X$ is not specified, we can be content to have $$\mathbb{P}(S_n >t) \le M \mathbb{E}^n\left(e^{\delta X^2} \right)\color{red}{e^{-\delta t}} \tag{9}$$

From $(9)$, we can deduce that $S_n$ follows a heavy-tailed distribution.

Answer 2

The random variable $S_n$ does concentrate (around its expectation by bounded differences inequality) but it does not concentrate around 0. Thus the desired probability of $P(S_n > t)$ might not be small for non-trivial $t$.

Let $A_i$, $B_i$ be i.i.d. Rademacher, i.e., uniform on $\{-1,1\}$. Then $A_iB_i$ is again a Rademacher random variable. For this setting, the union bound is vacuous for $t = o(n)$. (In fact, $t$ needs to be $\omega(n)$ to for it to be less than $1$, which is vacuous as $|S_n|\leq n$).

Let $\alpha$ and $\beta$ be the fraction of $-1$'s in $A_i$'s and $B_i$'s, respectively. With high probability, $\max(|\alpha-1/2|,|\beta-1/2|) \leq \Delta$, where $\Delta = O(1/\sqrt{n})$.

Now choose the permutation that sorts of both random variables in increasing order. For this choice of permutation, the sum is at equal to $\min(\alpha,\beta) n + \min(1-\alpha, 1- \beta) n - n|\beta-\alpha| $, which is of the order $n - O(\Delta n)$.

Thus, with high probability $\leq 0 \leq n - S_n \leq O(\sqrt{n})$.