The celebrated
"probabilistic method" with its major applications in convex and
discrete geometry and analysis will be the content of this course.
The first main highlight of the course is the concentration of measure
phenomenon, one of the powerful tools in modern probability. Its
isoperimetric proof relies on Brunn-Minkowski inequality, which will
bring us to the basics of convex geometry. The main text for this part
will be a recent book by Ledoux, "The concentration of measure
phenomenon".
At the same time, the study of the probabilistic nature of the
concentration of measure phenomenon will lead us to deviation
inequalities for sums of independent random variables and random
processes, a classical theme in probability theory. We will start with
basics, such as Chernoff and Azuma inequalities and will proceed to an
extremely powerful but simple Talagrand's inequality and will touch
upon gaussian processes. Main texts are a famous book by Alon and
Spencer, "The probabilistic method" and a monograph by Talagrand,
"Probability in Banach spaces".
The course will cumulate in phenomena of large dimensions, which are
further manifestations of the probabilistic method. A randomized
algorithm for dimension reduction (Johnson-Lindenstrauss flattening
lemma), widely used in theory and practice, will be discussed. If time
permits, we will complete the course by an existence theorem of
approximately round sections of any convex body (Dvoretzky's theorem),
which is a deep application of the probabilistic method: the section is
random. The primary text for this part is a recent book by Matousek,
"Lectures on discrete geometry".
Prerequisites: MAT 127, 131, or their equivalents, or consent
of the
instructor.
Texts (optional):
- Course plan for the first part,
"concentration of measure".
- K.
Ball, An Elementary Introduction to Modern Convex Geometry,
Flavors of geometry, 1--58,
MSRI Publ. 31, Cambridge Univ. Press, Cambridge, 1997
- M. Ledoux, The concentration of measure phenomenon. American
Mathematical Society, Providence, RI, 2001
- M. Ledoux, M. Talagrand, Probability in Banach spaces.
Isoperimetry and processes, Springer-Verlag, Berlin,
1991
- J. Matousek, Lectures on discrete geometry.
Graduate Texts in Mathematics, 212. Springer-Verlag, New York,
2002
I may also hand out some notes and announce some papers.
Grading:
Every registered student will present some topic or paper in
class. Joint presentations are welcome. A list of available papers and
topics will be discussed in class.
Possible presentations: (you
may suggest yours!)
- Introduction to martingales.
Concentration of measure on the Boolean cube. Source: p.67 of
Ledoux's book. Same method can be found in Section 7.2 of [Alon,
Spencer, Probabilistic method]
- Introduction to the
transportation of measure. [K.Ball,
An elementary introduction to monotone transportation]
- Applications of the
transportation of measure to Brunn-Minkowski inequality and Gaussian
concentration. [K.Ball,
An elementary introduction to monotone transportation]
- Volume Ratio. Random sections of cross-polytope. Source: either [K.Ball,
An elementary introduction to modern convex geometry] or [G.Pisier,
The volume of convex bodies and Banach space geometry]
- Introduction to the notion of entropy. Perhaps Poincare and
Log-Sobolev inequalities. Source: Ledoux's book and more.
Tentative
Schedule of Presentations
November 15, 17
|
Damien Pitman |
Martingales. Concentration on
the discrete cube. [Ledoux 4.1]
|
November 22, 24
|
Huawei Jiang |
Transportation of measure.
[K.Ball]
|
November 29
|
Igor Rumanov
|
An introduction to entropy
|
| December 1 |
Ram Puri |
Entropy,
spectrum, logarithmic Sobolev inequalities and concentration
|
December 6
|
Shimpei Baba |
Volume
ratio
|
Web: http://www.math.ucdavis.edu/~vershynin/teaching/280-2004/course.html