Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as off-topic by Stefan Kohl, Andrey Rekalo, Ramiro de la Vega, Noah Stein, Ryan Budney Mar 20 at 20:07

  • This question does not appear to be about research level mathematics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

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