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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.