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.

  • $\begingroup$ 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? $\endgroup$
    – J.John
    Aug 16 '20 at 21:57
  • $\begingroup$ No, I mean $X_{k\ell + j}$, so the indices of $X$ for different $\ell$ are disjoint. $\endgroup$ Aug 16 '20 at 23:20
  • $\begingroup$ $\|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 \}$. $\endgroup$ Aug 16 '20 at 23:25
  • $\begingroup$ 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. $\endgroup$
    – J.John
    Aug 17 '20 at 9:47

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.