Markov Chains and Random Walks

Michael Mitzenmacher, Eli UpfalCambridge 2005 · DOI · OpenAlex

Abstract

Markov chains provide a simple but powerful framework for modeling random processes. We start this chapter with the basic definitions related to Markov chains and then show how Markov chains can be used to analyze simple randomized algorithms for the 2-SAT and 3-SAT problems. Next we study the long-term behavior of Markov chains, explaining the classifications of states and conditions for convergence to a stationary distribution. We apply these techniques to analyzing simple gambling schemes and a discrete version of a Markovian queue. Of special interest is the limiting behavior of random walks on graphs. We prove bounds on the covering time of a graph and use this bound to develop a simple randomized algorithm for the s–t connectivity problem. Finally, we apply Markov chain techniques to resolve a subtle probability problem known as Parrondo's paradox.
BibTeX
@inproceedings{mitzenmacher2005markov,
  author = {Michael Mitzenmacher and Eli Upfal},
  title = {{Markov Chains and Random Walks}},
  booktitle = {Cambridge},
  year = {2005},
  doi = {10.1017/cbo9780511813603.008},
}

Loading related content...

Figure