In my first of two semesters of work on the subject, my first goal was to closely read and understand a small number of important treatments of the topic. These included "Markov Chains and Random Walks" from the text Randomized Algorithms (Motwani and Raghaven, 1995), and Markov Chains and Polynomial Time Algorithms (Kannan, 1994). With the background and advanced knowledge supplied therein, I proceeded with the main goal of the project: to closely read, understand, and supply the omitted proofs and solutions in Laszlo Lovász's work "Random Walks on Graphs: A Survey" (1993).

In my first semester thesis, I began with a summary of some introductory theoretical material on the subject matter. I continued by providing proofs for several assertions which Lovász leaves "to the reader'" to justify, and also solutions to some problems that he speculates would be "interesting for the reader" to solve. The areas covered included access time on paths and circuits, cover time, bounds on some of these main parameters, and the connection between Markov chains and the eigenvalues of a graph's Markov matrix. My study of Lovász's work and the field in general continued in the second semester of my thesis with a look at commute time, graph symmetry, and more eigenalgebra, and several applications of that and the previous semester's work.

Keywords:
Markov Chains, Random Walks, Randomized Algorithms

References

1. Motwani, Rajeev, and Prabhakar Raghaven. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.
2. R. Kannan. "Markov Chains and Polynomial Time Algorithms". Proceedings of the 35th Annual Symposium on Foundations of Computer Science. pp 656-671. IEEE, Los Alamitos, 1994.
3. L. Lovász."Random Walks on Graphs: A Survey". Combinatorics, Paul Erdös is Eighty, Volume II. pp 353-397. Bolyai Society for Mathematical Studies, Budapest, 1996.