What is the meaning of rank in the context of change-detection?

In a technique that uses CUSUM for change-point detection in this paper, the first step is given below:

Let $x_1, x_2,..., x_n$ be the $n$ samples in an event-series. The samples are ranked in increasing order and the rank $r_i$ for each sample is calculated. In case of ties, we assign average rank to each sample. The cumulative sums are computed as: $S_i = S_{i-1} + (r_i - \bar{r})$. If the ranks are randomly distributed, then there is no change-point. However, if there is indeed a change-point in the event-series, then higher ranks should dominate in either the earlier or later part of the event-series.

I am not quite sure I understand the meaning of rank in this context. For instance, if n=10 and my data points are: 5, 2, 4, 1, 9, 2, 9, 2, 10, 1 can someone please clarify what is really being done here?

• Sort in increasing order: 1, 1, 2, 2, 2, 4, 5, 9, 9, 10
• Assign Average Ranks to break ties: What does this step mean?
• Assign Final Ranks: What does this step mean?
-
Can you provide the citation or link to the text you quote? –  Gavin Simpson Apr 26 '11 at 10:51
@Gavin Simpson: Sure. I have updated my question with the link to the paper that contains this text. –  Legend Apr 26 '11 at 16:23

cp <- c(5, 2, 4, 1, 9, 2, 9, 2, 10, 1)


then the ranks, with ties being given average of the ranks, are:

> rank(cp)
[1]  7.0  4.0  6.0  1.5  8.5  4.0  8.5  4.0 10.0  1.5


What is being done here? If you sort the data in increasing order, then we have a 1 in both rank order positions 1 and 2. We could assign rank 1 to both 1s, or rank 2, or as stated above, the average of the rank orders (1/2) / 2 = 1.5. This is why the two 1s have been given rank of 1.5 in the above output from R.

Now look at the next values in the rank order, the 2s. The 2's are in rank order positions 3, 4, and 5, therefore they all get rank 4 from (3+4+5) / 3 = 4, as this is the average of the tied ranks for these values.

If we initiate $S_0 = 0$, i.e. the zeroth cumulative sum is 0, we compute the $i$th cumulative sum ($S_i$) as the previous cumulative sum ($S_{i-1}$) plus the difference between the rank of the $i$th data point ($r_i$) and the average over all ranks $\bar{r}$.

For the above data, the average rank is:

> rcp <- rank(cp)
> mean(rcp)
[1] 5.5


The values $r_i - \bar{r}$ for this set of data are:

> rcp - mean(rcp)
[1]  1.5 -1.5  0.5 -4.0  3.0 -1.5  3.0 -1.5  4.5 -4.0


and the cumulative sums are:

> cumsum(rcp - mean(rcp))
[1]  1.5  0.0  0.5 -3.5 -0.5 -2.0  1.0 -0.5  4.0  0.0

-
@Gavin Simpson: I was curious if the technique is a standard or they did something more. This clears it up. Thank you for your time and explanation. Really appreciate it. –  Legend Apr 26 '11 at 16:25
@Gavin Simpson: I hope you won't mind if I ask a related question. Why is ranking important? Is there some effect is it addressing here? –  Legend Apr 26 '11 at 21:58
@Legend in the paper you link to, the authors state "Since the test is based on ranks, it is robust to outliers and requires no special distributional assumptions." So there are two reasons. I'm not really that familiar with the CUSUM literature though; my experience is with these tests for structural changes in regression models, so the CUSUM is on residuals and there the actual residuals are used, not ranks, but in other respects the CUSUMs are calculated in the manner described. –  Gavin Simpson Apr 26 '11 at 22:10
@Legend, @Gavin, the basic idea behind the CUSUM tests is that under null hypothesis you sum up zero mean independent identically distributed random variables. This sum converges to random walk. If there is a change point, then the convergence does not happen. So ranking is important here, since under null hypothesis ranks are independent. Note that the actual convergence should be proved, since for funky samples you can get that there is no convergence even in case of no change point. Time trends come into mind. –  mpiktas Apr 27 '11 at 12:25
@mpiktas but residuals are assumed independent random variables so ranks are not a requirement - the strucchange package doesn't use ranked residuals IIRC. –  Gavin Simpson Apr 27 '11 at 12:45