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

Question

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?

Answer 1

Given your data:

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