Martingales and Conditional Expectation

MATH 6221

Spring 2013

Skiles 169

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


Will Perkins

Office: Skiles 017

  • 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?