Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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
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 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.
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$.
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!$.
