TCS Wiki - User contributions [en]

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

2026-04-23T08:47:16Z

Zhe: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = '''概率论与数理统计''' 
'''Probability Theory''' & '''Mathematical Statistics'''
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4 = office
|data4 = 计算机系 804
|header5 =
|label5 =
|data5 = '''刘景铖'''
|header6 =
|label6 = Email
|data6 = liu@nju.edu.cn
|header7 =
|label7 = office
|data7 = 计算机系 516
|header8 = Class
|label8 =
|data8 =
|header9 =
|label9 = Class meeting
|data9 = Wednesday, 9am-12am 
仙Ⅱ-212
|header10=
|label10 = Office hour
|data10 = TBA 计算机系 804（尹一通） 计算机系 516（刘景铖）
|header11= Textbook
|label11 =
|data11 =
|header12=
|label12 =
|data12 = [[File:概率导论.jpeg|border|100px]]
|header13=
|label13 =
|data13 = '''概率导论'''（第2版·修订版） Dimitri P. Bertsekas and John N. Tsitsiklis 郑忠国童行伟译；人民邮电出版社 (2022)
|header14=
|label14 =
|data14 = [[File:Grimmett_probability.jpg|border|100px]]
|header15=
|label15 =
|data15 = '''Probability and Random Processes''' (4E) Geoffrey Grimmett and David Stirzaker Oxford University Press (2020)
|header16=
|label16 =
|data16 = [[File:Probability_and_Computing_2ed.jpg|border|100px]]
|header17=
|label17 =
|data17 = '''Probability and Computing''' (2E) Michael Mitzenmacher and Eli Upfal Cambridge University Press (2017)
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* TBA

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching assistant''':
** 鞠哲：[mailto:juzhe@smail.nju.edu.cn <juzhe@smail.nju.edu.cn>]，计算机系 426
** 祝永祺：[mailto:652025330045@smail.nju.edu.cn <652025330045@smail.nju.edu.cn>]，计算机系 426
* '''Class meeting''':
** 周三：9am-12am，仙Ⅱ-212
* '''Office hour''':
:* TBA, 计算机系 804（尹一通）
:* TBA, 计算机系 516（刘景铖）
:* '''QQ群''': 1090092561（申请加入需提供姓名、院系、学号）

= 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）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

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

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

= Assignments =
*[[概率论与数理统计 (Spring 2026)/Problem Set 1|Problem Set 1]] 请在 2026/4/1 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A1.pdf').
** [[概率论与数理统计 (Spring 2026)/第一次作业提交名单|第一次作业提交名单]]

*[[概率论与数理统计 (Spring 2026)/Problem Set 2|Problem Set 2]] 请在 2026/4/22 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A2.pdf').
** [[概率论与数理统计 (Spring 2026)/第二次作业提交名单|第二次作业提交名单]]

*[[概率论与数理统计 (Spring 2026)/Problem Set 3|Problem Set 3]] 请在 TBA 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A3.pdf').

= Lectures =
# [http://tcs.nju.edu.cn/slides/prob2026/Intro.pdf 课程简介]
# [http://tcs.nju.edu.cn/slides/prob2026/ProbSpace.pdf 概率空间]
#* 阅读：'''[BT] 第1章''' 或 '''[GS] Chapter 1'''
#* [[概率论与数理统计 (Spring 2026)/Entropy and volume of Hamming balls|Entropy and volume of Hamming balls]]
#* [[概率论与数理统计 (Spring 2026)/Karger's min-cut algorithm| Karger's min-cut algorithm]]
# [http://tcs.nju.edu.cn/slides/prob2026/RandVar.pdf 随机变量]
#* 阅读：'''[BT] 第2章''' 或 '''[GS] Chapter 2, Sections 3.1~3.5, 3.7'''
#* 阅读：'''[MU] Chapter 2'''
#* [[概率论与数理统计 (Spring 2026)/Average-case analysis of QuickSort|Average-case analysis of '''''QuickSort''''']]
# [http://tcs.nju.edu.cn/slides/prob2026/Deviation.pdf 矩与偏差]
#* 阅读：'''[MU] Chapter 3'''
#* 阅读：'''[BT] 章节 2.4, 4.2, 4.3, 5.1''' 或 '''[GS] Sections 3.3, 3.6, 7.3'''
#* [[概率论与数理统计 (Spring 2026)/Threshold of k-clique in random graph|Threshold of <math>k</math>-clique in random graph]]
#* [[概率论与数理统计 (Spring 2026)/Weierstrass Approximation Theorem|Weierstrass approximation]]

= Concepts =
* [https://plato.stanford.edu/entries/probability-interpret/ Interpretations of probability]
* [https://en.wikipedia.org/wiki/History_of_probability History of probability]
* Example problems:
** [https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf von Neumann's Bernoulli factory] and other [https://peteroupc.github.io/bernoulli.html Bernoulli factory algorithms]
** [https://en.wikipedia.org/wiki/Boy_or_Girl_paradox Boy or Girl paradox]
** [https://en.wikipedia.org/wiki/Monty_Hall_problem Monty Hall problem]
** [https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) Bertrand paradox]
** [https://en.wikipedia.org/wiki/Hard_spheres Hard spheres model] and [https://en.wikipedia.org/wiki/Ising_model Ising model]
** [https://en.wikipedia.org/wiki/PageRank ''PageRank''] and stationary [https://en.wikipedia.org/wiki/Random_walk random walk]
** [https://en.wikipedia.org/wiki/Diffusion_process Diffusion process] and [https://en.wikipedia.org/wiki/Diffusion_model diffusion model]
*[https://en.wikipedia.org/wiki/Probability_space Probability space]
** [https://en.wikipedia.org/wiki/Sample_space Sample space]
** [https://en.wikipedia.org/wiki/Event_(probability_theory) Event] and [https://en.wikipedia.org/wiki/Σ-algebra <math>\sigma</math>-algebra]
** Kolmogorov's [https://en.wikipedia.org/wiki/Probability_axioms axioms of probability]
* [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Classical] and [https://en.wikipedia.org/wiki/Geometric_probability goemetric probability]
* [https://en.wikipedia.org/wiki/Boole%27s_inequality Union bound]
** [https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Inclusion-Exclusion principle]
** [https://en.wikipedia.org/wiki/Boole%27s_inequality#Bonferroni_inequalities Bonferroni inequalities]
* [https://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
** [https://en.wikipedia.org/wiki/Chain_rule_(probability) Chain rule]
** [https://en.wikipedia.org/wiki/Law_of_total_probability Law of total probability]
** [https://en.wikipedia.org/wiki/Bayes%27_theorem Bayes' law]
* [https://en.wikipedia.org/wiki/Independence_(probability_theory) Independence]
** [https://en.wikipedia.org/wiki/Pairwise_independence Pairwise independence]
* [https://en.wikipedia.org/wiki/Random_variable Random variable]
** [https://en.wikipedia.org/wiki/Cumulative_distribution_function Cumulative distribution function]
** [https://en.wikipedia.org/wiki/Probability_mass_function Probability mass function]
** [https://en.wikipedia.org/wiki/Probability_density_function Probability density function]
* [https://en.wikipedia.org/wiki/Multivariate_random_variable Random vector]
** [https://en.wikipedia.org/wiki/Joint_probability_distribution Joint probability distribution]
** [https://en.wikipedia.org/wiki/Conditional_probability_distribution Conditional probability distribution]
** [https://en.wikipedia.org/wiki/Marginal_distribution Marginal distribution]
* Some '''discrete''' probability distributions
** [https://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trial] and [https://en.wikipedia.org/wiki/Bernoulli_distribution Bernoulli distribution]
** [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Discrete uniform distribution]
** [https://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution]
** [https://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution]
** [https://en.wikipedia.org/wiki/Negative_binomial_distribution Negative binomial distribution]
** [https://en.wikipedia.org/wiki/Hypergeometric_distribution Hypergeometric distribution]
** [https://en.wikipedia.org/wiki/Poisson_distribution Poisson distribution]
** and [https://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions others]
* Balls into bins model
** [https://en.wikipedia.org/wiki/Multinomial_distribution Multinomial distribution]
** [https://en.wikipedia.org/wiki/Birthday_problem Birthday problem]
** [https://en.wikipedia.org/wiki/Coupon_collector%27s_problem Coupon collector]
** [https://en.wikipedia.org/wiki/Balls_into_bins_problem Occupancy problem]
* Random graphs
** [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi random graph model]
** [https://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process Galton–Watson branching process]
* [https://en.wikipedia.org/wiki/Expected_value Expectation]
** [https://en.wikipedia.org/wiki/Law_of_the_unconscious_statistician Law of the unconscious statistician, ''LOTUS'']
** [https://dlsun.github.io/probability/linearity.html Linearity of expectation]
** [https://en.wikipedia.org/wiki/Conditional_expectation Conditional expectation]
** [https://en.wikipedia.org/wiki/Law_of_total_expectation Law of total expectation]

概率论与数理统计 (Spring 2026)/第二次作业提交名单

2026-04-23T08:45:53Z

Zhe: Created page with "如有错漏邮件请及时联系助教。 <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 221180155 || 许云鹏 |- | 221830067 || 张笑 |- | 221840103 || 曹南 |- | 231250084 || 谢钦煌 |- | 241098114 || 于静涵 |- | 241180041 || 赵瀚清 |- | 241220002 || 张瑞珉 |- | 241220003 || 沈琪皓 |- | 241220004 || 张宸源 |- | 241220095 || 王天祥 |- | 241220136 || 祁书轩 |- | 241240001 || 董清扬 |- | 241240004 || 陈仝 |- | 241240007 || 杨煦..."

如有错漏邮件请及时联系助教。
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221180155 || 许云鹏
|-
| 221830067 || 张笑
|-
| 221840103 || 曹南
|-
| 231250084 || 谢钦煌
|-
| 241098114 || 于静涵
|-
| 241180041 || 赵瀚清
|-
| 241220002 || 张瑞珉
|-
| 241220003 || 沈琪皓
|-
| 241220004 || 张宸源
|-
| 241220095 || 王天祥
|-
| 241220136 || 祁书轩
|-
| 241240001 || 董清扬
|-
| 241240004 || 陈仝
|-
| 241240007 || 杨煦天
|-
| 241240008 || 张恒畅
|-
| 241240017 || 江子林
|-
| 241240019 || 王祎泽
|-
| 241240022 || 潘诚懿
|-
| 241240028 || 冯时
|-
| 241240029 || 谢骐泽
|-
| 241240032 || 崔佳雪
|-
| 241240033 || 付雨彤
|-
| 241240035 || 周玟序
|-
| 241240036 || 唐愉兵
|-
| 241240038 || 胡彦腾
|-
| 241240041 || 李东泽
|-
| 241240046 || 黄嘉诚
|-
| 241240048 || 康子凯
|-
| 241240049 || 罗嘉恒
|-
| 241240050 || 李柱锃
|-
| 241240051 || 何明航
|-
| 241240053 || 张家奇
|-
| 241240061 || 周泽钰
|-
| 241240066 || 贺子铭
|-
| 241240068 || 郑飞阳
|-
| 241240069 || 陈姝婷
|-
| 241240070 || 刘梦溪
|-
| 241276007 || 胡博
|-
| 241276008 || 袁颀沣
|-
| 241820122 || 商世雄
|-
| 241840052 || 李彦均
|-
| 241840065 || 荣恒嬉
|-
| 241840067 || 赵思景
|-
| 241840078 || 张惠泽
|-
| 241840087 || 朱枻
|-
| 241840113 || 曾睿鸣
|-
| 241840173 || 刘明俊
|-
| 241840199 || 陈诣涵
|-
| 241840240 || 李味鸿
|-
| 241850002 || 张子腾
|-
| 241870025 || 张科杰
|-
| 241870032 || 赵益
|-
| 241870040 || 陆子一
|-
| 241870077 || 张辰曦
|-
| 241870097 || 丁瀚铭
|-
| 241870230 || 闵文楷
|-
| 241870240 || 杨学舟
|-
| 241880173 || 陆知渔
|-
| 241880325 || 刘孟阳
|-
| 241880488 || 扶嘉年
|-
| 241880503 || 郑一鸣
|-
| 251275003 || 翟悦凯
|}
</center>
共 62 人。

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

2026-04-14T04:10:25Z

Zhe: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = '''概率论与数理统计''' 
'''Probability Theory''' & '''Mathematical Statistics'''
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4 = office
|data4 = 计算机系 804
|header5 =
|label5 =
|data5 = '''刘景铖'''
|header6 =
|label6 = Email
|data6 = liu@nju.edu.cn
|header7 =
|label7 = office
|data7 = 计算机系 516
|header8 = Class
|label8 =
|data8 =
|header9 =
|label9 = Class meeting
|data9 = Wednesday, 9am-12am 
仙Ⅱ-212
|header10=
|label10 = Office hour
|data10 = TBA 计算机系 804（尹一通） 计算机系 516（刘景铖）
|header11= Textbook
|label11 =
|data11 =
|header12=
|label12 =
|data12 = [[File:概率导论.jpeg|border|100px]]
|header13=
|label13 =
|data13 = '''概率导论'''（第2版·修订版） Dimitri P. Bertsekas and John N. Tsitsiklis 郑忠国童行伟译；人民邮电出版社 (2022)
|header14=
|label14 =
|data14 = [[File:Grimmett_probability.jpg|border|100px]]
|header15=
|label15 =
|data15 = '''Probability and Random Processes''' (4E) Geoffrey Grimmett and David Stirzaker Oxford University Press (2020)
|header16=
|label16 =
|data16 = [[File:Probability_and_Computing_2ed.jpg|border|100px]]
|header17=
|label17 =
|data17 = '''Probability and Computing''' (2E) Michael Mitzenmacher and Eli Upfal Cambridge University Press (2017)
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* TBA

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching assistant''':
** 鞠哲：[mailto:juzhe@smail.nju.edu.cn <juzhe@smail.nju.edu.cn>]，计算机系 426
** 祝永祺：[mailto:652025330045@smail.nju.edu.cn <652025330045@smail.nju.edu.cn>]，计算机系 426
* '''Class meeting''':
** 周三：9am-12am，仙Ⅱ-212
* '''Office hour''':
:* TBA, 计算机系 804（尹一通）
:* TBA, 计算机系 516（刘景铖）
:* '''QQ群''': 1090092561（申请加入需提供姓名、院系、学号）

= 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）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

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

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

= Assignments =
*[[概率论与数理统计 (Spring 2026)/Problem Set 1|Problem Set 1]] 请在 2026/4/1 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A1.pdf').
** [[概率论与数理统计 (Spring 2026)/第一次作业提交名单|第一次作业提交名单]]

*[[概率论与数理统计 (Spring 2026)/Problem Set 2|Problem Set 2]] 请在 2026/4/22 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A2.pdf').

= Lectures =
# [http://tcs.nju.edu.cn/slides/prob2026/Intro.pdf 课程简介]
# [http://tcs.nju.edu.cn/slides/prob2026/ProbSpace.pdf 概率空间]
#* 阅读：'''[BT] 第1章''' 或 '''[GS] Chapter 1'''
#* [[概率论与数理统计 (Spring 2026)/Entropy and volume of Hamming balls|Entropy and volume of Hamming balls]]
#* [[概率论与数理统计 (Spring 2026)/Karger's min-cut algorithm| Karger's min-cut algorithm]]
# [http://tcs.nju.edu.cn/slides/prob2026/RandVar.pdf 随机变量]
#* 阅读：'''[BT] 第2章''' 或 '''[GS] Chapter 2, Sections 3.1~3.5, 3.7'''
#* 阅读：'''[MU] Chapter 2'''
#* [[概率论与数理统计 (Spring 2026)/Average-case analysis of QuickSort|Average-case analysis of '''''QuickSort''''']]

= Concepts =
* [https://plato.stanford.edu/entries/probability-interpret/ Interpretations of probability]
* [https://en.wikipedia.org/wiki/History_of_probability History of probability]
* Example problems:
** [https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf von Neumann's Bernoulli factory] and other [https://peteroupc.github.io/bernoulli.html Bernoulli factory algorithms]
** [https://en.wikipedia.org/wiki/Boy_or_Girl_paradox Boy or Girl paradox]
** [https://en.wikipedia.org/wiki/Monty_Hall_problem Monty Hall problem]
** [https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) Bertrand paradox]
** [https://en.wikipedia.org/wiki/Hard_spheres Hard spheres model] and [https://en.wikipedia.org/wiki/Ising_model Ising model]
** [https://en.wikipedia.org/wiki/PageRank ''PageRank''] and stationary [https://en.wikipedia.org/wiki/Random_walk random walk]
** [https://en.wikipedia.org/wiki/Diffusion_process Diffusion process] and [https://en.wikipedia.org/wiki/Diffusion_model diffusion model]
*[https://en.wikipedia.org/wiki/Probability_space Probability space]
** [https://en.wikipedia.org/wiki/Sample_space Sample space]
** [https://en.wikipedia.org/wiki/Event_(probability_theory) Event] and [https://en.wikipedia.org/wiki/Σ-algebra <math>\sigma</math>-algebra]
** Kolmogorov's [https://en.wikipedia.org/wiki/Probability_axioms axioms of probability]
* [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Classical] and [https://en.wikipedia.org/wiki/Geometric_probability goemetric probability]
* [https://en.wikipedia.org/wiki/Boole%27s_inequality Union bound]
** [https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Inclusion-Exclusion principle]
** [https://en.wikipedia.org/wiki/Boole%27s_inequality#Bonferroni_inequalities Bonferroni inequalities]
* [https://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
** [https://en.wikipedia.org/wiki/Chain_rule_(probability) Chain rule]
** [https://en.wikipedia.org/wiki/Law_of_total_probability Law of total probability]
** [https://en.wikipedia.org/wiki/Bayes%27_theorem Bayes' law]
* [https://en.wikipedia.org/wiki/Independence_(probability_theory) Independence]
** [https://en.wikipedia.org/wiki/Pairwise_independence Pairwise independence]
* [https://en.wikipedia.org/wiki/Random_variable Random variable]
** [https://en.wikipedia.org/wiki/Cumulative_distribution_function Cumulative distribution function]
** [https://en.wikipedia.org/wiki/Probability_mass_function Probability mass function]
** [https://en.wikipedia.org/wiki/Probability_density_function Probability density function]
* [https://en.wikipedia.org/wiki/Multivariate_random_variable Random vector]
** [https://en.wikipedia.org/wiki/Joint_probability_distribution Joint probability distribution]
** [https://en.wikipedia.org/wiki/Conditional_probability_distribution Conditional probability distribution]
** [https://en.wikipedia.org/wiki/Marginal_distribution Marginal distribution]
* Some '''discrete''' probability distributions
** [https://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trial] and [https://en.wikipedia.org/wiki/Bernoulli_distribution Bernoulli distribution]
** [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Discrete uniform distribution]
** [https://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution]
** [https://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution]
** [https://en.wikipedia.org/wiki/Negative_binomial_distribution Negative binomial distribution]
** [https://en.wikipedia.org/wiki/Hypergeometric_distribution Hypergeometric distribution]
** [https://en.wikipedia.org/wiki/Poisson_distribution Poisson distribution]
** and [https://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions others]
* Balls into bins model
** [https://en.wikipedia.org/wiki/Multinomial_distribution Multinomial distribution]
** [https://en.wikipedia.org/wiki/Birthday_problem Birthday problem]
** [https://en.wikipedia.org/wiki/Coupon_collector%27s_problem Coupon collector]
** [https://en.wikipedia.org/wiki/Balls_into_bins_problem Occupancy problem]
* Random graphs
** [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi random graph model]
** [https://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process Galton–Watson branching process]
* [https://en.wikipedia.org/wiki/Expected_value Expectation]
** [https://en.wikipedia.org/wiki/Law_of_the_unconscious_statistician Law of the unconscious statistician, ''LOTUS'']
** [https://dlsun.github.io/probability/linearity.html Linearity of expectation]
** [https://en.wikipedia.org/wiki/Conditional_expectation Conditional expectation]
** [https://en.wikipedia.org/wiki/Law_of_total_expectation Law of total expectation]

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

2026-04-08T06:11:27Z

Zhe: /* Concepts */

{{Infobox
|name = Infobox
|bodystyle =
|title = '''概率论与数理统计''' 
'''Probability Theory''' & '''Mathematical Statistics'''
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4 = office
|data4 = 计算机系 804
|header5 =
|label5 =
|data5 = '''刘景铖'''
|header6 =
|label6 = Email
|data6 = liu@nju.edu.cn
|header7 =
|label7 = office
|data7 = 计算机系 516
|header8 = Class
|label8 =
|data8 =
|header9 =
|label9 = Class meeting
|data9 = Wednesday, 9am-12am 
仙Ⅱ-212
|header10=
|label10 = Office hour
|data10 = TBA 计算机系 804（尹一通） 计算机系 516（刘景铖）
|header11= Textbook
|label11 =
|data11 =
|header12=
|label12 =
|data12 = [[File:概率导论.jpeg|border|100px]]
|header13=
|label13 =
|data13 = '''概率导论'''（第2版·修订版） Dimitri P. Bertsekas and John N. Tsitsiklis 郑忠国童行伟译；人民邮电出版社 (2022)
|header14=
|label14 =
|data14 = [[File:Grimmett_probability.jpg|border|100px]]
|header15=
|label15 =
|data15 = '''Probability and Random Processes''' (4E) Geoffrey Grimmett and David Stirzaker Oxford University Press (2020)
|header16=
|label16 =
|data16 = [[File:Probability_and_Computing_2ed.jpg|border|100px]]
|header17=
|label17 =
|data17 = '''Probability and Computing''' (2E) Michael Mitzenmacher and Eli Upfal Cambridge University Press (2017)
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* TBA

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching assistant''':
** 鞠哲：[mailto:juzhe@smail.nju.edu.cn <juzhe@smail.nju.edu.cn>]，计算机系 426
** 祝永祺：[mailto:652025330045@smail.nju.edu.cn <652025330045@smail.nju.edu.cn>]，计算机系 426
* '''Class meeting''':
** 周三：9am-12am，仙Ⅱ-212
* '''Office hour''':
:* TBA, 计算机系 804（尹一通）
:* TBA, 计算机系 516（刘景铖）
:* '''QQ群''': 1090092561（申请加入需提供姓名、院系、学号）

= 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）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

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

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

= Assignments =
*[[概率论与数理统计 (Spring 2026)/Problem Set 1|Problem Set 1]] 请在 2026/4/1 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A1.pdf').
** [[概率论与数理统计 (Spring 2026)/第一次作业提交名单|第一次作业提交名单]]

*[[概率论与数理统计 (Spring 2026)/Problem Set 2|Problem Set 2]] 请在 2026/4/TBA 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A2.pdf').

= Lectures =
# [http://tcs.nju.edu.cn/slides/prob2026/Intro.pdf 课程简介]
# [http://tcs.nju.edu.cn/slides/prob2026/ProbSpace.pdf 概率空间]
#* 阅读：'''[BT] 第1章''' 或 '''[GS] Chapter 1'''
#* [[概率论与数理统计 (Spring 2026)/Entropy and volume of Hamming balls|Entropy and volume of Hamming balls]]
#* [[概率论与数理统计 (Spring 2026)/Karger's min-cut algorithm| Karger's min-cut algorithm]]
# [http://tcs.nju.edu.cn/slides/prob2026/RandVar.pdf 随机变量]
#* 阅读：'''[BT] 第2章''' 或 '''[GS] Chapter 2, Sections 3.1~3.5, 3.7'''
#* 阅读：'''[MU] Chapter 2'''

= Concepts =
* [https://plato.stanford.edu/entries/probability-interpret/ Interpretations of probability]
* [https://en.wikipedia.org/wiki/History_of_probability History of probability]
* Example problems:
** [https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf von Neumann's Bernoulli factory] and other [https://peteroupc.github.io/bernoulli.html Bernoulli factory algorithms]
** [https://en.wikipedia.org/wiki/Boy_or_Girl_paradox Boy or Girl paradox]
** [https://en.wikipedia.org/wiki/Monty_Hall_problem Monty Hall problem]
** [https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) Bertrand paradox]
** [https://en.wikipedia.org/wiki/Hard_spheres Hard spheres model] and [https://en.wikipedia.org/wiki/Ising_model Ising model]
** [https://en.wikipedia.org/wiki/PageRank ''PageRank''] and stationary [https://en.wikipedia.org/wiki/Random_walk random walk]
** [https://en.wikipedia.org/wiki/Diffusion_process Diffusion process] and [https://en.wikipedia.org/wiki/Diffusion_model diffusion model]
*[https://en.wikipedia.org/wiki/Probability_space Probability space]
** [https://en.wikipedia.org/wiki/Sample_space Sample space]
** [https://en.wikipedia.org/wiki/Event_(probability_theory) Event] and [https://en.wikipedia.org/wiki/Σ-algebra <math>\sigma</math>-algebra]
** Kolmogorov's [https://en.wikipedia.org/wiki/Probability_axioms axioms of probability]
* [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Classical] and [https://en.wikipedia.org/wiki/Geometric_probability goemetric probability]
* [https://en.wikipedia.org/wiki/Boole%27s_inequality Union bound]
** [https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Inclusion-Exclusion principle]
** [https://en.wikipedia.org/wiki/Boole%27s_inequality#Bonferroni_inequalities Bonferroni inequalities]
* [https://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
** [https://en.wikipedia.org/wiki/Chain_rule_(probability) Chain rule]
** [https://en.wikipedia.org/wiki/Law_of_total_probability Law of total probability]
** [https://en.wikipedia.org/wiki/Bayes%27_theorem Bayes' law]
* [https://en.wikipedia.org/wiki/Independence_(probability_theory) Independence]
** [https://en.wikipedia.org/wiki/Pairwise_independence Pairwise independence]
* [https://en.wikipedia.org/wiki/Random_variable Random variable]
** [https://en.wikipedia.org/wiki/Cumulative_distribution_function Cumulative distribution function]
** [https://en.wikipedia.org/wiki/Probability_mass_function Probability mass function]
** [https://en.wikipedia.org/wiki/Probability_density_function Probability density function]
* [https://en.wikipedia.org/wiki/Multivariate_random_variable Random vector]
** [https://en.wikipedia.org/wiki/Joint_probability_distribution Joint probability distribution]
** [https://en.wikipedia.org/wiki/Conditional_probability_distribution Conditional probability distribution]
** [https://en.wikipedia.org/wiki/Marginal_distribution Marginal distribution]
* Some '''discrete''' probability distributions
** [https://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trial] and [https://en.wikipedia.org/wiki/Bernoulli_distribution Bernoulli distribution]
** [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Discrete uniform distribution]
** [https://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution]
** [https://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution]
** [https://en.wikipedia.org/wiki/Negative_binomial_distribution Negative binomial distribution]
** [https://en.wikipedia.org/wiki/Hypergeometric_distribution Hypergeometric distribution]
** [https://en.wikipedia.org/wiki/Poisson_distribution Poisson distribution]
** and [https://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions others]
* Balls into bins model
** [https://en.wikipedia.org/wiki/Multinomial_distribution Multinomial distribution]
** [https://en.wikipedia.org/wiki/Birthday_problem Birthday problem]
** [https://en.wikipedia.org/wiki/Coupon_collector%27s_problem Coupon collector]
** [https://en.wikipedia.org/wiki/Balls_into_bins_problem Occupancy problem]
* Random graphs
** [https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi random graph model]
** [https://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process Galton–Watson branching process]
* [https://en.wikipedia.org/wiki/Expected_value Expectation]
** [https://en.wikipedia.org/wiki/Law_of_the_unconscious_statistician Law of the unconscious statistician, ''LOTUS'']
** [https://dlsun.github.io/probability/linearity.html Linearity of expectation]
** [https://en.wikipedia.org/wiki/Conditional_expectation Conditional expectation]
** [https://en.wikipedia.org/wiki/Law_of_total_expectation Law of total expectation]

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

2026-04-08T01:59:38Z

Zhe: /* Assignments */

{{Infobox
|name = Infobox
|bodystyle =
|title = '''概率论与数理统计''' 
'''Probability Theory''' & '''Mathematical Statistics'''
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4 = office
|data4 = 计算机系 804
|header5 =
|label5 =
|data5 = '''刘景铖'''
|header6 =
|label6 = Email
|data6 = liu@nju.edu.cn
|header7 =
|label7 = office
|data7 = 计算机系 516
|header8 = Class
|label8 =
|data8 =
|header9 =
|label9 = Class meeting
|data9 = Wednesday, 9am-12am 
仙Ⅱ-212
|header10=
|label10 = Office hour
|data10 = TBA 计算机系 804（尹一通） 计算机系 516（刘景铖）
|header11= Textbook
|label11 =
|data11 =
|header12=
|label12 =
|data12 = [[File:概率导论.jpeg|border|100px]]
|header13=
|label13 =
|data13 = '''概率导论'''（第2版·修订版） Dimitri P. Bertsekas and John N. Tsitsiklis 郑忠国童行伟译；人民邮电出版社 (2022)
|header14=
|label14 =
|data14 = [[File:Grimmett_probability.jpg|border|100px]]
|header15=
|label15 =
|data15 = '''Probability and Random Processes''' (4E) Geoffrey Grimmett and David Stirzaker Oxford University Press (2020)
|header16=
|label16 =
|data16 = [[File:Probability_and_Computing_2ed.jpg|border|100px]]
|header17=
|label17 =
|data17 = '''Probability and Computing''' (2E) Michael Mitzenmacher and Eli Upfal Cambridge University Press (2017)
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* TBA

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching assistant''':
** 鞠哲：[mailto:juzhe@smail.nju.edu.cn <juzhe@smail.nju.edu.cn>]，计算机系 426
** 祝永祺：[mailto:652025330045@smail.nju.edu.cn <652025330045@smail.nju.edu.cn>]，计算机系 426
* '''Class meeting''':
** 周三：9am-12am，仙Ⅱ-212
* '''Office hour''':
:* TBA, 计算机系 804（尹一通）
:* TBA, 计算机系 516（刘景铖）
:* '''QQ群''': 1090092561（申请加入需提供姓名、院系、学号）

= 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）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

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

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

= Assignments =
*[[概率论与数理统计 (Spring 2026)/Problem Set 1|Problem Set 1]] 请在 2026/4/1 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A1.pdf').
** [[概率论与数理统计 (Spring 2026)/第一次作业提交名单|第一次作业提交名单]]

*[[概率论与数理统计 (Spring 2026)/Problem Set 2|Problem Set 2]] 请在 2026/4/TBA 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'学号_姓名_A2.pdf').

= Lectures =
# [http://tcs.nju.edu.cn/slides/prob2026/Intro.pdf 课程简介]
# [http://tcs.nju.edu.cn/slides/prob2026/ProbSpace.pdf 概率空间]
#* 阅读：'''[BT] 第1章''' 或 '''[GS] Chapter 1'''
#* [[概率论与数理统计 (Spring 2026)/Entropy and volume of Hamming balls|Entropy and volume of Hamming balls]]
#* [[概率论与数理统计 (Spring 2026)/Karger's min-cut algorithm| Karger's min-cut algorithm]]
# [http://tcs.nju.edu.cn/slides/prob2026/RandVar.pdf 随机变量]
#* 阅读：'''[BT] 第2章''' 或 '''[GS] Chapter 2, Sections 3.1~3.5, 3.7'''
#* 阅读：'''[MU] Chapter 2'''

= Concepts =
* [https://plato.stanford.edu/entries/probability-interpret/ Interpretations of probability]
* [https://en.wikipedia.org/wiki/History_of_probability History of probability]
* Example problems:
** [https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf von Neumann's Bernoulli factory] and other [https://peteroupc.github.io/bernoulli.html Bernoulli factory algorithms]
** [https://en.wikipedia.org/wiki/Boy_or_Girl_paradox Boy or Girl paradox]
** [https://en.wikipedia.org/wiki/Monty_Hall_problem Monty Hall problem]
** [https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) Bertrand paradox]
** [https://en.wikipedia.org/wiki/Hard_spheres Hard spheres model] and [https://en.wikipedia.org/wiki/Ising_model Ising model]
** [https://en.wikipedia.org/wiki/PageRank ''PageRank''] and stationary [https://en.wikipedia.org/wiki/Random_walk random walk]
** [https://en.wikipedia.org/wiki/Diffusion_process Diffusion process] and [https://en.wikipedia.org/wiki/Diffusion_model diffusion model]
*[https://en.wikipedia.org/wiki/Probability_space Probability space]
** [https://en.wikipedia.org/wiki/Sample_space Sample space]
** [https://en.wikipedia.org/wiki/Event_(probability_theory) Event] and [https://en.wikipedia.org/wiki/Σ-algebra <math>\sigma</math>-algebra]
** Kolmogorov's [https://en.wikipedia.org/wiki/Probability_axioms axioms of probability]
* [https://en.wikipedia.org/wiki/Discrete_uniform_distribution Classical] and [https://en.wikipedia.org/wiki/Geometric_probability goemetric probability]
* [https://en.wikipedia.org/wiki/Boole%27s_inequality Union bound]
** [https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Inclusion-Exclusion principle]
** [https://en.wikipedia.org/wiki/Boole%27s_inequality#Bonferroni_inequalities Bonferroni inequalities]
* [https://en.wikipedia.org/wiki/Conditional_probability Conditional probability]
** [https://en.wikipedia.org/wiki/Chain_rule_(probability) Chain rule]
** [https://en.wikipedia.org/wiki/Law_of_total_probability Law of total probability]
** [https://en.wikipedia.org/wiki/Bayes%27_theorem Bayes' law]
* [https://en.wikipedia.org/wiki/Independence_(probability_theory) Independence]
** [https://en.wikipedia.org/wiki/Pairwise_independence Pairwise independence]

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:58:36Z

Zhe:

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumption of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variables and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \in [N]} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third flip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolated vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probabilistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:57:12Z

Zhe: /* Problem 4 (Probability meets graph theory, 14 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumption of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variables and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \in [N]} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third flip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolated vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probabilistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:54:20Z

Zhe: /* Problem 3 (Linearity of Expectation, 10 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumption of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variables and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \in [N]} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third flip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:52:19Z

Zhe: /* Problem 1 (Warm-up problems, 14 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumption of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variables and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \in [N]} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:48:11Z

Zhe: /* Problem 1 (Warm-up problems, 14 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumption of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variables and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-08T01:41:09Z

Zhe: /* Problem 1 (Warm-up problems, 14 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], and [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variable and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-07T16:10:50Z

Zhe: /* Problem 1 (Warm-up problems, 16 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 14 points) ==
* ['''Function of random variable'''] Let [math]X[/math] be a random variable and [math]g:\mathbb{R} \to \mathbb{R}[/math] be a continuous and strictly increasing function. Show that [math]Y = g(X)[/math] is a random variable.</li>
* ['''Cumulative distribution function (CDF)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Expectation'''] Provide specific examples of a random variable <math>X</math> and a function <math>f</math> for each of the following three scenarios. For each case, clearly define the probability distribution of <math>X</math>, define the function <math>f(x)</math>, and show the calculations for both <math>\mathbf{E}[f(X)]</math> and <math>f(\mathbf{E}[X])</math>.
<ol>
<li><math>\mathbf{E}[f(X)] = f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] > f(\mathbf{E}[X])</math></li>
<li><math>\mathbf{E}[f(X)] < f(\mathbf{E}[X])</math></li>
</ol>
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.
* [Random number of random variables] Let <math>\{X_n\}_{n \ge 1}</math> be identically distributed random variable and <math>N</math> be a random variable taking values in the non-negative integers and independent of the <math>X_n</math> for all <math>n \ge 1</math>. Prove that <math>\mathbf{E}\left[\sum_{i=1}^N X_i\right] = \mathbf{E}[N] \mathbf{E}[X_1]</math>.
* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-07T15:50:02Z

Zhe: /* Problem 3 (Linearity of Expectation, 12 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 16 points) ==
* ['''Cumulative distribution function (CDF) (I)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Cumulative distribution function (CDF) (II)'''] Let [math]X[/math] be a random variable with distribution function [math]\max(0,\min(1,x))[/math]. Let [math]F[/math] be a distribution function which is continuous and strictly increasing. Show that [math]Y=F^{-1}(X)[/math] is a random variable with distribution function [math]F[/math].
* ['''Probability density function (PDF)'''] We toss <math>n</math> coins, and each one shows heads with probability <math>p</math>, independently of each of the others. Each coin which shows head is tossed again. (If the coin shows tail, it won't be tossed again.) Let <math>X</math> be the number of heads resulting from the second round of tosses, and <math>Y</math> be the number of heads resulting from all tosses, which includes the first and (possible) second round of each toss.
<ol>
<li>Find the PDF of <math>X</math> and <math>Y</math>.</li>
<li>Find <math>\mathbf{E}[X]</math> and <math>\mathbf{E}[Y]</math>.</li>
<li>Let <math>p_X</math> be the PDF of <math>X</math>, show that [math]p_X(k-1)p_X(k+1)\leq [p_X(k)]^2[/math] for <math>1\leq k \leq n-1</math>.</li>
</ol></li>
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Dependence'''] Let <math>X</math> and <math>Y</math> be discrete random variables with joint mass function <math>f(x,y) = \frac{C}{(x+y-1)(x+y)(x+y+1)}</math> where <math>x,y \in \mathbb{N}_+</math> (in other words, <math>x,y = 1,2,3,\cdots</math>). Find (1) the value of <math>C</math>, (2) marginal mass function of <math>X</math> and (3) <math>\mathbf{E}[X]</math>.
* ['''Expectation'''] It is required to place in order <math>n</math> books <math>B_1, B_2, \cdots, B_n</math> on a library shelf in such way that readers searching from left to right waste as little time as possible on average. Assuming that a random reader requires book <math>B_i</math> with probability <math>p_i</math>, find the ordering of the books which minimizes the expected number of titles examined by a random reader before discovery of the required book.
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.

* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 10 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li>[Card shuffling]
A deck of <math>n</math> cards, numbered <math>1</math> through <math>n</math>, is initially laid out in order so that card <math>i</math> is in position <math>i</math>. At each step, a pair of distinct positions is chosen uniformly at random, and the two cards in those positions are swapped. This operation is repeated <math>k</math> times. Let <math>R_k</math> be the random variable representing the number of cards that are in their original starting positions after <math>k</math> swaps. Calculate the expectation <math>\mathbf{E}[R_k]</math>.
</li>
</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-07T15:35:52Z

Zhe: /* Problem 4 (Probability meets graph theory) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 16 points) ==
* ['''Cumulative distribution function (CDF) (I)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Cumulative distribution function (CDF) (II)'''] Let [math]X[/math] be a random variable with distribution function [math]\max(0,\min(1,x))[/math]. Let [math]F[/math] be a distribution function which is continuous and strictly increasing. Show that [math]Y=F^{-1}(X)[/math] is a random variable with distribution function [math]F[/math].
* ['''Probability density function (PDF)'''] We toss <math>n</math> coins, and each one shows heads with probability <math>p</math>, independently of each of the others. Each coin which shows head is tossed again. (If the coin shows tail, it won't be tossed again.) Let <math>X</math> be the number of heads resulting from the second round of tosses, and <math>Y</math> be the number of heads resulting from all tosses, which includes the first and (possible) second round of each toss.
<ol>
<li>Find the PDF of <math>X</math> and <math>Y</math>.</li>
<li>Find <math>\mathbf{E}[X]</math> and <math>\mathbf{E}[Y]</math>.</li>
<li>Let <math>p_X</math> be the PDF of <math>X</math>, show that [math]p_X(k-1)p_X(k+1)\leq [p_X(k)]^2[/math] for <math>1\leq k \leq n-1</math>.</li>
</ol></li>
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Dependence'''] Let <math>X</math> and <math>Y</math> be discrete random variables with joint mass function <math>f(x,y) = \frac{C}{(x+y-1)(x+y)(x+y+1)}</math> where <math>x,y \in \mathbb{N}_+</math> (in other words, <math>x,y = 1,2,3,\cdots</math>). Find (1) the value of <math>C</math>, (2) marginal mass function of <math>X</math> and (3) <math>\mathbf{E}[X]</math>.
* ['''Expectation'''] It is required to place in order <math>n</math> books <math>B_1, B_2, \cdots, B_n</math> on a library shelf in such way that readers searching from left to right waste as little time as possible on average. Assuming that a random reader requires book <math>B_i</math> with probability <math>p_i</math>, find the ordering of the books which minimizes the expected number of titles examined by a random reader before discovery of the required book.
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.

* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 12 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li> [Number of operations]
We have a directed graph <math>G=(V,E)</math> without self-loops and multi-edges.

Until the graph becomes empty, repeat the following operation:
<ul>
Choose one (unerased) vertex uniformly at random (independently from the previous choices). Then, erase that vertex and all vertices that are reachable from the chosen vertex by traversing some edges. Erasing a vertex will also erase the edges incident to it.

</ul>
Let <math>R_v</math> denotes the number of vertices from which vertex <math>v</math> is reachable. Prove that the expected value of the number of operations equals to <math>\sum_{v \in V} \frac{1}{R_v}</math>.
</li>

<li>[Expected Mex]
Let <math>X_1,X_2,\ldots,X_{100} \sim \mathrm{Geo}(1/2)</math> be independent random variables. Compute <math>\mathbf{E}[\mathrm{mex}(X_1,X_2,\ldots,X_{100})]</math>, where <math>\mathrm{mex}(a_1,a_2,\ldots,a_n)</math> is the smallest positive integer that does not appear in <math>a_1,a_2,\ldots,a_n</math>. Your answer is considered correct if the absolute error does not exceed <math>10^{-6}</math>. (Hint: Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required.)
</li>
</li>

</ul>

== Problem 4 (Probability meets graph theory, 14 points) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>

<li>[Erdős–Rényi random graph]
Consider <math>G\sim G(n,p)</math>, where <math>G(n,p)</math> is the Erdős–Rényi random graph model. Let <math>\ell \ge 3</math> be a fixed integer, and let <math>N_{\ell}</math> be the random variable representing the number of cycles of length exactly <math>\ell</math> in graph <math>G</math>. Find the expected value <math>\mathbf{E}[N_{\ell}]</math>.
</li>

<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Dominating set]
A ''dominating set'' of vertices in an undirected graph <math>G = (V, E)</math> is a set <math>S \subseteq V</math> such that every vertex of
<math>G</math> belongs to <math>S</math> or has a neighbor in <math>S</math>.

Let <math>G = (V, E)</math> be an <math>n</math>-vertex graph with minimum degree <math>d > 1</math>. Prove that <math>G</math> has a dominating set with at most <math>\frac{n\left(1+\log(d+1)\right)}{d+1}</math> vertices. (Hint: Consider a random vertex subset <math>S \subseteq V</math> by including each vertex independently with
probability <math>p := \log(d + 1)/(d + 1)</math>.)
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-07T15:19:23Z

Zhe: /* Problem 5 (1D random walk, 8 points) */

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 16 points) ==
* ['''Cumulative distribution function (CDF) (I)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Cumulative distribution function (CDF) (II)'''] Let [math]X[/math] be a random variable with distribution function [math]\max(0,\min(1,x))[/math]. Let [math]F[/math] be a distribution function which is continuous and strictly increasing. Show that [math]Y=F^{-1}(X)[/math] is a random variable with distribution function [math]F[/math].
* ['''Probability density function (PDF)'''] We toss <math>n</math> coins, and each one shows heads with probability <math>p</math>, independently of each of the others. Each coin which shows head is tossed again. (If the coin shows tail, it won't be tossed again.) Let <math>X</math> be the number of heads resulting from the second round of tosses, and <math>Y</math> be the number of heads resulting from all tosses, which includes the first and (possible) second round of each toss.
<ol>
<li>Find the PDF of <math>X</math> and <math>Y</math>.</li>
<li>Find <math>\mathbf{E}[X]</math> and <math>\mathbf{E}[Y]</math>.</li>
<li>Let <math>p_X</math> be the PDF of <math>X</math>, show that [math]p_X(k-1)p_X(k+1)\leq [p_X(k)]^2[/math] for <math>1\leq k \leq n-1</math>.</li>
</ol></li>
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Dependence'''] Let <math>X</math> and <math>Y</math> be discrete random variables with joint mass function <math>f(x,y) = \frac{C}{(x+y-1)(x+y)(x+y+1)}</math> where <math>x,y \in \mathbb{N}_+</math> (in other words, <math>x,y = 1,2,3,\cdots</math>). Find (1) the value of <math>C</math>, (2) marginal mass function of <math>X</math> and (3) <math>\mathbf{E}[X]</math>.
* ['''Expectation'''] It is required to place in order <math>n</math> books <math>B_1, B_2, \cdots, B_n</math> on a library shelf in such way that readers searching from left to right waste as little time as possible on average. Assuming that a random reader requires book <math>B_i</math> with probability <math>p_i</math>, find the ordering of the books which minimizes the expected number of titles examined by a random reader before discovery of the required book.
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.

* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 12 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li> [Number of operations]
We have a directed graph <math>G=(V,E)</math> without self-loops and multi-edges.

Until the graph becomes empty, repeat the following operation:
<ul>
Choose one (unerased) vertex uniformly at random (independently from the previous choices). Then, erase that vertex and all vertices that are reachable from the chosen vertex by traversing some edges. Erasing a vertex will also erase the edges incident to it.

</ul>
Let <math>R_v</math> denotes the number of vertices from which vertex <math>v</math> is reachable. Prove that the expected value of the number of operations equals to <math>\sum_{v \in V} \frac{1}{R_v}</math>.
</li>

<li>[Expected Mex]
Let <math>X_1,X_2,\ldots,X_{100} \sim \mathrm{Geo}(1/2)</math> be independent random variables. Compute <math>\mathbf{E}[\mathrm{mex}(X_1,X_2,\ldots,X_{100})]</math>, where <math>\mathrm{mex}(a_1,a_2,\ldots,a_n)</math> is the smallest positive integer that does not appear in <math>a_1,a_2,\ldots,a_n</math>. Your answer is considered correct if the absolute error does not exceed <math>10^{-6}</math>. (Hint: Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required.)
</li>
</li>

</ul>

== Problem 4 (Probability meets graph theory) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>
<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Tournament]
Prove that there is a [https://en.wikipedia.org/wiki/Tournament_(graph_theory) tournament] <math>T</math> with <math>n</math> players and at least <math>n!/2^{n-1}</math>Hamiltonian paths.
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

概率论与数理统计 (Spring 2026)/Problem Set 2

2026-04-07T15:10:13Z

Zhe: Created page with "NOT FINISHED YET *每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 *为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。 *若考试中被抽取到的作业题目答错..."

NOT FINISHED YET

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 2==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Warm-up problems, 16 points) ==
* ['''Cumulative distribution function (CDF) (I)'''] Express the distribution functions of [math]X^+ = \max\{0,X\}[/math], [math]X^- = -\min\{0,X\}[/math], [math]|X|=X^+ + X^-[/math], [math]-X[/math], in terms of the distribution function [math]F[/math] of the random variable [math]X[/math].
* ['''Cumulative distribution function (CDF) (II)'''] Let [math]X[/math] be a random variable with distribution function [math]\max(0,\min(1,x))[/math]. Let [math]F[/math] be a distribution function which is continuous and strictly increasing. Show that [math]Y=F^{-1}(X)[/math] is a random variable with distribution function [math]F[/math].
* ['''Probability density function (PDF)'''] We toss <math>n</math> coins, and each one shows heads with probability <math>p</math>, independently of each of the others. Each coin which shows head is tossed again. (If the coin shows tail, it won't be tossed again.) Let <math>X</math> be the number of heads resulting from the second round of tosses, and <math>Y</math> be the number of heads resulting from all tosses, which includes the first and (possible) second round of each toss.
<ol>
<li>Find the PDF of <math>X</math> and <math>Y</math>.</li>
<li>Find <math>\mathbf{E}[X]</math> and <math>\mathbf{E}[Y]</math>.</li>
<li>Let <math>p_X</math> be the PDF of <math>X</math>, show that [math]p_X(k-1)p_X(k+1)\leq [p_X(k)]^2[/math] for <math>1\leq k \leq n-1</math>.</li>
</ol></li>
* ['''Independence'''] Let <math>X_r</math>, <math>1\leq r\leq n</math> be independent random variables which are symmetric about <math>0</math>; that is, <math>X_r</math> and <math>-X_r</math> have the same distributions. Show that, for all <math>x</math>, <math>\mathbf{Pr}[S_n \geq x] = \mathbf{Pr}[S_n \leq -x]</math> where <math>S_n = \sum_{r=1}^n X_r</math>. Is the conclusion true without the assumtion of independence?
* ['''Dependence'''] Let <math>X</math> and <math>Y</math> be discrete random variables with joint mass function <math>f(x,y) = \frac{C}{(x+y-1)(x+y)(x+y+1)}</math> where <math>x,y \in \mathbb{N}_+</math> (in other words, <math>x,y = 1,2,3,\cdots</math>). Find (1) the value of <math>C</math>, (2) marginal mass function of <math>X</math> and (3) <math>\mathbf{E}[X]</math>.
* ['''Expectation'''] It is required to place in order <math>n</math> books <math>B_1, B_2, \cdots, B_n</math> on a library shelf in such way that readers searching from left to right waste as little time as possible on average. Assuming that a random reader requires book <math>B_i</math> with probability <math>p_i</math>, find the ordering of the books which minimizes the expected number of titles examined by a random reader before discovery of the required book.
* [Law of total expectation] Let [math]X \sim \mathrm{Geom}(p)[/math] for some parameter [math]p \in (0,1)[/math]. Calculate [math]\mathbf{E}[X][/math] using the law of total expectation.

* [Entropy of discrete random variable] Let [math]X[/math] be a discrete random variable with range of values [math][N] = \{1,2,\ldots,N\}[/math] and probability mass function [math]p[/math]. Define [math]H(X) = -\sum_{n \ge 1} p(n) \log p(n)[/math] with convention [math]0\log 0 = 0[/math]. Prove that [math]H(X) \le \log N[/math] using Jensen's inequality.

== Problem 2 (Discrete random variable, 14 points) ==
<ul>
<li> [Geometric distribution (I)] Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are [math]c[/math] different types of object, and each package is equally likely to contain any given type. You buy one package each day.
<ol>
<li>Find the expected number of days which elapse between the acquisitions of the [math]j[/math]-th new type of object and the [math](j + 1)[/math]-th new type.</li>
<li>Find the expected number of days which elapse before you have a full set of objects.</li>
</ol>
</li>

<li> [Geometric distribution (II)] Prove that geometric distribution is the only discrete memoryless distribution with range values <math>\mathbb{N}_+</math>.
</li>

<li> [Binomial distribution] Let <math>n_1,n_2 \in \mathbb{N}_+</math> and <math>0 \le p \le 1</math> be parameters, and <math>X \sim \mathrm{Bin}(n_1,p),Y \sim \mathrm{Bin}(n_2,p)</math> be independent random variables. Prove that <math>X+Y \sim \mathrm{Bin}(n_1+n_2,p)</math>.
</li>

<li> [Negative binomial distribution] Let <math>X</math> follows the negative binomial distribution with parameter <math>r \in \mathbb{N}_+</math> and <math>p \in (0,1)</math>. Calculate <math>\mathbf{Var}[X] = \mathbf{E}[X^2] - \left(\mathbf{E}[X]\right)^2</math>.
</li>
<li>[Hypergeometric distribution] An urn contains [math]N[/math] balls, [math]b[/math] of which are blue and [math]r = N -b[/math] of which are red. A random sample of [math]n[/math] balls is drawn without replacement (无放回) from the urn. Let [math]B[/math] the number of blue balls in this sample. Show that if [math]N, b[/math], and [math]r[/math] approach [math]+\infty[/math] in such a way that [math]b/N \rightarrow p[/math] and [math]r/N \rightarrow 1 - p[/math], then [math]\mathbf{Pr}(B = k) \rightarrow {n\choose k}p^k(1-p)^{n-k}[/math] for [math]0\leq k \leq n[/math].</li>

<li>[Poisson distribution] In your pocket is a random number <math>N</math> of coins, where <math>N</math> has the Poisson distribution with parameter <math>\lambda</math>. You toss each coin once, with heads showing with probability <math>p</math> each time. Let <math>X</math> be the (random) number of heads outcomes and <math>Y</math> be the (also random) number of tails.
<ol>
<li>Find the joint mass function of <math>(X,Y)</math>.</li>
<li>Find PDF of the marginal distribution of <math>X</math> in <math>(X,Y)</math>. Are <math>X</math> and <math>Y</math> independent?</li>
</ol>
</li>

<li>[Conditional distribution]
Let <math>\lambda,\mu > 0</math> and <math>n \in \mathbb{N}</math> be parameters, and <math>X \sim \mathrm{Pois}(\lambda), Y \sim \mathrm{Pois}(\mu)</math> be independent random variables. Find out the conditional distribution of <math>X</math>, given <math>X+Y = n</math>.
</li>
</ul>

== Problem 3 (Linearity of Expectation, 12 points) ==
<ul>
<li> [Streak]
Suppose we flip a fair coin <math>n</math> times independently to obtain a sequence of flips <math>X_1, X_2, \ldots , X_n</math>. A streak of flips is a consecutive subsequence of flips that are all the same. For example, if <math>X_3</math>, <math>X_4</math>, and <math>X_5</math> are all heads, there is a streak of length <math>3</math> starting at the third lip. (If <math>X_6</math> is also heads, then there is also a streak of length <math>4</math> starting at the third lip.) Find the expected number of streaks of length <math>k</math> for some integer <math>k \ge 1</math>.
</li>

<li> [Number of cycles]
At a banquet, there are <math>n</math> people who shake hands according to the following process: In each round, two idle hands are randomly selected and shaken (these two hands are no longer idle). After <math>n</math> rounds, there will be no idle hands left, and the <math>n</math> people will form several cycles. For example, when <math>n=3</math>, the following situation may occur: the left and right hands of the first person are held together, the left hand of the second person and the right hand of the third person are held together, and the right hand of the second person and the left hand of the third person are held together. In this case, three people form two cycles. How many cycles are expected to be formed after <math>n</math> rounds?
</li>

<li> [Number of operations]
We have a directed graph <math>G=(V,E)</math> without self-loops and multi-edges.

Until the graph becomes empty, repeat the following operation:
<ul>
Choose one (unerased) vertex uniformly at random (independently from the previous choices). Then, erase that vertex and all vertices that are reachable from the chosen vertex by traversing some edges. Erasing a vertex will also erase the edges incident to it.

</ul>
Let <math>R_v</math> denotes the number of vertices from which vertex <math>v</math> is reachable. Prove that the expected value of the number of operations equals to <math>\sum_{v \in V} \frac{1}{R_v}</math>.
</li>

<li>[Expected Mex]
Let <math>X_1,X_2,\ldots,X_{100} \sim \mathrm{Geo}(1/2)</math> be independent random variables. Compute <math>\mathbf{E}[\mathrm{mex}(X_1,X_2,\ldots,X_{100})]</math>, where <math>\mathrm{mex}(a_1,a_2,\ldots,a_n)</math> is the smallest positive integer that does not appear in <math>a_1,a_2,\ldots,a_n</math>. Your answer is considered correct if the absolute error does not exceed <math>10^{-6}</math>. (Hint: Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required.)
</li>
</li>

</ul>

== Problem 4 (Probability meets graph theory) ==
<ul>
<li>[Random social networks]
Let <math>G = (V, E)</math> be a fixed undirected graph without isolating vertex.
Let <math>d_v</math> be the degree of vertex <math>v</math>. Let <math>Y</math> be a uniformly chosen vertex, and <math>Z</math> a uniformly chosen neighbor of <math>Y</math>.
<ol>
<li>Show that <math>\mathbf{E}[d_Z] \geq \mathbf{E}[d_Y]</math>.</li>
<li>Interpret this inequality in the context of social networks, in which the vertices represent people, and the edges represent friendship.</li>
</ol>
</li>
<li>[Turán's Theorem]
Let <math>G=(V,E)</math> be a fixed undirected graph, and write <math>d_v</math> for the degree of the vertex <math>v</math>. Use probablistic method to prove that <math>\alpha(G) \ge \sum_{v \in V} \frac{1}{d_v + 1}</math>, where <math>\alpha(G)</math> is the size of a maximum independent set. (Hint: Consider the following random procedure for generating an independent set <math>I</math> from a graph with vertex set <math>V</math>: First, generate a random permutation of the vertices, denoted as <math>v_1,v_2,\ldots,v_n</math>. Then, construct the independent set <math>I</math> as follows: For each vertex <math>v_i \in V</math>, add <math>v_i</math> to <math>I</math> if and only if none of its predecessors in the permutation, i.e., <math>v_1,\ldots,v_{i-1}</math>, are neighbors of <math>v_i</math>.)
</li>

<li>[Tournament]
Prove that there is a [https://en.wikipedia.org/wiki/Tournament_(graph_theory) tournament] <math>T</math> with <math>n</math> players and at least <math>n!/2^{n-1}</math>Hamiltonian paths.
</li>
</ul>

== Problem 5 (1D random walk, 8 points) ==
Let <math>p \in (0,1)</math> be a constant, and <math>\{X_n\}_{n \ge 1}</math> be independent Bernoulli trials with successful probability <math>p</math>.
Define <math>S_n = 2\sum_{i=1}^n X_i - n</math> and <math>S_0 = 0</math>.

<ul>
<li>
[Range of random walk] The range <math>R_n</math> of <math>S_0, S_1, \ldots, S_n</math> is defined as the number of distinct values taken by the sequence. Show that <math>\mathbf{Pr}\left(R_n = R_{n-1}+1\right) = \mathbf{Pr}\left(\forall 1 \le i \le n, S_i \neq 0\right)</math> as <math>n \to \infty</math>, and deduce that <math>n^{-1} \mathbf{E}[R_n]\to \mathbf{Pr}(\forall i \ge 1, S_i \neq 0)</math>. Hence show that <math>n^{-1} \mathbf{E}[R_n] \to |2p-1|</math> as <math>n \to \infty</math>.
</li>

<li>
[Symmetric 1D random walk (III)] Suppose <math>p = \frac{1}{2}</math>. Prove that <math>\mathbf{E}[|S_n|] = \Theta(\sqrt{n})</math>.

</li>
</ul>

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

2026-03-10T06:00:27Z

Zhe: update Concepts

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

2026-03-01T14:48:50Z

Zhe: update class meeting

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

2026-02-28T09:38:04Z

Zhe: init page

Main Page

2026-02-28T09:25:26Z

Zhe:

This is a course/seminar wiki run by the [http://tcs.nju.edu.cn theory group] in the Department of Computer Science and Technology at Nanjing University.

== Home Pages for Courses and Seminars==
;Current semester
* [[高级算法 (Fall 2025)|高级算法 Advanced Algorithms (Fall 2025)]]

* [[高级算法 (Spring 2026)|高级算法 Advanced Algorithms (Spring 2026, Suzhou)]]

* [[概率论与数理统计 (Spring 2026)|概率论与数理统计 Probability Theory (Spring 2026)]]

;Past courses

* Advanced Algorithms: [[高级算法 (Spring 2025)|Spring 2025(Suzhou)]], [[高级算法 (Fall 2024)|Fall 2024]], [[高级算法 (Fall 2023)|Fall 2023]], [[高级算法 (Fall 2022)|Fall 2022]], [[高级算法 (Fall 2021)|Fall 2021]], [[高级算法 (Fall 2020)|Fall 2020]], [[高级算法 (Fall 2019)|Fall 2019]], [[高级算法 (Fall 2018)|Fall 2018]], [[高级算法 (Fall 2017)|Fall 2017]], [[随机算法 \ 高级算法 (Fall 2016)|Fall 2016]].

*Algorithm Design and Analysis: [https://tcs.nju.edu.cn/shili/courses/2024spring-algo/ Spring 2024]

* Combinatorics: [[组合数学 (Spring 2025)|Spring 2025]], [[组合数学 (Spring 2024)|Spring 2024]], [[组合数学 (Spring 2023)|Spring 2023]], [[组合数学 (Fall 2019)|Fall 2019]], [[组合数学 (Fall 2017)|Fall 2017]], [[组合数学 (Fall 2016)|Fall 2016]], [[组合数学 (Fall 2015)|Fall 2015]], [[组合数学 (Spring 2014)|Spring 2014]], [[组合数学 (Spring 2013)|Spring 2013]], [[组合数学 (Fall 2011)|Fall 2011]], [[Combinatorics (Fall 2010)|Fall 2010]].

* Computational Complexity: [[计算复杂性 (Spring 2025)|Spring 2025]], [[计算复杂性 (Spring 2024)|Spring 2024]], [[计算复杂性 (Spring 2023)|Spring 2023]], [[计算复杂性 (Fall 2019)|Fall 2019]], [[计算复杂性 (Fall 2018)|Fall 2018]].

* Foundations of Data Science: [[数据科学基础 (Fall 2025)|Fall 2025]], [[数据科学基础 (Fall 2024)|Fall 2024]]

* Numerical Method: [[计算方法 Numerical method (Spring 2025)|Spring 2025]], [[计算方法 Numerical method (Spring 2024)|Spring 2024]], [[计算方法 Numerical method (Spring 2023)|Spring 2023]], [https://liuexp.github.io/numerical.html Spring 2022].

* Probability Theory: [[概率论与数理统计 (Spring 2025)|Spring 2025]], [[概率论与数理统计 (Spring 2024)|Spring 2024]], [[概率论与数理统计 (Spring 2023)|Spring 2023]].

* Quantum Computation: [[量子计算 (Spring 2022)|Spring 2022]], [[量子计算 (Spring 2021)|Spring 2021]], [[量子计算 (Fall 2019)|Fall 2019]].

* Randomized Algorithms: [[随机算法 (Fall 2015)|Fall 2015]], [[随机算法 (Spring 2014)|Spring 2014]], [[随机算法 (Spring 2013)|Spring 2013]], [[随机算法 (Fall 2011)|Fall 2011]], [[Randomized Algorithms (Spring 2010)|Spring 2010]].

;Past seminars, workshops and summer schools
*计算理论之美暑期学校: [[计算理论之美 (Summer 2025)|2025]], [[计算理论之美 (Summer 2024)|2024]], [[计算理论之美 (Summer 2023)|2023]], [[计算理论之美 (Summer 2021)|2021]]
*[[Theory Seminar|理论计算机科学讨论班]]
*[[Study Group|理论计算机科学学习小组]]
*[[TCSPhD2020| 理论计算机科学优秀博士生论坛2020]]
*[[Quantum|量子算法与物理实现研讨会]]
*Theory Day: [[Theory@Suzhou 2025 | 2025 (Suzhou)]], [[Theory@Nanjing 2019|2019]], [[Theory@Nanjing 2018|2018]], [[Theory@Nanjing 2017|2017]]
*[[\Delta Seminar on Logic, Philosophy, and Computer Science|Δ Seminar on Logic, Philosophy, and Computer Science]]
*[[近似算法讨论班 (Fall 2011)|近似算法 Approximation Algorithms, Fall 2011.]]

; 其它链接
* [[General Circulation(Fall 2025)|大气环流 General Circulation of the Atmosphere, Fall 2025]]
* [[General Circulation(Fall 2024)|大气环流 General Circulation of the Atmosphere, Fall 2024]]

* [[概率论 (Summer 2014)| 概率与计算 (上海交大 Summer 2014)]]