PDF/CDF of max-min type random variable

Question

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

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.

set.seed(17)
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))
  })
  colSums(y)
}

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