Suppose I have a sequence of $n$ i.i.d. random variables $X_1,X_2,\ldots,X_n$. Each $X_i$ is positive and has variance $\sigma(n)$ that is an increasing function of the number of variables in the sequence, i.e. $\sigma(n)=\omega(1)$. The mean $\mu$ of each $X_i$ is a constant. I am trying to lower-bound the probability that the maximum of this sequence $X_\max$ exceeds a threshold $T(n)$ (which may either be a constant or a function of $n$ that grows much slower that $\sigma(n)$, i.e. $T(n)=o(\sigma(n))$).

Since $X_i$'s are i.i.d., by elementary probability we have:

$$P(X_\max> T(n))=1-(P(X_1\leq T(n)))^n=1-(1-P(X_1>T(n)))^n$$

Thus, I want to lower-bound the probability that a positive random variable $X_1$ with variance $\sigma(n)$ exceeds a threshold $T(n)=o(\sigma(n))$. Unfortunately, the only variance-based bound that I know is Chebyshev's and it's an upper bound. I also know that most extreme value theory results rely on the structure of the particular distribution function...

However, intuitively, it seems that, since $X_i$'s are positive and since their variance is growing faster than the threshold, $X_\max$ should exceed $T(n)$ with high probability... But I am having hard time proving this... can anyone help?

  • 1
    $\begingroup$ I assume iid is a typo; they are just independent? And talking about "a positive random variable with increasing variance" seems confusing. A random variable only has one variance, so you really want to talk about your sequence. $\endgroup$ – Nate Eldredge Oct 6 '13 at 2:22
  • $\begingroup$ They are i.i.d., but the twist is that the variance of each r.v. is the function of their number in the sequence. Basically, imagine a machine that lets you pick a number $n$, and produces $n$ positive random variables with constant means and variances that are some increasing function of the number $n$ that you chose. I edited the question to clarify this (I also noticed a typo in the last paragraph, which I fixed.) $\endgroup$ – Bullmoose Oct 6 '13 at 3:53
  • $\begingroup$ Oh -- I am really sorry for lack of clarity, I see how my comment can be misinterpreted. I meant to say that each random variable $X_i$ has variance $\sigma(n)$, which is the same for all $X_i$'s but is a function of the number $n$ of $X_i$'s in the sequence. $\endgroup$ – Bullmoose Oct 6 '13 at 4:04
  • $\begingroup$ You need something more than just the variance to get any sort of lower bound, or else you could something like all of the $X_i$ being $n^{9}$ with probability $n^{-16}$ and $0$ otherwise (so that the variance increases quickly, but with very high probability all of the variables are $0$). $\endgroup$ – Kevin P. Costello Oct 6 '13 at 4:13
  • 1
    $\begingroup$ @Bullmoose: Probabilists are used to expressing your "sequence of sequences" as a triangular array: a family of random variables $X_i^n$ indexed by $n \ge 1$ and $1 \le i \le n$, as Stephan Sturm suggested. $\endgroup$ – Nate Eldredge Oct 6 '13 at 4:45

From considerations above, I would guess that, when $n=o(\sigma(n))$, $T^{\star}(n)=\mu+\tfrac{\sigma(n)}{\mu}$ satisfies $$\lim_n\mathbb{P}(X_{max}\ge T^{\star}(n))=1,$$ for any array $X^n_i$ meeting the Bullmoose's conditions. If $T(n)>T^{\star}(n)$ the example given in the comments is a counterexample to $$\lim_n\mathbb{P}(X_{max}\ge T(n))=1.$$

  • $\begingroup$ Thank you for your answer! Your thoughts have been very helpful, and I have found that in the family of distributions that i am considering there is a necessary relationship between $\sigma(n)$, $n$ and mean $\mu(n)$ as a function of $n$: $\frac{\sigma(n)}{n\mu(n)}=\Omega(1)$. Unfortunately, this means that your approach may not work for it (I think that the bound is vacuous). $\endgroup$ – Bullmoose Oct 7 '13 at 2:24
  • $\begingroup$ My approach fails for too many things are heuristic, nothing new, but your assumption entails $n=o(\sigma(n))$, so at least this information is good news. Thanks for the nice question. $\endgroup$ – Chassaing Oct 7 '13 at 8:54

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.