# Lower bound on a minimum of maximum of a sequence of standard normal random variables

Let $X = (x_{ij}) \in \mathbb{R}^{n \times p}$ be a matrix with independent $N(0,1)$ entries.

We know that $\max_j x_{ij} < \sqrt{2\log(p/\delta)}$ with probability at least $1-\delta$.

I would like to obtain a lower bound for $\min_i (\max_j x_{ij})$ that holds with probability at least $1-\delta$. Could somebody point to a relevant reference please?

-

You know that

$$\Pr(\max_j x_{ij} \le k) = \Phi(k)^p$$

so

$$\Pr(\max_j x_{ij} \gt k) = 1 - \Phi(k)^p$$

so

$$\Pr(\min_i (\max_j x_{ij}) \gt k) = \left(1 - \Phi(k)^p\right)^n$$

so

$$\Pr(\min_i (\max_j x_{ij}) \le k) = 1- \left(1 - \Phi(k)^p\right)^n$$

and if this is is equal to $1-\delta$ then

$$k = \Phi^{-1}\left( (1- \delta^{\frac{1}{n}})^{\frac{1}{p}} \right)$$

-
In the RHS of all equations, $j$ should be replaced by $p$. –  Aditya May 17 '12 at 1:19
@Aditya: Yes - thank you –  Henry May 17 '12 at 6:14

You might try Gordon's inequality, which is a sort of comparison inequality for Gaussian processes. Here is a lecture note:

http://www-personal.umich.edu/~romanv/teaching/2006-07/280/lec11.pdf

Not sure if it gives the result you want. The general reference for these types of inequalities is Chapter 3 of Probability in Banach Spaces by Ledoux and Talagrand. Also, take a look at: http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf

-