Lecture on October 29 - Yilei Chen The lecture will focus on random walk on connected graphs, with it's application on showing a log-space algorithm of s-t connectivity. To begin with I have to introduce some stationary properties (section 7.3, page 167-174), but mainly focused on the properties that will be used in random walks (with less proofs, more examples): A finite Markov chain is ergodic if and only if it is aperiodic and irreducible -> Every ergodic Markov chain has a stationary distribution that is unique -> For an undirected graph that is connected and not bipartite, the stationary distribution is blablabla The rest of the lecture will be focused on the log-space randomized algorithm for s-t connectivity (section 7.4, page 174-177, with formal proof and examples). Outline of Oct 29: - Random walk - Stationary distribution - A log-space algorithm for s-t connectivity Reading: section 7.3-7.4 from the book. Students are encouraged to check the following material in order to understand the analysis in the flavor of complexity http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf pages 22-27