5
$\begingroup$

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.

  • 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)$.2011-09-14
  • 0
    Why $X_i$ are continuous? Because there might be duplications?2011-09-14
  • 0
    Yes, because of duplications.2011-09-14
  • 0
    I posted an answer and deleted it. I'll be back.....2011-09-14
  • 0
    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.2011-09-14

1 Answers 1

1

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.

  • 0
    Of course, more pedestrian combinatorial arguments also work.2011-09-14
  • 0
    I think this is rigorous proof. But to be sure, I will leave it for 1 or 2 days to see if others agrees.2011-09-14
  • 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.2011-09-14
  • 0
    I will put that into know condition.2011-09-15
  • 0
    @cardinal: One need only have a hypothesis that there are no ties. And of course, as you observed, that happens with continuous distributions and not with discrete distributions. It doesn't happen with any distribution that has at least one point mass somewhere.2011-09-15
  • 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.2011-09-15
  • 0
    I see that the OP has now edited his question. As we have both stated in different words, we can get away with a little less than requiring that $X_i$ have an absolutely continuous distribution.2011-09-15