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)$?
Best Answer
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 $sigmainmathfrak{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")