Let $X_i,i=1,2,...,$ be a sequence of i.i.d. random variables and $u_n$ be a sequence of positive real numbers. I was motivated by the fact that if

$$P(\max_{1\leq i\leq n}|X_i|\geq u_n)\to 0 \quad \text{as}\quad n\to\infty. $$


$$P(\max_{1\leq i\leq n}|X_i|\geq u_n) \sim nP(|X_1|\geq u_n)$$

This statement is a direct result of Chung's textbook: A course in Probability Theory; Third Edition; Page 67; Exercise 17; which says

If $\forall n:\{E_j^{(n)},1\leq j\leq n\}$ are independent events, and $$P\left(\bigcup_{j=1}^n E_j^{(n)}\right)\to 0\quad\text{and}\quad n\to\infty.$$ Then $$P\left(\bigcup_{j=1}^n E_j^{(n)}\right) \sim \sum_{j=1}^n P\left(E_j^{(n)}\right)$$ Then I made a conjecture based on this.


$$P(\max_{1\leq i<j\leq n}|X_iX_j|\geq u_n)\to 0 \quad \text{as}\quad n\to\infty. $$ then $$P(\max_{1\leq i<j\leq n}|X_iX_j|\geq u_n) \sim \frac{n^2}{2}P(|X_1X_2|\geq u_n)$$ The problem is now that the events $\{|X_iX_j|\geq u_n\}$, $1\leq i<j\leq n$ are not mutually independent anymore, since there are some overlaps in the indices, and this makes the conjecture hard to prove or even disprove.

Any comment and discussions are appreciated for the proof or disproof of this conjecture.

  • $\begingroup$ The union bound gives you $\leq$, regardless of independence. $\endgroup$ – Michael May 17 '17 at 17:41
  • $\begingroup$ @Michael Yes, this direction is trivial infact. $\endgroup$ – Schrödinger's Cat May 17 '17 at 18:02
  • $\begingroup$ Quick idea (no time to trace it through): What if you look for counterexamples over random variables $X_i \geq 1$ with the property that $P[X_i>\sqrt{a}]^2 << P[X>a]$ for large $a$? Such as $P[X>a] = 1/\log(a)$ for large $a$. The intuition is that if $X_i \geq 1$ always, then $X_iX_j> u$ whenever at least one of the random variables is larger than $u$. For "usual distributions" one expects the "most likely" way for $X_iX_j$ to be larger than $u$ is for $X_i > \sqrt{u}$ and $X_j>\sqrt{u}$, but for other distributions the most likely way is either $X_i>u$ or $X_j>u$. $\endgroup$ – Michael May 18 '17 at 17:21
  • $\begingroup$ So, the intuition is to get a distribution so that the probability $X_iX_j>u$ occurs for some $i, j$ is closer to the probability that $X_i>u$ for at least one of the indices $i \in \{1, ..., n\}$, rather than the probability that $\{X_i>\sqrt{u}\} \cap \{X_j > \sqrt{u}\}$ for at least one instance of $i,j$. $\endgroup$ – Michael May 18 '17 at 17:24
  • $\begingroup$ My very first comment regarding the union bound implying $\leq$ was implicitly using $\max_{i,j : i \neq j}X_iX_j$, rather than $\max_{i,j} X_iX_j$, and should have omitted "regardless of independence" (since we need $P[X_iX_j \geq u_n] = P[X_1X_2\geq u_n]$ for all $i \neq j$). That is, by the union bound, $$P[\max_{i,j \in \{1, ..., n\}, i \neq j} X_iX_j \geq u_n] = P[\cup_{1\leq i < j \leq n}\{X_iX_j \geq u_n\}] \leq {n \choose 2}P[X_1X_2 \geq u_n]$$ My counter-example in the answer below works for both cases $i, j \in \{1, ..., n\}$ and $i, j \in \{1, ..., n\}, i\neq j$. $\endgroup$ – Michael May 18 '17 at 23:11

I decided to trace through the intuition in my above comments, and it seems to work. Here is an explicit counter-example:

Consider $\{X_i\}$ i.i.d. with a continuous CDF that satisfies: $$ Q(u) = P[X_i>u] = \frac{1}{\log(e-1+u)} \quad , \forall u \geq 1 $$ In particular, $X_i \geq 1$ with probability 1.

Define $u_n$ so that $Q(\sqrt{u_n}) = 1/n^2$ for all $n \in \{1, 2, 3,...\}$. We have: \begin{align*} P\left[\max_{i,j \in \{1, ..., n\}} X_iX_j > u_n\right] &\leq 1-P[\cap_{i=1}^n \{X_i \leq \sqrt{u_n}\}]\\ &=1-(1-Q(\sqrt{u_n}))^n\\ &= 1- (1-\frac{1}{n^2})^n \rightarrow 0 \end{align*} On the other hand: $$P[X_1X_2 > u_n] \geq P[X_1> u_n] = Q(u_n) $$ Thus, for all $n \in \{1, 2, 3, ...\}$ we have \begin{align*} n^2P[X_1X_2>u_n] &\geq n^2Q(u_n) \\ &=\frac{n^2}{\log(e-1+u_n)} \\ &= \frac{(1/2)n^2}{\log(\sqrt{e-1+u_n})}\\ &\overset{(a)}{\geq} \frac{(1/2)n^2}{\log(e-1 + \sqrt{u_n})}\\ &= (1/2)n^2Q(\sqrt{u_n}) \\ &= 1/2 \end{align*} where the inequality (a) follows because $\sqrt{e-1+u_n} \leq \sqrt{e-1} + \sqrt{u_n} \leq e-1 + \sqrt{u_n}$ (since $u_n\geq 0$). So we see that $n^2P[X_1X_2>u_n]$ does not even converge to zero!

| cite | improve this answer | |
  • $\begingroup$ Thanks for your reply. This conter example is very impressive $\endgroup$ – Schrödinger's Cat May 18 '17 at 21:01
  • $\begingroup$ @Schrödinger'sCat : Thanks. The above counter-example indeed works out nicely. The same example holds if you restrict attention to $i\neq j$, which is perhaps what you intuitively wanted anyway, that is, $\max_{i, j \in \{1, ..., n\}, i \neq j} X_iX_j > u_n$. I was implicitly assuming $i \neq j$ in my very first comment about the union bound giving $\leq$. $\endgroup$ – Michael May 18 '17 at 22:55

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.