Independence among order statistics

Question

Given i.i.d uniform variables $X_1, ..., X_n \sim U[0,1]$, is it true that the event $X_i \leq \min_{k \in [i-1]} X_k$ is independent of $X_j \leq \min_{k \in [j-1]} X_k$ for any $i > j$?

The answer seems to be yes through symmetry: $\Pr(X_i \leq \min_{k \in [i-1]} X_k | X_j \leq \min_{k \in [j-1]} X_k) = \Pr(X_i \leq \min_{k \in [i-1]} X_k | X_l \leq \min_{k \in [j-1]} X_k)$ for any $l \in [j-1]$, but I don't have a rigorous proof.

Also, if the above is true, it seems then that this statement is true regardless of the distribution of $X_i$?

Answer 1

Setting. Let $(X_i)_{i\in[n]}$ be i.i.d. random variables having a continuous distribution. Then $X_i$'s are all distinct with probability one. Hence, we can define a random permutation $\pi:[n]\to[n]$ satisfying

$$ \pi(i) = k \quad\iff\quad \text{$X_i$ is the $k$th largest among $X_1,\ldots,X_n$}, $$

or equivalently,

$$ X_{\pi^{-1}(1)} > X_{\pi^{-1}(2)} > \ldots > X_{\pi^{-1}(n)}. $$

Now by the exchangeability, it is easy to prove that $\pi$ has the uniform distribution over the set of all permutations on $[n]$.

Analysis. By noting that $X_i < X_j \iff \pi(i) < \pi(j)$, we have

$$ A_i := \Bigl\{ X_i \leq \min_{k\in[i-1]} X_k \Bigr\} = \Bigl\{ X_i = \min_{k\in[i]} X_k \Bigr\} = \{ \pi(i) = \min \pi([i]) \}. $$

Then we have to check whether $A_i$ and $A_j$ are independent whenever $i \neq j$. To this end, we note that, given $A_i$ and $\pi(i) = p$, the restriction $\pi|_{[j]}$ can assume any $j$-permutation of $\{p+1, \ldots, n\}$ equally likely. Hence,

\begin{align*} \mathbf{P}(A_j \mid A_i, \pi(i) = p) = \frac{1}{j} = \mathbf{P}(A_j). \end{align*}

and we get

\begin{align*} \mathbf{P}(A_j \mid A_i) &= \sum_{p \in [n]} \mathbf{P}(A_j \mid A_i, \pi(i) = p) \mathbf{P}(\pi(i) = p \mid A_i) \\ &= \sum_{p \in [n]} \mathbf{P}(A_j) \mathbf{P}(\pi(i) = p \mid A_i) \\ &= \mathbf{P}(A_j). \end{align*}

This proves that $A_i$ and $A_j$ are independent.

Experiment. The below code verifies $\mathbf{P}(A_i \cap A_j) = \mathbf{P}(A_i)\mathbf{P}(A_j)$ for $n = 8$, $i = 6$, and $j = 3$:

We can play with the values of $n, i, j$, but of course, we will always get $\texttt{True}$ as we have proved.

Answer 2

The answer should be "yes, they are independent" as Sangchul proved. Really sorry for my original answer which is wrong.

Below is my original wrong answer.

---

Fix $i > j$ and fix $X_k, k \in [j-1]$, we want to check whether $\Pr((X_i \leq \min_{i' \in [i-1]} X_{i'}) \land (X_j \leq \min_{j' \in [j-1]} X_{j'})) = \Pr(X_i \leq \min_{i' \in [i-1]} X_{i'}) \Pr(X_j \leq \min_{j' \in [i-1]} X_{j'}).$

It is easy to see that $\Pr(X_j \leq \min_{j' \in [i-1]} X_{j'}) = \min_{j' \in [j-1]} X_{j'}$ (assuming uniform variables). Similarly, $\Pr(X_i \leq \min_{i' \in [i-1]} X_{i'}) = \min_{i' \in [i-1]} X_{i'}$, where \begin{align} \min_{i' \in [i-1]} X_{i'} = \begin{cases} \min_{j' \in [j-1]} X_{j'},& \text{if } X_{t} > \min_{j' \in [j-1]} X_{j'}, \forall j \leq t \leq i - 1\\ \min_{j \leq t \leq i - 1} X_t, & \text{otherwise} \end{cases} \end{align}

We can see that if $X_j \leq \min_{j' \in [j-1]} X_{j'}$, then it rules out the possibility that $X_j > \min_{j' \in [j-1]} X_{j'}$ and thus reduce $\Pr(X_i \leq \min_{i' \in [i-1]} X_{i'})$.