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