# Markov Chain aggregation method

1. Jun 22, 2012

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−Ʃj≠i P(i, j). Under certain conditions, this process has a unique (up to scalar multiples) limiting distribution x that satis es 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 $\delta$ > 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  $\delta$= $\frac{1}{7}$ , which is the value of $\delta$ 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.
This paper can be found here with this specific part on page 43.

2. Jun 24, 2012

### Stephen Tashi

Is this the part that you need explained?: