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 TBA (Fridays)
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-Renyi 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 Students-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-11am).
Quizzes are marked 0, 1, 2 (20% of final mark; drop 1))
• Two midterm tests: October 18, November 22i, in-class (20% each)
• Final assessment: (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 Verofication of Illness or Injury is currently not required. See the University's policy on Verification of Illness or Injury.

## 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 (Benoulli 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 Erdő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 Erdős-Rényi graph, revisited    Recording (passcode rSj4!W^7a1)
F: Hardy-Ramanujan theorem
Exercises in Sections 2.3-2.4.
Week 6 (October 18-22)
Chapter 3 -- Exponential inequalities (Sections 1-3)
M: Midterm 1 (9:10-11am, in class)
Week 7 (October 25-29)
Chapter 3 -- Exponential inequalities (Sections 4-5)
Week 8 (November 1-5)
Chapter 4 -- Gaussian distributions (Sections 1-4)