189-671A Applied Stochastic Processes- Winter 08


Lecture 1. An Introduction to Stochastic Processes

Lecture 2. Random Walks 1, Reflection and Reversal.

Lecture 3. Random Walks 2, Differential Equations and Generating Functions.

Lecture 4. Random Walks 3, More on Generating Functions.

Lecture 5. Random Walks 4, Coupling and Concentration.

Lectures 6 and 7: Moment Generating Functions, Characteristic Functions, and proving some Concentration Results.

Lecture 8. Percolation I

Lecture 9. Markov Chains I: Definitions and The State Space Decomposition.

Lecture 10 Markov Chains II: Stationary and Limit Distributions

Lecture 11 Markov Chains III: Limit Distributions in Finite Chains

Lecture 12. Percolation II We considered the proof in Section 4 of this paper that as d goes to infinity, the critical probability of the $d$-dimensional integer lattice goes to 1/2d-1.

Midterm: To be held in Class on February 21 2008.

Lecture 13. A Lower Bound on the Mixing Time

Lecture 14. The Monte Carlo Markov Chain Method

Lecture 15. An Upper Bound on the Mixing Time

Lectures 16. and 17 Percolation III and IV: We proved that $p_H={1 \over 2}$ for the two dimensional integer lattice modulo an inequality due to Friedgut and Kalai. See pages 36-70 of Bollobas and Riordan handed out in class.

Lectures 18: First Passage Percolation We discussed the expected height of a random binary search tree and how it relates to first passage percolation on trees. This Paper contains the details of the proof you are responsible for which was presented slightly differently in class. We also discussed further results which can be found here . The sharpest result is here.

Lectures 19: The mixing time of Gnp

Lectures 20,21,23,24: Renewal Theory for General Random Variables

Lecture 22: Edge Isoperimetric Inequalities and the Friedgut-Kalai Inequality