Math 525: Probability
Course notes
Qiulin Fan
2026
Chapter 1basic combinatorics and probability space
1.1permutations and combinations
1.1.1permutations
一个 permutation 就是对一组 objects 的一个 rearrangement (这些 objects 中可以有 same 的也可以有 distinct 的).
对于
个 permutations.
Example 1.1
求 "STATISTICS" 的 # distinct permutations.
Solution
这里一共有 10 个 objects. 但问题是: 其中有 3 个
于是: 我们首先假设它们都是 distinct 的, 则存在
所以这个结果是真实结果的
同样地, 由于因而, 正确结果是:
Remark
求一组 objects 的 distinct permutations 的数量时, 对于其中相同的 objects, 我们只需要除去它们的重复数量的 factorial (即: 它们自己内部有多少个 permutation 都算作一个 permutation).
公式:
其中
这个式子又叫做 multinomial coefficient.
Proposition 1.1
如果我们需要
1.1.2combinations
Proposition 1.2
从
Proof
我们可以将问题转化为: 从
而其中, 对于每个 valid combination, 都包含了它的所有 ordered permutations, 即重复了
1.1.3binomial theorem
Proof
我们可以 prove this by combiinatorial interpretation. 因为把
因而:
考虑所有的 possible
这是 combinatorial 的 proof.
另外一种更轮椅的思路是 prove by induction. 这需要一个辅助的 proposition:
Proposition 1.3
这个等式的 combinatorial interpretation 很 trivial: 对于其中的任意一个 object:
- •
这个 object 被选中的情况, combinations 的数量:
(从其他里面选 个); - •
这个 object 不被选中的情况, combinations 的数量:
(从其他里面选 个).
Example 1.2
一个 52-card deck, 取 5 张随机牌, 我们获得:
- •
4 张同 rank 的牌, 最后一张不同 rank 的牌
- •
a full house (3 张同 rank 的牌, 2 张同 rank 的牌)
的概率是多少?
Solution
一共有
如果是取 3 张同 rank 的牌 + 两张 different 同 rank 的牌: 我们首先在 4 个花色里面选 3 个, 有
因而选取 3 cards of the same rank 的数量为:
然后选取剩余的两张: 然后故技重施, 从剩下的 12 个 rank 里面选 1 个, 而选择它们的花色有
Example 1.3
我们有
Solution
一共有
- •
正确钥匙出现在第
个位置, 其他 随便排列: 种 - •
- •
正确钥匙出现在第
个位置, 其他 随便排列: 种
因而正确的 permutations 的数量为:
因而, 概率是:
Remark
正确钥匙出现在每个位置上的概率都是
这是一类典型的问题: 不放回的抽取. 在只关心"是否在前
- •
你允许的尝试次数
- •
总可能性数
而如果是放回则是不同的情况. 通过补事件容易得:
放回和不防回最大的区别是: 放回时, 每次尝试都是独立的, 而不放回时, 每次尝试都不是独立的. 最明显的例子就是, 如果不放回,
Example 1.4
一个篮子里有
Solution
不放回:
放回: 5 ways to choose the blue ball, 10 ways to choose the red ball, 以及 3 positions to place the blue ball,
1.1.4combinations with repetition
Definition 1.4 (combinations with repetition)
一个 combination with repetition 就是从一个 set 中选取若干个 elements, 而忽略它们的顺序, 并且允许重复选取.
Proposition 1.4
从
Remark
关于这个问题我们最开始可能会犯一个错误: 认为 combinations with
但是想一下就知道这是错的. 因为我们相当于给 repeated 的同一个 objects 赋予了顺序, 从而计入了额外的数量.
Proof
这个问题比较巧妙. 我们上面错误的尝试已经表明: 用 "make copies" 的方法行不通. 我们需要变换一下思路. 原问题是 "要选哪几个元素, 每个元素要选几个". 而我们可以把这个问题理解为: 一共有
Formalize 这个想法即: 对于第
到这里我们想到一个经典的问题: stars and bars. 即: 把
问题是: 我们这里, 一个组可以有
这就强制每个组至少有一个 star, 于是可以使用 stars and bars 的方法来解决. 即: 用
Example 1.5
有 5 种口味的 ice creams. 一个人随机选择 20 个 scoops. 求: 每种口味至少被选中一次的 probability.
Solution
即从
而满足条件的 combinations: 即每种口味我们都预选一个. 然后再从
1.1.5inclusion-exclusion principle
Proposition 1.5 (inclusion-exclusion principle)
如果
Remark
这里的
这个定理是 countable additivity 的直接推广.
Example 1.6
(Divisibility) 令
Solution
令
于是我们要计算的是:
Example 1.7 (matching problem)
假设有
Solution
令
由于:
我们可以得到:
Remark
当
1.2probability space
我们这里跳过所有 measure theory 的内容, 见 notes on measure theory.
Definition 1.5 (probability space, probability measure, sample space, event space)
按 measure space 的定义, 一个 probability space 是三元组
对于这样的 measure
而这里的
任意的
Remark
回顾一下 measure space 的定义:
- •
一个 set
的一个 -algebra 就是一个包含空集的子集簇, 其 closed under countable unions and complements. (如果只 closed under finite unions, 则只称为一个 algebra.) - •
一个 Borel algebra 是一个定义在 topological space 上的
-algebra, 由 all open sets 生成. (因而: closed under countable unions and complements.) 的 Borel algebra 可以由 all open intervals 生成. - •
一个 measure on a measurable space
就是一个从 的函数, 满足 countable additivity. - •
measure 的性质: (1)non-negativity, (2) monotonicity, (3) countable subadditivity, (4) inclusion-exclusion principle (上节已讲), (5) continuity from below and above. 第 (5) 条具体即: For measurable sets
, then .
For measurable sets , then .
Remark
对于 discrete 的 prob space 而言, 通常选取
Remark
概率空间的现实意义是: 一次 experiment 的所有可能的结果的集合, 以及每个结果的概率.
Example 1.8
(dice roll) 如果我们掷一个 6 面的骰子, 那么样本空间
根据我们 measure-based 的定义, 这一结果自然 follows from countable additivity of
Example 1.9
三个人独立地掷一个 6 面的骰子, 求第三个人掷出的点数等于前两个人的点数之和的概率.
Solution
样本空间
这个 event 有 15 个 elements:
因此, 概率是:
Example 1.10
两个人计划在 12:00 到 1:00 之间碰面. 他们各自都会在期间的某个时间点到达. 求: 他们彼此不会等待对方超过 10 分钟的概率.
1.2.1conditional probability and Bayes’ theorem
Definition 1.6 (conditional probability)
对于 probability space
Proof
Naturally follows from the def.
Proof
Remark
Remark
这其实是一个非常直接的结果, 因为
但是它的意义在于, 如果我们知道两个事件的概率和其中一个对另一个的条件概率, 我们就也得到了反过来的条件概率.
Example 1.11 (Medical testing)
在一个群体中, 随机选取一个人患有某种罕见疾病的概率是 0.001. 该疾病有一个诊断测试, 其性质如下: 给定个体患病, 测试呈阳性的概率 (真正阳性率) 是 0.99. 给定个体健康, 测试呈阳性的概率 (假阳性率) 是 0.02. 从群体中随机选取的一个人测试呈阳性. 该个体实际上患有该疾病的概率是多少? 于是
Solution
由 law of total probability, 我们有
于是
Example 1.12 (Monty Hall problem)
假设你参加一个游戏节目, 面前有三扇门: 一扇门后面有一辆车; 其他两扇门后面是山羊. 你选择了一扇门, 比如说是 1 号门, 然后主持人打开了另一扇门, 比如说是 3 号门, 里面有一只山羊. 然后他说 "你想换成 2 号门吗?". 换门对你有利吗?
Solution
令
因而, 换门是有利的.
Remark
这是一个非常反直觉的例子. 我们直觉肯定会觉得: 一共 1 辆车和 2 个山羊, 主持人帮忙排除掉了一个山羊, 那么剩下来的两个里面我们二选一, 肯定是
在第一次选择和第二次选择之间, 主持人带来了额外的信息.
- •
不换门: win iff 在一开始就选择对了车, 这个概率是
. - •
换门: win iff 在一开始选择的是山羊, 这个概率是
.
从条件概率的视角来看:
- •
如果车在 2 号门: 主持人在这个环节里只能选择 3 号门.
- •
如果车在 1 号门: 主持人在这个环节里可以随机在 2 号和 3 号门里面选择一扇门.
也就是说, 主持人打开 3 号门的这个动作, 把 3 号门原本含有的 "中奖潜力" 全部转移给了 2 号门. 这很反直觉. 但是可以用一段 python 程序验证:
def monty_hall_sim(trials=10000):
stay_wins = 0
switch_wins = 0
for _ in range(trials):
# 初始化门: 0代表羊, 1代表车
doors = [0, 0, 0]
car_position = random.randint(0, 2)
doors[car_position] = 1
# 玩家最初的选择
player_choice = random.randint(0, 2)
# 主持人打开一扇有山羊的门
possible_host_doors = [
i for i in range(3)
if i != player_choice and doors[i] == 0
]
host_opens = random.choice(possible_host_doors)
# 如果"不换"赢了
if doors[player_choice] == 1:
stay_wins += 1
# 如果"换门"赢了
remaining_door = [
i for i in range(3)
if i != player_choice and i != host_opens
][0]
if doors[remaining_door] == 1:
switch_wins += 1
print(f"坚持不换中奖次数: {stay_wins} (概率: {stay_wins/trials:.2%})")
print(f"换门后中奖次数: {switch_wins} (概率: {switch_wins/trials:.2%})")运行结果:
总实验次数: 10000
坚持不换中奖次数: 3312 (概率: 33.12%)
换门后中奖次数: 6688 (概率: 66.88%)Example 1.13 (Wizards)
两个巫师
Solution
任意一轮射击 (假设前一轮没有结束, 于是游戏回到初始状态. 因而任意一轮都是独立的) 中, 令
Solving the system, we find
Remark
这个例子表明了先手优势有多大. 相比上一个例子, 这是很直观的.
另外, 这个例子有趣的是, 我们把无限的回合转化为了一个循环结构, 利用游戏状态的自相似, 只需要考虑任意一轮即可.
1.2.2Kolmogorov definition of conditional probability
我们通过
但是, 难道
在考虑这个定义之前, 首先我们发现: 基于我们先前定义的 conditional probability, 我们可以获得一个新的 probability space:
Definition 1.7 (conditional probability space and trace
对于给定的 prob space
继承自原空间的
容易验证, 这个 triplet 是一个 prob space.
Remark
当我们把整个 prob space 限制在 event
定义
因而和我们的直觉一样, 条件概率是通过一个 density function 来重新加权原本的概率测度.
既然这样, 我们能否直接从一个新的 prob space
Definition 1.8 (Kolmogorov definition of conditional probability)
对于给定的 prob space
显然, 当
这个 random variable
Remark
条件概率
这个定义里没有指明, 给定一个 event
- •
看向产生
的 random variable , 即 , 令 , 即由 random variable 生成的 -algebra. 这个 -algebra 包含了所有关于 可能取值的信息. - •
既然
是关于 可测的, 那么它一定可以写成 的形式. 通过对 的所有可能取值进行积分, 我们确定了函数 的整体形态, 这时我们定义 为函数 在点 处的值. - •
实际就是 conditional expectation . 当 时, 它就退化回经典定义 .
Remark
Further issue: Borel-Kolmogorov paradox.
即便是这个定义, 也会出现问题.
给定一个事件
为了解决这个问题, 可以引入更精细的结构, 比如说 regular conditional probability, 以及 disintegration theorem. 不过此处不展开了.
1.2.3independence of events
Definition 1.9 (independence of events)
对于 prob space
则称
更加 generally, 对于任意 collection of events
则称
Remark
根据条件概率的定义, 容易得出: 两个 events
Proof
Directly follows from the definition of conditional probability.
因而 independence of two events 的定义等价于: 事件
将它推广到多个事件: 即任意一个事件的发生与否都不影响其他事件发生的概率.
Remark
我们从 measure 的角度看待两个事件的 independence: 首先
意思是: 事件
因而, 这两个集合在 measure (probability) 的意义下是完全解耦的, 这就是 independence 的 information geometric 意义.
Proposition 1.8
如果 events
Proof
Example 1.14 (Pairwise Independence vs. Mutual Independence)
一组事件
即: 即便对于任意
下面为一个 counterexample: 考虑掷两个骰子. 令事件
我们发现:
Remark
这个反例能够成功的理由是: 事件
(注意: 如果
这个例子说明了, mutual independence 是一个比较强的条件. 我们可以把这三个事件看作是对结果空间的约束:
- •
两个骰子的结果空间有 36 个点.
- •
是一条线 (6个点), 是另一条线 (6个点), 是一条对角线 (6个点)。 - •
两两独立: 意味着任意两条线相交的点数, 恰好符合概率乘积.
- •
相互独立: 要求这三条线交于一点的概率也符合乘积.
这个例子提醒我们: 独立性不是一种可以由低维向高维简单“归纳”的性质. 一个系统可以局部解耦(两两独立, 但在全局尺度上却存在强耦合. 总之 mutual independence 是一个很强的条件.
Example 1.15 (coin tossing)
假设我们有一枚不均匀的硬币, 掷出正面的概率是
Solution
对于任意
Remark
这个问题还可以通过 law of total probability 来解决.
令
Solve 这个 equation 得到同样结果.
Chapter 2random variable
2.1random variable and generated -algebra
2.1.1random variable: 即 prob space 上的一个 Borel measurable function
Definition 2.1 (random variable)
对于 probability space
Remark
回顾 (Borel) measurable function 的定义: 即对于任意
例如:
并且 recall: 任意的 continuous function 都是 (Borel) measurable function. (所以之后我们看到 continuous function 就知道它一定是一个 random variable).
Remark
Random variable (Borel measurable function) 本质上是对样本空间中的事件进行 weights assignment.
原本, 一个 prob space 只能表示: 有多少个 outcomes, 每个 outcome 的概率是多少 (对于无限的 sample space, 一些 outcomes 组合, 即事件, 的概率是多少).
而 random variable 就是给这些 outcomes 以 weights: 比如
Example 2.1
在一副扑克牌中抽一张, 那么每一张的概率都是
Question: 为什么对于 assigning weights 的行为, 我们一定要求它是一个 (Borel) measurable function 呢? 普通的给 outcomes 以 weights 的行为 (任意一个 function
Answer: 因为我们想要知道
因为这一切都是建立在我们以 measure theory 的 framework 来定义 probability 的基础上的.
下面是一个简单的 proposition: 我们可以把多个 random variables 以一种 Borel measurable 的方式组合起来, 那么就成为一个新的 random variable.
Proposition 2.1 (以 Borel measurable 的方式组合起多个 random variables)
Prob space
也是一个 random variable.
Proof
我们在 measure theory 中证明过: 对于任意的 finite seq of Borel measureable functions
而这里的
Remark
以一种 Borel measurable 的方式组合多个 random variables, 这个函数也仍然是一个 random variable.
这个 proposition 看似没有什么卵用, 但是它其实是我们之后构造 random variable 的一个重要工具. 很多我们默认合法的行为, 它都作为基础.
比如我们:
- •
定义了两个 random variable
和 , 那么它们的和 以及积 也是 random variables. - •
更加复杂的: 标量变换
, 向量变换 , 等等, 都是 random variables. - •
统计学中, 我们有一堆样本, 每一个都是随机采样得到的 (即一个 random variable
). 因而在观测之前, 我们把它看作一个 random variable , 然后在观测之后取到它的一个实际值 .通常我们假设所有样本都是 independent and identically distributed (i.i.d., 独立同分布) 的, 即所有的
都是 independent 的, 并且服从同一个 distribution (discuss later…).然后, 我们就可以从这些样本中计算各种统计量, 比如平均值
, 再比如 order statistic, sample variance 等等, 从而通过大数定律等工具的辅佐, 来估计这个 distribution 到底是什么样的一个 distribution.这里这些统计量, 由于是以 Borel measurable 的方式组合起多个 random variables, 也是 random variables. 所以这个 proposition 其实也奠定了统计学中各种统计量的合法性.
2.1.2由一个 random variable generate 的 -algebra
Definition 2.2 (
对于 random variable
这个集合
=2em 这个
Remark
我们知道, 一个
最大的
而给定一个 prob space
而一个 random variable
比如
Example 2.2
掷一次骰子, 所有可能结果为 sample space:
而我们定义一个 random variable
那么它 generate 的
因为
至此我们知道: 一个 random variable
除了能表示 information granularity 以外,
- •
之后讨论关于 independence of two random variables
和 时, 可以用它来作严格定义, 并且展现 independence 的本质: 两个 RV 的 independence 实际表示它们蕴含的信息颗粒度之间没有任何 overlap - •
用以定义 conditional expectation:
, 通常简写为 , 但是其实 是一个更加直观的事情, 表述了一种 Partial Averaging 的概念. - •
Stochastic Process 中有众多应用. 比如 stopping time 的定义.
至此关于 random variable, 我们已经讨论了很多 general 的刻画. 现在我们来讲一点实用的:
2.2distributions
2.2.1distribution and cumulative distribution function
Definition 2.3 (probability distribution)
对于 random variable
我们 write:
Remark
看着有点不直观. 实则我们拆解:
- •
即: 有多少 samples (即哪一个事件 ) 在这个 RV 的映射下落入 这个区间? - •
即: 这个事件 的概率是多少?
接下来的定义和例子会更加直观.
Definition 2.4 (distribution function (也称 cumulative distribution function, cdf))
对于 random variable
Remark
Example 2.3 (geometric probability)
Fix
我们 define 随机变量:
这很简单: 对于
因为
注意: 在这个例子中, probability measure
Theorem 2.1 (distribution function 的性质)
对于 random variable
- •
是 non-decreasing (non-strictly increasing) 的. - •
, . - •
是 right-continuous 的. 即对于任意 , 有 . - •
对于任意
, 有 . 并且 . - •
对于任意
, 有 .
Proof
其他都显然. right-continuity 是源自 measure 的 continuity from above, 我们证明一下: 考虑一个单调递减序列
由 measure 的 continuity from above,
而下面一条
那么
Remark
我们此时心里会默认一件事情: 一旦知道了 RV
回忆一下: 我们在 measure theory 中, 证明 Carathéodory extension theorem 的时候, 证明过一个
Theorem 2.2 (Dynkin’s
设
我们考虑所有的 half-open interval
然后考虑
即两个 measure 一致的 collection of sets. 容易证明, 这个
从而,
并且
因而:
Corollary 2.1 (distribution function
对于 random variable
2.2.2discrete random variable 与 probability mass function
我们基本上研究两类 random variable: discrete random variable 和 continuous random variable.
Definition 2.5 (discrete random variable)
对于 random variable
Remark
就是说,
Remark
对于 discrete random variable
因而, 对于 discrete random variable
这个 pmf 就是
值得一提的是, 这个 pmf 其实就是
Proposition 2.2 (pmf 是 distribution 对于 counting measure
对于一个 discrete random variable
那么, distribution
Proof
这很容易证明. 首先, 这个 counting measure 即:
那么显然, 如果
且对于任意 Borel set
2.2.3continuous random variable 与 probability density function
相对应 discrete random variable, 我们定义 continuous random variable:
Definition 2.7 (continuous random variable)
我们称一个 random variable
Remark
回顾 absolutely continuous function 的定义, 这是一个比较复杂的定义: 对于任意
这是 uniform continuity 的一个加强版本. uniform continuity 对应的是
这个定义有点麻烦, 不过存在等价的条件. 为此我们要 recall 一系列定义与结论, 详细请见: notes on measure theory, module 12: differentiation on
- •
给定一个 function
, 我们定义它的 total variation function 为: - •
如果
(注意这是单调递增函数, 因而即对于任意的 都有 ), 那么我们称 是一个 function of bounded variation, 写作 . - •
如果
, 且 是 right-continuous 的, 且 , 那么我们称 . (即 normalized function of bounded variation). - •
任意的
都 -a.e. differentiable, 且导数 , 并且以下三个条件等价:
这几行字浓缩了 measure theory 的 differentiation theory 的两个星期的内容… 具体见上文 notes 链接, 都有详细证明. 而我们这里就利用起最后这一条结论. 首先, 我们 state 一件事:
Proof
依旧见 notes, 有一个关键 lemma:
其次, 由 2.1 我们知道,
因而我们自然得出:
Theorem 2.3 (一个 random variable 是 continuous random variable 的充要条件)
- •
一个 random variable
的 cdf 一定是 -a.e. differentiable 的. - •
是一个 continuous random variable 当且仅当 , 即当且仅当存在一个函数 , 使得使得对于任意 Borel set , 有这个函数
即是:- –
distribution 对于 Lebesgue measure 的 Radon-Nikodym derivative:
. - –
cdf
的 -a.e.导数 .
我们也称这个
是 continuous random variable 的 probability density function (pdf). - –
Proof
即 remark 的最后一条结论. 由于
并且,
Remark
因而, 在简化的教材中, 通常会直接定义: 一个 random variable
Definition 2.8 (probability density function (pdf))
对于 continuous random variable
我们最后梳理一下.
- •
任意的 random variable 的 cdf
都是一个 function, 因而一定 a.e. 可导. 但是它的导数 的积分不一定返回原函数. - •
如果一个
-a.e. 导数 满足 对所有 成立, 即导数的积分返回原函数, 那么 就是一个 continuous random variable, 而我们定义 为 的 probability density function.
以及, 显然 pdf 有以下性质:
Proposition 2.3 (probability density function 的性质)
对于 continuous random variable
- •
for -a.e. . (因为 是 non-decreasing 的.) - •
. (因为 .) - •
对于任意 Borel set
, 有 - •
对于
-a.e. ,
2.2.4singular continuous random variable 与 Lebesgue Decomposition Theorem
对于 continuous random variable 的定义, 有些地方会简化定义为: continuous random variable 就是指其 cdf 是一个 continuous function.
但是我们现在知道, 这个定义是错的. 首先, 标准定义中的 absolutely continuous 要强于 continuous (它能推导出 a.e. differentiable); 而且, 这个更强的定义是 necessary 的.
因为当提及 continuous random variable 时, 通常意思是它存在一个 pdf. 而存在一个 pdf 即意味着它满足 FTC of Lebesgue integral, 也就等价于
我们这里给出一个 counterexample: Cantor distribution. 它的 cdf 是 continuous 的, 但是它并没有能够满足 FTC of Lebesgue integral (返回原函数) 的 a.e. derivative, 因而没有 pdf.
Example 2.4 (Cantor distribution)
令
它刻画的是:
- •
把
三等分, 去掉中间的部分, 然后在剩下的两部分中, 以 的概率选择左边的区间, 以 的概率选择右边的区间; - •
在选定的区间中, 再把它三等分, infinitely 重复这一过程.
- •
最后, 这一行为会收敛于 Cantor set 上的一个点.
具体而言:
- •
第 1 步 (
) 我们查看 , 如果 , 你选择了左边的区间 ; 如果 , 你选择了右边的区间 . - •
第 2 步 (
): 在第 1 步选定的区间内,查看 如果 , 你在当前小区间内选择了左侧的 1/3; 如果 , 你在当前小区间内选择了右侧的 1/3. - •
从而,
它也表示了: 三进制小数中, 所有完全不包含数字 1 的小数的集合.
由于其 uncountability, 对于任意单点
然而,
因而
对于 Cantor distribution 这个例子, 我们称这样的 random variable 是一个 singular continuous random variable:
Definition 2.9 (singular continuous random variable)
对于 random variable
Remark
singular continuous random variable 的意思是, 在
这个例子向我们说明了: 除了 discrete random variable 和 continuous random variable 以外, 还有其他的奇异的 random variables. 而下面这一定理刻画了任意的 random variable 的结构:
Theorem 2.4 (Lebesgue Decomposition Theorem)
对于任意 random variable
其中
Proof
TODO.
Remark
我们也可以这样展开:
其中
2.3expectation and variance
Distribution 是一个 random variable 的完整刻画, 而这一节我们来谈一谈 expectation 和 variance, 这是一个 random variable 的两个重要的数值特征: 它的均值和离散程度.
最后我们会谈一谈
2.3.1expectation and variance 的 definition 和计算方法
随机变量的 expectation 是它 w.r.t. 它所在概率空间 prob measure
而其 variance 是
Definition 2.10 (expectation and variance of random variable)
对于 random variable
其 variance 定义为
Remark
Note that:
要计算 discrete random vairable 的 expectation 和 variance, 直接 by def, sum 就可以:
Proposition 2.4 (discrete random variable 的 expectation 和 variance)
对于 discrete random variable
非常简单.
但是对于 continuous random variable 而言, 怎么求呢? 这里有一个 w.r.t. prob measure
为了实现这个目标, 我们首先需要一个工具来过渡一下:
Lemma 2.2 (用 distribution (
对于 random variable
Proof
这个结论是 Lebesgue integral 的 change of variable formula 的一个 special case. 注意,
By change of variable formula,
(如果不用 change of variable theorem, 也可以证明. 考虑 simple function 的 case, 显然; 然后对 simple function 自然成立, 然后用 monotone convergence theorem 推广到一般情况.)
//TODO: 从 diffeomorphism version 的 change of variable formula 证明 push-forward version 的 change of variable formula, 然后 apply 这个结论. 参考: change of variable
Proposition 2.5 (continuous random variable 的 expectation 和 variance)
对于 continuous random variable
并且, 对于任意的 measurable function
Proof
由于
从而得证.
Proposition 2.6 (expectation 的性质)
令
- •
linearity of expectation:
for any . - •
monotonicity of expectation: 如果
a.s., 那么 . - •
absolute value:
这三条性质都容易验证, 直接 follow from linearity of Lebesgue integral, monotonicity of Lebesgue integral, triangle inequality of Lebesgue integral.
By def, 容易验证.
2.3.2 与 covariance and correlation as inner product and cosine
我们 recall measure theory 中的一丢丢 functional analysis 的内容:
where
即把所有 a.s. 相等的 random variables 都看作相等.
我们知道, 这是一个 Hilbert space, 即一个 complete inner product space, 其中
- •
两个 random variables as vectors 的 inner product 定义为:
即它们的 second - •
一个 random variable 的 norm 即:
即它的 second moment 的 square root. 它表示了这个 random variable 的整体离散程度.
虽然这个空间已经有一定的 information geometry 了, 但是我们实际上希望能够用一个结构来描述两个 random variables 之间的线性相关性:
- •
任意取一个
, 较大 (距离它的 expectation 较远) 的时候, 是否也通常较大 (距离它的 expectation 较远)? 较小的时候, 是否也通常较小?
而
比如考虑
我们希望的是这个 cosine similarity 应当是 1. 即, 应该忽略掉绝对数值, 而是考虑这两个 random variables 的变化趋势.
因而 solution: normalize 每个 random variable, 把它们移动到均值为 0 的位置! 即: 把每个
并且, 我们可以通过把每个
而投影+度量的行为, 就是计算:
我们容易发现一件事情:
Theorem 2.5 (covariance is a positive-semidefinite symmetric bilinear form)
- •
covariance 是一个 symmetric bilinear form (并且 translation-invariant, 忽略 translation) 的 operator:
- •
covariance 满足 positive definiteness:
.
Proof
By def.
而当我们把空间限定在
Theorem 2.6 (
Proof
很显然. 因为在
而在
显然,
where
从而有以下显然的结论:
Proposition 2.8 (properties of correlation)
- •
- •
如果
, 那么 for some and ; 如果 , 那么 for some and . - •
By Cauchy-Schwarz inequality,
.
做一个总结:
求两个 random variables 之间的 correlation, 就是把它们都 center 到 zero-centered 的位置 (即投影到
此时我们看到 decomposition of variance:
Proposition 2.9 (两个 random variables 之和的 variance)
两个 random variables 的和的 variance 可分解成 variances 和 covariance:
Proof
Remark
它其实这就是标准的 inner product space 上的向量平方公式:
2.4discrete random variables
Recall: discrete random variable 是指其 range a.s. 是 countable 的 random variable. (存在一个 countable set
discrete RV 的 probability mass unction (pmf):
就是
因为假设
下面我们给出一些经典的 discrete random variable 的例子, 以及它们的 pmf 和 cdf.
2.4.1Bernoulli distribution and Binomial distribution
Example 2.5 (Bernoulli distribution)
令
令
令
那么显然可以计算:
我们称
称
这是最简单的 random variable 和 distribution 了. 它 model 的是: 比如我们 toss 一枚 biased coin, 以
Proposition 2.10
如果
显然.
Example 2.6 (Binomial distribution)
我们 independently repeat
考虑:
为 success 的总次数. 那么
我们称
它 model 的是: 比如我们 toss 一枚 biased coin
Proposition 2.11
如果
Proof
由于
可以得到
然后计算得
2.4.2Geometric distribution and Negative Binomial distribution
Example 2.7 (Geometric distribution)
我们 perform independent Bernoulli trial, 每次 trial 的 success probability 都是
考虑 random variable
那么
容易计算出
我们称
它 model 的是: 比如我们 toss 一枚 biased coin, 第一次得到 heads 的 trial number.
Proposition 2.12
如果
Proof
similarly, 可以计算得
因而
Example 2.8 (Negative Binomial distribution)
这是 Geometric distribution 的 generalization (但不完全一样).
我们 perform independent Bernoulli trial, 每次 trial 的 success probability 都是
令 random variable
那么
容易计算出
这是因为:最后一次 success 的位置是固定的. 我们要在前
我们称
它 model 的是: 比如我们 toss 一枚 biased coin, 得到第
2.4.3Poisson distribution
Example 2.9 (Poisson distribution)
考虑这一 pmf:
我们称
以
Remark
当
考虑
展开组合数
重组项:
其中, (1) 的 limit 是 1, (2) 的 limit 是
这个极限行为的意义是:
- •
表示: 在一个固定时间/空间窗口内, 一个事件出现的平均次数的观测. - •
我们把这段时间间分成
个小窗口, 将这个观测作为先验知识用来 model 这类事件实现的平均概率, 那么每个小窗口内事件出现的概率是 . - •
每个
都表示: 在时间细分成 个小窗口的情况下, 这个事件出现的次数的分布. (注意不是在时间上的分布, 而是在次数上的分布) - •
当
时, 其意义: 基于连续时间的估计, 这个事件在原固定事件窗口内出现的次数的分布. 这就是 的意义.
因而 Poisson distribution 的意义本质上是: 给定对一个事件在固定窗口下出现的平均次数的观测(估计), 那么这个事件在这个窗口内出现
所以 Poisson 分布, 即是根据一个事件在给定 windows 内发生次数的 expectation, 来估计这个事件在该 windows 内发生次数的分布的标准方法.
Remark
Further remark: Poisson distribution 的用途.
- •
它是 model "大量级的小概率事件" 的通用模型.
即一段时间内, 一件事情的发生的概率非常小 ( ), 但是有很多机会发生 ( ). 比如放射性衰变. - •
现实世界中, 对于一些事情, 我们想要 model 其在一段时间内发生的总次数 (
) 和单次成功率 ( ) 是很困难的. 比如统计今天路过百货大楼的总人数 ( ), 以及每个人路过百货大楼时走进去的概率 ( ). 但是我们很容易可以知道: 的观测. 即: 每天平均有多少人走进百货大楼. 那么我们就可以用 Poisson distribution 来 model 这件事情在一天内发生的次数的分布.
Proposition 2.13
如果
Proof
recall
因而
similarly, 可以计算得
因此,
2.4.3.1Poisson distribution 的 additivity
Remark
这个事实通过简单的计算即可得到.
但是值得一提的是, 我们之后会证明一个结论: 两个 independent 的 random variable 的 sum 的 distribution 是它们 convolution 的 distribution.
而 Poisson distribution 的 convolution 仍然是 Poisson distribution, 并且是 linear 的. 这就是 additivity of Poisson distribution 的本质原因.
2.5continuous random variables
recall: 总而言之, continuous random variable 是指其 distribution
对于任意
而由
这里还有一个额外的结论:
Proposition 2.14
对于任意的 measurable function
Proof
下面我们介绍一些常见的 continuous random variables, 以及它们的 pdf, cdf, expectation 和 variance.
2.5.1uniform distribution: 最简单的 continuous RV
Definition 2.14 (uniform distribution)
如果
对于 uniform distribution, 很容易计算得:
Example 2.10 (uniform distribution 的 pdf 和 cdf)
考虑
2.5.2exponential distribution: geometric distribution 的 continuous version
Exponential random variable model 的是一盏灯的 remaining lifetime. 它 assume: 任意时间, 这盏灯有一个 constant 的磨损速率.
假设它的磨损速率是
即 ODE:
with initial condition
我们知道这个 ODE 的 solution 是:
Definition 2.15 (exponential distribution)
我们称
写作
刚才已经计算出, exponential random variable 的 distribution 为
容易验证,
计算其 expectation:
并 notice:
即:
Remark
exponential 随机变量是 geometric 随机变量的 continuous analogue. 因为 geometric random variable 是假设一个事件在每个时间点以 constant 的概率发生, 用来 model 它第一次发生的时间;
而 exponential random variable 其实也是, 只是 on a continuous time scale: 它假设的 constant 损坏率其实 implies: 在任意时间, 如果灯还没坏, 那么灯此刻坏掉的概率是 constant 的.
Proof
简单而言
因而对于 geometric RV 的 pmf, 当我们把时间间隔 (discrete time interval) 变得越来越小, 这一行为的极限就变为了 exponential RV 的 pdf.
这是一个很自然的 limit behavior, 此处不验证了.
Example 2.11
假设我们有一个 storage battery, 它的 lifetime 是 exponentially distributed 的, 并且 average 为 10 hours. Suppose 我们想要 use this battery for 5 hours for.
计算: probability of finishing the task, if:
(a) 使用一个 new battery
(b) 使用一个已经用过 2 hours 的 battery
Solution
如果我们使用一个 new battery, 则 want:
Notice:
2.5.3Gamma distribution: negative binomial distribution 的 continuous version
recall Gamma 函数:
这个函数有一个重要的性质:
因而对于
Gamma 函数就是 factorial 函数的 continuous generalization.
Definition 2.16 (
如果 continuous random variable
那么我们称
其中
and for
Expectation:
(since
容易发现: 当
而当
Proof
证明这一结论除了硬算之外, 更快的方法是通过 moment generating function. //TODO
2.5.4normal random variables: 最重要的 continuous RV, 任意 RV 的叠加极限
Definition 2.17
我们称
写作:
特别地, 当
被称为 standard normal distribution.
- •
验证其为 valid pdf:
我们首先验证 standard normal distribution. 令:
则
从而得到
. 因而 , 因而 .从而对于任意的
和 , 通过 change of variable formula 易得 . - •
计算其 expectation 和 variance:
我们只需要计算 standard normal distribution 的 expectation 和 variance, 然后通过 expectation 的 linearity 和 variance 的 scale invariance 来计算.
令
. Then因为这是一个 odd function. 从而
从而:
For general normally distributed
, 我们知道了 的 , , 因而and
对于多个 i.i.d. normally distributed
,For
odd, it is .
For even:从而:
- •
其 cdf:
我们在微积分中知道, 这个 integral 没有 closed form solution. 因而我们只能给出数值 approximation. Important numerical values:
Note 由于
(std) 是一个 even function, 有 因而Similarly,
为什么 normal random variables 非常重要: 因为有一个 universality property called central limit theorem. 之后的章节我们会展开讨论:
2.5.4.0.1任意的 random variable, 只要 expectation 和 variance 都是 finite 的, 那么它们的叠加极限都会服从 normal distribution.
这里我们先给出一个 special case of central limit theorem:
(Proof: later chapters.)
Example 2.12
Toss a million times 一个 fair coin. Approximate the prob that we get more than
因而:
2.5.4.0.2除此之外 need to mention: Poission distribution 当
这并不是一个令人惊讶的事情. 也可以用 central limit theorem 来解释. 因为 recall: Poisson distribution 有一个很重要的 property: additivity. 因而
Chapter 3joint and conditional distributions
3.1random vector and joint distributions
3.1.1random vector
Definition 3.1 (random vector)
对于 prob space
通常我们将 random vector 写成分量形式
random vector 相当于在一个 prob space 上, 考虑多个重新分配 mass 的方法, 并把它们并列起来.
Proposition 3.1 (由
令
是一个 random vector.
Proof
我们在 measure theory 中证明过: 对于任意的 finite seq of Borel measureable functions
Proposition 3.2 (一个 random vector 的每个分量都是一个 random variable)
令
Proof
对于
其中
由于 projection map
Remark
上两条 propositions 说明了一个事情: random vectors 和其分量 random variables 完全相互决定.
- •
random variables 组合起来一定是一个 random vector.
- •
random vector 拆开每个分量一定是 random variable.
因而, 研究一个 random vector 也就相当于研究分量 random variables 之间的关系.
这一章节我们会从 random vector 的性质 (比如 joint distribution 和 marginal distribution, conditional distribution) 出发, 研究分量 random variables 之间的关系.
(但是注意: 前提是这些 random variables 必须定义在同一个 prob space 上. 也就是, 它们的 base probability measure 一定相同. 如果我们考虑不同 prob space 上的 random variables 的话, 那它们没有一个公共的 base probability measure, 很难说它们之间有什么关系. 这种情况下, 我们需要 coupling: 构造一个新的 prob space (说白了就是 product space), 让这两个 random variables 都有一个新 version. 这一问题我们之后再讨论.)
3.1.2joint distribution
Definition 3.2 (joint distribution and joint cdf)
令
我们称
为
而我们称
(即
joint distribution 的定义已经包括了如何从多个 random variables 的 distributions 得到一个 joint distribution. 而, 我们也可以从一个 joint distribution 的 limit behavior 得到每个 random variable 分量的 distributions, 称之为 marginal distribution:
Definition 3.3 (marginal distribution)
令
我们以
Proposition 3.3 (通过 joint distribution 的极限得到 marginal distribution)
令
此外, joint distribution 有其他明显的 limit behaviors:
- •
- •
对于每个维度都是 increasing 且 right-continuous 的. - •
- •
Remark
最后一条: 右边相当于
因而成立.
discrete random vector 很容易处理. 我们可以直接定义 joint pmf. 而 continuous random vector 需要展开讨论. 接下来我们讲单独讨论 continuous random vector 的 joint distribution.
3.1.3condinuous joint cdf 与 joint pdf
recall: continuous random variable
这个定义可以 generalize 到 random vector 上.
Definition 3.4 (continuous random vector 和 continuous joint cdf)
对于 random vector
则称
注意: 由于是在
Remark
这个函数
Remark
我们已经知道, 只要存在导数
那么这个还原积分的计算可以任意换序吗?
显然是可以的. 因为 recall Fubini’s Theorem: 只要
而我们知道,
这就很舒服. 这也给出了 margin distribution 的计算方法: 只要对 joint pdf
Remark
注意: 多个 continuous random variables 的 joint distribution 不一定是 continuous 的. 反例: 考虑 random vector
Proposition 3.4 (joint pdf 和 joint cdf 的性质)
令
- •
a.e. 并且 . - •
(如果一个集合
有一个零测维度, 那么 ) - •
每个
的 marginal distribution 也是 (absolutely) continuous 的, 并且例如,
- •
对每个
, 都可以通过偏导数从 joint cdf 得到 joint pdf (这个偏导数一定 (a.e.) 存在):并且 by Fubini’s theorem 可以 (a.e.) 任意换序:
Proof
- •
由于
是 对于 的 Radon-Nikodym derivative, 因为任何 Borel 集 都有 , 假设存在一个集合 使得在其上 且 , 那么根据积分定义因而反证得
a.e.并且
- •
natural.
- •
即 marginal distribution 的定义在 continuous case 中的展开
- •
by Fubini’s theorem, 以及 joint cdf 的定义.
Example 3.1
考虑
Find
Solution
我们需要
evaluate 这两个积分:
因为
计算
然后计算
最后计算
这两个定积分分别为:
因而
Theorem 3.1
对于 continuous random vector
Example 3.2
Let
- •
求 marginal density
- •
计算概率
和
3.2independence of two random variables
3.2.1independence of two random variables 的三种等价定义
Definition 3.5 (independence via product distribution of marginal distributions)
两个 random variables
注意这个定义等价于 for all points
即它们的 joint distribution 是它们 marginal distributions 的 product.
对于 discrete 和 continuous random variables 而言, 这还意味着 independence 等价于:
- •
joint pmf 是 marginal pmfs 的 product, for discrete case.
- •
joint pdf 是 marginal pdfs 的 product, for continuous case.
这里离散情形沿用 discrete random variable 的定义. 详细而言:
Theorem 3.2 (independence via joint-density factorization marginal densities)
令
- •
如果
是 discrete random variables, 则它们 independent 的条件等价于对于任意 , 都有 - •
如果
是 continuous random variables, 则它们 independent 的条件等价于对于任意 , 都有
Proof
discrete case: 显然可得.
continuous case:
- •
: 取偏导数即可. - •
: 积分即可.
因而对于 independent 的两个 random variables, 固定
Remark
Recall independence of events 的定义:
也等价于对于任意的 Borel sets
即: 一个事件发生与否都不会对另一个事件发生的概率产生任何影响.
而再看到两个 random variables independence 的定义是:
这个定义也当然等价于:
Proposition 3.5 (independence via conditional distribution: marginal distribution)
两个 random variables
即:
所以它实际上意义是: 知道一个 random variable 的任何信息, 对于另外一个都没有任何帮助.
因而它们的 joint distribution 可以分解成 marginal distributions 的 product.
Remark
Furthermore: 我们不难发现一件事情, 可以在 independence of two events 和 independence of two random variables 之间建立一个桥梁:
Proposition 3.6 (independence via generated sigma-algebras)
令
这严格说明了: 两个 random variables 之间的 independence, 本质上是它们各自蕴含的 information (由 generated sigma-algebra 严格刻画) 的完全不相关: 对
以上就是 independence of two random variables 的定义, 以及其 information geometric intuition.
下面我们讲 independence between two random variables, generalize 到 mutual independence among 任意的 family of random variables.
3.2.2mutual independence of a family of random variables: 强于 pairwise independence
我们定义了两个 random variables 的 independence, 但是这个定义可以推广到多个 (甚至 uncountably many) random variables 上.
Definition 3.6 (mutual independence of multiple random variables)
令
则称这个 family of random variables 是 independent 的.
注意: joint mass & density 的 factorization 也可以推广到多个 random variables 上. 有一件事情值得说明: 这里定义的是mutual independence, 也就是说, 对于任意的 finite subset
而两两 independent 的 random variables family 不一定是 mutual independent 的. 即: 如果对于任意的
举个例子:
Example 3.3 pairwise independence does NOT imply mutual independence
假设我们抛掷两枚公平的硬币. 令
现在, 我们定义第三个 random variable
容易验证:
但是, 如果我们同时知道
这说明 pairwise independence 只能保证局部的信息解耦, 而 mutual independence 则保证了在这个 family of random variables 之间的全局信息解耦.
3.2.3independent uncorrelated
Independence 的概念会让我们回忆起另外一个刻画两个 random variables 之间关系的概念: covariance, 它丈量了两个 random variables 之间的线性关系.
covariance 的定义:
我们称 covariance 为 0 的两个 random variables 为 uncorrelated random variables. 我们容易发现: independence 是一个比 uncorrelated 更强的概念:
Proposition 3.7 (independent 严格强于 uncorrelated)
令
Proof
- •
independence
covariance 是 0, 因为 independence 显然 imply , 从而 covariance 的定义式中 . - •
有一个经典反例: 考虑
是任意按原点对称的分布, 比如一个 standard normal distribution; 而定义 , 此时由于
的分布是关于原点对称的, 且 , 因而 covariance 是 0. 但是 和 显然不是 independent 的.
刚才说到, 两个 random variables 的 independence 显然 imply
Theorem 3.3 (independence
令
特别地, 取每个
Proof
令
根据 Change of Variables Formula,
由于被积函数
其中每一项都是
Remark
recall: expectation is a linear operator (因而 linearity 是 regardless of independence). 但是它不一定是一个 multiplicative operator.
而这里我们说, 如果 random variables 是 independent 的, 那么 expectation 就是一个 multiplicative operator.
实际上: 当这些 Borel measurable functions
Theorem 3.4
令
则这个 family of random variables 是 independent 的.
Proof
不妨特取 indicator functions. 对于任意的 Borel sets
注意到
注意:
OK. 以上是 pretty much general properties of independence. 最后我们看一下, 对于 discrete 和 continuous random variables 而言, independence 的 characterization 具体长什么样子.
3.2.4discrete RV independence 的 characterization
Remark
关于两个 discrete random variables
Proposition 3.8 (discrete RV independence 的 characterization)
两个 discrete random variables
Proof
note: 一个矩阵
where
(
如果我们定义向量
这正是 Rank 1 矩阵的标准形式.
(
Example 3.4
这里的
3.2.5continuous RV independence 的 geometric intuition
对于 independent continuous random variables
- •
joint pdf 的 support set 一定是一个矩形 (不一定 bounded)
- •
joint pdf 的每个维度上的任意截面的形状都是一样的 (因为固定
, 则 方向的性质只由 决定.)即: 固定
, -distribution 的横截面永远长得像 , 只是乘上了一个常数 而已. 同样的, 固定 , 分布的横截面永远长得像 , 只是乘上了一个常数 而已.
3.3conditional distribution function and density
3.3.1conditional distribution and its distribution function
Definition 3.7 (conditional distribution)
给定 random variables
并将 function
称为 the conditional distribution function of
Remark
注意: 每个取值
也就是说, 一个 random variable 可以 induce 出另一个 random variable 的可能 uncountably many 个 conditional distribution.
Remark
如果
以及
其他情况稍复杂一些. 但是我们可以确定的是:
3.3.2conditional density for random variables jointly continuous
Theorem 3.5 (jointly continuous RVs 之间所有 defined 处总有 conditional density)
令
即:
Proof
注意:
则
因而,
Remark
为了保证 continuous random vector 下分量之间的 conditional distribution 总是 (a.e.) 拥有 pdf 的, 我们可以给 not well-defined 处下定义: 如果
在这个定义下: continuous random vector 下分量之间的 conditional distribution 也总是 continuous 的.
3.3.3Law of Total Probability for continuous random vector
Theorem 3.6
令
Proof
注意:
即,
因而 compute:
Remark
recall 最普通的全概率公式: 把样本空间 partition 成几个 disjoint 的事件
这很容易理解. 而这里的 law of total probability for continuous random vector 就是这个公式在 continuous case 的推广:
由于在每一点
Example 3.5
考虑 random vector
计算:
Solution
首先计算 margianl pdfs:
and
由于这是一个 continuous random vector, 因而根据3.5 可以得到:
同理计算出
3.4conditional expectation
Definition 3.8 (conditional expectation)
令
特别地, 如果
而如果
Remark
注意: conditional expectation 对于给定的
对于
Notice: 这个函数是一个 random variable. 同理, 我们可以构造 conditional expectation given multiple random variables
Proposition 3.9 (independence 下 conditional distribution 不变, independence 下 conditional density 不变和 independence 下 conditional expectation 不变)
如果
以及
Example 3.6
(constant random variable 的 conditional expectation)
令
Solution
因而它们 independent (当然,,) 因而
为什么我们要提及这个很呆的例子因为我们要说一个很呆但是要说一下的事情:
Proposition 3.10
conditional expectation 满足 linear property. 即任取
Example 3.7
(computation exercise) 令
计算:
Solution
根据 3.5 和 3.8, 我们就是要做两件事情: 一个是计算
那么
我们发现
因而
而对于
//TODO: 如果
3.5law of total expectation
Proof
对于更加严格的 conditional expectation 的定义而言 (as an orthogonal projection from
那么取
而我们目前的定义下, 要证明它则要对于 discrete 和 continuous 两种情况分别计算证明. (recall Lebesgue Decomposition Theorem: 任意 measure 都可以被分解成一个 discrete 的部分和一个 continuous 的部分以及一个可以忽略的 singular 的部分. 因而证明了 discrete 和 continuous 两种情况即可.)
For discrete case:
For continuous case:
Example 3.8
(fair coin toss) 我们投掷一枚 fair coin.
问题: 计算
Solution
We condition on 第一次 toss
解出
Example 3.9
一只鸡在一段时间内下
Solution
由题意得
因此,
然后由 law of total probability,
因而
Example 3.10
令
首先, verify
Solution
verify 很简单. 然后我们首先计算 density of
然后计算 conditional density of
因而 by 3.8,
然后 by law of total expectation,
since
Chapter 4Behaviors of a sequence of random variables
4.1Toolbox review: inequalities in probability
这一节是一个 review, 复习一些在 measure theory 中我们已经证明过, 在 probability theory 中经常用到的 inequalities.
4.1.1Markov’s ineqaulity and Chebyshev’s inequality
Theorem 4.1 (Markov’s inequality)
下文的 expectation 与 variance 采用 expectation and variance of random variable 的定义。对于一个 non-negative random variable
Proof
我们考虑一个 indicator function
(在
因而 by linearity of expectation,
其值为 1 当
Remark
Markov’s ineq 是通过均值来 bound 非负随机变量达到一定大小的概率 (在多少事件上是大于
Chebyshev’s ineq 则是通过方差来 bound 任意随机变量偏离均值达到一定程度的概率 (在多少事件上是偏离均值超过
Proof
考虑 non-negative random variable
4.1.2Cauchy-Schwarz and Jensen’s ineq
这是 prob space 作为一个 measure space, 其上的函数空间
Theorem 4.3 (Jensen’s inequality)
对于一个 convex function
Proof
Let
Since
因而 apply to
因此 by linearity of expectation,
4.1.3Fatou’s Lemma, MCT and DCT
我们在 measure theory 中最熟悉的三个定理. 复习一下. 这里不 prove 了. proof 请左转 measure theory notes.
Remark
pointwise 下极限的积分, 得到的结果不会大于每个函数积分的下极限.
因为 pointwise 下极限即: 在每个
而逐个函数可能会有一些 spike, 使得它的 expectation 很大, 但是这个 spike 只出现有限次, 导致 pointwise limitinf 的函数没有受到它的影响; 但是, 不同的 spike 可能 finitely 出现在不同的位置上, 而这个出现的行为是无限的(比如 typewritter 函数), 使得每个函数的 expectation 都很大, 从而导致 expectation 的 limit 很大.
而 pointwise liminf 的 expectation 就是对每个点都取最终稳定的最低水平, 从而避免了这些 spikes 的影响.
Theorem 4.5 (monotone convergence theorem)
令
Remark
如果
Theorem 4.6 (dominated convergence theorem)
令
那么
Remark
只要这个序列有一个 integrable 的 uniform bound (不要有很多 unbounded 的 spike 就行了), 那么 expectation 的 limit 就等于逐点 limit 的 expectation 了.
4.1.4Tonneli and fubini
Theorem 4.8 (Fubini’s Theorem)
对于一列任意的 random variables
Remark
Fubini 和 Tonelli 即: 把 linearity of expectation 推广到 countable sum 的情况, 前提是 either 非负(因而无穷不用管) or 它们的 expectation 是一个绝对收敛的 series 就行了.
4.2Definition review: modes of convergence
这一个 section 也是一个 review. 讲讲不同的 convergence mode 的定义, 以及它们之间的关系.
首先, 我们对 pointwise limit 和 uniform limit 的定义已经很熟悉了, 这里就不赘述了. (算了 uniform 还是提一嘴, 意思是我们需要 pointwise limit 的收敛速度也是 uniform 的, 即对任意的
- •
converge a.s. (almost surely) 或称 converge with probability 1:
即:
也就是说
的 a.e. pointwise limit 是 . - •
converge in
: 对于 -integrable 的 random variables sequence 和 , 我们称 , 如果即: 这个 seq of RVs 与这个 limit function 之间的
distance 收敛到 0; 也就是它们的偏差 as a random variable, 其 -th moment 收敛到 0. - •
converge in probability: 对于任意的
, 如果即
与 之间的偏差超过 的概率收敛到 0.
4.3Borel-Cantelli Lemma
4.4Laws of Large Numbers
4.4.1weak and strong LLN
下面是概率论中最重要的定律之一: 大数定律 (Laws of Large Numbers, LLN).
它证明的是一个十分符合直觉的结论: 一个 random variable 的 sample mean (即
就是说: 我们重复做一个相同的实验并取结果的平均值, 当我们做的实验足够多时, 这个平均值就会非常接近于这个实验的 expectation, 也就是理论的均值.
例如最经典的例子就是抛硬币: 我们连续抛
LLN 有两个阶段, weak LLN 和 strong LLN, weak LLN 证明的是这个 convergence 是 in probability 的, 而 strong LLN 证明的是这个 convergence 是 a.s. 的. 就是说 strong LLN 是严格强于 weak LLN 的.
Theorem 4.9 (weak Law of Large Numbers)
对于一列 i.i.d. 的 random variables
Proof
简写
Let
notice: 由于每个
因而
Proof
For simplicity, 我们不证明更弱的条件 (
简写
我们将要证明:
首先, 在 weak LLN 的 proof 中, 我们已经证明了:
我们发现: 当我们只采样
先考虑所有
因而
意味把在
而我们可以通过 squeeze theorem 得到 general case: 对于任意正整数
我们发现:
notice:
General case:
因而
得证.
Remark
我们要求
实际上在
此处不证明了.
4.4.2application: Monte Carlo methods
任何利用 LLN 来近似计算一个 quantity 的方法, 都可以称之为 Monte Carlo 方法.
它的核心思想是:
- •
选择一个随机变量, 其 expectation 等于我们要计算的 quantity.
- •
大量重复采样这个随机变量, 并计算样本的平均值
- •
根据大数定律, 这个平均值近似于我们要计算的 quantity.
- •
我们可以用 Chebyshev’s inequality 来给出这个近似的误差 bound.
Example 4.1 估算
我们令
那么
注意我们每次随机采样
根据 LLN, 不论单次的采样结果如何, 我们都可以得到
我们还可以用 Chebyshev’s inequality 来给出这个近似的误差 bound:
因而当
import random
def estimate_pi(n):
S_n = 0 # This step 1
for _ in range(n):
# Here is step 2 (and 3)
X = random.uniform(-1, 1)
Y = random.uniform(-1, 1)
# Check if the point is inside the unit circle
if X**2 + Y**2 <= 1:
S_n += 1
pi_estimate = 4 * S_n / n
return pi_estimate
# Example usage
n = 1000000
pi_approx = estimate_pi(n)
print(pi_approx)4.4.3application: Bernstein Polynomials
4.4.4application: Hypothesis testing
Chapter 5Central Limit Theorem
5.1convergence in distribution
Definition 5.1 (convergence in distribution)
这里的分布采用 probability distribution 的定义。我们称一个 seq of random variables
Remark
Convergence in distribution 的意思就是: 随着
并且 notice: 并不要求对所有点
比如: 令
而
所以对于这种跳跃不连续点, 如果不跳过, 那么就会得出
5.2Characterization of a distribution
5.2.1moment generating function
Remark
为什么这个东西叫做 moment generating function 呢? 因为如果
Proposition 5.1
如果
其中
5.2.2characteristic function
5.3Central Limit Theorem
Remark
De Moivre–Laplace theorem 给出了二项分布到正态分布的先导特例。
Theorem 5.1 (Lindeberg-Levy Central Limit Theorem)
对于任意一个 seq of i.i.d. random variables
我们有:
Remark
LLN 告诉我们, 当
CLT 则是进一步告诉我们这个接近的过程是如何发生的: 随着
随着
Remark
CLT 的一个主要的应用价值, 就是可以用来估计由多个 i.i.d. 随机因素共同作用的现象的分布.
统计学中常用于对 confidence interval 的估计, 以及 hypothesis testing, 通过计算如
在进行证明前, 我们先看一些 applications of CLT. 可能会帮助我们更好地理解 CLT 的意义.
5.3.1applications of CLT
Example 5.1 (判断 coin 是否 fair)
我们有两个 coins, 想要判断它们是否是 fair coin. 我们可以 toss 这个 coin
现在: 观测到第一个 coin 100 次 toss 中有 38 次是 heads, 第二个 coin 100 次 toss 中有 43 次是 heads.
Solution
假设这两个 coins 是 fair coin. 那么
因而这个第一个 coin 很可能不是 fair coin. 同样的方法计算出
Example 5.2 (样本量需求的计算)
工厂生产了一批电线, 我们想知道它们的平均断裂强度
已知量: 强度的方差
Solution
我们要达到:
我们要把它转成标准的 normal distribution 的形式, 即
于是我们把
于是原式变为:
对于正态分布我们知道
于是想要:
通过查表我们知道当
Remark
这里的应用正是我们开头说的: LLN 告诉我们, 当
随着
5.3.2Berry-Esseen Theorem: CLT 的收敛速度
之前的例子中, 我们都使用了
但是: 这两个分布的近似行为的本身有多么精准?
下面有一个 theorem 刻画了这件事.
Theorem 5.2 (Berry-Esseen Theorem)
给定一个 seq of i.i.d. random variables
Remark
给定一个 number of samples
并且, 这个 bound 不是概率意义上的 bound, 而是一个 deterministic bound, 没有任何的随机性; 并且是 uniform across all
这是因为这里本身就是两个概率的值之间的差, 而不是样本之间的差. 因而其实这是一个非常强大的结论, 表面我们用正态分布近似估计出的概率和真实的概率之间的差值是 determinstically controllable 意义上非常小的.
我们马上可以想到: 对于控制样本数量来达到某个置信水平的问题, 这是一个非常有用的工具, 因为它告诉我们, 当
并且, 这个控制应该是比较精准的. 因为相比其他的控制方法: Chebyshev 只需要 first, second order moments 的信息; Hoeffding 只需要有界性的假设, 甚至不需要知道分布的任何 moment 信息; 而 Berry-Esseen 需要 third order moment 的信息, 因此它应该能够给一个更精准的控制.
Proof
//TODO:
Example 5.3
一个工厂生产电子元件, 每个原件有概率是有缺陷的.
令
并假设 i.i.d. with parameter
其中
工厂方面表示这个 process 是 under control 的, 并给出了假设:
为了验证这个假设, 一个 quality control manager 需要从生产线上需要随机
我们希望这个估计的误差最多为 0.005, 并且这个误差的置信度至少为 0.99, 即我们希望:
那么我们至少需要多少样本量
Solution
首先计算样本均值
此时我们有三个办法:
- •
办法1: Chebyshev’s inequality.
由于
for any , 式子可以进一步控制为我们希望此概率不超过 0.01, 并且
, 那么进一步得到需要解得至少需要
. - •
办法2: Hoeffding’s inequality.
由于 , 我们可以直接使用 Hoeffding’s inequality 来控制:我们 require 了
, 因而可以解得 - •
办法3: Berry-Esseen Theorem.
首先我们假设报告的 的值 0.02 是正确的, 从而可以计算出:并且, 由于
, 我们知道偏度 .因而可以应用 Berry-Esseen Theorem. 我们希望:
等价于
Berry-Esseen Theorem 可以得到: 对于任意的
, 有因而我们需要选择
s.t.忽略掉
这个很小的项 (计算可以再精细地选择 ), 我们也可以得到:因而至少需要
.
我们可以看到
- •
通过 Chebyshev’s inequality 来控制, 我们需要的样本量是 100 万级别的;
- •
通过 Hoeffding’s inequality 来控制, 我们需要的样本量是 10 万级别的;
- •
通过 Berry-Esseen Theorem 来控制, 我们需要的样本量是 5000 级别的, 显然更为高效.
不过, 这个结果是基于我们假设