# Surprisal in rankings

I'm looking for some metric of surprisal when comparing ranked lists - things along the lines of (eg) the rankings in a marathon race, or the times in the race.

Intuitively, in a race with 100 people, it is not terribly surprising if #60 moves up 10 spots (since there is probably a pack in the middle), but it would be much more surprising if #11 moves up 10 spots. If we think of the distribution of everyone's timings as a histogram or probability density, then the "surprisingness" of a move is in some sense the change in probability of the result. But it's not just change in probability - someone being #1 or #100 are both relatively low probability, but jumping from one to the other is literally the most surprising outcome (why?). So maybe it is an integral of the surprisingness over all intermediate changes in probability needed to get from one value to the other. This seems related to entropy or cross-entropy or mutual information, I'm just not sure how to describe it as a formula.

A slight twist on this is if comparing multiple ranked lists (eg multiple races with the same participants). Each person has their own distribution that results are drawn from, with some expected value but also a measure of how consistent a performer they are; there is also an overall distribution from which (eg) the expected results of people are drawn from. Someone moving #1->#10 or vice versa may be surprising (if they were a consistent performer), or not very (if they are inconsistent), but we'd need enough races to get an idea of the variance of their results.

All of the above is described in terms of rankings, but my actual problem deals with continuous variables (more like scores than rankings). Difference in scores matters - the difference between #1 and #2 may be large, or they may be almost tied (but what is "large" of course depends on the distribution of scores, it's only large if it's large relative to the typical spread).

What's a good metric for surprisal in that context?

P.S. It occurs to me that this is related to Kullback–Leibler divergence - if KL describes just the change in distributions (considering all samples to be interchangeable), what I'm looking for is something like "paired-samples KL" which takes into account that samples are drawn from the two distributions as pairs and are not interchangeable, and the two distributions may not be independent - there's some joint distribution which is not just the product of the two.

UPDATE I've been thinking about how to formalize this question and have a possible definition (not necessarily a way to calculate it though). Given k lists of n real values each (where k is eg the number of races and n the number of participants in the race - all the same participants are in every race, so there are k samples per participant), what is the pdf of getting a specific k+1 th result (another list of n values)? Alternately, what is the total surprisal (in the Shannon information sense) if the next m results (k+1 to k+m) are some specific values? (assuming each of the n results is drawn from its own distribution).

• I think variance and some measure of "heavy-tail"-edness would point you in the right direction. Commented Sep 15, 2022 at 18:17

"Well known" comparisons of two rankings are:

These two have been studied and compared in the paper by Persi Diaconis and R.L. Graham, 1977: Spearman's footrule as a measure of disarray. They prove that for any ranking: $$K \leq S \leq 2K$$, where $$K$$ is Kendall tau distance and $$S$$ is Spearman's footrule. Additionally, that paper also gives the min and max values for each measure, so you can divide by them to obtain normalized values in $$[0, 1]$$.

Another interesting paper is by Ravi Kumar and Sergei Vassilvitskii, 2010: Generalized distances between rankings. This paper adds the observation that disagreement in rankings near the top or bottom of the rankings, rather than in the middle, are more "interesting", so it may be even more relevant to your goal.

You are correct, it does sound like related to entropy.

The core idea of information theory is that the "informational value" of a communicated message depends on the degree to which the content of the message is surprising. If a highly likely event occurs, the message carries very little information. On the other hand, if a highly unlikely event occurs, the message is much more informative.

More specifically, we could use self-information defined as

$$I(x) = -\log p_X(x)$$

Intuitively, in a race with 100 people, it is not terribly surprising if #60 moves up 10 spots (since there is probably a pack in the middle), but it would be much more surprising if #11 moves up 10 spots. If we think of the distribution of everyone's timings as a histogram or probability density, then the "surprisingness" of a move is in some sense the change in probability of the result. But it's not just change in probability - someone being #1 or #100 are both relatively low probability, but jumping from one to the other is literally the most surprising outcome (why?). [...]

$$\Pr(\text{next rank} | \text{current rank})$$

It probably can be simplified to looking at the probability distribution of the change in the rank

$$\Pr(\text{next rank} - \text{current rank})$$

with the possible (?) assumption that the distribution for the jump is independent of the previous rank (the same, regardless of the previous rank). You could estimate this distribution by looking at all the historical data taken together, or another source of information that would inform you what the distribution is supposed to be.

“Surprisingness” of the result should be inversely proportional this probability, and that’s like self-information! So just calculate the self-information using the above distribution as $$p_X$$ in the definition. It's simple and nicely grounded in information theory.

UPDATE I've been thinking about how to formalize this question and have a possible definition (not necessarily a way to calculate it though). Given k lists of n real values each (where k is eg the number of races and n the number of participants in the race - all the same participants are in every race, so there are k samples per participant), what is the pdf of getting a specific k+1 th result (another list of n values)? Alternately, what is the total surprisal (in the Shannon information sense) if the next m results (k+1 to k+m) are some specific values? (assuming each of the n results is drawn from its own distribution).

If I understand you correctly, you have collected $$k$$ results per participant, each being a rank. You want to be able to tell how surprising would be some result for this participant, given what is known from their historical results. Again, you can use the results to find the distribution of the rankings (not jumps) using the historical data (empirical distribution, or some parametric one) and use this distribution as $$p_X$$ to calculate the self-information of some $$x$$ rank.

Notice that in both cases I'm not discussing the change of the probability distribution, but assume that $$p_X$$ is fixed and calculate how surprising is the value $$x$$ given the known distribution (historical results). If you want to model changing probability distribution, it's a different question because then you want to build a time-series model, rather than just assessing how surprising the result is.