Question: 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..

My attempt: 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?

  • 1
    $\begingroup$ 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. $\endgroup$ – MLS Jun 12 '12 at 12:00
  • 1
    $\begingroup$ If (2) holds for a collection of random variables, does it also hold if you add a Bernoulli random variable to the collection? $\endgroup$ – Douglas Zare Jun 12 '12 at 13:49
  • $\begingroup$ @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}$. $\endgroup$ – MLS Jun 12 '12 at 14:45
  • 2
    $\begingroup$ Crossposted to stats.SE: stats.stackexchange.com/questions/30245 $\endgroup$ – cardinal Jun 13 '12 at 0:08
  • 1
    $\begingroup$ 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. $\endgroup$ – MLS Jun 13 '12 at 14:35

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.