# Calculate the probability that at least one random variable in one set greater than all random variables in another set

I have two sets of random variables. Denote $$A=\{X_1,...,X_m\}$$ and $$B=\{X_{m+1},...,X_{m+n}\}$$ All random variables are independent and take values in $$(0,\infty)$$. We know the probability that $$Pr(X_i>X_j)=p_{ij},\ j\neq i$$ How to find the probability that at least one of $$X_1,...,X_m$$ is greater than all of $$X_{m+1},...,X_{m+n}$$?

The question has no unique answer. In particular, any putative formula based solely on the $$p_{ij}$$ cannot be generally correct.

There are two reasons. The first is that when there is a positive chance of ties among any of the values, the answer will obviously depend on how frequently ties occur. Let's deal with that by assuming there is no chance of ties among the $$X_i.$$

The second reason is that the pairwise probabilities $$\Pr(X_i\gt X_j)$$ still don't provide enough information to deduce the full distribution of how the variables are ordered. A good way to appreciate that fact is to construct a counterexample. It must exhibit two sets of random variables $$X_i$$ that (a) have the same values of all the $$p_{ij}$$ but (b) for which the answers differ.

A simple counterexample uses $$m=1$$ and $$n=2.$$ The question asks for the chance that $$X_1$$ is the largest of the $$m+n=3$$ variables. Let $$X_1, Y_2,$$ and $$X_3$$ be iid continuous variables symmetrically distributed around $$0.$$ Pick a number $$e$$ and define $$X_2=eY_2.$$ $$X_2$$ remains symmetrically distributed, implying all the $$p_{ij}=1/2$$ regardless of the value of $$e.$$ Two different values of $$e$$ will provide the counterexample.

Note that since $$X_1$$ and $$X_3$$ play equivalent roles in this setup, they have equal chances of being the largest, no matter what value $$e$$ might have.

• First, let $$|e|$$ be tiny, so that $$X_2$$ is essentially $$0.$$ The chance that $$X_2$$ will be largest is approximately the chance that $$X_1$$ and $$X_2$$ are simultaneously negative, which (because they independently have $$1/2$$ probability of being negative) is $$1/2\times1/2 = 1/4.$$ Therefore one of $$X_1$$ or $$X_3$$ is largest with a chance of $$(1-1/4),$$ implying $$X_1$$ is largest with a chance close to $$3/8.$$

• Second, let $$|e|$$ be huge, so that compared to $$X_2$$ the other $$X_i$$ are essentially $$0.$$ Evidently $$X_2$$ will be the largest of the three variables almost half the time. Now one of $$X_1,$$ $$X_2$$ is largest only half the time, implying $$X_1$$ is largest with a chance close to $$1/4.$$

Because there are different possible answers for a given set of $$p_{ij},$$ the problem is indeterminate.

Let event $$E_k=\{X_k>\max_{i\neq k}X_i\},\ k=1,...,m$$ It's easy to observe that $$E_k,\ k=1,...,m$$ are mutually exclusive. Therefore, we have \begin{align} &Pr(At\ least\ one\ of\ X_1,...,X_m\ is\ greater\ than\ all\ of\ X_{m+1},...,X_{m+n})\\ =&Pr\left(\bigcup_{k=1}^mE_k\right)\\ =&\sum_{k=1}^mPr(E_k) \end{align} Since all random variables are independent, we have $$Pr(E_k)=\prod_{i\neq k}p_{ki}$$ Therefore, we have $$Pr(At\ least\ one\ of\ X_1,...,X_m\ is\ greater\ than\ all\ of\ X_{m+1},...,X_{m+n})=\sum_{k=1}^m\prod_{i\neq k}p_{ki}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The above method was partially wrong according to the comment. The mistake lies on the calculation of $$Pr(E_k)$$, which is not simply the product of $$p_{kj}$$. Actually, the probability to be found not only depends on the probabilities that $$X_k$$ is greater than $$X_j$$ for all other $$j$$'s, but depends on the distributions of the random variables.

Assume that random variables $$X_1,...,X_{m+n}$$ have CDFs $$F_1,...,F_{m+n}$$. We may calculate $$Pr(E_k)=Pr(X_k>X_{(-k,m+n-1)})$$ where $$X_{(-k,m+n-1)}$$ is the largest order statistic of $$X_1,...X_{(k-1)},X_{(k+1)},X_{(m+n)}$$, which is independent of $$X_k$$. Let $$F_{(-k,m+n-1)}$$ and $$f_{(-k,m+n-1)}$$ be the CDF and PDF of $$X_{(-k,m+n-1)}$$, respectively, we have $$F_{(-k,m+n-1)}(x)=\prod_{j\neq k}^{m+n}F_j(x)$$ and $$f_{(-k,m+n-1)}(x)=\frac{\partial}{\partial x}\prod_{j\neq k}^{m+n}F_j(x)$$ Then we have \begin{align} &Pr(E_k)\\ =&Pr(X_k>X_{(-k,m+n-1)})\\ =&\int_0^{\infty}Pr(X_k>x)f_{(-k,m+n-1)}(x)dx\\ =&\int_0^{\infty}\left[1-F_k(x)\right]\frac{\partial}{\partial x}\prod_{j\neq k}^{m+n}F_j(x)dx\\ =&\left.\left[\left[1-F_k(x)\right]\prod_{j\neq k}^{m+n}F_j(x)\right]\right|_0^{\infty}+\int_0^{\infty}f_k(x)\prod_{j\neq k}^{m+n}F_j(x)dx\\ =&\int_0^{\infty}f_k(x)\prod_{j\neq k}^{m+n}F_j(x)dx \end{align} Therefore, \begin{align} &Pr(At\ least\ one\ of\ X_1,...,X_m\ is\ greater\ than\ all\ of\ X_{m+1},...,X_{m+n})\\ =&\sum_{k=1}^m\int_0^{\infty}f_k(x)\prod_{j\neq k}^{m+n}F_j(x)dx \end{align}

• This argument is incorrect and so is the answer. The error originates in the "mutually exclusive" claim. As a counterexample, suppose the $X_i$ are continuous iid variables, so that $p_{ij}=1/2$ for all $i\ne j$ Let $m=n-1.$ The only way there cannot be at least one of the first $m$ variables exceeding the last is for the last to be largest, which has a chance of $1/n,$ so the answer should be $1-1/n.$ However, the products in your formula will all equal $2^{1-n}$ so their sum is $(n-1)2^{1-n},$ but for $n\gt 2$ that does not equal the correct value. – whuber Feb 18 at 18:46
• @whuber yes I think your comment is right. However, the mistake may not be "mutually exclusive", but the calculation of $Pr(E_k)$. The multiplication is wrong, since the events are not independent. – kaixu Feb 18 at 19:26
• Re your edit: see en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle. – whuber Feb 19 at 14:26
• @whuber Here we have $E_j\cap E_k=\emptyset$ for $j\neq k$. – kaixu Feb 19 at 15:12
• Consider a slightly different definition of the $E_j:$ compare them only to the last $n$ variables, as is relevant in this question, and apply the PIE: then you should obtain a correct answer. – whuber Feb 19 at 16:23