Probability: a Graduate Course

Welcome to my course in probability theory. I am Roman Vershynin, professor of mathematics at the University of California, Irvine. This course is aimed at Ph.D. students in mathematics, statistics, computer science and related areas. An essential prerequisite for this course is measure theory.

• September 28 Lecture 1

  From measure theory to probability theory. Examples, including random permutations and the Gibbs measure.

• October 3 Lecture 2

  More examples: Buffon's needle, random graphs, random matrices, Haar measure.

• October 5 Lecture 3

  Monotonicity and continuity of probability measures. Union bound. Example of the probabilistic method: placing a sticker on a soccer ball. Inclusion-exclusion principle. Example: probability of a derangement. The distribution function of a measure on R.

• October 10 Lecture 4 Homework 1 due October 26 in class

  Random variables. The distribution of a random variable. Cumulative distribution function. Generating a random variable with a given distribution.

• October 12 Lecture 5

  Expected value. Linearity of expectation. A probabilistic proof of the sum of angles in a triangle formula. St. Petersburg paradox. The expected number of cycles in a random permutation.

• October 17 Lecture 6

  The expected length of the longest increasing subsequence of a random permutation; Erdos-Szekeres theorem and Baik-Deift-Johansson theorem mentioned. Random variables with absolutely continuous distributions. Probability density function.

• October 19 Lecture 7

  Normal distribution. Gaussian tail bounds. Variance. Variance of the number of fixed points in a random permutation. Jensen's inequality.

• October 24 Lecture 8

  Markov's and Chebyshev's inequalities. Exponential Markov inequality. Independent events. Pairwise independence. Stability of independence; Dynkin's pi-lambda theorem used.

• October 26 Lecture 9 Homework 2 due November 9 in class

  Independent random variables. Joint distributions. Expectation of the product and variance of the sum of independent random variables. Binomial distribution.

• October 31 Lecture 10

  Joint and marginal densities. Standard normal random vector. Order statistic. Examples. Finding a large cut in a graph. Balancing vectors.

• November 2 Lecture 11

  Turan's theorem on independent sets: a probabilistic proof. A random k-SAT problem. Monte-Carlo integration.

• November 7 Lecture 12

  Connectivity threshold of Erdos-Renyi random graphs.

• November 9 Lecture 13 Homework 3 due November 28 in class

  A probabilistic proof of Sperner's theorem. Littlewood-Offord-Erdos inequality. Covariance and correlation.

• November 14 Lecture 14

  Covariance matrix. Principal component analysis. Multivariate normal distribution.

• November 16 Lecture 15

  Jointly normal random variables. Kolmogorov's extension theorem.

• November 21 Lecture 16

  Infinite products of probability spaces. Infinitely many independent random variables. Explicit constructions: Rademacher functions. A general (uncountable) version of Kolmogorov's extension theorem. White noise. Lim sup and lim inf of events: occurrence "infinitely often" and "eventually". Borel-Cantelli lemma. Infinite monkey theorem.

• November 28 Lecture 17 Homework 4 due December 11; slide under my door (RH 540D)

  Applications of Borel-Cantelli lemma: maximum of gaussians; length of runs (infinite monkey II); zero-sum games with infinite winnings (Saint Petersburg paradox II); a version of Stein's covering lemma.

• November 30 Lecture 18

  Kolmogorov's zero-one law. Examples: phase transition in percolation; recurrence of a simple random walk. Sums of independent random variables; computing the density by convolution.

• December 5 Lecture 19

  Stability of normal distribution. Cauchy and other stable distributions. Binomial distribution. Weak law of large numbers. Applications: a probabilistic proof of Weierstrass approximation theorem via Bernstein polynomials.

• December 7 Lecture 20

  Applications of the weak law of large numbers continued: occupancy problems; approximate Caratheodory theorem; geometry of polyhedra in high dimensions.

• January 9 Lecture 21

  Removing the variance assumption from the weak law of large numbers: Khinchin's WLLN.

• January 11 Lecture 22

  Convergence in probability vs almost surely. A strong law of large numbers under the fourth moment assumption.

• January 16 Lecture 23

  Kolmogorov's strong law of large numbers. The necessity of the finite mean.

• January 18 Lecture 24 Homework 5 due February 1

  Applications: almost all numbers are normal; Shannon's source coding theorem.

• January 23 Lecture 25

  Glivenko-Cantelli theorem. Empirical measure and empirical cdf. Kolmogorov-Smirnov test mentioned.

• January 25 Lecture 26

  Etemadi's maximal inequality. Kolmogorov's maximal inequality. Convergence of random series: Kolmogorov's two-series theorem.

• January 30 Lecture 27

  De Moivre-Laplace central limit theorem for a simple random walk: a physical derivation using the heat equation. Weak convergence. Convergence in probability implies weak convergence. Skorokhod's almost sure representation theorem.

• February 1 Lecture 28 Homework 6 due February 15

  Portmanteau lemma. Helly's selection theorem. Tighness. Prokhorov's theorem on the existence of a weakly convergent subsequences.

• February 6 Lecture 29

  Central limit theorem for i.i.d. random variables. Proof by Lyapunov-Lindeberg replacement method and truncation.

• February 8 Lecture 30

  Characteristic functions. Levy's continuity theorem. A Fourier analytic proof of the classical central limit theorem.

• February 13 Lecture 31

  Lindeberg's central limit theorem for non-iid random variables. Example: de Moivre-Laplace theorem. Poisson distribution. Poisson limit theorem. Gaussian-Poisson dichotomy.

• February 15 Lecture 32 Homework 7 due February 29 in class

  Stein's method. Central limit theorem in Wasserstein metric. Berry-Esseen theorem mentioned.

• February 20 Lecture 33

  Central limit theorem for m-dependent random variables. Asymptotic normality of the number of triangles in an Erdos-Renyi random graph.

• February 22 Lecture 34

  Conditional probability. Law of total probability. Bayes formula. Conditional expectation. Conditioning on a sigma-algebra. Existence and uniqueness.

• February 27 Lecture 35

  Computing probabilities by conditioning. Gambler's ruin. Secretary problem. Properties of conditional expectation. Expected hitting time of a random walk. Conditional expectation as a projection.

• February 29 Lecture 36 Homework 8 due March 14 in class

  Conditioning on a random variable. Sums with random number of terms. The law of total variance. The exchange paradox.

• March 5 Lecture 37

  Conditional distributions. Conditional densities. Exponential distribution. Geometric distribution. Memoryless property. Coupon collector's problem.

• March 7 Lecture 38

  Martingales. Examples, including quadratic martingales, product martingales, de Moivre's martingale, likelihood ratio test martingale, Galton-Watson branching process, Polya's urn, and Doob martingale. Martingale differences.

• March 12 Lecture 39

  Submartingales and supermartingales. Predictable sequences. Doob's decomposition. Quadratic variation. Martingale transform. Stopping times. Stopped martingales.

• March 14 Lecture 40

  Optional stopping theorem. Applications: probability and expected time of gambler's ruin, Wald's equation, expected time and distribution of the hitting time of one point.

• Left out:

  Martingale convergence theorems.