# Bounding the probability that a random variable is maximal

Suppose we have $N$ independent random variables $X_1$, $\ldots$, $X_N$ with finite means $\mu_1 \leq \ldots \leq \mu_N$ and variances $\sigma_1^2$, $\ldots$, $\sigma_N^2$. I am looking for distribution-free bounds on the probability that any $X_i \neq X_N$ is larger than all other $X_j$, $j \neq i$. In other words, if for simplicity we assume the distributions of $X_i$ are continuous (such that $P(X_i = X_j) = 0$), I am looking for upper bounds for: $$P( X_i = \max_j X_j ) \enspace.$$ More specifically, I want to lower bound: $$\sum_{i=1}^N \mu_i P( X_i = \max_j X_j ) \enspace.$$ Below is a possible answer, but the bound seems quite loose and I would like to know if sharper bounds can be formulated (ideally without additional assumptions). Please note that the variables are not assumed to be i.i.d..

Recall that by assumption, $\mu_j \geq \mu_i$ whenever $j > i$. If $N=2$, we can use Chebyshev's inequality to get $$P(X_1 = \max_j X_j) = P(X_1 > X_2) \leq \frac{\sigma_1^2 + \sigma_2^2}{\sigma_1^2 + \sigma_2^2 + (\mu_1 - \mu_2)^2} \enspace.$$ We can use this bound for general $N \geq 2$ to arrive at $$P(X_i = \max_j X_j) \leq \min_{j > i} \frac{\sigma_i^2 + \sigma_j^2}{\sigma_i^2 + \sigma_j^2 + (\mu_j - \mu_i)^2} \leq \frac{\sigma_i^2 + \sigma_N^2}{\sigma_i^2 + \sigma_N^2 + (\mu_N - \mu_i)^2} \enspace.$$ This implies, for all $i$ $$( \mu_N - \mu_i ) P( X_i = \max_j X_j ) \leq (\mu_N - \mu_i) \frac{\sigma_i^2 + \sigma_N^2}{\sigma_i^2 + \sigma_N^2 + (\mu_N - \mu_i)^2} \leq \frac{1}{2} \sqrt{ \sigma_i^2 + \sigma_N^2 } \enspace.$$ This, in turn, implies $$\tag{1} \sum_{i=1}^N \mu_i P( X_i = \max_j X_j ) \geq \mu_N - \frac{N-1}{2} \sqrt{ \sum_{i=1}^{N-1} (\sigma_i^2 + \sigma_N^2) } \enspace.$$ I am trying to find out whether this bound can be improved to something that does not depend linearly on $N$. For instance, does the following hold: $$\tag{2} \sum_{i=1}^N \mu_i P( X_i = \max_j X_j ) \geq \mu_N - \sqrt{ \sum_{i=1}^N \sigma_i^2 } \enspace?$$ And if not, what could be a counterexample?

-
It may be good to note that (2) is implied by (1) for $N = 2$ and $N = 3$, so if a counterexample for (2) exists, it would have to be for $N \geq 4$. Any thoughts, for instance for a different route to attack this problem or references in which similar problems are discussed, are greatly appreciated. – MLS Jun 12 '12 at 12:00
If (2) holds for a collection of random variables, does it also hold if you add a Bernoulli random variable to the collection? – Douglas Zare Jun 12 '12 at 13:49
@Douglas Zare : Good question, I'm not sure. Lets denote $$p_i(n)=P(X_i=\max_{j\leq n}X_j)$$ and renumber s.t. $\mu_1\geq\ldots\geq\mu_N$. Then (2) states $$\sum_i^N p_i(N)(\mu_1-\mu_i)\leq\sqrt{\sum_i^N\sigma_i^2}.$$ Suppose this holds and we add $X_{N+1}$, with $\mu_{N+1}\leq\mu_N$. Of course, $p_i(N+1)\leq p_i(N)$ for all $i\leq N$. Therefore, $$\sum_i^N p_i(N+1)(\mu_1-\mu_i) \leq p_i(N+1)(\mu_1-\mu_{N+1})+\sum_i^N p_i(N)(\mu_1-\mu_i) \leq \frac{1}{2}\sqrt{\sigma_1^2+\sigma_{N+1}^2}+\sqrt{\sum_i^N \sigma_i^2},$$ but this is not always smaller than $\sqrt{\sum_i^{N+1}\sigma_i^2}$. – MLS Jun 12 '12 at 14:45
Crossposted to stats.SE: stats.stackexchange.com/questions/30245 – cardinal Jun 13 '12 at 0:08
I propose to take any future discussion on this question to stats.stackexchange.com/questions/30245 since it was posted there first. I hope this is okay. – MLS Jun 13 '12 at 14:35