# 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

• It seems to me that the sum should expressible simple in terms of the number of r.v.s > t, for example, if n=10 , k=5, and there are 2 r.v.s > t then in order not to get a max > t, you have to draw all your samples from the 8 r.v.s < t, and the sum is $10 \choose 5 - 8 \choose 5$
– mike
Dec 11, 2021 at 7:11

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,
$$$$P(S\ge s(x))=P(\nu\ge x)\text{ for any x\in\{0,\dots,n-k+1\}}.$$$$ 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$$.

• Thank you very much for your very detailed answer! (and the other approach as well!) Dec 12, 2021 at 21:57


The random variable $$$$U_n:=\frac{S-ES}{\binom nk}=\frac1{\binom nk}\sum_{J\in\binom{[n]}k}(Y_J-EY_J)$$$$ 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 $$$$\si_1^2:=Var\,g(X_1),\quad g(X_1):=E(Y_{[k]}|X_1).$$$$ In our case, $$$$g(x)=1(x\ge t)+1(x and hence $$$$\si_1^2=1-q+q \left(1-q^{k-1}\right)^2-\left(1-q^k\right)^2=(1-q)q^{2k-1}.$$$$

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.