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

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

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.

Figure

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")

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.