# Maximum of a sequence of $n$ positive random variables where variance is an increasing function of $n$

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?

• 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. – Nate Eldredge Oct 6 '13 at 2:22
• 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.) – Bullmoose Oct 6 '13 at 3:53
• 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. – Bullmoose Oct 6 '13 at 4:04
• 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$). – Kevin P. Costello Oct 6 '13 at 4:13
• @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. – Nate Eldredge Oct 6 '13 at 4:45

## 1 Answer

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

• 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). – Bullmoose Oct 7 '13 at 2:24
• 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. – Chassaing Oct 7 '13 at 8:54