Math 525: Probability

Course notes

Qiulin Fan

2026

Chapter 1basic combinatorics and probability space

1.1permutations and combinations

1.1.1permutations

Definition 1.1 (permutations)

一个 permutation 就是对一组 objects 的一个 rearrangement (这些 objects 中可以有 same 的也可以有 distinct 的).
对于 个 distinct objects, 一共存在

个 permutations.

Example 1.1

求 "STATISTICS" 的 # distinct permutations.

Solution

这里一共有 10 个 objects. 但问题是: 其中有 3 个 , 3 个 , 2 个 是相同的.
于是: 我们首先假设它们都是 distinct 的, 则存在 个 permutations. 而, 每个 permutation 都包含了对 3 个 的一个子 permutation. 而对 3 个 的任意 permutation 都是相同的! 同样的道理 apply to 3 个 和 2 个 .
所以这个结果是真实结果的 倍.
同样地, 由于因而, 正确结果是:

Remark

求一组 objects 的 distinct permutations 的数量时, 对于其中相同的 objects, 我们只需要除去它们的重复数量的 factorial (即: 它们自己内部有多少个 permutation 都算作一个 permutation).
公式:

其中 是每个 object 的重复数量.
这个式子又叫做 multinomial coefficient.

Definition 1.2 (multinomial coefficient)

令 , 我们定义 multinomial coefficient:

Proposition 1.1

如果我们需要 个 object 1, 个 object 2, , 个 object , 那么它们的 distinct permutations 的数量为:

1.1.2combinations

Definition 1.3 (combinations)

一个 combination 就是从一个 set 中选取若干个 elements, 而忽略它们的顺序.

Proposition 1.2

从 个 distinct objects 中选取 个的 combinations 的数量为:

Proof

我们可以将问题转化为: 从 个 distinct objects 中选取 个的 permutations 的数量, 然后再除去重复的 permutations. 而, 从 个 distinct objects 中选取 个的 permutations 的数量为:

而其中, 对于每个 valid combination, 都包含了它的所有 ordered permutations, 即重复了 次. 因此, 最终的结果为:

1.1.3binomial theorem

Theorem 1.1 (Binomial Theorem)

令 , 则有:

Proof

我们可以 prove this by combiinatorial interpretation. 因为把 展开即 个 的乘积. 即: 对于每个被乘项, 我们都是在 和 之间选择一个.
因而: 的系数就是从 个 中选取 个 的 combinations 的数量, 即 .
考虑所有的 possible 值, 我们得到:

这是 combinatorial 的 proof.

另外一种更轮椅的思路是 prove by induction. 这需要一个辅助的 proposition:

Proposition 1.3

这个等式的 combinatorial interpretation 很 trivial: 对于其中的任意一个 object:

Example 1.2

一个 52-card deck, 取 5 张随机牌, 我们获得:

的概率是多少?

Solution

一共有 种取法. 取 4 张同 rank 的牌: 13 种取法. 取最后一张不同 rank 的牌: 52-4 = 48 种取法. 因而, 概率是:

如果是取 3 张同 rank 的牌 + 两张 different 同 rank 的牌: 我们首先在 4 个花色里面选 3 个, 有 种取法.
因而选取 3 cards of the same rank 的数量为: .
然后选取剩余的两张: 然后故技重施, 从剩下的 12 个 rank 里面选 1 个, 而选择它们的花色有 种取法. 因而, 概率是:

Example 1.3

我们有 把钥匙, 其中有一把是正确的. 尝试 次, 能够成功开门的概率是多少?

Solution

一共有 种钥匙的 permutations. 我们需要的情况: 正确的钥匙出现在前 个位置:

因而正确的 permutations 的数量为:

因而, 概率是:

Remark

正确钥匙出现在每个位置上的概率都是 . 因而它出现在前 个位置的概率就是 .
这是一类典型的问题: 不放回的抽取. 在只关心"是否在前 次成功"这一事件时, 这个过程等价于"正确钥匙在一个随机排列中的位置". 这一结果只和比例有关, 与过程细节无关. 只要没有信息bias, 没有偏好, 完全随机, 那么成功概率只取决于:

而如果是放回则是不同的情况. 通过补事件容易得:

放回和不防回最大的区别是: 放回时, 每次尝试都是独立的, 而不放回时, 每次尝试都不是独立的. 最明显的例子就是, 如果不放回, 时概率为 1. 而如果放回, 不论 有多大, 概率都小于 1; 当 的时候, 这两个概率相近 (符合直觉, 因为 很大时放回和不放回几乎没区别.)

Example 1.4

一个篮子里有 个 red balls 和 个 blue balls. 我们随机从中取出 个 balls, exactly 其中 个是 blue ball 的概率是多少? 如果每次都放回呢?

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

从 个 distinct objects 中选取 个的 combinations with repetition 的数量为:

Remark

关于这个问题我们最开始可能会犯一个错误: 认为 combinations with repetitions 的数量为:

但是想一下就知道这是错的. 因为我们相当于给 repeated 的同一个 objects 赋予了顺序, 从而计入了额外的数量.

Proof

这个问题比较巧妙. 我们上面错误的尝试已经表明: 用 "make copies" 的方法行不通. 我们需要变换一下思路. 原问题是 "要选哪几个元素, 每个元素要选几个". 而我们可以把这个问题理解为: 一共有 个位置, 个组, 我们给每个组分配多少个位置?
Formalize 这个想法即: 对于第 个 object, 我们给它分配 个位置. 所有满足条件的 combinations 可以 represent by:

到这里我们想到一个经典的问题: stars and bars. 即: 把 个星星分成 个组, 每个组至少有 1 个星星. 这个问题等价于: 把 个星星和 个隔板排成一排, 然后选择 个隔板的位置.
问题是: 我们这里, 一个组可以有 个 stars; 但是这是小问题. 因为我们可以 set , 问题等价转化为:

这就强制每个组至少有一个 star, 于是可以使用 stars and bars 的方法来解决. 即: 用 个隔板隔开 个星星 (有 个空档). 因而, 满足条件的 combinations 的数量为:

Example 1.5

有 5 种口味的 ice creams. 一个人随机选择 20 个 scoops. 求: 每种口味至少被选中一次的 probability.

Solution

即从 种口味中选取 个 combinations with repetition. 于是 sample space 的大小: .
而满足条件的 combinations: 即每种口味我们都预选一个. 然后再从 种口味中选取 个 combinations with repetition.

1.1.5inclusion-exclusion principle

Proposition 1.5 (inclusion-exclusion principle)

如果 是 measure space 意义下的一个 finite measure space, 那么对于任意 的, 有:

Remark

这里的 等 index 意思就是考虑所有可能的 combinations, 不考虑顺序, 和下标的顺序没有关系. 比如一共有三个集合 , 那么 就是 的并集.
这个定理是 countable additivity 的直接推广.

Example 1.6

(Divisibility) 令 , 我们随机取一个 , 求 is divisible by 2 or 3 or 5 的概率.

Solution

令 为 是 2, 3, 5 的倍数的 events. 即:

于是我们要计算的是:

Example 1.7 (matching problem)

假设有 个人参加一个 event, 每个人都上交了一顶帽子; 现在再把帽子随机地发给每个人, 求没有人拿回自己的帽子的概率.

Solution

令 为第 个人拿回自己的帽子的事件. 则我们要求的概率是: .

由于:

我们可以得到:

Remark

当 的时候, 这个结果趋向于 . (By Taylor’s expansion of .)

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 , 我们称之为 probability measure (概率测度, 即概率).
而这里的 我们称之为 sample space (样本空间); 这里的 -algebra , 我们称之为 event space (事件空间).
任意的 都是一个 event, 但是概率论中只考虑 , 即 measurable event. 为简化, event 这个单词就指 measurable event.

Remark

回顾一下 measure space 的定义:

Remark

对于 discrete 的 prob space 而言, 通常选取 , 即 的任意子集都是一个 event.

Remark

概率空间的现实意义是: 一次 experiment 的所有可能的结果的集合, 以及每个结果的概率.

是一次的可能的结果结果的可能性

Example 1.8

(dice roll) 如果我们掷一个 6 面的骰子, 那么样本空间 . 一个可能的事件是 . 如果假设骰子是公平的 (所有结果都是等可能的), 那么事件 的概率是

根据我们 measure-based 的定义, 这一结果自然 follows from countable additivity of .

Example 1.9

三个人独立地掷一个 6 面的骰子, 求第三个人掷出的点数等于前两个人的点数之和的概率.

Solution

样本空间 . event: .
这个 event 有 15 个 elements:

因此, 概率是:

Example 1.10

两个人计划在 12:00 到 1:00 之间碰面. 他们各自都会在期间的某个时间点到达. 求: 他们彼此不会等待对方超过 10 分钟的概率.

Solution Samplespace Ω= { ( x , y ):0 ≤ x ≤ 60 , 0 ≤ y ≤ 60 } =[0 , 60] × [0 , 60]  E = { ( x , y ) ∈ Ω: | x − y |≤ 10 } : x y 60 60 | x − y |≤ 10 Figure1.1:  P ( E )= m ( E ) m (Ω)=3600 − 2500 3600=11 36

1.2.1conditional probability and Bayes’ theorem

Definition 1.6 (conditional probability)

对于 probability space , 给定一个 event , 如果 , 我们定义 conditional probability of an event given 为:

Proposition 1.6 (decomposing probability of intersection of events)

令 为一个 seq of events, 对于任意 :

Proof

Naturally follows from the def.

Theorem 1.2 (law of total probability)

令 为一个 seq of pairwise disjoint events, 如果 , 那么对于任意 event :

Proof

Remark

就等于 , 也就是在 这个区域上, 的 measure. 因而 disjoint union 之下就是 的完整 measure.

Theorem 1.3 (Bayes theorem)

If such that , then

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

令 表示: car 在 号门后面; 事件表示: 主持人打开 3 号门. 我们要求的概率是在事件 发生的情况下, 的个概率, 即 . 它的大小是:

因而, 换门是有利的.

Remark

这是一个非常反直觉的例子. 我们直觉肯定会觉得: 一共 1 辆车和 2 个山羊, 主持人帮忙排除掉了一个山羊, 那么剩下来的两个里面我们二选一, 肯定是 概率, 而这个 "更换与否" 就是二选一的抉择. 但其实不是这样的.
在第一次选择和第二次选择之间, 主持人带来了额外的信息.

从条件概率的视角来看:

也就是说, 主持人打开 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 有一个限制, 就是 enforce .
但是, 难道 就不能定义条件概率了吗? 我们考虑一个连续情况: 在 中任意选择一个点, 求: 该点位于单位球面上的概率. 显然, 这个概率是 0. 但是, 如果我们知道该点位于单位球内, 那么该点距离原点的距离为 的概率应当为 . 也就是说, 即使在 的情况下, 我们也希望定义 .
在考虑这个定义之前, 首先我们发现: 基于我们先前定义的 conditional probability, 我们可以获得一个新的 probability space:

Definition 1.7 (conditional probability space and trace -algebra)

对于给定的 prob space , 给定一个 event 且 , 我们定义 conditional probability space as the triplet , 其中:

继承自原空间的 -algebra , 并被称为 trace -algebra on .
容易验证, 这个 triplet 是一个 prob space.

Remark

当我们把整个 prob space 限制在 event 上时, 本质上是在做一个 Radon-Nikodym derivative 的操作.
定义 , 那么对于任意 event , 有:

因而和我们的直觉一样, 条件概率是通过一个 density function 来重新加权原本的概率测度.

既然这样, 我们能否直接从一个新的 prob space 出发, 来定义条件概率呢? 这就是 Kolmogorov 的定义:

Definition 1.8 (Kolmogorov definition of conditional probability)

对于给定的 prob space , 设 是一个 sub--algebra. 对于 event , 条件概率 是一个 -measurable 的随机变量, 其满足对于任意 , 有:

显然, 当 时, 这个定义和我们之前的定义是等价的.
这个 random variable 在 -a.s. 意义下是唯一的.

Remark

条件概率 这个测度是 这个测度相对于背景测度 在子信息流 下的 Radon-Nikodym derivative, 也就是一个密度函数.
这个定义里没有指明, 给定一个 event , 如何去确定 以及 . 虽然这是一个抽象的存在性 & 唯一性定义, 但是标准的做法是:

Remark

Further issue: Borel-Kolmogorov paradox.
即便是这个定义, 也会出现问题.
给定一个事件 , 如果 , 则 的取值取决于我们将 嵌入到哪一个随机变量 中. 不同的随机变量 即使都能产生相同的事件 , 它们生成的子 -代数 和 却不同, 导致最终确定的条件概率 .
为了解决这个问题, 可以引入更精细的结构, 比如说 regular conditional probability, 以及 disintegration theorem. 不过此处不展开了.

1.2.3independence of events

Definition 1.9 (independence of events)

对于 prob space , 两个 events 如果有

则称 和 是 independent 的.
更加 generally, 对于任意 collection of events , 如果对于任意有限子集 , 有

则称 是 mutually independent 的.

Remark

根据条件概率的定义, 容易得出: 两个 events independent 的定义等价于 , 即事件 的发生与否不影响事件 发生的概率.

Proposition 1.7 (independence of two events 的等价定义)

对于 prob space , 两个 events independent iff:

Proof

Directly follows from the definition of conditional probability.

因而 independence of two events 的定义等价于: 事件 的发生与否不影响事件 发生的概率 (反之亦然).

将它推广到多个事件: 即任意一个事件的发生与否都不影响其他事件发生的概率.

Remark

我们从 measure 的角度看待两个事件的 independence: 首先 是 trivial case, 而如果 , 那么 independence 其实可以化为一个等式:

意思是: 事件 在 这个 set 中占据的 measure 比例, 完全等于事件 在整个空间 中占据的 measure 比例; 也就是说, 事件 的发生并没有改变事件 在空间中的 measure 分布.

因而, 这两个集合在 measure (probability) 的意义下是完全解耦的, 这就是 independence 的 information geometric 意义.

Proposition 1.8

如果 events 和 independent, 则 和 也是 independent 的.

Proof

Example 1.14 (Pairwise Independence vs. Mutual Independence)

一组事件 如果是 mutually independent 的, 则它们两两 independent. 但是反过来不成立.
即: 即便对于任意 , 有 , 也并不意味着这些事件是 mutually independent 的.
下面为一个 counterexample: 考虑掷两个骰子. 令事件

我们发现: , 因而 并不 mutually independent. 然而, However, and , 因而它们两两 pairwise independent.

Remark

这个反例能够成功的理由是: 事件 (总和) 和事件 (第一个骰子) 以及事件 (第二个骰子) 分别都是独立的, 因为知道了其中一个并不会影响另一个的概率. 但是, 一旦我们知道了 和 的值, 那么 的值就被完全确定了 (因为总和就是两个骰子的和). 因而, 三个事件并不 mutually independent.
(注意: 如果 事件不是和为 7 而是一个小于 7 的数, 那就不是了, 因为如果我们知道第一次是 6, 那么和就不可能是 6, 那么就也失去了 pairwise independence).
这个例子说明了, mutual independence 是一个比较强的条件. 我们可以把这三个事件看作是对结果空间的约束:

这个例子提醒我们: 独立性不是一种可以由低维向高维简单“归纳”的性质. 一个系统可以局部解耦(两两独立, 但在全局尺度上却存在强耦合. 总之 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 , 一个 random variable 是一个 -measurable function(Borel measurable function).

Remark

回顾 (Borel) measurable function 的定义: 即对于任意 , 有 ; 由于是在 real space 上, Borel measurable 也可以简化为: 对于任意的 open ray , 有 .

例如: 是一个 (Borel) measurable function, 因为对于任意 open ray , 是一个 interval (either or ).

并且 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

在一副扑克牌中抽一张, 那么每一张的概率都是 . 但是如果我想知道抽到的牌的价值, 那么我就需要一个 random variable 来给每一张牌赋予一个 weight; 比如说, , , , .

Question: 为什么对于 assigning weights 的行为, 我们一定要求它是一个 (Borel) measurable function 呢? 普通的给 outcomes 以 weights 的行为 (任意一个 function ) 不行吗?

Answer: 因为我们想要知道 的值在一个范围 , 比如 之内的 probability (which is defined on 原本的 prob measure 上的) 是多少. 而只有每一个这样的范围集合的 preimage 都是 中的事件, 我们才能够通过 来计算这个 probability; that is, 我们需要这个 是一个 measurable function.

因为这一切都是建立在我们以 measure theory 的 framework 来定义 probability 的基础上的.

下面是一个简单的 proposition: 我们可以把多个 random variables 以一种 Borel measurable 的方式组合起来, 那么就成为一个新的 random variable.

Proposition 2.1 (以 Borel measurable 的方式组合起多个 random variables)

Prob space 上的 random variables , 任取 Borel measurable function ,

也是一个 random variable.

Proof

我们在 measure theory 中证明过: 对于任意的 finite seq of Borel measureable functions , 其各作为一个维度组成的函数 也是一个 Borel measurable function (from 到 ).
而这里的 就是 , 是两个 Borel measurable function 的 composition, 因而也是一个 Borel measurable function (即 random variable).

Remark

以一种 Borel measurable 的方式组合多个 random variables, 这个函数也仍然是一个 random variable.

这个 proposition 看似没有什么卵用, 但是它其实是我们之后构造 random variable 的一个重要工具. 很多我们默认合法的行为, 它都作为基础.

比如我们:

2.1.2由一个 random variable generate 的 -algebra

Definition 2.2 (-algebra generated by a random variable (measurable function))

对于 random variable , 其 generate 的 -algebra 定义为

这个集合 是一个 -algebra, 是一个 trivial truth. 因为里面所有的 set 都是 的 preimage, 而 是一个 measurable function, 因而任意的 .

=2em 这个 也是让 成为一个 measurable function (即 random variable) 的最小的 -algebra. 它的意义是: 当我们仅仅观察到 的取值时, 我们所掌握的关于 underlying sample space 的全部 "information".

Remark

我们知道, 一个 -algebra 可以看作是一个 information structure: 它是对 underlying sample space 进行划分的一个工具.
最大的 -algebra , 即 power set, 是最细的划分, 也是信息量最大的 -algebra. 它把每一个元素都区分开来. 对于 discrete 的 sample space, 通常我们的 probability measure 就是定义在 power set 上的, 正是因为我们希望区分每一个 outcome.
而给定一个 prob space , 原本的 prob measure 所 base on 的 -algebra 就成为了一个基准的 information 的颗粒度: 哪些事件是我们可以区分, 即可以在上面定义 probability 的.

而一个 random variable 可能会把多个 outcomes 映射到同一个值上, 也即把多个 events 映射到同一个值上, 从而把这些 events 区分不开来. 因而, random variable generate 的 -algebra 就可能是一个更粗的划分. 当我们取这些 events 所映射到的同一个值的 preimage 的时候, 取到的是它们的 union, 也就是它们中最大的一个.

比如

Example 2.2

掷一次骰子, 所有可能结果为 sample space:

而我们定义一个 random variable 来表示掷出的点数的奇偶性, 即:

那么它 generate 的 -algebra:

因为 这些事件都被映射到了同一个值 上, 即 这些事件都被 这个事件吸收了, 它们在这个 random variable 的映射下是区分不开的. 这就代表了这个 random variable 所蕴含的信息颗粒度: 我们只能区分掷出的点数是奇数还是偶数, 但是无法区分具体的点数是多少.
至此我们知道: 一个 random variable 的 generate 的 -algebra 表示了这个 random variable 对 underlying sample space 所能区分的 information granularity (信息颗粒度).

除了能表示 information granularity 以外, 还有什么实际用处呢:

至此关于 random variable, 我们已经讨论了很多 general 的刻画. 现在我们来讲一点实用的:

2.2distributions

2.2.1distribution and cumulative distribution function

Definition 2.3 (probability distribution)

对于 random variable on , 其 probability distribution 是 对于 的 pushforward measure, 记作 . 即

我们 write:

Remark

看着有点不直观. 实则我们拆解:

接下来的定义和例子会更加直观.

Definition 2.4 (distribution function (也称 cumulative distribution function, cdf))

对于 random variable , 其 cumulative distribution function 是 这一函数的 distribution function, 记作 . 即对于任意 , 有

Remark

即 我们也会简写为 .
的意义是: random variable 的值不超过 的概率.

Example 2.3 (geometric probability)

Fix . 我们在正方形区域 上均匀地随机选取一个点 .
我们 define 随机变量: by . 求 的 distribution function .
这很简单: 对于 ,

因为

注意: 在这个例子中, probability measure 是 Lebesgue measure on . 很多时候我们在计算 RV 的 distribution function 的时候, 都是直接直观地计算 . 但是在稍微复杂一些的例子中, 我们需要对各个条件的 formalization 更清楚一点.

Theorem 2.1 (distribution function 的性质)

对于 random variable , 其 distribution function 满足:

Proof

其他都显然. right-continuity 是源自 measure 的 continuity from above, 我们证明一下: 考虑一个单调递减序列 , 令 seq of events , 注意这是一个嵌套递减的 set seq. 通过 的 completeness 容易证明:

由 measure 的 continuity from above, . 也即 .
而下面一条 同理是源自 measure 的 continuity from below.
那么 是 natural 的 (by def).

Remark

我们此时心里会默认一件事情: 一旦知道了 RV 的 distribution function , 就知道了 的完整 distribution . 这个直觉是对的.
回忆一下: 我们在 measure theory 中, 证明 Carathéodory extension theorem 的时候, 证明过一个 theorem, 以它作为工具才把 premeasure 从一个 algebra extend 到一个 measure on the generated -algebra:

Theorem 2.2 (Dynkin’s theorem)

设 是一个 -system (closed under finite intersection), 是一个 -system (closed under complementation and countable disjoint union), 如果 , 那么 .

我们考虑所有的 half-open interval 组成的集合 , 这个集合 generate the Borel -algebra, 并且还是一个 -system, 即: 它 closed under finite intersection:

然后考虑

即两个 measure 一致的 collection of sets. 容易证明, 这个 是一个 -system, 并且 .
从而,

并且 对于任意 .

因而:

Corollary 2.1 (distribution function determines distribution )

对于 random variable , 其 distribution function 确定了 distribution ; 即如果两个 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 , 如果存在一个 countable set 使得 , 那么 是一个 discrete random variable.

Remark

就是说, 的 range a.s. 是 countable 的 (允许 null set 上的值不在这个 countable set 里, 但是这是 measure theory 下的概念, 所以这些都可以忽略不计).

Remark

对于 discrete random variable , 其 distribution function 是一个 step function, 只有 countable 多个 jump discontinuity, 每个 jump 的大小就是 在那个点的 probability mass.
因而, 对于 discrete random variable , 通常考虑其 probability mass function (pmf) 更加有用:

Definition 2.6 (probability mass function (pmf))

对于 discrete random variable , 其 pmf 定义为

这个 pmf 就是 的 jump size function. 当然, 根据定义明显可得:

值得一提的是, 这个 pmf 其实就是 的 distribution 对于 counting measure (for range of )的 Radon-Nikodym derivative:

Proposition 2.2 (pmf 是 distribution 对于 counting measure 的 Radon-Nikodym 导数)

对于一个 discrete random variable , 假设其 range 是 countable set , 则我们定义 counting measure on 为:

那么, 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 是一个 continuous random variable, 如果它的 cdf 是一个 absolutely continuous function.

Remark

回顾 absolutely continuous function 的定义, 这是一个比较复杂的定义: 对于任意 , 都存在 使得任取 finite collection of disjoint intervals , 都满足:

这是 uniform continuity 的一个加强版本. uniform continuity 对应的是 的情况, 即: 任意的区间上, 只要长度足够小, 就能保证 在这个区间上的增量足够小; 而 absolutely continuity 更严格: 即便是任意数量的分散的区间, 只要总长度足够小, 就能保证 在这些 interval 上的增量的总和足够小.

这个定义有点麻烦, 不过存在等价的条件. 为此我们要 recall 一系列定义与结论, 详细请见: notes on measure theory, module 12: differentiation on :

这几行字浓缩了 measure theory 的 differentiation theory 的两个星期的内容… 具体见上文 notes 链接, 都有详细证明. 而我们这里就利用起最后这一条结论. 首先, 我们 state 一件事:

Lemma 2.1 (cdf 一定是 的)

任意的 random variable 的 cdf 都是一个 function.

Proof

依旧见 notes, 有一个关键 lemma: 当且仅当它可以表示为两个 monotone increasing function 的差. 而 random variable 的 cdf 自身是一个 non-decreasing function, 因而首先 .
其次, 由 2.1 我们知道, 是 right-continuous 的, 且 . 因而 .

因而我们自然得出:

Theorem 2.3 (一个 random variable 是 continuous random variable 的充要条件)

Proof

即 remark 的最后一条结论. 由于 是一个 function, 因而 是 -a.e. differentiable 的.
并且, iff 它满足 FTC of Lebesgue integral.

Remark

因而, 在简化的教材中, 通常会直接定义: 一个 random variable 是 continuous random variable, 如果存在一个 使得 for all . 这里其实是跳过了我们刚才的所有步骤, 直接使用了这个等价条件. 因为这个条件也等价于:

Definition 2.8 (probability density function (pdf))

对于 continuous random variable , 其 probability density function 定义为 的 (-a.e.)导数, 即

我们最后梳理一下.

以及, 显然 pdf 有以下性质:

Proposition 2.3 (probability density function 的性质)

对于 continuous random variable with pdf ,

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, 也就等价于 一定是一个 absolutely continuous function. 而仅仅 continuous 什么都无法保证.

我们这里给出一个 counterexample: Cantor distribution. 它的 cdf 是 continuous 的, 但是它并没有能够满足 FTC of Lebesgue integral (返回原函数) 的 a.e. derivative, 因而没有 pdf.

Example 2.4 (Cantor distribution)

令 be 独立同分布 (i.i.d.) 的随机变量 . 然后定义:

它刻画的是:

具体而言:

从而, 的 range 是 Cantor set, recall: 这是一个 measure zero 的 uncountable set, 其 cardinality 是 continuum (与 等势).

它也表示了: 三进制小数中, 所有完全不包含数字 1 的小数的集合.

由于其 uncountability, 对于任意单点 都有 , 因而 在 上处处连续; 并且容易证明: 在 处的导数 . (因为对于 中的任意被挖掉的区间, 在这个区间上是 constant 的).

然而, 却不满足 FTC of Lebesgue integral. 比如反例: , 但是

因而 没有 pdf, 也就不是 continuous random variable.

对于 Cantor distribution 这个例子, 我们称这样的 random variable 是一个 singular continuous random variable:

Definition 2.9 (singular continuous random variable)

对于 random variable , 如果 的 cdf 是一个 continuous function, 并且 (即存在一个 measure zero 的 Borel set 使得 , 也等价于 的导数 a.e.), 那么我们称 是一个 singular continuous random variable.

Remark

singular continuous random variable 的意思是, 在 上, 的值 a.s. 落在一个 measure zero 的 set 上, 也就是说它的 cdf 大部分是平的, 只有在 measure zero 的 set 上才有 jump.

这个例子向我们说明了: 除了 discrete random variable 和 continuous random variable 以外, 还有其他的奇异的 random variables. 而下面这一定理刻画了任意的 random variable 的结构:

Theorem 2.4 (Lebesgue Decomposition Theorem)

对于任意 random variable , 其 distribution 可以唯一分解为三个 mutually singular 的 measure 的和:

其中 是 absolutely continuous measure, 是一个 singular continuous measure, 是 discrete measure.

Proof

TODO.

Remark

我们也可以这样展开:

其中 是 的 pdf, 是 的 pmf, 而 由于其奇异性是无法分解的.

2.3expectation and variance

Distribution 是一个 random variable 的完整刻画, 而这一节我们来谈一谈 expectation 和 variance, 这是一个 random variable 的两个重要的数值特征: 它的均值和离散程度.

最后我们会谈一谈 空间: all square-integrable random variables; 以及它的一个重要 subspace : 所有 square-integrable 的 zero-centered random variables. 它们都是由 random variables 组成的 Hilbert space, 并且在其中, expectation, variance, covariance 都会得到一个非常自然的 interpretation, 展现这个空间的几何结构.

2.3.1expectation and variance 的 definition 和计算方法

随机变量的 expectation 是它 w.r.t. 它所在概率空间 prob measure 的积分, 表示它的值的 prob-weighted average;

而其 variance 是 这个 induced RV w.r.t. 的积分, 表示 离它的值的 weighted average 的聚集程度:

Definition 2.10 (expectation and variance of random variable)

对于 random variable , 其 expectation 定义为

其 variance 定义为

Remark

, 因而 可以看作是 的值的 weighted average, 其中权重就是每个 sample point 在这个原 prob space 上的概率.

Note that: 未必是 finite 的. .

要计算 discrete random vairable 的 expectation 和 variance, 直接 by def, sum 就可以:

Proposition 2.4 (discrete random variable 的 expectation 和 variance)

对于 discrete random variable with pmf ,

非常简单.

但是对于 continuous random variable 而言, 怎么求呢? 这里有一个 w.r.t. prob measure 的积分, 有点难计算. 我们更希望计算 w.r.t. Lebesgue measure 的积分, 这样就可以用一些经典的方法来算它了.

为了实现这个目标, 我们首先需要一个工具来过渡一下:

Lemma 2.2 (用 distribution ( 的 push-forward measure) 计算 expectation)

对于 random variable , 如果 integrable, 那么其 expectation

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 with pdf , 如果 和 都是 finite 的, 那么

并且, 对于任意的 measurable function , 都有

Proof

由于 , 而对于 ctn random variable,

从而得证.

Proposition 2.6 (expectation 的性质)

令 为 integrable random variables, 则

这三条性质都容易验证, 直接 follow from linearity of Lebesgue integral, monotonicity of Lebesgue integral, triangle inequality of Lebesgue integral.

Proposition 2.7 (computing variance)

对于 random variable with finite expectation,

By def, 容易验证.

2.3.2 与 covariance and correlation as inner product and cosine

我们 recall measure theory 中的一丢丢 functional analysis 的内容:

即

where 表示 almost sure equality 的等价类, 即

即把所有 a.s. 相等的 random variables 都看作相等.

我们知道, 这是一个 Hilbert space, 即一个 complete inner product space, 其中

虽然这个空间已经有一定的 information geometry 了, 但是我们实际上希望能够用一个结构来描述两个 random variables 之间的线性相关性:

而 这个空间作为一个 Hilbert space 时, 两个 random variables 之间的距离其实是它们作为函数的相似性而不是它们变化趋势 (波动) 的相似性.

比如考虑 和 , 它们的线性相关性其实是 1, 即变化趋势完全相同, 但是它们在 中的 cosine similarity 却是

我们希望的是这个 cosine similarity 应当是 1. 即, 应该忽略掉绝对数值, 而是考虑这两个 random variables 的变化趋势.

因而 solution: normalize 每个 random variable, 把它们移动到均值为 0 的位置! 即: 把每个 center 为 . 这就是:

Definition 2.11 (zero-centered square integrable random variables )

我们定义:

注意, 这个空间是 的一个 subspace.

并且, 我们可以通过把每个 center 为 的行为, 把 从 投影到 这个 subspace 上.
而投影+度量的行为, 就是计算:

Definition 2.12 (covariance)

给定两个 random variables , 我们定义它们的 covariance 为

Remark Geometricintuitionofcovariance:randomvariablessamplepoints ( x , y ) . covariance,samplepointstendencyline; covariance,samplepointstendencyline; covariance0,samplepointstendencyline. Cov( X,Y ) > 0 Cov( X,Y ) < 0 Cov( X,Y )=0 Figure2.1: : covariancelinearrelationship,,nonlinearrelationship.independence,covari-ance0, X Y dependent., ( X , Y ) asagraph,covariance0,. x y x 2 + y 2 = r 2 Cov( X,Y )=0 ,but X,Y aredependent Figure2.2:  Covariancerandomvariablesscale,randomvariableslinearrelationship.linearrelationshipnormalizebynorms, [ − 1 , 1] correlation.

我们容易发现一件事情:

Theorem 2.5 (covariance is a positive-semidefinite symmetric bilinear form)

Proof

By def.

而当我们把空间限定在 上时,

Theorem 2.6 ( 为一个 Hilbert space, with covariance as an inner product)

为一个 Hilbert space, 即: covariance 在其上是一个 inner product (positive definite symmetric bilinear form).

Proof

很显然. 因为在 space 上, 一个 constant random variable 的 variance 是 0, 但是它并不是一个零函数; 而在 space 上, 所有的 random variables 都是 zero-centered 的, 因而 constant random variable 就是零函数了. 从而 covariance 在 space 上是 positive definite 的, 从而是 inner product.

而在 上, 两个 random variables 之间的夹角 的 cosine, 就是它们真正的 linear relationship 的强弱程度, 因而我们把它叫做 correlation:

Definition 2.13 (correlation)

显然,

where 是 之间的夹角. And we have:

从而有以下显然的结论:

Proposition 2.8 (properties of correlation)

做一个总结:

L 2 space L 20 innerproduct X , Y E [ XY ] Cov ( X , Y ) (covariance)norm X E [ X 2 ] Var ( X ) (standarddeviation)cosinesimilarity E [ XY ] √ E [ X 2 ] √ E [ Y 2 ] Cov ( X , Y ) √ Var ( X ) √ Var ( Y ) (correlation)

求两个 random variables 之间的 correlation, 就是把它们都 center 到 zero-centered 的位置 (即投影到 space 上), 然后计算它们在 space 上的 cosine similarity.
此时我们看到 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):

就是 的 distribution 对于 counting measure of range 的 Radon-Nikodym derivative:

因为假设 的 range 是 , 那么对于任意 Borel set ,

下面我们给出一些经典的 discrete random variable 的例子, 以及它们的 pmf 和 cdf.

2.4.1Bernoulli distribution and Binomial distribution

Example 2.5 (Bernoulli distribution)

令 , .
令 , 来表示这两个 singular 事件的概率.
令 , 分别表示 success 和 failure.
那么显然可以计算:

我们称 为一个 Bernoulli probability space (它 model 了一个 Bernoulli trial, 即一个 random experiment with two possible outcomes: success 和 failure)
称 这个 random variable 为一个 Bernoulli random variable, 并称 的 distribution 为一个 Bernoulli distribution, 写作

这是最简单的 random variable 和 distribution 了. 它 model 的是: 比如我们 toss 一枚 biased coin, 以 的概率得到 heads (success), 以 的概率得到 tails (failure).

Proposition 2.10

如果 , 那么 , .

显然.

Example 2.6 (Binomial distribution)

我们 independently repeat 次 Bernoulli trial, 每次 trial 的 success probability 都是 .
考虑:

为 success 的总次数. 那么 是一个 discrete random variable 容易计算出 的 pmf:

我们称 的 distribution 为一个 Binomial distribution, 写作

它 model 的是: 比如我们 toss 一枚 biased coin 次, 得到 heads 的总次数.

Proposition 2.11

如果 , 那么 , .

Proof

由于

可以得到

然后计算得 . 但是这是比较麻烦的方法. 也可以利用 , 其中 i.i.d 这个事实来计算, 那么直接通过线性叠加 Bernoulli random variable 的 expectation 和 variance 就可以了.

2.4.2Geometric distribution and Negative Binomial distribution

Example 2.7 (Geometric distribution)

我们 perform independent Bernoulli trial, 每次 trial 的 success probability 都是 .
考虑 random variable 表示第一次 success 发生的 trial number. (也就是等于: 我们一直 trial, 直到第一次 success 发生, 那么这个 trial 的 number 就是 ).
那么 是一个 discrete random variable .
容易计算出 的 pmf:

我们称 的 distribution 为一个 Geometric distribution, 写作

它 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 都是 . (即 independent and identically distributed)
令 random variable 表示第 次 success 发生之前的 failures 的数量. (也就是等于: 我们一直 trial, 直到第 次 success 发生, 那么这个 trial 的 number 就是 , 因为 是 failures 的数量, 还要加上 个 success. ).
那么 是一个 discrete random variable .
容易计算出 的 pmf:

这是因为:最后一次 success 的位置是固定的. 我们要在前 次 trial 中选择 次作为 failures.
我们称 的 distribution 为一个 Negative Binomial distribution, 写作

它 model 的是: 比如我们 toss 一枚 biased coin, 得到第 个 heads 之前会经历的 failures 的数量.

2.4.3Poisson distribution

Example 2.9 (Poisson distribution)

考虑这一 pmf:

我们称 的 distribution 为一个 Poisson distribution, 写作

以 为例画出 pmf 示意图:

k P ( X = k ) 0 1 2 3 4 5 6 7 8 9 10 λ =3
Figure 2.3参数 的 Poisson 概率质量函数

Remark

当 时, 的 distribution 趋近于 .
考虑 , 对于固定的 :

展开组合数 :

重组项:

其中, (1) 的 limit 是 1, (2) 的 limit 是 , (3) 的 limit 是 1, 因而

这个极限行为的意义是:

因而 Poisson distribution 的意义本质上是: 给定对一个事件在固定窗口下出现的平均次数的观测(估计), 那么这个事件在这个窗口内出现 次 ()的概率是多少?
所以 Poisson 分布, 即是根据一个事件在给定 windows 内发生次数的 expectation, 来估计这个事件在该 windows 内发生次数的分布的标准方法.

Remark

Further remark: Poisson distribution 的用途.

Proposition 2.13

如果 , 那么 , .

Proof

recall 的 taylor expansion:

因而

similarly, 可以计算得

因此,

2.4.3.1Poisson distribution 的 additivity

Theorem 2.7 (additivity of Poisson distribution)

如果 , are independent, 那么

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 对于 Lebesgue measure 是 absolutely continuous 的 random variable, 等价于存在一个 pdf 使得

对于任意 都成立.

而由 可得

这里还有一个额外的结论:

Proposition 2.14

对于任意的 measurable function , 都有

Proof

下面我们介绍一些常见的 continuous random variables, 以及它们的 pdf, cdf, expectation 和 variance.

2.5.1uniform distribution: 最简单的 continuous RV

Definition 2.14 (uniform distribution)

如果 on and elsewhere, 那么我们称 的 distribution 为一个 uniform distribution, 写作

对于 uniform distribution, 很容易计算得:

Example 2.10 (uniform distribution 的 pdf 和 cdf)

考虑 , 其 pdf 和 cdf 的图像如下:

x f X ( x ) a b 1 b − a
Figure 2.4区间 上均匀分布的概率密度函数
x F X ( x ) a b 1
Figure 2.5区间 上均匀分布的累积分布函数

2.5.2exponential distribution: geometric distribution 的 continuous version

Exponential random variable model 的是一盏灯的 remaining lifetime. 它 assume: 任意时间, 这盏灯有一个 constant 的磨损速率.

假设它的磨损速率是 for all , 那么在任意时间 上:

即 ODE:

with initial condition .

我们知道这个 ODE 的 solution 是:

Definition 2.15 (exponential distribution)

我们称 为一个 exponential random variable with parameter , 如果它的 pdf is given by:

写作

刚才已经计算出, exponential random variable 的 distribution 为

容易验证, when , 以及 when

计算其 expectation:

并 notice: . 因而 recursively get:

即: 从而:

x f X ( x ) f X ( x ) = λ exp( − λx )
Figure 2.6指数分布的概率密度函数
x F X ( x ) F X ( x ) =1 − exp( − λx )
Figure 2.7指数分布的累积分布函数

Remark

exponential 随机变量是 geometric 随机变量的 continuous analogue. 因为 geometric random variable 是假设一个事件在每个时间点以 constant 的概率发生, 用来 model 它第一次发生的时间;

而 exponential random variable 其实也是, 只是 on a continuous time scale: 它假设的 constant 损坏率其实 implies: 在任意时间, 如果灯还没坏, 那么灯此刻坏掉的概率是 constant 的.

Theorem 2.8 (memoryless property of exponential distribution)

任意 continuous RV,

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: 如果我们使用一个用过 2 hours 的 battery, 则 want:

Notice:

2.5.3Gamma distribution: negative binomial distribution 的 continuous version

recall Gamma 函数:

这个函数有一个重要的性质:

因而对于 , 我们有:

Gamma 函数就是 factorial 函数的 continuous generalization.

Definition 2.16 (-distribution)

如果 continuous random variable 的 pdf 是:

那么我们称 服从 distribution, 写作

其中 称为 shape parameter, 称为 rate parameter.

distribution 的 cdf 这样求: for ,

and for , .

Expectation:

(since .) 同理我们可以计算得: 从而

容易发现: 当 时, distribution 就退化成了 exponential distribution.

而当 是一个正整数 时, distribution 实际就是 个 independent exponential distribution 的 sum:

Proposition 2.15 (Gamma distribution as a sum of independent exponentials)

Let be i.i.d., 则

Proof

证明这一结论除了硬算之外, 更快的方法是通过 moment generating function. //TODO

Remark Gammadistributioni.i.d.exponentialdistributionsum;exponentialdistributiongeometricdistributioncontinuousanalogue; Gammadistributionnegativebinomialdistributioncontinuousanalogue. rateparameter λ =1 shapeparameter α Gammadistribution x f X ( x ) Gammadensities, λ =1 Figure2.8:  λ =1 shapeGamma x F X ( x ) Gammacdfs, λ =1 Figure2.9:  λ =1 shapeGamma α =1 ,Gamma,pdf;  α ,pdf0,,; cdf α ,

2.5.4normal random variables: 最重要的 continuous RV, 任意 RV 的叠加极限

Definition 2.17

我们称 is normally distributed with parameter and , if the pdf of is given by:

写作:

特别地, 当 时,

被称为 standard normal distribution.

为什么 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:

Theorem 2.9 (De Moivre–Laplace theorem)

令 , 则

(Proof: later chapters.)

Example 2.12

Toss a million times 一个 fair coin. Approximate the prob that we get more than heads:

因而:

2.5.4.0.2除此之外 need to mention: Poission distribution 当 时, 也得到 normal distribution.

这并不是一个令人惊讶的事情. 也可以用 central limit theorem 来解释. 因为 recall: Poisson distribution 有一个很重要的 property: additivity. 因而 也可以看作 个 i.i.d. Poisson distribution 的 sum 在 时的极限行为, 从而通过 central limit theorem 得到 normal distribution.

2.5.5summmaryofdiscreteandcontinuousvariablesexamples distributionpmf/pdfcdf E [ X ] Var ( X ) meaning Ber ( p ) P ( X =1)= p , P ( X =0)=1 − pF ( x )=1 − p , 0 ≤ x < 1 pp (1 − p ) Bernoullitrial(unfaircoin)Bin ( n , p ) P ( X = k )= nk p k (1 − p ) n − k , k =0 ,..., nF ( k )= k j =0 nj p j (1 − p ) n − j npnp (1 − p ) n i.i.d.BernoullitrialsGeom ( p ) P ( X = k )=(1 − p ) k − 1 p , k ≥ 1 F ( k )=1 − (1 − p ) k 1 p 1 − p p 2 BernoullitrialNB ( r , p ) P ( X = k )= k + r − 1 k (1 − p ) k p r , k ≥ 0 F ( k )= kj =0 j + r − 1 j (1 − p ) j p rr (1 − p ) pr (1 − p ) p 2 Bernoullitrial r Poi ( λ ) P ( X = k )= e − λλ k k ! , k ≥ 0 F ( k )= kj =0 e − λλ j j ! λλ fixedwindow(time/space) U ([ a , b ]) f ( x )= 1 b − a , a ≤ x ≤ bF ( x )= ⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩ 0 , x < a x − a b − a , a ≤ x ≤ b 1 , x > b a + b 2( b − a ) 2 12 uniformchoiceonanintervalExp ( λ ) f ( x )= λ e − λ x , x ≥ 0 F ( x )= ⎧⎪⎨⎪⎩ 0 , x ≤ 01 − e − λ x , x > 0 1 λ 1 λ 2 , Γ( α,λ ) f ( x )= λ α Γ( α ) x α − 1 e − λ x , x ≥ 0 F ( x )= 1 Γ( α ) λ x 0 t α − 1 e − t dt α λα λ 2 α i.i.d.exponentialdistributions( α ) N ( µ,σ 2 ) f ( x )=1 /σ √ 2 π exp( − ( x − µ ) 2 / 2 σ 2 ) noelementaryclosedform µσ 2 (/)

Chapter 3joint and conditional distributions

3.1random vector and joint distributions

3.1.1random vector

Definition 3.1 (random vector)

对于 prob space , 一个 function 如果是一个 -measurable function (即 -measurable function 在这两个 measurable spaces 上的情形), 则称它为一个 -dimensional random variable, 或者 -dimensional random vector.

通常我们将 random vector 写成分量形式

random vector 相当于在一个 prob space 上, 考虑多个重新分配 mass 的方法, 并把它们并列起来.

Proposition 3.1 (由 个 random variable 构成的 vector 是一个 random vector)

令 是定义在同一个 prob space 上的 个 random variables. 则函数 defined by

是一个 random vector.

Proof

我们在 measure theory 中证明过: 对于任意的 finite seq of Borel measureable functions , 其各作为一个维度组成的函数 也是一个 Borel measurable function (from 到 ).

Proposition 3.2 (一个 random vector 的每个分量都是一个 random variable)

令 是一个 random vector. 则对于任意 , 都是一个 random variable.

Proof

对于 是 -measurable, 我们可以将第 个分量 看作是 composition of two maps:

其中 projection map .
由于 projection map 是一个 Borel measurable function, 我们可以得出: 也是一个 Borel measurable function, 也就是一个 random variable.

Remark

上两条 propositions 说明了一个事情: random vectors 和其分量 random variables 完全相互决定.

因而, 研究一个 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)

令 为 RV from the same prob space. 即 是一个 random vector. 下面的两个对象分别将 probability distribution 和 distribution function (也称 cumulative distribution function, cdf) 推广到 random vector.

我们称 defined by

为 的 joint distribution.

而我们称 defined by

(即 restricted to the set of rectangles ) 为它们的 joint distribution function (或称 joint cdf).

joint distribution 的定义已经包括了如何从多个 random variables 的 distributions 得到一个 joint distribution. 而, 我们也可以从一个 joint distribution 的 limit behavior 得到每个 random variable 分量的 distributions, 称之为 marginal distribution:

Definition 3.3 (marginal distribution)

令 是一个 random vector. 则对于任意 , 的 distribution 被称为 的第 个分量的 marginal distribution.

我们以 为例. 得出的结论可以推广到 .

Proposition 3.3 (通过 joint distribution 的极限得到 marginal distribution)

令 是一个 random vector. 则对于任意 , 有

的 marginal distribution 也可以通过同样的方法得到.

此外, joint distribution 有其他明显的 limit behaviors:

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 的 cdf 是 absolutely continuous 的. 这个条件也等价于, 存在一个函数 使得

这个定义可以 generalize 到 random vector 上.

Definition 3.4 (continuous random vector 和 continuous joint cdf)

对于 random vector 如果 , 即它满足 absolute continuity of signed measures 中的绝对连续性条件, 即存在一个函数 使得对于任意 Borel set , 有

则称 是一个 continuous random vector.

注意: 由于是在 上, 这等价于存在一个函数 使得对于任意 , 有

Remark

这个函数 就是 continuous random vector 的 joint probability density function (joint pdf). 它是 probability density function (pdf) 在 random vector 上的对应概念. 它是 joint distribution measure 对于 Lebesgue measure 的 Radon-Nikodym derivative:

Remark

我们已经知道, 只要存在导数 可以对于任意 还原出 joint cdf 的值, 那么 就是 joint pdf, 这个 random vector 就是一个 continuous random vector.

那么这个还原积分的计算可以任意换序吗?

显然是可以的. 因为 recall Fubini’s Theorem: 只要 绝对可积, 即 , 那么对于任意的 permutation of , 我们都可以将积分的顺序换成

而我们知道, 一定是非负的, 而且积分一定是 1, 因而可以任意换序积分.

这就很舒服. 这也给出了 margin distribution 的计算方法: 只要对 joint pdf 在其他维度上积分掉就行了.

Remark

注意: 多个 continuous random variables 的 joint distribution 不一定是 continuous 的. 反例: 考虑 random vector where 则 . 而注意, 在 中的 Lebesgue measure 为 0, 而 absolute continuity 要求: 对于一个零测集, 其 测度也必须是 0 (这是 的标准定义), 因而 joint distribution 不是 continuous 的.

Proposition 3.4 (joint pdf 和 joint cdf 的性质)

令 是一个 continuous random vector, 则它的 joint pdf 和 joint cdf 有以下性质:

Proof

Example 3.1

考虑

Find 使得这是一个合法的 joint pdf, 并且计算 和 的 marginal pdfs, 以及 .

Solution

我们需要

evaluate 这两个积分:

因为 必须为 2.

计算 的 marginal pdf:

然后计算 的 marginal pdf:

最后计算 :

这两个定积分分别为:

因而

Theorem 3.1

对于 continuous random vector , 取任意 Borel measurable function , 则 是一个 random variable, 并且如果 , 则 , 则

Example 3.2

Let be a two-dimensional random variable with joint density function

Solution  y  0 < y < 2 x x < 1 , x > y / 2 x < 1 . 0 < y < 2 f Y ( y )= ∞−∞ f X , Y ( x , y ) dx = 1 y / 2 1 dx =1 − y 2 , 0 < y < 2  f Y ( y )=0 .  X continuousrandomvariable, P ( X =1 / 2)=0 . P ( X + Y ≤ 3 / 2) : ( x , y ):0 < y 2 < x < 1 , y ≤ 3 / 2 − x , 0 < y < min(2 x , 3 / 2 − x ) : 2 x =3 / 2 − x ⇒ x =1 / 2 0 < x < 1 / 2 , 2 x < 3 / 2 − x , 2 x ; 1 / 2 < x < 1 , 3 / 2 − x . P ( X + Y ≤ 3 / 2)= 1 / 20 2 x 0 1 dydx + 11 / 2 3 / 2 − x 0 1 dydx  1 / 20 2 xdx = x 2 1 / 20 = 1 4 11 / 2 3 2 − x dx = 3 2 x − x 2 2 11 / 2 =1 − 5 8 = 3 8  P ( X + Y ≤ 3 / 2)=1 4+3 8=5 8 .supportset: x y ( 1 2 , 1) (1 , 1 2 ) Figure3.1: support X + Y ≤ 3 2 .

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 被称为 independent 的, 如果对于任意的 Borel sets , 都有

注意这个定义等价于 for all points ,

即它们的 joint distribution 是它们 marginal distributions 的 product.

对于 discrete 和 continuous random variables 而言, 这还意味着 independence 等价于:

这里离散情形沿用 discrete random variable 的定义. 详细而言:

Theorem 3.2 (independence via joint-density factorization marginal densities)

令 是两个 random variables.

Proof

discrete case: 显然可得.

continuous case:

因而对于 independent 的两个 random variables, 固定 , 那么联合密度函数 就是 的边际密度函数 乘上一个常数 .

Remark

Recall independence of events 的定义:

也等价于对于任意的 Borel sets where , 都有

即: 一个事件发生与否都不会对另一个事件发生的概率产生任何影响.

而再看到两个 random variables independence 的定义是:

这个定义也当然等价于:

Proposition 3.5 (independence via conditional distribution: marginal distribution)

两个 random variables 是 independent 的, iff: 对于任意的 Borel sets , 如果, 则

即: 的 conditional distribution, 不论给定 的任何信息, 都等于 的 marginal distribution.

所以它实际上意义是: 知道一个 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. 则 是 independent 的 iff: 和 按 -algebra generated by a random variable (measurable function) 分别生成的 和 中分别任取一个事件, 这两个事件都是 independent 的. 即:

这严格说明了: 两个 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)

令 是一个 random variables 的 family, 其中 是一个 index set. 则如果对于任意的 finite subset , 以及对于任意的 Borel sets , 都有

则称这个 family of random variables 是 independent 的.

注意: joint mass & density 的 factorization 也可以推广到多个 random variables 上. 有一件事情值得说明: 这里定义的是mutual independence, 也就是说, 对于任意的 finite subset , 它们的 joint distribution 都 factorizes into product of marginal distributions.

而两两 independent 的 random variables family 不一定是 mutual independent 的. 即: 如果对于任意的 , 和 是 independent 的, 并不意味着对于任意的 finite subset , 是 independent 的.

举个例子:

Example 3.3 pairwise independence does NOT imply mutual independence

假设我们抛掷两枚公平的硬币. 令 是两个 independent 的 random variables, 且都服从 uniform distribution on . 即:

现在, 我们定义第三个 random variable 为前两者的 product:

容易验证: 两两 independent, 但不 mutual independent. 因为如果只是知道 的值, 那么我们对于 的值完全没有信息 (因为有一个完全随机的 没有任何已知信息); 同样, 如果只是知道 的值, 那么我们对于 的值也完全没有信息;

但是, 如果我们同时知道 和 的值, 那么 的值就完全确定了.

这说明 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)

令 是两个 random variables. 则 是 independent 的 . 但是 不一定 是 independent 的.

Proof

Remark ,independence.covariancelinearrelationship.:? x y x 2 + y 2 = r 2 Cov( X,Y )=0 ,but X,Y aredependent Figure3.2: covariance0,independent.covariance,independence.

刚才说到, 两个 random variables 的 independence 显然 imply . 而 BTW: 这个性质其实可以 generalize 到任意 finite number of independent random variables 的 product 上, 并且我们可以在这些 random variables 上任意地施加 Borel measurable functions, 只要保证这些函数的 expectation 是 finite 的,

Theorem 3.3 (independence expectation is closed under product)

令 是一个 independent 的 random variables 的 family, 则对于任意的 finite subset , 以及对于任意的 Borel measurable functions , 如果 for all , 则

特别地, 取每个 , 则

Proof

令 . 由于 是 independent 的, 它们的 joint distribution 是其 marginal distributions 的 product measure:

根据 Change of Variables Formula,

由于被积函数 是变量分离的, 根据 Fubini’s Theorem 可以把积分分解成多个积分的 product:

其中每一项都是.

Remark

recall: expectation is a linear operator (因而 linearity 是 regardless of independence). 但是它不一定是一个 multiplicative operator.

而这里我们说, 如果 random variables 是 independent 的, 那么 expectation 就是一个 multiplicative operator.

实际上: 当这些 Borel measurable functions 全都 bounded 时, 这个定理其实反向也是成立的:

Theorem 3.4

令 是一个family of random variables. 如果对于任意的 finite subset , 以及任意的 bounded Borel measurable functions , 都有

则这个 family of random variables 是 independent 的.

Proof

不妨特取 indicator functions. 对于任意的 Borel sets , 令 , . 代入等式得到:

注意到 . 根据 expectation of indicator function 等于 probability, 我们立刻得到:

注意: 并不是 bounded 的 function, 因而 uncorrelation independence.
OK. 以上是 pretty much general properties of independence. 最后我们看一下, 对于 discrete 和 continuous random variables 而言, independence 的 characterization 具体长什么样子.

3.2.4discrete RV independence 的 characterization

Remark

关于两个 discrete random variables 是否 independent 的判断, 还有一个直观的方法.

Proposition 3.8 (discrete RV independence 的 characterization)

两个 discrete random variables 是 independent 的 iff 它们的 joint pmf as a matrix 有 rank 1(每行每列都互为倍数).

Proof

note: 一个矩阵 的 rank 等于 1 iff 它可以被分解为两个向量的 outer product :

where 和 是非零列向量.

(): 如果 independent, 那么对于所有 , joint probability 满足:

如果我们定义向量 和 , 那么整个联合分布矩阵 就可以写成:

这正是 Rank 1 矩阵的标准形式.

() 如果 的 rank 为 1, 那么存在向量 和 使得 .由于 , 我们可以归一化这两个向量, 使得 且 .此时, 恰好就是 的 marginal PMF, 恰好就是 的 marginal PMF. 因此满足 , 即两个变量独立.

Example 3.4

这里的 就是 independent 的 random variables.

3.2.5continuous RV independence 的 geometric intuition

对于 independent continuous random variables , 它的 characterization 我们已经知道了: 即 joint pdf factorizes into marginal pdfs. 这一个 characterization 的 geometric intuition 是:

x y x 1 x 2 supportof f X,Y sameshape,differentscale
Figure 3.3独立连续随机变量的矩形 support 与等形横截面

3.3conditional distribution function and density

3.3.1conditional distribution and its distribution function

Definition 3.7 (conditional distribution)

给定 random variables , 其中下面极限里的条件概率按 conditional probability 理解. 我们定义 the conditional distribution of given 为 the probability measure :

并将 function defined by :

称为 the conditional distribution function of given .

Remark

注意: 每个取值 都对应一个 conditional distribution measure 和一个 conditional distribution function . 因此, conditional distribution 和 conditional distribution function 都是一个 family of measures/functions, 而不是一个 measure/function.

也就是说, 一个 random variable 可以 induce 出另一个 random variable 的可能 uncountably many 个 conditional distribution.

Remark

如果 是两个 discrete random variables, 那么它们的 conditional distribution 就很简单了.

以及

其他情况稍复杂一些. 但是我们可以确定的是:

3.3.2conditional density for random variables jointly continuous

Theorem 3.5 (jointly continuous RVs 之间所有 defined 处总有 conditional density)

令 是一个 continuous random vector, 则对于任意 使得 , 都有 conditional distribution of given 的 pdf:

即: 有:

Proof

注意: 是 continuous random vector 是一个 continuous random variable. 因而因而 是 well-defined 的. (反过来不成立) 取 s.t. .

则

因而, 是 的 pdf.

Remark

为了保证 continuous random vector 下分量之间的 conditional distribution 总是 (a.e.) 拥有 pdf 的, 我们可以给 not well-defined 处下定义: 如果 , 就直接 set for all .

在这个定义下: continuous random vector 下分量之间的 conditional distribution 也总是 continuous 的.

3.3.3Law of Total Probability for continuous random vector

Theorem 3.6

令 是一个 continuous random vector, 则对于任意 ,

Proof

注意:

即, 是一个 null set. (不是说 的 是 null set, 意思是说 落在这些 上的事件是 null set.)

因而 compute:

Remark

recall 最普通的全概率公式: 把样本空间 partition 成几个 disjoint 的事件 , 则任意事件 等于它在每个 上的 conditional probability 的和:

这很容易理解. 而这里的 law of total probability for continuous random vector 就是这个公式在 continuous case 的推广:

由于在每一点 上, 的概率都有一个 conditional distribution , 因而 的概率就等于这个 conditional distribution 在所有 上的加权和, 权重就是 的 pdf . 因而才有

Example 3.5

考虑 random vector with joint pdf

计算: .

Solution

首先计算 margianl pdfs:

and

由于这是一个 continuous random vector, 因而根据3.5 可以得到:

同理计算出

3.4conditional expectation

Definition 3.8 (conditional expectation)

令 为 RVs. 这里沿用 expectation and variance of random variable 中 expectation 的积分定义. 对于 where is defined (这个条件对于 discrete 是筛选掉 的点, 对于 continuous 这是为了筛选掉 的点), 我们定义 conditional expectation:

特别地, 如果 是一个 discrete random vector, 则它即是:

而如果 是一个 (absolutely) continuous random vector, 则它即是:

Remark

注意: conditional expectation 对于给定的 是一个值; 而它也整体是一个 function of , 同时也是 function from the sample space (更准确而言是 , 但是去掉的这个集合的测度为零, 所以不用管, a.e. define 即可).

对于 ,

Notice: 这个函数是一个 random variable. 同理, 我们可以构造 conditional expectation given multiple random variables . 但是暂时不谈论这个.

Proposition 3.9 (independence 下 conditional distribution 不变, independence 下 conditional density 不变和 independence 下 conditional expectation 不变)

如果 是 independent 的, 那么在任意 defined 上,

以及

Example 3.6

(constant random variable 的 conditional expectation)

令 为一个 constant random variable. 为一个 (absolutely) continuous random variable. compute: when .

Solution

因而它们 independent (当然,,) 因而

为什么我们要提及这个很呆的例子因为我们要说一个很呆但是要说一下的事情:

Proposition 3.10

conditional expectation 满足 linear property. 即任取 ,

Example 3.7

(computation exercise) 令 为 RVs with joint pdf

计算: .

Solution

根据 3.5 和 3.8, 我们就是要做两件事情: 一个是计算 , 然后根据 和 计算出 , 最后根据 积分计算出 .

那么

我们发现 . 然后对于 ,

因而 . 最后,

而对于 , 因为 , is not defined.

//TODO: 如果 是 continous 的, 而 是 discrete 的, 那么我们怎么 define conditional distribution, 以及 expectation 呢? 这个时候我们就需要用到之前说的 generated -algebra 的概念了.

3.5law of total expectation

Theorem 3.7 (law of total expectation)

令 为 RVs, 我们知道它们的 conditional expectation 也是一个 的 RV.

如果 , 则

Proof

对于更加严格的 conditional expectation 的定义而言 (as an orthogonal projection from onto the subspace of -measurable functions), 这个定理是 trivial 的, 直接 follow from def. 这个定义在 indicator function 上也包含 Kolmogorov definition of conditional probability 的情形. 在该定义中, 被定义为一个 -measurable function , 使得对于任意 , 都有

那么取 , 自然得到.

而我们目前的定义下, 要证明它则要对于 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. : 直到 HH 出现钱, 投掷的次数;

: 直到 HT 出现钱, 投掷的次数.

问题: 计算 和 .

Solution

We condition on 第一次 toss , 以及第二次 toss .

解出 . 同理, 可以解出 .

Example 3.9

一只鸡在一段时间内下 个蛋, 其中 . 每只蛋孵化成小鸡的概率为 , 互相独立. 令 表示孵化成小鸡的蛋的数量, 计算 , 以及 的 distribution.

Solution

由题意得

因此, 因而 . 由 law of total expectation,

然后由 law of total probability,

因而 .

Example 3.10

令 为一对 continuous RVs with joint pdf:

首先, verify is a valid joint pdf, 然后计算 和 .

Solution

verify 很简单. 然后我们首先计算 density of :

然后计算 conditional density of given :

因而 by 3.8,

然后 by law of total expectation,

since is a constant function.

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 (即 a.s.), 任取 , 都有

Remark geometricintuition: t  µ 3, X  t  µ 1/3;, X  µ (0).imply:densityfunction,RV,densityfunctiontail,upperbound: x f X ( x ) t P ( X ≥ t ) Figure4.1:  t 

Proof

我们考虑一个 indicator function , 这也是一个 non-negative random variable. 显然:

(在 的事件上等于, 其他事件上小于), 并且这个 indicator function 的 expectation 正是 大于 的概率 .

因而 by linearity of expectation,

其值为 1 当 时, 否则为 0. 对于任意的 , 有

Corollary 4.1 (Chebyshev’s inequality)

对于一个 random variable 和任意的 , 如果它的方差 是有限的, 那么有

Remark

Markov’s ineq 是通过均值来 bound 非负随机变量达到一定大小的概率 (在多少事件上是大于 的);

Chebyshev’s ineq 则是通过方差来 bound 任意随机变量偏离均值达到一定程度的概率 (在多少事件上是偏离均值超过 的).

Proof

考虑 non-negative random variable , 那么

4.1.2Cauchy-Schwarz and Jensen’s ineq

Theorem 4.2 (Cauchy-Schwarz inequality)

对于任意的 random variables 和 , 都有

这是 prob space 作为一个 measure space, 其上的函数空间 作为一个 Hilbert space, 自然的 Cauchy-Schwarz inequality. 不赘述了.

Theorem 4.3 (Jensen’s inequality)

对于一个 convex function 和任意的 random variable , 只要 和 都是 well-defined 的 (即 finite), 都有

Proof

Let .

Since is convex, for any , there exists a supporting line to the graph of at . 即存在一个 s.t. 对于任意的 , 都有

因而 apply to , 我们 a.s. 有

因此 by linearity of expectation,

4.1.3Fatou’s Lemma, MCT and DCT

我们在 measure theory 中最熟悉的三个定理. 复习一下. 这里不 prove 了. proof 请左转 measure theory notes.

Theorem 4.4 (Fatou’s Lemma)

令 是一列 non-negative random variables, 那么

Remark

pointwise 下极限的积分, 得到的结果不会大于每个函数积分的下极限.

因为 pointwise 下极限即: 在每个 上, 整个序列中最终稳定的最低水平 , 这是最稳定的一层.

而逐个函数可能会有一些 spike, 使得它的 expectation 很大, 但是这个 spike 只出现有限次, 导致 pointwise limitinf 的函数没有受到它的影响; 但是, 不同的 spike 可能 finitely 出现在不同的位置上, 而这个出现的行为是无限的(比如 typewritter 函数), 使得每个函数的 expectation 都很大, 从而导致 expectation 的 limit 很大.

而 pointwise liminf 的 expectation 就是对每个点都取最终稳定的最低水平, 从而避免了这些 spikes 的影响.

Theorem 4.5 (monotone convergence theorem)

令 是一列递增的 non-negative random variables (即 a.s.), 那么 suppose a.e. exists, 那么 a.s. 有

Remark

如果 是递减的, 那么 expectation 的 limit 就等于逐点 limit 的 expectation 了.

Theorem 4.6 (dominated convergence theorem)

令 是一列 random variables, 并且存在一个 a.e. pointwise limit (即 a.s.), 并且存在一个 integrable random variable 作为一个 bound: 使得 a.s. 对所有的 成立,

那么

Remark

只要这个序列有一个 integrable 的 uniform bound (不要有很多 unbounded 的 spike 就行了), 那么 expectation 的 limit 就等于逐点 limit 的 expectation 了.

4.1.4Tonneli and fubini

Theorem 4.7 (Tonelli)

对于一列 non-negative random variables , 累加和积分(求期望)的顺序可以交换:

Theorem 4.8 (Fubini’s Theorem)

对于一列任意的 random variables , 只要其绝对值的 sum 的 expectation 是 finite 的 (或者绝对值的 expectation 的 sum 是 finite 的, by Tonneli 都是一样的), 那么就有 linearity of expectation 的推广:

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 的, 即对任意的 , 都存在一个 使得对于所有的 和所有的 , 都有 , 是一个严格强于 pointwise 的收敛方式. )

Definition 4.1 (RV 序列的三种收敛方式)

4.3Borel-Cantelli Lemma

4.4Laws of Large Numbers

4.4.1weak and strong LLN

下面是概率论中最重要的定律之一: 大数定律 (Laws of Large Numbers, LLN).

它证明的是一个十分符合直觉的结论: 一个 random variable 的 sample mean (即 个 i.i.d. 的 copy 的均值), 随着 sample 数量的增加, 会 converge to 它的 expectation.

就是说: 我们重复做一个相同的实验并取结果的平均值, 当我们做的实验足够多时, 这个平均值就会非常接近于这个实验的 expectation, 也就是理论的均值.
例如最经典的例子就是抛硬币: 我们连续抛 次一个公平的硬币, 记录每次抛出正面 (记为 1) 或者反面 (记为 0), 然后计算这些结果的平均值, 随着 的增加, 这个平均值会趋近于 0.5, 等于理论的 expectation (这是个 Bernouli random variable, 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 , 只要这个 random variable 的 expectation 是 finite 的 , 那么就有:

Proof

简写 , for each .

Let . It suffices to show: as . By Chebyshev’s inequality, we have

notice: 由于每个 都是 i.i.d. 的, independence uncorrelatedness , 因而 for each .

因而

Theorem 4.10 (strong Law of Large Numbers)

在 weak LLN4.9 的相同条件 (其实可以更弱, 让 即可) 下, 我们其实可以得到一个更强的结论:

Proof

For simplicity, 我们不证明更弱的条件 () 下的 strong LLN 了. 只沿用相同的条件.

简写 , , for each , 以及

我们将要证明: .

首先, 在 weak LLN 的 proof 中, 我们已经证明了:

我们发现: 当我们只采样 indexed 的时候, 它们的 expectation 的 sum 是 finite 的, by p-test (因为 收敛当且仅当 ), 即:

先考虑所有 都非负的 case. 我们知道: expectation of 一个 non-negative random variable 是 finite 的, 就 imply 它是 a.e. finite 的. 因而

因而

意味把在 这些 index 的 求 average, 确实收敛到了 .

而我们可以通过 squeeze theorem 得到 general case: 对于任意正整数 , 总能找到一对平方数把它夹在中间. 比如令 .

我们发现:

notice: , 前向 converge to , 后向 converge to 1, 因而 , 后面那个也同理. 因而夹逼得到 . 从而得证.

General case:

因而

得证.

Remark

我们要求 是 finite 的, 或者 是 finite 的, 并不是一个硬性的条件, 只是结果确实 converge to 这个 finite value 的条件.

实际上在 infinite (等于 或者 ) 时, 我们会得到这个 average 发散, 因而也是和 一样, 只不过不是 converge 而是 diverge.

此处不证明了.

4.4.2application: Monte Carlo methods

任何利用 LLN 来近似计算一个 quantity 的方法, 都可以称之为 Monte Carlo 方法.

它的核心思想是:

Example 4.1 估算

我们令

那么

注意我们每次随机采样 的时候, 都是在 这个正方形里随机选一个点, 即创建了一个 random variable 并进行观测.

根据 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 converge in distribution to a random variable , 写作 , 如果 的分布函数 下所有右连续的 (即 ), 都有

Remark

Convergence in distribution 的意思就是: 随着 越来越大, 的分布是否越来越接近 的分布. 这是一个非常弱的收敛概念, 因为它甚至不要求 和 在同一个概率空间上定义, 也不要求 和 之间有任何关系. 只需要分布函数收敛即可.

并且 notice: 并不要求对所有点 都有 , 而是只要求对 的分布函数 下所有右连续的点 . 这是因为如果不加这个限制, 很多直观上应该收敛的情况在数学上就会失败.

比如: 令, 一个 constant random variable, 那么 的分布函数 是一个 step function. 但是在 处, for all , 因而 .

而 .

所以对于这种跳跃不连续点, 如果不跳过, 那么就会得出 不收敛于 的错误结论. 但是我们知道, 分布函数作为一个单调递增的函数, 是 a.e. continuous 的, 因而这些点是可以忽略掉的.

5.2Characterization of a distribution

5.2.1moment generating function

Definition 5.2 (moment generating function)

对于一个随机变量 , 其 moment generating function (MGF) 定义为

Remark

为什么这个东西叫做 moment generating function 呢? 因为如果 在 的某个 neighborhood 内存在, 那么我们可以通过对 求导来得到 的各阶矩:

Proposition 5.1

如果 在 的某个 neighborhood 内存在, 则 的 阶矩可以表示为

其中 表示 在 处的 阶导数.

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 with mean and variance , set for each .

我们有:

Remark

LLN 告诉我们, 当 越来越大时, 越来越接近 . 每个 随机取样, 不论结果如何, 其平均值大概率都是 .
CLT 则是进一步告诉我们这个接近的过程是如何发生的: 随着 越来越大, 的分布会越来越接近一个正态分布, 且波动的幅度(标准差)数量级为 . 因而平均值 的分布会越来越接近一个均值为 , 标准差为 的正态分布

随着 越来越大, 这个标准差会越来越小, 因而其极限坍缩为一个 constant .

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 次, 记录下每次 toss 的结果, 记为 , 其中 if the -th toss is heads.

现在: 观测到第一个 coin 100 次 toss 中有 38 次是 heads, 第二个 coin 100 次 toss 中有 43 次是 heads.

Solution

假设这两个 coins 是 fair coin. 那么 是 i.i.d. Bernoulli random variables with parameter , 因而 , . 从而根据 CLT,

因而这个第一个 coin 很可能不是 fair coin. 同样的方法计算出 , 因而第二个 coin 虽然也可疑不是 fair coin, 但是不如第一个 coin 可疑. 如果以 0.05 作为显著性水平, 那么我们可以拒绝第一个 coin 是 fair coin 的假设.

Example 5.2 (样本量需求的计算)

工厂生产了一批电线, 我们想知道它们的平均断裂强度 是多少. 遂抽取 根电线进行测量, 得到 , 然后计算它们的样本平均值 来估计 .

已知量: 强度的方差 .; 我们想估计的是 的值. 并且我们希望我们的估计是准的, in the sense that: 误差 不超过 0.01 的概率至少为 0.95.

Solution

我们要达到: .

我们要把它转成标准的 normal distribution 的形式, 即 的形式.

于是我们把 写为 , 然后两边同时乘 . 右边的常数项也做相同的变换: .

于是原式变为:

对于正态分布我们知道

于是想要:

通过查表我们知道当 时, . 因此要求 , 解得至少需要 , floor 一下得到 .

Remark

这里的应用正是我们开头说的: LLN 告诉我们, 当 越来越大时, 越来越接近 . 每个 随机取样, 不论结果如何, 其平均值大概率都是 ; 而 CLT 则是进一步告诉我们这个接近的过程是如何发生的:

随着 越来越大, 这个标准差会越来越小, 因而其极限坍缩为一个 constant . 因而, 我们可以通过 CLT 来得到: 我们要用样本均值来估计分布的真实均值的话, 在一定的置信水平下, 需要多少样本量 才能保证我们的估计是准的.

5.3.2Berry-Esseen Theorem: CLT 的收敛速度

之前的例子中, 我们都使用了 表示: 我们直接把此时的分布近似当作了一个 normal distribution, 来计算一些概率.

但是: 这两个分布的近似行为的本身有多么精准?

下面有一个 theorem 刻画了这件事.

Theorem 5.2 (Berry-Esseen Theorem)

给定一个 seq of i.i.d. random variables with mean and variance , 以及 , set , 我们有: 对于任意 ,

Remark

给定一个 number of samples , 我们可以给出此时的真实概率与正态近似值之间的差值的一个 upper bound.
并且, 这个 bound 不是概率意义上的 bound, 而是一个 deterministic bound, 没有任何的随机性; 并且是 uniform across all 的 bound.
这是因为这里本身就是两个概率的值之间的差, 而不是样本之间的差. 因而其实这是一个非常强大的结论, 表面我们用正态分布近似估计出的概率和真实的概率之间的差值是 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 需要从生产线上需要随机 个元件进行测试, 并估计出 的值 by 样本均值:

我们希望这个估计的误差最多为 0.005, 并且这个误差的置信度至少为 0.99, 即我们希望:

那么我们至少需要多少样本量 来达到这个要求呢?

Solution

首先计算样本均值 的 mean 和 variance:

此时我们有三个办法:

我们可以看到

不过, 这个结果是基于我们假设 的前提下得到的. Chebyshev 的逻辑 (保守估计): 我不相信厂家的任何话, 我要建立一个无论真实 是多少都绝对成立的置信区间. 所以我必须用最差的情况 来算 . CLT/Berry-Esseen 的逻辑 (假设检验): 厂家宣称 . 在统计学中, 我们通常先假设这个宣称是正确的 (即 假设). 如果我们用在这个假设下得出的需要的样本量 去测, 发现结果远超 , 那我们就直接推翻厂家的说法.

5.3.3proof of CLT