Course Content
1. Basics Chernoff, Hoeffding, Efron-Stein inequalities 2. Martingale Inequalities Doobs martingale, bounded difference and bounded variance methods (Azuma-Hoeffding, McDiarmids inequalities) 3. Isoperimetric inequality - Talagrands inequality for Hamming distance 9. 4. Logarithmic Sobolev Inequality 5. Markov Chains on Graphs Reversible Discrete-Time Markov Chains, Eigenvalues and conductance 6. Rumours and Epidemics First passage percolation
Text / References
- 1 Book: Authors (Initials & Last name), Title, Edition (Optional), Publisher, Year.Journal Articles: Authors (Initials & Last name), Title, Journal name, Volume, Page nos., Year. Web References:Authors/Organization, Title, Year (if available), URL.)Williams, David. Probability with martingales. Cambridge university press, 1991.
- 2 Williams, David. Probability with martingales. Cambridge university press, 1991.
- 3 Concentration of Measure for the Analysis of Randomized Algorithms, D. Dubhashi andA. Panconesi, Cambridge University Press, 20093. Epidemics and Rumors in Complex Networks, M. Draief and L. Massoulie, CambridgeUniversity Press, 20104. Concentration inequalities: A nonasymptotic theory of independence, Boucheron,St303251phane, G303241bor Lugosi, and Pascal Massart.. Oxford university press, 2013.
- 4 Concentration of measure for the analysis of randomized algorithms , Dubhashi, Devdatt P.,and Alessandro Panconesi, Cambridge University Press, 2.