# Martingales and Conditional Expectation

### Spring 2013

#### T / Th, 4:35 - 5:55 pm

Instructor

Will Perkins

wperkins3@math.gatech.edu

Office: Skiles 017

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:
1. General Definition of Conditional Expectation
2. Existence and Uniqueness of Conditional Expectation
3. Properties of Conditional Expectation
4. Filtration
5. Martingale
6. Upcrossing Inequality
7. Almost-sure Martingale Convergence Theorem
8. Azuma's Inequality
9. Isoperimetric Inequality for the Hamming Cube
10. Edge and Vertex exposure filtrations for a random graph
• Sample Questions:
1. Give an example of a Martingale that converges almost surely but not in L_1.
2. 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?
3. Prove that a Doob's Martingale, X_n = E [ X | F_n] converges almost surely to X.
4. 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.
5. 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] ?
6. 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?