Concentration bound for sum of indicators of maximum value of k combinations

Question

Let $X_1, \dots, X_n$ be i.i.d. random variables distributed as $\mathrm{Exp}(\lambda)$ for some $\lambda > 0$ and let $t > 0$. For every combination $J$ of $k$ of these variables, we define $Y_J = \mathbf 1 \{ \max_{j \in J} X_j \ge t \}$ where $\mathbf 1 \{ \cdot \}$ is the indicator function. We define

$$S = \sum_{J \in C([n], k)} Y_J$$

where $C([n], k)$ is the set of combinations of the set $[n] = \{ 1, \dots, n \}$ choosing $k$ (i.e. $|C([n], k)| = \binom n k$). Do there exist concentration bounds in the literature for the variable $S$?

Below is a plot of $S$ for $t = \lambda = 1$, $n = 100$, $k = 2$ and $T = 1000$ simulations

Answer 1

Here is another way to obtain results very similar to those in my other answer here.

Again, by rescaling, without loss of generality $\lambda=1$.

Note that \begin{equation*} S=\binom nk-\binom{n-\nu}k, \tag{0} \end{equation*} where \begin{equation*} \nu:=\sum_{j\in[n]}1(X_j\ge t). \tag{1} \end{equation*} So, \begin{equation*} S=\mu_n+f_n(\bar V), \end{equation*} where \begin{equation*} \mu_n:=\binom nk-\binom{nq}k, \end{equation*} \begin{equation*} q:=1-e^{-t}, \end{equation*} \begin{equation*} f_n(v):=\binom{nq}k-\binom{n(q-v)}k, \end{equation*} \begin{equation*} \bar V:=\frac1n\,\sum_{j\in[n]}V_j \end{equation*} (so that $n-\nu=n(q-\bar V)$), \begin{equation*} V_j:=1(X_j\ge t)-E1(X_j\ge t)=1(X_j\ge t)-(1-q). \end{equation*} Note that \begin{equation*} \mu_n=\frac{n^k}{k!}\,(1+O(1/n)-q^k) \end{equation*} (as $n\to\infty$), \begin{equation*} f_n(v)=\frac{n^k}{k!}\,(1+O(1/n))f(v),\quad f(v):=q^k-(q-v)^k, \end{equation*} $f(0)=0$, $f'(0)=kq^{k-1}$, and the $V_j$'s are iid zero-mean random variables with variance $(1-q)q$.

Now it follows by Theorem 2.10 that $S$ is asymptotically normal with (asymptotic) mean $n^k(1-q^k)/k!$ and asymptotic variance $(1-q)q^{2k-1}n^{2k-1}/((k-1)!)^2$.

For $n=100$, $k=2$, and $t=1$, we get $S\approx N(3002,305^2)$, which is in agreement with your picture.

Explicit bounds on the rate of convergence of $S$ to normality can be obtained from Theorem 2.11.

---

An advantage of this approach is that, (i) by (1), $\nu$ has the binomial distribution with parameters $n$ and $1-q$ and (ii) by (0), $S=s(\nu)$ for the function $$\{0,\dots,n\}\ni\mapsto s(x):=\binom nk-\binom{n-x}k\in\{0,1,\dots\},$$ and the function $s$ is strictly increasing on the set $\{0,\dots,n-k+1\}$ (and equals the constant $\binom nk$ on the set $\{n-k+1,n-k+2,\dots,n\}$, which is relatively small if $n$ is much greater than $k$). So,
\begin{equation} P(S\ge s(x))=P(\nu\ge x)\text{ for any $x\in\{0,\dots,n-k+1\}$}. \end{equation} Thus, any one of the many upper or lower bounds on the tail probabilities of a binomial distribution results in the corresponding upper or lower bound on the tail probabilities of $S$.

Answer 2

$\newcommand{\si}{\sigma}\newcommand{\Si}{\Sigma}$By rescaling, without loss of generality $\lambda=1$.

The random variable \begin{equation} U_n:=\frac{S-ES}{\binom nk}=\frac1{\binom nk}\sum_{J\in\binom{[n]}k}(Y_J-EY_J) \end{equation} is a U-statistic. Therefore, for each natural $k\ge2$, by Hoeffding's Theorem 7.1, $U_n$ is asymptotically normal (as $n\to\infty$) with (asymptotic) mean $0$ and asymptotic variance $k^2\si_1^2/n$, where \begin{equation} \si_1^2:=Var\,g(X_1),\quad g(X_1):=E(Y_{[k]}|X_1). \end{equation} In our case, \begin{equation} g(x)=1(x\ge t)+1(x<t)(1-q^{k-1}),\quad q:=1-e^{-t}, \end{equation} and hence \begin{equation} \si_1^2=1-q+q \left(1-q^{k-1}\right)^2-\left(1-q^k\right)^2=(1-q)q^{2k-1}. \end{equation}

It is easy to see that $ES=\binom nk (1-q^k)$.

Thus, $S$ is asymptotically normal with (asymptotic) mean $ES=\binom nk (1-q^k)$ and asymptotic variance $\Si^2:=\binom nk ^2 k^2\si_1^2/n$.

For $n=100$, $k=2$, and $t=1$, we get $S\approx N(ES,\Si^2)$ with $ES\approx2972$ and $\Si:=\sqrt{\Si^2}\approx302$, which is in agreement with your picture.

Explicit bounds on the rate of convergence of $U_n$ to normality (obtained using Stein's method) are available -- see Chen and Shao, Theorem 3.1.