Topics

- Sections: 7.7 - 7.9
- Notes: Martingales and Conditional Expectation, Almost Sure Martingale Convergence, Azuma's Inequality
- Homework Problems: HW 5: 7,8 HW 6: 1-6
- Definitions and Theorems:
- General Definition of Conditional Expectation
- Existence and Uniqueness of Conditional Expectation
- Properties of Conditional Expectation
- Filtration
- Martingale
- Upcrossing Inequality
- Almost-sure Martingale Convergence Theorem
- Azuma's Inequality
- Isoperimetric Inequality for the Hamming Cube
- Edge and Vertex exposure filtrations for a random graph

- Sample Questions:
- Give an example of a Martingale that converges almost surely but not in L_1.
- The Urn Problem: start with one red ball and one green. At each step pick a ball at random, and return it along with an additional ball of the same color. Let X_n be the proportion of red balls. To what and in what sense does X_n converge?
- Prove that a Doob's Martingale, X_n = E [ X | F_n] converges almost surely to X.
- Prove an isoperimetric inequality for S_n, the space of permutations on n elements, with the distance function defined by the number of elements sent to different places by two permutations.
- Consider a random graph with the vertex exposure filtration. Let X be the number of triangles in the graph G(n,p). What is E[ X| F_3] ?
- Use Azuma's inequality to prove a concentration result for the number of triangles in a random graph. Compare this to the concentration you would get from Chebyshev's inequality. Which is better?