Probability of having an increasing trend in normal variates

Question

Let $x\sim N(\mu,\sigma)$ and $x_i$ is ordered instances of random variate of $x$ for $i=1...n$. What is the probability that the series is in increasing (or decreasing) order?

The problem is finding the probility that consecutive differences $(x_{i+1}-x_i)$ are all positive (or negative) for $i=1...\left(n-1\right)$. At first intuition, it can be thought that the probaility is $2^{-n}$ because $P\left[\left(x_{i+1}-x_i\right)\right>0]=0.5$ for one couple and $x_i$s are independent. But this is wrong. Consider the example for $n=3$: The desired probability is $P\left[(x_3-x_2)>0|(x_{2}-x_1)>0\right]$. This probability is conditional, although $x_i$s are independent.

The simulation for normal distribution with several $n$s suggests this probability is $1/n!$. It is also similar for uniform and exponential distribution, so it looks like that this probability is distribution independent.

I guess this problem is related with order statistics which I am not much familiar with. So, what is the theory behind it?

Answer 1

Implicit in the question is the assumption that the $x_i$ are independent. This implies a weaker condition: exchangeability; namely, that any fixed permutation of the vector $\mathbf{x}=(x_1, x_2, \ldots, x_n)$ has the same distribution as that of $\mathbf{x}$ itself.

Because the common marginal distribution (assumed here to be Normal, but that detail is irrelevant) is continuous, the chance of any tie among the $x_i$ is zero. See our thread at Why are all the permutations of i.i.d. samples from a continuous distribution equally likely? for a rigorous demonstration of these assertions.

Because almost surely all the $x_i$ differ, there is a unique permutation that orders them. Since exchangeability implies all permutations are equally likely and there are $n!$ permutations, the answer is $1/n!.$

Reference

N. Balakrishnan and A. Clifford Cohen, Order Statistics and Inference. Academic Press, 1991: Section 2.2.

Balakrishnan and Cohen use the result stated here as the point of departure for deriving the joint distributions of any set of order statistics of a sample, assuming only that the common underlying distribution is continuous. (Otherwise, the possibility of ties creates combinatorial complications.)