Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm following an equation from a published paper in order to calculate probabilities using a Markov Chain. The equation says:

Construct a set $U$ that consists of all items that appear in the top-$k$ in at least one list.

For each pair of items $i$ and $j$ in $U$, let the preference for $i$ over $j$, $m_i{_j}$, equal $1$ if the majority of the lists ($>=50$%) that rank both $i$ and $j$ rank $j$ above $i$ and $0$ otherwise. Let $m_i{_j} = m_j{_i} = 0.5$ if items $i$ and $j$ are never directly compared in any list.

My problem with the above is: $U$ is composed of the top-k items in at least one list. Wouldn't this mean that $m_i{_j} = 0.5$ would never be possible because if $U$ is composed of items that must all appear in one list, each item is directly compared in at least one list.

I just want someone to confirm my reading of this.

share|cite|improve this question
It is hard to read without having the article, but I am reading it in the same way as you are. – utdiscant Jul 13 '12 at 10:35
@utdiscant the article gives no other relevant information it's exactly as I've typed it out. The article isn't about this specific equation, it's just one of the equations they are using for their proof – adohertyd Jul 13 '12 at 10:37
Maybe you could post a link to the article, or at least a title. – utdiscant Jul 13 '12 at 12:35
If there are at least two lists, the convention is necessary if i appears in some lists, j appears in some other lists and no list contains them both. – Did Jul 13 '12 at 13:39
@did after reading your point and going over my data again, with a pen and paper for more than an hour!, I can see that you are correct and that there are in fact a few instances of this state. Thanks for that! – adohertyd Jul 13 '12 at 15:07
up vote 1 down vote accepted

If there are at least two lists, the convention is necessary if item $i$ appears in some lists, item $j$ appears in some other lists, and no list contains both items $i$ and $j$.

share|cite|improve this answer
Correct, I don't know how I was reading it to come to my original conclusion but this ties it up nicely. Thank you. Edit: Apologies to the authors of the paper for questioning their reasoning :) – adohertyd Jul 13 '12 at 15:19
Do you think they care? Anyway, this is a mistake to erase your comment where you gave the reference of the paper, and you should put this information back, in a new comment or, better still, in the post. – Did Jul 13 '12 at 15:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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