Concentration bound for sum of indicators of maximum value of k combinations 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

 A: $\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.
A: 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$.
