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 $i$, select page $j$ uniformly from the union of the results from each search engine. If the rank of $j$ < rank of $i$ in 2 of the 3 engines that rank both $i$ and $j$, move to $j$. Else, remain at $i$.
I understand the above no problem. The sorting point is where I am stuck however. The paper I am using that explains this says:
This is known as a Markov process, where the transition matrix $P$ has $P(i, j) = \frac{1}{n}$ if a majority of the input rankings prefer j to i, and $P(i, i) = 1−\sum_{j≠i} P(i, j)$ Under certain conditions, this process has a unique (up to scalar multiples) limiting distribution $x$ that satisfies $x = xP$, where $x(i)$ gives the fraction of time the process spends at element $i$. Dwork et al. propose sorting the elements by non-increasing $x(i)$ values. To ensure that the process has a unique limiting distribution $x$, we use a "random jump": with probability $δ > 0$, we will choose a random element and move to this element (regardless of whether this element is preferred to the current element). In our experiments we have used $δ= \frac{1}{7}$ , which is the value of $δ$ that is often chosen in the literature for PageRank implementations.
Could someone please explain this to me in plain english because I am completely lost with it at this stage. I don't really understand the whole concept. This paper can be found here with this specific part on page 43.
It may help if I add a small example. I have 5 result pages from 3 search engines. These are their rankings:
engine1 engine2 engine3 Page 1 1 2 2 Page 2 4 3 1 Page 3 2 4 5 Page 4 5 5 3 Page 5 3 1 4
If page 1 is the start point, to move to page 2 it has to have a lower rank than page 1 in 2 out of 3 of the search engines. The probability of this is $\frac{x}{n}$. I don't know if n should be 3 or 5? That's my first major problem!