1
$\begingroup$

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

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ 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$ $\endgroup$
    – mike
    Dec 11, 2021 at 7:11

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your very detailed answer! (and the other approach as well!) $\endgroup$
    – bolzano
    Dec 12, 2021 at 21:57
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.