# Why are all the permutations of i.i.d. samples from a continuous distribution equally likely?

Suppose $X$ is i.i.d from a continuous distribution

Why is$$P(X_{i_1}<X_{i_2}<\cdots<X_{i_3})=P(X_{j_1}<X_{j_2}<\cdots<X_{j_3})=\frac{1}{n!}$$for all $i,j$?

I think we can reason this by probability measure is translational invariant? (But I don't think this is true in general)

Update: I know the intuition but please give a mathematical proof of this

• Since the sample is iid, any ranking of the observations is equally likely. Jan 16 '17 at 11:32
• This assertion is not true. It holds only for continuous distributions. The simplest counterexample is an iid sample of $2$ values from a Bernoulli$(1/2)$ distribution, where it's easy to compute that $$\Pr(X_1\lt X_2)=\Pr(X_1=0, X_2=1)=1/4\ne 1/2!.$$
– whuber
Jan 16 '17 at 17:30
• He corrected the question to restrict it to continuous distributions. Jan 16 '17 at 20:44

## 1 Answer

Although this is intuitively obvious, there is merit in providing a rigorous proof because it helps demonstrate that our definitions really do capture what we think ought to be true.

### The basic idea

The independence of two variables $X$ and $Y$ is defined in terms of the probabilities of rectangles: $X$ and $Y$ are independent if and only if

$$\Pr(X\in\mathcal{A}\text{ and }Y\in\mathcal{B}) = \Pr(X\in\mathcal{A})\Pr(Y\in\mathcal{B})$$

for all events $\mathcal{A}$ and $\mathcal{B}$. On the other hand, even the simplest example of the question (involving just $n=2$ variables) involves events of the form $X \lt Y$. This event is an infinite triangle, which in general cannot be expressed in terms of a finite--or even a countable--number of rectangles. The crux of the matter is to decompose these triangles into rectangles. It's geometrically obvious that an infinite number of rectangles is needed, so we're going to have to be a little careful.

### Demonstration for $n=2$

The case $n=2$ captures all the important ideas, so let's begin there and call the two iid variables $X$ and $Y$. Since some kind of limiting argument is needed, let's partition the real numbers at the outset into a union of intervals of length $e \gt 0$, with the intention of letting $e$ grow arbitrarily small. These intervals are going to carve the plane into rectangles. The important ones are these:

$$\mathcal{A}(i,e) = (-\infty, ie) \times (ie, (i+1)e],$$

$$\mathcal{A}^\prime(i,e) = (ie, (i+1)e] \times (-\infty, ie),$$

and

$$\mathcal{B}(i,e) = (ie, (i+1)e] \times (ie, (i+1)e].$$

The idea to what follows is that the union of red rectangles of the form $\mathcal{A}(i,e)$ just about fills up the region $X \lt Y$, the union of the blue rectangles $\mathcal{A}^\prime(i,e)$ just about fills up the region $Y \lt X$, and the remainder--the union of the squares $\mathcal{B}(i,e)$--has vanishing probability as $e\to 0$ provided the common distribution is continuous. The iid assumption shows the chance of each red $\mathcal{A}(i,e)$ equals the chance of its blue counterpart $\mathcal{A}^\prime(i,e)$, showing $\Pr(X\lt Y) = \Pr(Y\lt X)$ in the limit.

As usual, let $F(x) = \Pr(X \le x) = \Pr(Y \le x)$ denote the common distribution function for the variables. Let $F_0(x) = \Pr(X \lt x) = \Pr(Y \lt x)$. With these we may compute probabilities of rectangles:

\eqalign{ &\Pr((X,Y)\in \mathcal{A}(i,e) &= \Pr(X\lt ie)\Pr(ie \lt Y \le (i+1)e) \\ &&= F_0(ie)(F((i+1)e - F(ie)) \\ &&= (F((i+1)e - F(ie))F_0(ie) \\ &&= \Pr(ie \lt X \le (i+1)e)\Pr(Y\lt ie) \\ &=\Pr((X,Y)\in \mathcal{A}^\prime(i,e).\tag{1} }

There is the anticipated symmetry: the $\mathcal{A}(i,e)$ nearly fill up the upper triangular region $X \lt Y$ while the $\mathcal{A}^\prime(i,e)$ nearly fill up the lower triangular region $X \gt Y$. Furthermore, because the three kinds of rectangles partition the plane without overlap, the Law of Total Probability asserts

$$1 = \sum_{i\in\mathbb{Z}} \mathcal{A}(i,e) + \sum_{i\in\mathbb{Z}} \mathcal{A}^\prime(i,e) + \sum_{i\in\mathbb{Z}} \mathcal{B}(i,e).\tag{2}$$

Consider these last terms, the sums of the squares $\mathcal{B}(i,e)$ straddling the diagonal. Again by independence, the probabilities of these squares are found by multiplying, yielding

$$\Pr(\mathcal{B}(i,e)) = (F((i+1)e)-F(ie))^2.$$

When $F$ is continuous, the right hand side has a limit equal to $0$ as $e$ approaches $0$ (from above). This is an elementary (but somewhat technical) fact about continuous functions, so I will forgo the distraction of proving it. Assuming this fact, taking limits in (2), and exploiting the equality in $(1)$ yields

\eqalign{ 1 &= \lim_{e\to0^{+}}\sum_{i\in\mathbb{Z}} \Pr(\mathcal{A}(i,e)) \\ &+ \lim_{e\to0^{+}}\sum_{i\in\mathbb{Z}} \Pr(\mathcal{A}^\prime(i,e)) \\ &+ \lim_{e\to0^{+}}\sum_{i\in\mathbb{Z}} \Pr(\mathcal{B}(i,e)) \\ &= \lim_{e\to0^{+}}\left(\Pr(\cup_{i\in\mathbb{Z}} \mathcal{A}(i,e)) + \Pr(\cup_{i\in\mathbb{Z}} \mathcal{A}^\prime(i,e))\right) + 0 \\ &\le 2\Pr(X \lt Y). }

Since $2\Pr(X \lt Y) \le 1$, the only possibility is $\Pr(X\lt Y) = \Pr(Y \lt X) = 1/2$.

### Demonstration for general $n$

The rest is mopping up. When all $X_i, i=1,2,\ldots, n$ are independent for $n\gt 2$, then $X_i$ and $X_j$ are a fortiori independent. The same argument shows that switching $X_i$ and $X_j$ in any ordering of all the variables does not change the probability. Since such swaps generate the group of all permutations, we deduce that all orderings have equal probabilities and the sum of those probabilities is $1$. Since there are $n!$ distinct orderings, each one has a probability of $1/n!$.