Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have n IID random variables $X_1, X_2, \ldots, X_n$. Let $R_i$ be $X_i$'s rank in the set $\{X_1, X_2, \ldots, X_3 \}$ when we order from large to small. How to prove $R_i, \forall i \in \{1, 2, \ldots, n\}$, is uniformly distributed on $\{1, 2, \ldots, n\}$?


My first guess is that, for any position $j$ in ordered sequence of $X$s, as $X_1, X_2, \ldots, X_n$ are equally likely to be the $j$th largest,

$$\Pr \{ R_i = j \} = \frac 1 n.$$

So $R_i$ is uniformly distributed on $\{1, 2, \ldots, n\}$.


Another way to think about it, is to count how many possible cases are there when $R_i = j$. As $X_i$'s position in ordered sequence is fixed at $j$, then we can just permute the rest of $X$s to get all possible ordered sequence. Since there are $n-1$ variables left, there are $(n-1)!$ situations. As for any $R_i = j, 1 \le j \le n$, there are always $(n-1)!$ possible ordered sequences, we can say $R_i$ is uniformly distributed on $\{1, 2, \ldots, n\}$.


Are these 2 proof rigorous?


Edit:

As cardinal pointed out, an additional condition is needed for the proof, and a sufficient such condition is that $X_i$ to be a continuous random variable.

share|improve this question
2  
You need either an additional hypothesis (e.g., $X_i$ are continuous random variables) or you need to specify how ties are broken for this to hold. For example, consider $X_i \sim \mathrm{Ber}(1/2)$. –  cardinal Sep 14 '11 at 14:25
    
Why $X_i$ are continuous? Because there might be duplications? –  ablmf Sep 14 '11 at 15:07
    
Yes, because of duplications. –  Robert Israel Sep 14 '11 at 15:29
    
I posted an answer and deleted it. I'll be back..... –  Michael Hardy Sep 14 '11 at 15:43
    
Now I've done several edits within a few minutes and if you looked during that time, you might have been confused, but now I think I have it about where I want it. –  Michael Hardy Sep 14 '11 at 19:33
add comment

1 Answer 1

up vote 0 down vote accepted

Suppose $Y_1 = X_2$, $Y_2=X_3$, and $Y_3 = X_1$. If you can show that the joint distribution of the vector $(Y_1,Y_2,Y_3)$ is the same as the joint distribution of the vector $(X_1,X_2,X_3)$, then it follows that the probability that $X_1$ has a certain rank is the same as the probability that $Y_1$ has that rank. But the latter is the probability that $X_2$ has that rank. Thus the probability that $X_1$ has a certain rank is the same as the probability that $X_2$ has that rank. As with $1$ and $2$, so also with the others. Thus $$ \Pr(R_1 = j) = \Pr(R_2=j)=\cdots=\Pr(R_n=j). $$ Since these are mutually exclusive and exhaustive events, each must have probability $1/n$. Notice that we didn't need to know the value of $j$ for this. Therefore $$ \Pr(R_1 = 1) = \Pr (R_1=2) = \Pr(R_1=3) = \cdots = \Pr(R_1=n) = \frac1n, $$ and similarly with any of the other indices besides $1$.

So your first guess was right, but one can say a few things to demonstrate that it's right, and call that a proof.

share|improve this answer
    
Of course, more pedestrian combinatorial arguments also work. –  Michael Hardy Sep 14 '11 at 19:35
    
I think this is rigorous proof. But to be sure, I will leave it for 1 or 2 days to see if others agrees. –  ablmf Sep 14 '11 at 20:57
1  
As far as I can tell, this argument suffers from the same pitfall as the OP's attempts. I believe my example still shows why. –  cardinal Sep 14 '11 at 23:39
    
I will put that into know condition. –  ablmf Sep 15 '11 at 1:55
1  
@Michael: Precisely. Since others will (hopefully) be reading this in the future, my thought was that it might be important to actually state this, lest one draw the wrong conclusion otherwise. A version of Lebesgue's decomposition theorem tells us exactly what the measures with the required hypothesis must look like. –  cardinal Sep 15 '11 at 11:23
show 2 more comments

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.