EE 6112: Topics in Random Processes and Concentrations

July-November 2016

Instructor: Krishna Jagannathan, Assistant Professor

Slot: G

Classroom: ESB 207B

Prerequisite: EE 5110

 

This is an advanced graduate course, dealing predominantly with martingale techniques and concentration of probability measures, along with a few allied topics of interest in probability theory. Martingale and measure concentration techniques are becoming increasingly popular in various active areas of research, such as machine learning, resource allocation, complex networks, information theory and coding theory. It is hoped that this course would equip the students with the requisite familiarity and conceptual grasp to tackle various contemporary analysis and proof techniques.

Course Contents:

1.      A nuanced look at Conditional Expectations

a.                  The Hilbert Space L2 – covariance as an inner product

b.                  Conditioning on sigma-algebras

c.                   Kolmogorov’s Existence Theorem for conditional expectation

d.                  Properties of Conditional Expectations – iterated expectations, MMSE estimator as a projection onto an L2 subspace

2.      Filtrations – sequence of sigma-algebras evolving in time

3.      Martingales

a.      Definitions, basic properties

b.      Doob’s Optional Stopping Theorem

c.       Kolmogorov Submartingale Inequality

d.      Martingale convergence theorems and applications (Polya urn, stochastic approximation, population extinction, polar codes etc.)

4.      Concentration of Measure and applications

a.                  MGF methods (Chernoff-Hoeffding, Bernstein…)

b.                  Martingale concentrations (Azuma-Hoeffding, Doob’s martingale method, median concentrations)

c.                   Logarithmic Sobolev Inequality

d.                  Talagrand’s Isoperimetric Inequality

5.      Random Walks

a.                  Random walks, hitting times, and threshold crossing probabilities, Kingman bound for a G/G/1 queue

b.                  Stopping times and Wald’s identity

6.      Exchangeability and Zero-One Laws

a.                  Exchangeable random variables, de Finetti’s theorem

b.                  Zero-One Laws (Kolmogorov and Hewitt Savage) with applications

 

Text Books:

1.      Probability with Martingales, David Williams, CUP 1991.

2.      Concentration-of-measure inequalities, Gábor Lugosi.

       References:

1.      Concentration Inequalities: A Nonasymptotic Theory of Independence by Stéphane Boucheron, Gábor Lugosi, Pascal Massart, OUP 2013.

2.      Concentration of Measure Inequalities in Information Theory, Communications and Coding by Maxim Raginsky and Igal Sason. NOW publishers Inc. 2nd Edition, 2015.

Acknowledgements:

·       This course is heavily influenced by Sanjay Shakkottai’s (UT Austin) lectures on the topic.

·       Thanks to Sharayu Moharir (IITB) for valuable inputs on contents, structure and pedagogy.