Improve Markov Chain results

Question

Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results.

The chain starts at State x, a uniform distribution of set S = {1,2,3,...30}. If the current state is page P, select page Q uniformly from the union of the results from each search engine. If the rank of Q < rank of P in 2 of the 3 engines that rank both P and Q, move to Q. Else, remain at P.

This results in a number of pairwise comparisons being carried out. result2 is compared with result1 and a count is made of each time result2 ranks better than 1. The results are sorted by the results of the pairwise comparisons, with the lowest score ranked first. e.g.

Engine Rankings:                       Pairwise Comparison:
         eng1   eng2   eng3                    result1  result2  result3  result4  result5
result1   1      2      2              result1    0        1        0        0        1
result2   4      3      1              result2    2        0        1        2        2
result3   2      4      5              result3    3        2        0        1        2
result4   5      5      3              result4    3        1        2        0        1
result5   3      1      4              result5    2        1        1        2        0

The problem with this example is, if we add the total of each row in the pairwise comparison, we get {2,7,8,7,7}, leaving 3 different results with the same score. I'm wondering if there is a method to further sort these results in order to refine the results so that I'm not left with a number of results that have the same score? I've seen Keminization but I can't see how this would apply? Can someone please give me some guidance?

Answer 1

Let $\mathcal{S}$ be the state space of your Markov chain, and assume that we start at some state $i \in \mathcal{S}$. Let $\mathcal{Y}_i$ be the set of states (pages) that are ranked lower than $i$ by two of the three engines. According to your description, the probability of transition to state $j$ can be defined as follows:

\begin{equation} P_{ij} = \begin{cases} 1 - \frac{|\mathcal{Y}_i|}{|\mathcal{S}|} & \text{if } j = i, \\ \frac{1}{|\mathcal{S}|} & \text{if } j \in \mathcal{Y}_i, \\ 0 & \text{Otherwise} \end{cases} \end{equation}

If I have understood your question correctly, this Markov chain does not always produce credible results due to the following issues. First, your chain allows repetitive comparisons. In other words, it is likely that a state $i$ is compared against some state $j$ multiple times. This, of course, does not make trouble as long as your chain is irreducible. However, in some cases, you will not get the correct result. For example, consider the following scenario.

Imagine for some state $i \in \mathcal{S}$, no state (page) can be found that is ranked lower than $i$ by two other engines, that is $\mathcal{Y}_i = \varnothing$. Therefore, $P_{ii} = 1$ making $i$ an absorbing state. In this case, your chain will be trapped in state $i$ in finite time, and from then on, it will only compare state $i$ against other states repeatedly. If chain is trapped in such a state and you let it run for a long enough time, then your results would clearly be wrong. Similar problem occurs if your chain contains recurrent sub-classes.

Assuming that no such states exist, then you would have an irreducible chain. In that case, if you let the chain run for sufficiently long time, the counting process would result in a good approximation of correct rankings (according to your algorithm).

P.S. This answer is just based on my understanding of your problem and may not be 100% correct.