21
$\begingroup$

$\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?

$\endgroup$
  • 3
    $\begingroup$ This bound can be tighter if you use the index $j$ that gives you the smaller upper bound instead of $N$. Note that this value depends on both the mean and the variance. $\endgroup$ – user10525 Jun 11 '12 at 14:39
  • 5
    $\begingroup$ @MichaelChernick : I don't believe that is correct. Suppose for instance we have three uniform distributions on $[0,1]$. Then, if I'm not mistaken, $P( X_1 < \max_j X_j ) = 2/3$, whereas $P(X_1 < X_2) = P(X_1 < X_3) = 1/2$. I do not know if you meant to write $P( X_i > \max_j X_j )$, but then the same example shows that it still isn't valid. $\endgroup$ – MLS Jun 11 '12 at 15:23
  • 2
    $\begingroup$ @Michael: That is still not true, unfortunately. The events $A_j = \{X_i > X_j\}$ for fixed $i$ are not independent. $\endgroup$ – cardinal Jun 12 '12 at 1:08
  • 2
    $\begingroup$ @cardinal : Amongst other things, it's related to multi-armed bandits. If you pick an arm based on previous rewards, how big is the probability that you picked the best arm (that would be $P(X_N = \max_j X_j)$ in the notation above), and can we bound the expected loss for picking a sub-optimal arm? $\endgroup$ – MLS Jun 12 '12 at 15:41
  • 2
    $\begingroup$ Crossposted to MathOverflow: mathoverflow.net/questions/99313 $\endgroup$ – cardinal Jun 13 '12 at 0:09
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Could you provide a clear statement of the multivariate Chebyshev Inequality? $\endgroup$ – whuber Jun 21 '17 at 13:59
  • 1
    $\begingroup$ I have edited the solution providing the entire theorem. $\endgroup$ – Martijn Weterings Jun 21 '17 at 14:26
-1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.