For i.i.d. random variables, we may write the CDF of $t=\max(t_1,\cdots,t_N)$ as $$F_t(t)=F_{t_i}(x)^n$$ and the CDF of $x=\min(x_1,\cdots,x_N)$ as $$F_x(x)=1-(1-F_{x_i}(x))^n$$

When we have $X=\max(\min(\cdots),\cdots,\min(\cdots))$, we may combine above results if every entry in $\min(\cdots)$ are independent to each other in each $\min$ term.

However, I have some common terms in $\min(\cdots)$ terms. For example: $$X=\max(\min(x_1,x_2,x_3),\min(x_1,x_4,x_5),\min(x_5,x_6,x_7),\min(x_3,x_6,x_8))$$ I understand that they are correlated (and dependent?), but I am not sure how I can apply correlation and/or dependency, specially for the general case. Basically, $x_i$'s are exponentially distributed.

Can someone guide me to derive $F_X(x)$?

  • $\begingroup$ It gets really messy if you cannot assume $F_{t_i}$ is continuous. $\endgroup$
    – whuber
    Jul 27, 2016 at 12:29
  • $\begingroup$ they are continuous RVs. $\endgroup$
    – Frey
    Jul 27, 2016 at 17:20

1 Answer 1


I will illustrate with the example in the question, because a general answer is too complicated to write down.

Let $F$ be the common distribution function. We will need the distributions of the order statistics $x_{[1]} \le x_{[2]} \le \cdots \le x_{[n]}$. Their distribution functions $f_{[k]}$ are easy to express in terms of $F$ and its distribution function $f=F^\prime$ because, heuristically, the chance that $x_{[k]}$ lies within an infinitesimal interval $(x, x+dx]$ is given by the trinomial distribution with probabilities $F(x)$, $f(x)dx$, and $(1-F(x+dx))$,

$$\eqalign{ f_{[k]}(x)dx &= \Pr(x_{[k]} \in (x, x+dx]) \\&= \binom{n}{k-1,1,n-k} F(x)^{k-1} (1-F(x+dx))^{n-k} f(x)dx\\ &= \frac{n!}{(k-1)!(1)!(n-k)!} F(x)^{k-1} (1-F(x))^{n-k} f(x)dx. }$$

Because the $x_i$ are iid, they are exchangeable: every possible ordering $\sigma$ of the $n$ indices has equal probability. $X$ will correspond to some order statistic, but which order statistic depends on $\sigma$. Therefore let $\operatorname{Rk}(\sigma)$ be the value of $k$ for which

$$\eqalign{ x_{[k]} = X = \max&\left( \min(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)}),\min(x_{\sigma(1)},x_{\sigma(4)},x_{\sigma(5)}), \right. \\ & \left. \min(x_{\sigma(5)},x_{\sigma(6)},x_{\sigma(7)}),\min(x_{\sigma(3)},x_{\sigma(6)},x_{\sigma(8)})\right). }$$

The distribution of $X$ is a mixture over all the values of $\sigma\in\mathfrak{S}_n$. To write this down, let $p(k)$ be the number of reorderings $\sigma$ for which $\operatorname{Rk}(\sigma)=k$, whence $p(k)/n!$ is the chance that $\operatorname{Rk}(\sigma)=k$. Thus the density function of $X$ is

$$\eqalign{ g(x) &= \frac{1}{n!} \sum_{\sigma \in \mathfrak{S}_n} f_{k(\sigma)}(x) \\ &= \frac{1}{n!}\sum_{k=1}^n p(k)\binom{n}{k-1,1,n-k} F(x)^{k-1} (1-F(x))^{n-k} f(x) \\ &=\left(\sum_{k=1}^n \frac{p(k)}{(k-1)!(n-k)!}F(x)^{k-1} (1-F(x))^{n-k} \right)f(x) .}$$

I do not know of any general way to find the $p(k)$. In this example, exhaustive enumeration gives

$$\begin{array}{l|rrrrrrrrr} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline p(k) & 0 & 20160 & 74880 & 106560 & 92160 & 51840 & 17280 & 0 & 0 \end{array}$$

The figure shows a histogram of $10,000$ simulated values of $X$ where $F$ is an Exponential$(1)$ distribution. On it is superimposed in red the graph of $g$. It fits beautifully.


The R code that produced this simulation follows.

n.sim <- 1e4
n <- 9
x <- matrix(rexp(n.sim*n), n)
X <- pmax(pmin(x[1,], x[2,], x[3,]),
          pmin(x[1,], x[4,], x[5,]),
          pmin(x[5,], x[6,], x[7,]),
          pmin(x[3,], x[6,], x[8,]))

f <- function(x, p) {
  n <- length(p)
  y <- outer(1:n, x, function(k, x) {
    pexp(x)^(k-1) * pexp(x, lower.tail=FALSE)^(n-k) * dexp(x) * p[k] /
      (factorial(k-1) * factorial(n-k))

hist(X, freq=FALSE)
curve(f(x, p), add=TRUE, lwd=2, col="Red")

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.