BannerHauptseite TUMHauptseite LehrstuhlMathematik SchriftzugHauptseite LehrstuhlHauptseite Fakultät

Concentration Inequalities [MA601398]

Sommersemester 2017

Prof. Dr. Robert König


  • First meeting: Thursday, June 22, 10am, room 02.06.011
  • Second meeting: Thursday, July 13, 10am, room 03.12.020
  • List of topics and suggested references

    1. 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.
    2. 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)
    3. Sub-Gaussian random variables: Bernstein's inequality, application to Johnson-Lindenstrass Lemma  [7, Chap. 2.8], [2, Chap. 2.3, Chap. 2.8, Chap 2.9] (Alexander Marx)
    4. Isoperimetry and concentration in Rd: Concentration of Lipschitz functions, concentration functions and Lévy's inequalities, Brunn-Minkowski inequality and the classical isoperimetric theorem. [2, Chap. 1.2, Chap. 7.1, Chap. 7.2] (Vincent Steffan)
    5. Application of Gaussian isoperimetry: Statement of the Gaussian isoperimetric theorem, concentration function for Gaussian distribution, isoperimetric problem on Sd-1. Gaussian concentration, Lipschitz functions of Gaussian random variables.[2, Chap. 10.4, 10.5] (Alexander Marx)
    6. 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].
    7. 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].


    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, 206-214 (1997)
    S. Boucheron G. Lugosi and P. Massart, Concentration inequalities, Oxford University Press (2013).
    T. Cover and J. Thomas, Elements of Information Theory, Wiley, Oxford University Press (2001).
    M. Ledoux, The concentration of measure phenomenon, AMS Monographs, Providence (2001).
    M. Talagrand, A new look at independence, Ann. Probab. 24, 1-34 (1996)
    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, 328-331 (2004)
    R. Vershynin, High dimensional probability, textbook/course notes MATH 626, University of Michigan, 2016