Proof for the emergence of a ranking with paired comparisons [closed]

Question

Take a set {A, B, C, D, E}, and assume each of the set elements has a random real value attached to it between 0 and 1. For example, this gives us: {A, B, C, D, E} = {0.1, 0.9, 0.4, 0.6, 0.5}. Assume that the set has a preferred order, {A > B > C > D > E}.

Repeatedly taking random pairs of this set, and assigning an increment to the element of the pair that 'beats' the other element according to the preferred order, results in the real values having a ranking.

For example:

A v's B: A <- 0.1 + increment, B <- 0.9 - increment

C v's D: C <- 0.4 + increment, D <- 0.5 - increment

and so on for many pairings.

So the result after many pairings in a simulation is, for example:

{A, B, C, D, E} = {0.9, 0.7, 0.3, 0.3, 0.1}

Is there a proof that can be created that states that a ranking will always emerge in such a scenario?

Answer 1

The answer is "yes" for at least one reasonable interpretation of "emerge", and doesn't depend on the starting weights.

For each of $k$ objects, let $X_i(t)$ be the weight of the $i$th object at time $t$. At each time step, we choose a random pair of objects $1 \leq i < j \leq k$, adding 1 to the weight of object $j$ and subtracting 1 from the weight of object $i$. Looking only at what happens to the $i$th object, we have that $$ X_i(t+1) = \begin{cases} X_i(t) & \text{if $i$ was not chosen at time $t+1$} \\ X_i(t) + 1 & \text{if $i$ and a smaller $j$ were chosen at time $t+1$} \\ X_i(t) - 1 & \text{if $i$ and a larger $j$ were chosen at time $t+1$.} \end{cases} $$

So each $X_i(t)$ is a random walk on $\mathbb Z$, with differing probabilities of moving up, down or staying still. The expectation of $X_i(t)$ is of the form $c\big(\frac{i-1}{k-1}-\frac 1 2\big)t$ for some constant $c$, so we expect the weights of the objects to be in the correct order with gaps of order $t$ between them. But the deviation from the expectation is around $\sqrt t$ with high probability by Chernoff's inequality, so typically the random fluctuations around the mean are not enough to break the ordering.