This year we will focus on measure theory -- as a background for probability. Also on geometry in high dimensions and a bit of functional analysis.
| Date | Topic | Literature |
|---|---|---|
| 18. 2. | [IK] Motivation for why we need the notion of Lebesgue measure (i.e., a generalization of the length of an interval to more general sets): integrating more exotic functions, probability. Four natural properties that we would like this measure to satisfy (it is defined on all subsets of reals, for intervals it agrees with their length, it is translation invariant and countably additive) . Definition of outer Lebesgue measure and proof that it has three-and-half of the four properties: instead of countable additivity, we could prove only countable subadditivity. Sadly, there is a counterexample to countable additivity: the Vitali set. And tragically, it can be proved our whole task is hopeless: that no set function on \(\mathbb{R}\) satisfies all 4 properties. We give up on the first property, define (Lebesgue) measurable sets and restrict the outer measure to this family. Definition of \(\sigma\)-algebra and mentioned that measurable sets form a \(\sigma\)-algebra (proof left as an exercise). Definition of smallest \(\sigma\)-algebra generated by a set. Borel sets. Mentioned that Borel sets are measurable (proof left as an exercise). | [KMS], Chapter 1 |
| 25.2. | [IK] Proof of countable additivity for the Lebesgue measure. Terminology: null set, almost everywhere. Higher dimensional Lebesgue measure. General definition of measure and of measure space. Examples: counting measure, Dirac measure. Generalized definition of partition of a set. Simple function, integral of simple function. Integral of nonnegative function. A particular approximation of a nonnegative function by a simple function (as a motivation for why we only want to define integrals for measurable functions). Measurable functions, integral of a measurable function. Integrable functions. Lemma (without proof): for a bounded function f defined on a set of finite measure, supremum of the integrals of lower approximations by simple functions equals infimum of the integrals of upper approximations by simple functions, if and only if f is measurable. | [KMS], Chapter 1 |
| 4.3. | [IK] Measurable functions defined on general measure spaces (with codomain being the real line). In this context: simple functions, integral. Properties of integral. Complete measure spaces (and why we like them). Fatou's lemma. Monotone convergence theorem. Linearity of integral. Littlewood principles: mentioned informally. | [KMS], Chapter 1 |
| 11. 3. | [IK] Dominated convergence theorem. Product of measure spaces. Sigma-finite measure spaces. Fubini theorem, Tonelli theorem. Definition of probability space. Observation that the axioms are the same as for measure space, with the added requirement that probability of the whole set is 1. Motivation for the notion of density. In general, if we have a nonnegative measurable function f defined on a measure space, we may use it as "density" to define a new measure. This way, we get, e.g., the Gaussian measure from the Lebesgue measure. Motivation and definition of expected value. Normal distribution, computation of the constant of the density function. | [KMS], Chapter 2.3 |
| ... | [RŠ] | ... |
| 22.4. | [MT] High-dimensional geometry. Brief motivation (image recognition, mathcing polytope, ellipsoid method). High-dimensional paradoxes ("small" ball enclosed by other balls, not-so-good random sampling, neighborhood of the equator of a high-dimensional sphere). Unidomdular function, Brunn's theorem. The Brunn-Minkowski inequaliy. Proof that the Brunn-Minkowski inequality implies Brunn's theorem. Isoperimetric problem and its solution via the Brunn-Minkowski inequality. Lemma (Brunn-Minkowski on the line). A dimension-free Brunn-Minkowski inequality and the proof that it implies the standard Brunn-Minkowski inequality. | [KMS], Chapters 2.1, 2.2. |
| 29.4. | [MT] Prékopa--Leindler inequality (as a generalization of a dimesion-free Brunn-Minkowski) and its proof. Measure concentration: Measure concentration on the sphere. Other spaces with measure concentration (Gaussian measure in $\mathbb{R}^d$; Hamming cube, permutations, constant degree expanders.) A sketch of the proof of measure concentration on the sphere (the first step is the isoperimetric inequality on the sphere---it has not been sketched how to get it; the second step is to bound the measure of a neighborhood of a hemisphere---this has been explained). | [KMS], Chapters 2.2, 2.4 |
| 6.5. | [MT] Lipschitz functions (definition and two examples). Theorem: Concentration of Lipschitz functions on the sphere (proof via measure concentration on the sphere). Gromov's sphere waist theorem (without proof). Martingales: motivation, definition, a vertex exposure martingale. Azuma's inequality (without proof) and its corollary. An application of Azuma's inequality: Concentration of the chromatic number in the random graph $G(n,p)$ (proof sketched). Higher-dimensional Gaussian measure (via formula as well as via a vector of independent random variables with the standard normal distribution). An application of the Gaussian measure: generating a random point on the sphere. Lemma regarding Gaussian projection (proof sketched). Remarks on normal distribution (not necessarily standard normal). | [KMS], Chapters 2.3, 2.4; [AS], Chapters 7.1, 7.2 (according to the 4th edition). |
| 20.5. | [MT] The Johnson-Lindenstrauss flattening lemma: motivation, statement, a minor application on storing distances between points. Towards the proof: Concentration of $n$-dimensional Gaussian measure in a spherical shell with radius roughly $\sqrt n$. Random projection and a Gaussian random projection lemma. The Johnson-Lindenstrauss lemma is then a quite straighforward consequence. | [KMS], Chapter 2.5. |