MAT 377 University of Toronto, Fall 2021
 

MAT 377H1F Mathematical Probability, Fall 2021

Almut Burchard, Instructor

How to reach me: Almut Burchard, BA 6234, 978-3318.
almut @math , www.math.utoronto.ca/almut/
Lectures Mon 10-11 and Wed 9-10 in SS 2127; Fri 10-11 in SS 1084
Tutorial Mon 9-10 in SS 2127
If you cannot attend in person please email me
Office hours Thursdays 5-6:30, on zoom
Teaching assistant: Jack Montemurro, jack.montemurro @mail.utoronto.ca .
Textbook:   Dmitry Panchenko, Introduction to Probability Theory

Course content: Introduction to Probability Theory for Math, CS and Physics specialists. We will not dwell on definitions and standard techniques too much (which means you will have to digest them quickly), and will try to learn important ideas through examples from computer science, random graphs, statistics, geometry, and number theory.
  1. Introduction: The language of probability. Discrete probability spaces and distributions. Bernoulli, binomial, geometric, exponential, negative binomial distributions. Independence; conditional distributions.
  2. Second moment calculus: Variance and covariance; the Law of Large Numbers. Applications to Bernstein polynomials, Erdős-Rényi graphs, and the Hardy-Ramanujan theorem.
  3. Exponential inequalities: Hoeffding inequality, Johnson-Lindenstrauss lemma, Hoeffding-Chernoff inequality, Azuma inequality; applications.
  4. Gaussian distributions: Gaussian distributions on R and Rn. Central Limit Theorem. Gamma, Chi-squared, F- and Student's-t distributions. Linear regression.
  5. (time permitting) Finite State Markov chains: Definitions and basic properties. Stationary distributions and convergence; reversible Markov chains.
Homework. All exercises in the textbook are part of homework.
  • Quizzes. Once-a-week short quiz based on one homework problem will be given in the tutorials (Mondays 9-10am).
    Quizzes are marked 0, 1, 2 (20% of final mark; drop 2))
  • Two midterm tests: October 18, November 22, in-class (20% each)
  • Final assessment: Wednesday December 15, 9-12noon, in SS 2117 (40%)
  • Plus up to 5 bonus points for feedback and participation.
Attendance is expected; if you can't be at a lecture in person please follow along in the book; use my office hours for questions.
Missed term work: If you miss a quiz or midterm, please let me know ASAP what happened. A Verification of Illness or Injury is currently not required. See the University's policy on Verification of Illness or Injury.
Academic integrity statement: Consult the website Student Academic Integrity for information.

Schedule:

First lecture: September 10
Chapter 1 -- Introduction (Section 1)
F: A motivating example
Week 1 (September 13-17)
Chapter 1 -- Introduction (Sections 2-4)
M: First tutorial and quiz.
Discrete probability spaces and distributions. Expectation; change of variables    (Recording failed)
W: Random variables and distributions (Bernoulli B(p), Binomial B(n,p), geometric (p))    Recording (passcode a5BgTf8^M2)
F: Independence. Poisson distribution    Recording (passcode g.6Ww*g.Z!)
Exercises 1.1.1-1.1.5 and 1.2.1-1.2.16
Week 2 (September 20-24)
Chapter 1 -- Introduction (Sections 4-5)
M: Tutorial and quiz.
Independent random variables. Convergence of Binomial to Poisson    Recording (passcode Tdgb&^4&61)
W: Independence and conditional distributions    Recording (passcode esnR7Cb^Vr)
F: Fubini's theorem    Recording (passcode 2W*#DQp+8w)
Exercises in Sections 1.2-1.4.
Week 3 (September 27-October 1)
Chapter 1 -- Examples (Section 5)
M: Tutorial and quiz.
Method of indicators; inclusion-exclusion; random maps on {1, ..., n}    Recording (passcode &s&57AX^88)
W: Random maps from {1, .. n} to {1, ..., n}; random permutations    Recording (passcode b?kD!w23Fz)
F: Chebychev (Markov) inequality    Recording (passcode BCpG=05gY@)
Exercises in Sections 1.4-1.5
Week 4 (October 4-8)
Chapter 2 -- Second moment calculus (Sections 1-4)
M: Tutorial and quiz.
Cliques in the Erdős-Rényi graph. Variance (definition, and the classical Chebychev inequality)    Recording (passcode aju&7P^pdU)
W: Covariance and correlation. Jensen's inequality. Law of Large Numbers    Recording (passcode J9!azx4khx)
F: Bernstein polynomials.    Recording (passcode E+R!g&UcV5)
Exercises in Sections 2.1-2.3.
Week 5 (October 11-15)
Chapter 2 -- Second moment calculus (Conclusion, Sections 4-5)
M: Thanksgiving holiday
W: Cliques in the Erdős-Rényi graph, revisited    Recording (passcode rSj4!W^7a1)
F: Hardy-Ramanujan theorem    Recording (passcode ryz819#=RA)
Exercises in Sections 2.3-2.4.
Week 6 (October 18-22)
Chapter 3 -- Exponential inequalities (Sections 1 and 3)
M: Midterm 1 (9:10-11am, in class)
W: Hoeffding's inequality    Recording (passcode W0le&.N=9^)
F: Hoeffding-Chernoff inequality (start of discussion)    Recording (passcode *WG4z@FzvJ)
Exercises in Sections 2.4-2.5.
Week 7 (October 25-29)
Chapter 3 -- Exponential inequalities (Sections 2 and 4)
M: Tutorial and quiz.
Johnson-Lindenstrauss lemma (tutorial & lecture)
W: Hoeffding-Chernoff bound    Recording (passcode 8EANA^BL1!)
F: Azuma's inequality    Recording (passcode 8NvWKGweD?)
Exercises in Sections 3.1-3.3 (except Problem 3.3.6)
Week 8 (November 1-5)
Chapter 3 -- exponential inequalities (examples in Sections 3 and 5).
M: Tutorial and quiz.
Johnson-Lindenstrauss lemma; chromatic number of the Erdős-Rényi graph    Recording (passcode O8#G4c&G%A)
W: Max-cut of sparse random graph    Recording (passcode 1jq4XLS=8s)
F: Neighborhoods in the Hamming cube    Recording (passcode 3p60k*ere%)
Exercises in Sections 3.4-3.5 (and Problem 3.3.6)
Reading Week (November 8-12)
Week 9 (November 15-19)
Chapter 4 -- Gaussian distributions (Sections 1-3)
M: Tutorial and quiz.
Central Limit Theorem (statement and motivation). Continuously distributed random variables; informal discussion of countable additivity    Recording (passcode fzN3r84Yj^)
W: Gaussian distributions on R. Examples of distributions (exponential, uniform); change of variables    Recording (passcode ^m&i@61qyW)
F: Multivariate Gaussians    Recording (passcode 80kgn.3CRK)
Exercises in Sections 4.1-4.2, and Problems 4.3.1-4.3.4
Week 10 (November 22-26)
Chapter 4 -- Central Limit Theorem (Sections 3-4)
M: Midterm 2 (9:10-11am, in class)
W: Lindeberg's proof of the CLT    Recording (passcode zgP7%!K9we)
F: Lyapunov's condition. Applications of the CLT    Recording (passcode T*cjXK1w9.)
Exercises in Sections 4.3
Week 11 (November 29 - December 3)
Conclusion of Chapter 4 (sections 3 & 4). Chapter 5 -- Markov chains (Section 1)
M: Tutorial and quiz.
Gamma and Chi-squared distributions.    Recording (passcode an10cuKz@q)
W: Convolutions    Recording (passcode $EjwZqNb89)
F: Markov chains: Definition and basic properties    Recording (passcode dy1r?7!#C1)
Exercises in Sections 4.4
Week 12 (December 6-8)
Chapter 5 -- Markov chains (Sections 2-4)
M: Tutorial and quiz.
Irreducible Markov chains; periods and aperiodicity.    Recording (passcode dqp!+9.e4M)
W: Stationary distributions; Convergence theorems
R: Reversible Markov chains
Exercises in Chapter 5
Wednesday December 15, 9-12noon, in SS 2117
Final assessment    Old tests: 2020 Midterm, 2021 Midterm 1, 2021 Midterm 2, 2020 Final,
The University of Toronto is committed to accessibility. If you require accommodations for a disability, or have any accessibility concerns about the course, the classroom or course materials, please contact Accessibility Services as soon as possible: disability.services@utoronto.ca, or http://studentlife.utoronto.ca/accessibility