Skip to main content
edited tags
Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229
Source Link
bolzano
  • 143
  • 4

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

enter image description here