Concentration Inequalities [MA601398]
Sommersemester 2017
Prof. Dr. Robert König
News
List of topics and suggested references
 Probability theory refresher: Almost sure convergence, convergence in probability, convergence in distribution. Markov's inequality, Chebyshev's inequality, Strong Law of Large Numbers, Central Limit Theorem. Lévy's equivalence theorem for sums of independent real random variables.
 Sums of independent random variables: Hoeffding's inequality, Chernoff's inequality, comparison to the central limit theorem, application: concentration of degrees of random dense graphs. [7, Chap. 2.3, Chap. 2.4] (Vincent Steffan)
 SubGaussian random variables: Bernstein's inequality, application to JohnsonLindenstrass Lemma [7, Chap. 2.8], [2, Chap. 2.3, Chap. 2.8, Chap 2.9] (Alexander Marx)
 Isoperimetry and concentration in R^{d}: Concentration of Lipschitz functions, concentration functions and Lévy's inequalities, BrunnMinkowski inequality and the classical isoperimetric theorem. [2, Chap. 1.2, Chap. 7.1, Chap. 7.2] (Vincent Steffan)
 Application of Gaussian isoperimetry: Statement of the Gaussian isoperimetric theorem, concentration function for Gaussian distribution, isoperimetric problem on S^{d1}. Gaussian concentration, Lipschitz functions of Gaussian random variables.[2, Chap. 10.4, 10.5] (Alexander Marx)
 Proof of the Gaussian isoperimetric theorem: Bobkov's inequality on the hypercube, Bobkov's Gaussian inequality and proof of the Gaussian isoperimetric theorem [1], [2, Chap. 10.1, 10.4].
 Decoding for the additive white Gaussian noise channel: Definition of a code, code distance, maximum likelihood decoding, error probability. Additive white Gaussian noise channel and bounds on the decoding probability [3, Chap. 10], [6].
Literature

 1
 S. Bobkhov, An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space, Ann. Probab. vol. 25, No. 1, 206214 (1997)
 2
 S. Boucheron G. Lugosi and P. Massart, Concentration inequalities, Oxford University Press (2013).
 3
 T. Cover and J. Thomas, Elements of Information Theory, Wiley, Oxford University Press (2001).
 4
 M. Ledoux, The concentration of measure phenomenon, AMS Monographs, Providence (2001).
 5
 M. Talagrand, A new look at independence, Ann. Probab. 24, 134 (1996)
 6
 J.P. Tillich and G. Zémor, The Gaussian Isoperimetric Inequality and Decoding Error Probabilities for the Gaussian Channel, IEEE Transactions on Information Theory, vol. 50, no. 2, 328331 (2004)
 7
 R. Vershynin, High dimensional probability, textbook/course notes MATH 626, University of Michigan, 2016