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!

  • 1
    $\begingroup$ The results you give for the iid case hold for any continuous distribution. Furthermore, the sequence of events $A_i := \cap_{j < i} \{O_i < O_j\}$ corresponding to whether the $i$th observation is a record are, in fact, independent. This is a famous result due to Renyi. There is also some recent work on statistical properties of rankings. One example, which isn't immediately related to your problem, but has some vague similarities is P. Hall and H. Miller (2010), Modeling the variability of rankings, Ann. Stat., vol. 38, no. 5, 2652-2677. $\endgroup$ – cardinal Aug 19 '12 at 18:58

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.

  • 1
    $\begingroup$ Thanks Douglas! Thanks for your remark regarding the use integer-valued statistics. I'll throw out the first ranking, but the second ranking algorithm I came up with, $\displaystyle\prod_{i=1}^{n-1}P(O_i > O_{i+1}) \times 2^{n-1}$, can be refactored as $\displaystyle\prod_{i=1}^{n-1} 2 \times P(O_i > O_{i+1})$. This can be reduced to counting $i$ such that $O_i > O_{i+1}$ as per your suggestion. I'm still thinking of how to make use of your inversion insight to produce a ranking. $\endgroup$ – Matt W-D Aug 19 '12 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.