10 - Real-World Examples: Google, Aloha, and Harder Chains

Summary

This chapter discusses applications of DTMCs in the real world. Section 10.1 describes Google's PageRank algorithm, and Section 10.2 analyzes the Aloha Ethernet protocol. Both problems are presented from the perspective of open-ended research problems, so that they serve as a lesson in modeling. Both are also good examples of ergodicity issues that come up in real-world problems. Finally, in Section 10.3, we consider DTMCs that arise frequently in practice but for which it is difficult to “guess a solution” for the limiting probabilities. We illustrate how generating functions can be used to find the solution for such chains.

Google's PageRank Algorithm

Google's DTMC Algorithm

Most of you probably cannot remember a search engine before google.com. When Google came on the scene, it quickly wiped out all prior search engines. The feature that makes Google so good is not the web pages that it finds, but the order in which it ranks them.

Consider a search on some term; for example, “koala bears.” Thousands of web pages include the phrase “koala bears,” ranging from the San Diego zoo koala bear home page, to anecdotes on the mating preferences of Australian lesbian koala bears, to a koala bear chair. The value of a good search engine is to rank these pages so that the page we need will most likely fall within the “top 10,” thus enabling us to quickly find our information. Of course, how can a search engine know exactly which of the thousand pages will be most relevant to us?