Ranking randomly distributed variables based on decreasingness

Question

For some research I am conducting, I have run into the following problem, which I must solve repeatedly:

My data consists of sequences of observations $\{O_1,O_2,\ldots,O_n\}$, each with a different normally distributed error. The sequences are variable in length, ranging from 5 to 44 observations.

I need a ranking system that expresses how much a given sequence of observations is decreasing.

---

Here's what I've come up with so far:

Since everything is normally distributed, it's easy to compute $P(O_1 > \cdots > O_n )$ or $\prod_{i=1}^{n-1}P(O_i > O_{i+1})$ via Monte Carlo. So my first naïve way of tackling this problem is to try these two scores.

There are problems with this approach. In my data, the observations may correspond to an exponentially decreasing quantity, or follow a power law. In these asymptotically convergent cases, for large $n$ these scores could be very low. What's more, a short sequence with wide error bars could easily get a higher score.

So a good ranking system should punish short, ambiguous sequences and forgive long, asymptotically convergent sequences.

Thinking of the ambiguous case, one can show that if all of the observation are i.i.d, then regardless of the distribution:

• $\displaystyle P(O_1 > O_2 > \cdots > O_n) = \frac{1}{n!}$ and
• $\displaystyle\prod_{i=1}^{n-1}P(O_i > O_{i+1}) = \frac{1}{2^{n-1}}$

From these observations, I was inspired to come up with the following rankings:

• $P(O_1 > \cdots > O_n ) \times {n!}$
• $\displaystyle\prod_{i=1}^{n-1}P(O_i > O_{i+1}) \times 2^{n-1}$

I can't say anything about the statistical properties of these rankings, as they are my own invention and I can't find any papers on this problem. Also, I have yet to implement anything, since I only encountered this problem very recently. I will update this question with my developments.

Input and criticisms are welcome! Thanks everyone in advance!

Answer 1

Instead of approximating a really small probability, then rescaling it by something huge (like $44! \approx 2.7 \times 10^54$) you would do better to compute integer-valued statistics such as the count of values $i$ so that $O_i \gt O_{i+1}$. This will be a more efficient use of any MonteCarlo runs you perform.

One idea which has been studied a lot by mathematicians is the number of inversions, pairs $i \lt j$ where $O_i \gt O_j$. For a uniformly random permutation, the number of inversions is a sum of independent discrete uniform distributions

$$ \sum_{i=1}^n U[\lbrace 0, 1, ..., i-1 \rbrace] $$

and as $n \to \infty$ this is asymptotically normal with mean ${n \choose 2}/2$ and standard deviation $\sqrt{(2n^3 + 3n^2-5n)/72} = n^{3/2}/6 + O(n).$

I don't know of a closed form expression for the number of permutations of $n$ with exactly/at least $i$ inversions but there are recursions which are fast enough for much larger $n$ than you are using. Let $I(n,i)$ be the number of permutations of $n$ with exactly $i$ inversions. Then

$$ I(n,i) = \sum_{j=0}^{i-1} I(n-1,i-j)$$

by conditioning on the last uniform random variable above.