# Solved – PDF/CDF of max-min type random variable

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

Contents

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_{} le x_{} 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") ``

Rate this post