Prove ranks are uniformly distributed

Question

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.

Answer 1

Michael Hardy's proof doesn't use the IID assumption but rather assumes exchangeability, and hence is more general.

If we assume IID, here's how you can show the rank of a given random variable is discrete uniform. Showing the rank of $X_n$, denoted by $R_n$, is discrete uniform will suffice.

Define $R_n$ as follows: $$ R_n = \sum_{i=1}^n I(X_i \leq X_n) = 1 + \sum_{i=1}^{n-1}I(X_i \leq X_n). $$ Note that $I(\cdot)$ is an indicator function, and $I(X_i \leq X_n) = I(F(X_i) \leq F(X_n))$, where $F$ is the distribution function of $X_n$, which is the distribution function of any arbitrary $X_i$, using IID. By the probability integral transform, $F(X_i) \overset{d}{\equiv} U_i \sim \mathrm{Uniform}(0,1)$. Thus, $$ R_n = 1 + \sum_{i=1}^{n-1}I(U_i \leq U_n). $$ Now, to show that $R_n$ follows a discrete uniform on $\{1,\ldots,n\}$, we must show $\mathrm{P}(R_n=r)=1/n$—i.e., derive the probability mass function of $R_n$. Note that $I(U_i \leq U_n)$ and $I(U_j \leq U_n)$ for $i\neq j$ are not independent because they both have $U_n$. Therefore, even though we know $I(U_i \leq U_n)$ follows a Bernoulli distribution with probability $1/2$, we can't use that directly.

Instead, we condition on $U_n$ and use the law of total expectation as follows: \begin{align} \mathrm{P}(R_n=r) &= \mathrm{E}\left\{\mathrm{P}\left(\sum_{i=1}^{n-1}I(U_i \leq U_n) =r-1\mid U_n\right)\right\}. \end{align} Given $U_n$, $I(U_i \leq U_n) \sim \mathrm{Bernoulli}(U_n)$ and $\sum_{i=1}^{n-1}I(U_i \leq U_n) \sim \mathrm{Binomial}(n-1, U_n)$. Therefore, \begin{align} \mathrm{P}(R_n = r) &= \mathrm{E}\left(\binom{n-1}{r-1}U_n^{r-1}(1-U_n)^{n-r} \right)\\ &= \binom{n-1}{r-1}\int_0^1 u^{r-1}(1-u)^{n-r+1-1} \,\mathrm{d}u\\ &= \binom{n-1}{r-1} \mathrm{B}(r,n-r+1) \\ &= \binom{n-1}{r-1} \frac{(r-1)!(n-r)!}{n!} = \frac{(n-1)!}{(r-1)!(n-r)!}\frac{(r-1)!(n-r)!}{n!}\\ &= \frac{1}{n}. \end{align}

QED.

Answer 2

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.