Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
    
may i ask where did you get this problem? –  Theta30 Jul 20 '11 at 0:18
    
JandR you deleted a comment of yours in which you indicated an ad-hoc method using weights. –  Theta30 Jul 31 '11 at 8:54
    
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. –  Jand Aug 9 '11 at 18:15
    
yes, but there might be some interesting ideas –  Theta30 Aug 9 '11 at 18:25
    
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...) –  Jand Aug 9 '11 at 21:18
show 1 more comment

2 Answers 2

up vote 3 down vote accepted

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
$$g(y)=9(1-y)^2(3y+y^3-3y^2)^2,$$

$$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$ .

share|improve this answer
    
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? –  Jand Jul 20 '11 at 19:09
    
@JandR I rechecked it today; see the corrections –  Theta30 Jul 20 '11 at 19:30
    
yes! That's exactly it! Thanks so much! –  Jand Jul 20 '11 at 20:14
    
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 –  Jand Jul 20 '11 at 20:33
add comment

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.$$

share|improve this answer
    
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! –  Jand Jul 19 '11 at 21:43
    
This answer seems to be missing some Binomial coefficients. –  whuber Jul 20 '11 at 13:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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