How can we bound the probability that a random variable is maximal?

Question

$\newcommand{\P}{\mathbb{P}}$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 bounds on: $$ \P( X_i = \max_j X_j ) \enspace. $$ 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. $$ I would like to find some simple (not necessarily tight) bounds for general $N$, but I have not been able to find (esthetically) pleasing results for general $N$.

Please note that the variables are not assumed to be i.i.d.. Any suggestions or references to related work are welcome.

---

Update: recall that by assumption, $\mu_j \geq \mu_i$. We can then use the above bound 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: $$ ( \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: $$ \sum_{i=1}^N \mu_i \P( X_i = \max_j X_j ) \geq \mu_N - \frac{N}{2} \sqrt{ \sum_{i=1}^{N-1} (\sigma_i^2 + \sigma_N^2) } \enspace. $$ I am now wondering whether this bound can be improved to something that does not depend linearly on $N$. For instance, does the following hold: $$ \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?

Answer 1

You can use the multivariate Chebyshev's inequality.

Two variables case

For a single situation, $X_1$ vs $X_2$, I arrive at the same situation as Jochen's comment on Nov 4 2016

1) If $\mu_1 < \mu_2$ then $ P(X_1>X_2) \leq (\sigma_1^2 + \sigma_2^2)/(\mu_1-\mu_2)^2 $

(and I wonder as well about your derivation)

Derivation of equation 1

• using the new variable $X_1-X_2$
• transforming it such that it has the mean at zero
• taking the absolute value
• applying the Chebyshev's inequality

\begin{array} \\ P \left( X_1 > X_2 \right) &= P \left( X_1 - X_2 > 0 \right)\\ &= P\left( X_1 - X_2 - (\mu_1 - \mu_2) > - (\mu_1 - \mu_2)\right) \\ &\leq P\left( \vert X_1 - X_2 - (\mu_1 - \mu_2) \vert > \mu_2 - \mu_1\right) \\ &\leq \frac{\sigma_{(X_1-X_2- (\mu_1 - \mu_2))}^2}{(\mu_2 - \mu_1)^2} = \frac{\sigma_{X_1}^2+\sigma_{X_2}^2}{(\mu_2 - \mu_1)^2}\\ \end{array}

Multivariate Case

The inequality in equation (1) can be changed into a multivariate case by applying it to multiple transformed variables $(X_n-X_i)$ for each $i<n$ (note that these are correlated).

A solution to this problem (multivariate and correlated) has been described by I. Olkin and J. W. Pratt. 'A Multivariate Tchebycheff Inequality' in the Annals of Mathematical Statistics, volume 29 pages 226-234 http://projecteuclid.org/euclid.aoms/1177706720

Note theorem 2.3

$P(\vert y_i \vert \geq k_i \sigma_i \text{ for some } i) = P(\vert x_i \vert \geq 1 \text{ for some } i) \leq \frac{(\sqrt{u} + \sqrt{(pt-u)(p-1)})^2}{p^2}$

in which $p$ the number of variables, $t=\sum k_i^{-2}$, and $u=\sum \rho_{ij}/(k_ik_j)$.

Theorem 3.6 provides a tighter bound, but is less easy to calculate.

Edit

A sharper bound can be found using the multivariate Cantelli's inequality. That inequality is the type that you used before and provided you with the boundary $(\sigma_1^2 + \sigma_2^2)/(\sigma_1^2 + \sigma_2^2 + (\mu_1-\mu_2)^2)$ which is sharper than $(\sigma_1^2 + \sigma_2^2)/(\mu_1-\mu_2)^2$.

I haven't taken the time to study the entire article, but anyway, you can find a solution here:

A. W. Marshall and I. Olkin 'A One-Sided Inequality of the Chebyshev Type' in Annals of Mathematical Statistics volume 31 pp. 488-491 https://projecteuclid.org/euclid.aoms/1177705913

(later note: This inequality is for equal correlations and not sufficient help. But anyway your problem, to find the sharpest bound, is equal to the, more general, multivariate Cantelli inequality. I would be surprised if the solution does not exist)

Answer 2

I have found a theorem that might help you and will try to adjust it for your needs. Assume you have:

$$exp(t \cdot \mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i}))$$

Then by Jensen's inequality (since exp(.) is a convex function), we get:

$$exp(t \cdot \mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i})) \leq \mathbf{E}(exp( t \cdot \underset{1 \leq i \leq n}{max}X_{i})) = \mathbf{E}( \underset{1 \leq i \leq n}{max} \text{ }exp( t \cdot X_{i})) \leq \sum_{i=1}^{n} \mathbf{E} (exp(t \cdot X_{i}) $$

Now for $exp(t \cdot X_{i} $ you have to plug in whatever the moment generating function of your random variable $X_{i}$ is (since it is just the definition of the mgf). Then, after doing so (and potentially simplifying your term), you take this term and take the log and divide by it by t so that you get a statement about the term $\mathbf{E}(\underset{1 \leq i \leq n}{max}X_{i})$. Then you can choose t with some arbitrary value (best so that the term is small so that the bound is tight).

Then, you have a statement about the expected value of the maximum over n rvs. To get now the a statement about the probabilty that the maximum of those rv's deviates from this expected value, you can just use Markov's inequality (assuming that your rv is non-negative) or another, more specific rv, applying to your particular rv.