# Probability that a subsequence of random variables exceeds the maximum

Let $$(X_i)_{i=1}^n$$ be a sequence of i.i.d. non-negative and bounded random variables. I would like to show that for any $$\epsilon>0$$ and $$k$$, one can find an index $$\ell$$ such that $$X_{\ell+j}\geq\max_{i\in\{1,2,\ldots,n\}}X_i-\epsilon$$, for all $$1\leq j\leq k$$, with probability tending to $$1$$, as $$n\to\infty$$. In particular, how can we lower bound the probability $$\Pr\left[\exists\ell:\; X_{\ell+j}\geq\max_{i\in\{1,2,\ldots,n\}}X_i-\epsilon,\;\forall 1\leq j\leq k\right].$$ Note that for $$k=1$$ this probability is trivially unity. It seems that standard techniques, such as, the union bound to upper bound the complementary event, are too weak due to the strong dependency of the events indexed by $$\ell$$.

Hint: The events $$\bigcap_{j=1\ldots k} (X_{kl+j} \ge \|X\|_\infty - \epsilon)$$ are independent and have the same nonzero probability.

• Thanks! Should it be $X_{\ell+j}$ instead of $X_{k\ell+j}$? Also, do you mean that the events which are independent are those inside the intersection, or those which are indexed by $\ell$?. Anyhow, all of these events depend on $\|X\|_\infty$ which is random, so there must be some dependency, right? Aug 16 '20 at 21:57
• No, I mean $X_{k\ell + j}$, so the indices of $X$ for different $\ell$ are disjoint. Aug 16 '20 at 23:20
• $\|X\|_\infty$ is not really random if you take an infinite sequence, which is what I thought you meant: with probability $1$ it is $\sup \{x: {\rm Pr}(|X| \ge x) > 0 \}$. Aug 16 '20 at 23:25
• I see, that is correct. By $\|X\|_\infty$ I really meant $\max_{i=1,2,\ldots,n}X_i$. I will edit the question accordingly. Aug 17 '20 at 9:47