When you submit a query to a search engine, an ordered list of web pages is returned. The pages are ranked by their relevance to your query and also by the quality of the page. Consider the small network of web pages in figure 1.12. We will assume this is the set of web pages indexed by our search engine. Each vertex in the graph is a web page. A directed link is drawn from web page i to web page j if web page i has a link to web page j. So, we can see, for example, that web page 1 links to web page 4. The PageRank algorithm assumes that a surfer follows a link on a web page 85% of the time, with any of the links being equally likely. The other 15% of the time the surfer will enter the URL for another web page, possibly the same one that is currently being visited, again with all pages being equally likely. Let Xi (t) denote the probability of being at web page i after the surfer takes t steps through the network. We will assume the surfer starts at web page 1, so that X1 (0) = 1 and Xi (0) = 0 for i = 2, 3, 4, 5.

Find Xi (2) for 1 i 5.

As a measure of the quality of a page, PageRank approximates limt Xi (t) for all i.