# Maximum of minimum of random variables

Is there a general formula for calculating distribution of the maximum of the minimum of random variables?

For example: say I have independent random variables $X_1,X_2,X_3$ distributed with CDFs $F_1,F_2,F_3$ respectively. I'm interested in the distribution of $Z = \max(\min(X_1,X_2),\min(X_1,X_3),\min(X_2,X_3))$. My current solution is to calculate $P(Z\leq t) = P(\{\min(X_1,X_2)\leq t\} \land \{\min(X_1,X_3) \leq t\} \land \{\min(X_2,X_3)\leq t \})$.

I can evaluate this by using a modified version of the inclusion-exclusion principle in terms of simpler expressions. This creates an expression with 55 terms that can be simplified to 5. Is there a theorem to go straight to the simplified 5 term expression? I'd like to generalize this to the case of the maximum of an arbitrary number of minimums of an arbitrary subset of independent variables. Using my current algorithm with the inclusion-exclusion principle doesn't scale as well as I would like. Is there a better solution to this problem?

• For continuous random variables, does $Z$ equal the median value of the three? Jul 8, 2016 at 13:06
• In this particular example, I think it does. But in general it may not. The subsets that the minima are taken over are not restricted to cardinal of 2. For example, with 4 random variables that take on the ordering $X_1\leq X_2 \leq X_3 \leq X_4$ and three of the minima functions include $X_1$ with the fourth including $X_2$, the maximum would be $X_2$. Jul 8, 2016 at 13:23
• For differing $F_i$, this problem is intractable: there is no simplification apart from the following. When you consider all $\binom{n}{k}$ minima of among all $k$-element subsets of $n$ RVs, the largest of them will (obviously) be the $n-k+1^\text{st}$ order coefficient. At that point, finding the distribution is straightforward but there is no simplification or closed form. As far as an "arbitrary number of" minima goes, life is even worse because the result is not even an order statistic.
– whuber
Jul 8, 2016 at 13:40
• If I were to restrict my attention to only exponentially distributed RVs, then the minima are also exponentially distributed. I know there's a closed form solution for the maximum of exponentially distributed RVs, but my minima aren't necessarily independent. Apart from identically distributions, is there any other restriction that you might suggest to make this problem tractable? Jul 8, 2016 at 13:51
• Balakrishnan & Cohen, Order Statistics and Inference. Academic Press, 1991.
– whuber
Jul 8, 2016 at 18:05

Let $X_1, X_2, X_3$ be continuous independent non-identical random variables. We have a sample of 3 values, namely $(X_1, X_2, X_3)$, where:

• 1 value is drawn from $X_1$,
• 1 value is drawn from $X_2$ and
• 1 value is drawn from $X_3$.

We seek the pdf of:

$$Z = \max(\min(X_1,X_2),\min(X_1,X_3),\min(X_2,X_3))$$

Without loss of generality, imagine that the sample is such that $X_1 < X_2 < X_3$. Then, $Z = max(X_1,X_2) = X_2$ (i.e. we seek the pdf of the second largest order statistic, from the sample of 3 values).

In summary: given sample $(X_1, X_2, X_3)$ of non-identical random variables, we seek the pdf of the $2^{nd}$ order statistic.

This problem is solvable exactly, but, for any typical example (with overlapping domains of support) the computation can be difficult to do by hand, and it is easiest to solve with the help of a computer algebra system. See, for instance:

• Rose, C. and Smith, M.D. (2005), Computational order statistics, The Mathematica Journal, 9(4), 790-802.

Example

Let:

• $X_1 \sim \text{Exponential}(1)$ with pdf $f(x_1)$
• $X_2 \sim N(0,1) \quad \quad \quad$ with pdf $g(x_2)$
• $X_3 \sim \text{Uniform}(-1,1)$ with pdf $h(x_3)$

That is:

Here is a plot of the 3 parent pdf's:

We seek the pdf of $Z$, namely the pdf of the $2^{nd}$ order statistic in sample of size 3, where 1 value is taken from each of ${f,g,h}$. This can be calculated with the OrderStatNonIdentical function from the mathStatica package for Mathematica:

Here is a plot of the pdf of $Z$:

Monte Carlo check

Here is quick check of the empirical pdf of $Z = \max(\min(X_1,X_2),\min(X_1,X_3),\min(X_2,X_3))$ using Monte Carlo methods:

• How does the computational difficulty of applying OrderStatNonIdentical to this problem scale with n? Jul 8, 2016 at 17:59
• While this is a great answer and solves the particular example I gave, I was hoping to be able to generalize to several minima functions over an arbitrary (but known) subset of RVs. This answer is predicated on the assumption that the pdf is always the $2^{nd}$ order statistic, and this may not always be the case. Jul 8, 2016 at 18:19
• (+1) This illustrates how complex the answer might be even in a simple situation. I believe what @Mark was hinting at is that the tripartite appearance of the graph in the case of $n=3$ variables reflects the general result that the equation requires $n!$ separate formulas (one for each possible ordering of the variables), which is as awful as it could possibly be.
– whuber
Jul 8, 2016 at 18:27
• @MarkL.Stone That's an interesting question. I think it depends more on whether the scaling of $n$ is due to adding more distributions (e.g. $n=50$ with 50 different random variables) versus $n=50$ drawings with 3 random variables, with say {23,12,15}, denoting 23 drawings from $f$, 12 from $g$ and 15 from $h$. Things may get more complicated in the former case, and especially if there are many domain overlaps ... which may place a practical cap of $n = 30$ to 50. In the latter case, the complication will often be simplifying the solution ... not finding it. Jul 8, 2016 at 20:17