概率论与数理统计 (Spring 2023)

概率论与数理统计
Probability Theory
& Mathematical Statistics

Instructor
尹一通
Email	yinyt@nju.edu.cn
office	计算机系 804
刘景铖
Email	liu@nju.edu.cn
office	计算机系 516
Class
Class meeting	Wednesday, 2pm-4pm Friday (双), 2pm-4pm 仙II-403
Office hour	Thursday, 2pm-4pm 计算机系 804（尹一通） 计算机系 516（刘景铖）
Textbook
概率导论（第2版·修订版） Dimitri P. Bertsekas and John N. Tsitsiklis 郑忠国 童行伟 译；人民邮电出版社 (2022)
Probability and Random Processes (4E) Geoffrey Grimmett and David Stirzaker Oxford University Press (2020)
Probability and Computing (2E) Michael Mitzenmacher and Eli Upfal Cambridge University Press (2017)

This is the webpage for the Probability Theory and Mathematical Statistics (概率论与数理统计) class of Spring 2023. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

• 6月14日周三晚6点30分开始，线上习题课。#腾讯会议：598-944-8767

Course info

• Instructor :

• 尹一通：<yinyt@nju.edu.cn>，计算机系 804
• 刘景铖：<liu@nju.edu.cn>，计算机系 516

• Teaching assistant:
  • 张昕渊：<zhangxy@smail.nju.edu.cn>，计算机系 410
  • 邹宗瑞：<zou.zongrui@smail.nju.edu.cn>，计算机系 410
• Class meeting: 每周三, 双周五, 2pm-4pm，仙II-403
• Office hour: 周四, 2pm-4pm, 计算机系 804（尹一通）, 计算机系 516（刘景铖）

• QQ群: 598724033（申请加入需提供姓名、院系、学号）

Syllabus

课程内容分为三大部分：

• 经典概率论：概率空间、随机变量及其数字特征、多维与连续随机变量、极限定理等内容
• 概率与计算：测度集中现象 (concentration of measure)、概率法 (the probabilistic method)、离散随机过程的相关专题
• 数理统计：参数估计、假设检验、贝叶斯估计、线性回归等统计推断等概念

对于第一和第二部分，要求清楚掌握基本概念，深刻理解关键的现象与规律以及背后的原理，并可以灵活运用所学方法求解相关问题。对于第三部分，要求熟悉数理统计的若干基本概念，以及典型的统计模型和统计推断问题。

经过本课程的训练，力求使学生能够熟悉掌握概率的语言，并会利用概率思维来理解客观世界并对其建模，以及驾驭概率的数学工具来分析和求解专业问题。

教材与参考书 Course Materials

• [BT] 概率导论（第2版·修订版），[美]伯特瑟卡斯（Dimitri P.Bertsekas）[美]齐齐克利斯（John N.Tsitsiklis）著，郑忠国 童行伟 译，人民邮电出版社（2022）。
• [GS] Probability and Random Processes, by Geoffrey Grimmett and David Stirzaker; Oxford University Press; 4th edition (2020).
• [MU] Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Michael Mitzenmacher, Eli Upfal; Cambridge University Press; 2nd edition (2017).

成绩 Grading Policy

• 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
• 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

学术诚信 Academic Integrity

学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

Assignments

• Problem Set 1 请在 2023/3/1522 上课之前(14:00 UTC+8)提交到 pr2023_nju@163.com (文件名为'学号_姓名_A1.pdf').
  • 第一次作业提交名单
• Problem Set 2 请在 2023/4/1219 上课之前(14:00 UTC+8)提交到 pr2023_nju@163.com (文件名为'学号_姓名_A2.pdf').
  • 第二次作业提交名单
• Problem Set 3 请在 2023/5/10 上课之前(14:00 UTC+8)提交到 pr2023_nju@163.com (文件名为'学号_姓名_A3.pdf').
  • 第三次作业提交名单
• Problem Set 4 请在 2023/6/714 (14:00 UTC+8)之前提交到 pr2023_nju@163.com (文件名为'学号_姓名_A4.pdf').
  • 第四次作业提交名单

Lectures

1. 课程简介
2. 概率空间
   • 阅读：[BT] 第1章 或 [GS] Chapter 1
   • Example for chain rule: Karger's min-cut algorithm
   • Example for total probability: Polynomial identity testing
3. 随机变量
   • 阅读：[BT] 第2章 或 [GS] Chapter 2, Sections 3.1~3.5, 3.7
   • 阅读：[MU] Chapter 2
   • the Mathematica notebook file for the PMFs of basic discrete distributions
   • 高尔顿板（Galton board）视频 和 维基百科页面
   • Average-case analysis of QuickSort
4. 矩与偏差
   • 阅读：[MU] Chapter 3
   • 阅读：[BT] 章节 2.4, 4.2, 4.3, 5.1 或 [GS] Sections 3.3, 3.6, 7.3
   • Two-point sampling
   • Threshold of [math]\displaystyle{ k }[/math]-clique in random graph
   • Weierstrass approximation
5. 连续分布
   • 阅读：[BT] 第3章, 和4.1节 或 [GS] Chapter 4
   • 阅读：[MU] Chapters 8, 9
   • Measure, Integration & Real Analysis by Sheldon Axler
6. 极限定理
   • 阅读：[BT] 第5章
   • 阅读：[GS] Sections 5.7~5.10, 7.1~7.5
7. 测度集中
   • 阅读：[MU] Chapters 4 and Sections 13.1, 13.4~13.5
   • 阅读：[GS] Sections 5.11, 12.1~12.3, 7.8~7.9
   • Hoeffding's lemma
   • Entropy and volume of Hamming balls
8. 随机过程
   • 阅读：[BT] 第6章, 第7章
   • 阅读：[MU] Chapters 7, Sections 13.1~13.3 or [GS] Chapters 6, Sections 12.4~12.5
   • OST and applications
9. 统计与贝叶斯推断, 经典统计推断
   • 阅读：[BT] 第8章, 第9章

Concepts

• Interpretations of probability
• History of probability
• Example problems:
  • von Neumann's Bernoulli factory and other Bernoulli factory algorithms
  • Boy or Girl paradox
  • Monty Hall problem
  • Bertrand paradox
  • Hard spheres model and Ising model
  • PageRank and stationary random walk
  • DALL-E 2 and diffusion model
• Probability space
  • Sample space
  • Event and [math]\displaystyle{ \sigma }[/math]-algebra
  • Kolmogorov's axioms of probability
• Classical and goemetric probability
• Union bound
  • Inclusion-Exclusion principle
  • Bonferroni inequalities
• Conditional probability
  • Chain rule
  • Law of total probability
  • Bayes' law
• Independence
  • Pairwise independence
• Random variable
  • Cumulative distribution function
  • Probability mass function
  • Probability density function
• Random vector
  • Joint probability distribution
  • Conditional probability distribution
  • Marginal distribution
• Some discrete probability distributions
  • Bernoulli trial and Bernoulli distribution
  • Discrete uniform distribution
  • Binomial distribution
  • Geometric distribution
  • Negative binomial distribution
  • Hypergeometric distribution
  • Poisson distribution
  • and others
• Balls into bins model
  • Multinomial distribution
  • Birthday problem
  • Coupon collector
  • Occupancy problem
• Random graphs
  • Erdős–Rényi random graph model
  • Galton–Watson branching process
• Expectation
  • Law of the unconscious statistician, LOTUS
  • Linearity of expectation
  • Conditional expectation
  • Law of total expectation
• Markov's inequality
• Chebyshev's inequality
• Moment related
  • Central moment
  • Variance
  • Standard deviation
  • Covariance
  • Correlation
  • Correlation does not imply causation
  • Skewness
  • Kurtosis
• Probability density function
  • Continuous probability distribution
  • Conditional continuous distributions
  • Convolution of probability distributions and List of convolutions of probability distributions
• Measure
  • Borel set
  • Lebesgue integration
  • Measurable function
  • Cantor set
  • Non-measurable set
• Some continuous probability distributions
  • Continuous uniform distribution
  • Exponential distribution and Poisson point process
  • Normal (Gaussion) distribution
    • Gaussian function and Gaussian integral
    • Standard normal table
    • 68–95–99.7 rule
    • Sum of normally distributed random variables
    • Multivariate normal distribution
  • Chi-squared distribution
  • Gamma distribution and Gamma function
  • Beta distribution and Beta function
  • Cauchy distribution
  • and others
• Inverse transform sampling
• Stochastic dominance and Coupling
• Moment-generating function
• Convergence of random variables
  • Pointwise convergence
  • Weak convergence of measures
  • Convergence in measure
  • Skorokhod's representation theorem
  • Continuous mapping theorem
• Borel–Cantelli lemma and zero-one laws
• Law of large numbers
• Central limit theorem
  • De Moivre–Laplace theorem
  • Berry–Esseen theorem
• Characteristic function
  • Lévy's continuity theorem
• Concentration of measures:
  • Moment-generating function
  • Chernoff bound
  • Hoeffding's bound
  • McDiarmid's inequality
  • Doob martingale and Azuma's inequality
  • Sub-Gaussian distribution
• Stochastic process
• Stopping time
• Martingale
  • Optional stopping theorem
• Wald's equation
• Markov chain
  • Markov property and memorylessness
  • Stochastic matrix
  • Stationary distribution