Consider $n\cdot m$ independent draws from cdf $F(x)$, which is defined over 0-1, where $n$ and $m$ are integers. Arbitrarily group the draws into $n$ groups with m values in each group. Look at the minimum value in each group. Take the group that has the greatest of these minima. Now, what is the distribution that defines the maximum value in that group? More generally, what is the distribution for the $j$-th order statistic of $m$ draws of $F(x)$, where the kth order of those m draws is also the pth order of the n draws of that kth order statistic?

All of that is at the most abstract, so here is a more concrete example. Consider 8 draws of $F(x)$. Group them into 4 pairs of 2. Compare the minimum value in each pair. Select the pair with the highest of these 4 minima. Label that draw "a". Label the other value in that same pair as "b". What is the distribution $F_b(b)$? We know $b>a$. We know a is the maximum of 4 minimums of $F(x)$, of $F_a(a) = (1-(1-F(x))^2)^4$. What is $F_b(b)$?

  • $\begingroup$ may i ask where did you get this problem? $\endgroup$
    – Theta30
    Jul 20 '11 at 0:18
  • $\begingroup$ JandR you deleted a comment of yours in which you indicated an ad-hoc method using weights. $\endgroup$
    – Theta30
    Jul 31 '11 at 8:54
  • $\begingroup$ yeah, I figured it was now irrelevant, since you provided a much better solution. I'll see if I can find what I'd written. $\endgroup$
    – OctaviaQ
    Aug 9 '11 at 18:15
  • $\begingroup$ yes, but there might be some interesting ideas $\endgroup$
    – Theta30
    Aug 9 '11 at 18:25
  • $\begingroup$ My brute force method: I figured that $X_{final}$ would be a mixture of predictable weights of order statistics of n*m draws from F(x). For example, for $n=4$ and $m=2$, we start with 8 independent draws from F(x), and $X_{final}$ > the 4th order statistic. To find the PR of it being each order stat 5-8, I wrote a computer script that wrote out every permutation of 1-8, and an algorithm that found $X_{final}$ for each permutation (using the order stats themselves as the comparisons) (cont...) $\endgroup$
    – OctaviaQ
    Aug 9 '11 at 21:18

I answer this: "Arbitrarily group the draws into n groups with m values in each group. Look at the minimum value in each group. Take the group that has the greatest of these minima. Now, what is the distribution that defines the maximum value in that group?"
Let $X_{i,j}$ the i-th random variable in group j and $f(x_{i,j})$ ($F(x_{i,j})$) its density (cdf) function.
Let $X_{\max,j}, X_{\min,j}$ the maximum and minimum in group $j$. Let $X_{final}$ the variable that results at the end of all process. We want to calculate $P(X_{final}<x)$ which is
$$P(X_{\max,j_0}<x \hbox{ and } X_{\min,j_0}=\max_j{X_{\min,j}} \hbox { and } 1\leq j_0\leq n)$$ $$=nP(X_{max,1}<x \hbox{ and } X_{\min,1}=\max_j{X_{\min,j}})$$ $$=nmP(X_{1,1}<x\hbox{ and } X_{1,1}=\max_i(X_{i,1})\hbox{ and } X_{\min,1}=\max_j{X_{\min,j}})$$ $$=nmP(X_{1,1}<x, X_{1,1}>X_{2,1}>\max_{j=2\ldots n} X_{min,j},\ldots,X_{1,1}>X_{m,1}>\max_{j=2\ldots n} X_{min,j})$$ Now, let $Y=\max_{j=2\ldots n} X_{min,j}$ and $W=X_{1,1}$.

A reminder: if $X_1,\ldots X_n$ are iid with pdf (cdf) $h$ ($H$), then $X_{\min}$ has pdf $h_{\min}=nh(1-H)^{n-1}$ and $X_{\max}$ has pdf $h_{max}=nhH^{n-1}$.
Using this, we get the pdf of $Y$ is $$g(y)=(n-1)mf(1-F)^{m-1}[\int_0^y mf(z)(1-F(z))^{m-1} dz]^{n-2},n\geq 2$$

Note that $Y$ is a statistics that is independent of group 1 so its joint density with any variable in the group 1 is the product of densities.
Now the above probability becomes
$$nm\int_0^x f(w)[\int_0^w \int_y^w f(x_{2,1})dx_{2,1}\ldots\int_y^w f(x_{m,1})dx_{m,1}g(y)dy]dw$$ $$=nm\int_0^x f(w)[\int_0^w (F(w)-F(y))^{m-1}g(y)dy]dw$$ By taking derivative of this integral wrt $x$ and using binomial formula we obtain the pdf of $X_{final}$.

Example: $X$ is uniform, $n=4$, $m=3$. Then

$$P(X_{final}<x)=(1/55)x^{12}-(12/55)x^{11}$$ $$+ (6/5)x^{10}-(27/7)x^9+(54/7)x^8-(324/35)x^7+(27/5)x^6. $$

Mean of $X_{final}$ is $374/455=0.822$ and its s.d. is $0.145$ .

  • $\begingroup$ Thank you for your help! But, when I follow the process exactly for simple examples (such as F(x) = x, n=4, m=2), the resulting pdf does not integrate to 1 or otherwise look reasonable. So, I'm not sure what is wrong. Also, I am unclear about your g(y). I thought it would need m's: hmin(y) = m*f(y)(1-F(y))^(m-1)  g(y) = (n-1)*hmin(y)*[Integral over 0 to x of hmin(y)]^(n-2) or, more simply, G(y) = (1-(1-F(y))^m)^(n-1) , g(y) = G’(y) . But, even if I substitute this in for g(y), the final pdf still doesn’t make sense. Am I interpreting something wrong? $\endgroup$
    – OctaviaQ
    Jul 20 '11 at 19:09
  • $\begingroup$ @JandR I rechecked it today; see the corrections $\endgroup$
    – Theta30
    Jul 20 '11 at 19:30
  • $\begingroup$ FYI, I originally posted this question in mathoverflow.net. I posted a link to your answer here, but if you are interested in re-posting or linking your answer yourself, the question is here: link $\endgroup$
    – OctaviaQ
    Jul 20 '11 at 20:33

Since the draws are from an iid samples, we can just consider the draw selected. Consider $f(x) = \frac{d F(x)}{dx}$. Now we know that $b$ is from $f(x)$ and that $b>a$. So,

$$p(b|a) = \frac{f(b)}{\int_a^1 f(y) dy} \forall b>a, 0 \text{ otherwise}.$$

The minimum $m$ in a draw of two is $$p_2(m) = f(m)\int_m^1f(y) dy.$$

The largest minimum among 4 draws would be

$$p(a) = p_2(a)\left[\int_0^a p_2(z) dz\right]^3 = f(a)\int_a^1f(x) dx \left[\int_0^af(y)\left(\int_y^1f(z)dz\right) dy \right]^3.$$

So finally,

$$p(b) = \int_0^1 \left[u(a) \frac{f(b)}{\int_a^1 f(y)dy} f(a)\int_a^1f(x) dx \left[\int_0^af(y)\left(\int_y^1f(z)dz\right) dy \right]^3 \right] da.$$

  • $\begingroup$ Thanks for the elaboration. I am trying to get this! Two questions: What is u(a) in the last equation? and, are you sure your equation for p2(m) is correct? It is different (and comes up with a different answer) from all the other minimum equations I've seen. BTW -- I really appreciate your help! $\endgroup$
    – OctaviaQ
    Jul 19 '11 at 21:43
  • $\begingroup$ This answer seems to be missing some Binomial coefficients. $\endgroup$
    – whuber
    Jul 20 '11 at 13:24

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.