Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Markov Chain aggregation method

  1. Jun 22, 2012 #1
    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) = [itex]\frac{1}{n}[/itex] 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 [itex]\delta[/itex] > 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  [itex]\delta[/itex]= [itex]\frac{1}{7}[/itex] , which is the value of [itex]\delta[/itex] 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. jcsd
  3. Jun 24, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    Is this the part that you need explained?:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook