MA3K0 High-dimensional Probability

Introductory description

N/A

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

• Probability theory background, including moment generating functions and the weak law of large numbers
• Sanov's theorem, Cramer's theorem and related large deviations theorems
• Entropy and information theory
• Concentration in discrete spaces
• Concentration in continuous spaces

Learning outcomes

By the end of the module, students should be able to:

• Know the standard ways of controlling tails of random variables and their uses
• Know the meaning and formula for Shannon entropy of discrete random variables, with some applications to coding theorems
• Be able to derive and use basic concentration inequalities for functions of discrete random variables, including Bernstein's and McDairmid's
• Be able to derive and use the Poincare inequality and exponential concentration for Lipschitz functions of high-dimensional standard Gaussian random vectors
• Know the application of Gaussian concentration to some slicing results for high-dimensional norms.
• Understand the link between high-dimensional concentration and isoperimetry for such basic examples as spheres.

Indicative reading list

We won't follow a particular book and will provide lecture notes. The course overlaps in various places with the following standard books:
[1] Grimmett and Welsh, Probability: An Introduction, 2nd Ed., Cambridge (2014)
[2] Welsh, Codes and Cryptography, Oxford (1988)
[3] Cover and Thomas, Information Theory, 2nd. Ed., Wiley (2005)
[4] Alon and Spencer, The Probabilistic Method, 2nd Ed, Wiley (2000)
[5] Matousek, Lectures on Discrete Geometry, Springer (2006)
[6] Roman Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics, (2018).

Subject specific skills

• Basic large deviations theorems such as Cramer's and Sanov's
• Introduction to entropy and information theory, and connections with large deviations
• Concentration inequalities in some discrete spaces, with applications
• Concentration inequalities for Gaussian random vectors
• Application to random slices through some families of high-dimensional norms

Transferable skills

Students will acquire key reasoning and problem solving skills which will empower them to address new problems with confidence.