PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

功茹
5 years ago
Views:

1 离散概率 1

2 回顾集合计数容斥原理鸽笼原理排列与组合

3 提要 3 概率论贝叶斯定理期望与方差

4 例 : 生日问题 4 有 k 个人, 设每个人的生日是 365 天的任何一天是等可能的, 求至少两人生日相同的概率解 : 令 E = { 至少两人生日相同 }, 则 ഥE = k 个人生日均不同. 显然,Pr ഥE = 365 k 365 k. 故 Pr E = 1 Pr ഥE = k 365 k.

5 例 : 生日问题 5 Pr E = 1 Pr ഥE = k 365 k 人数概率

6 基于集合论给概率以数学定义定义 : 可数样本空间 S 乃一个可数集合 S 的每一个元素 ω 称为一个结果定义 : 满足下列条件的函数 Pr: S R 称为样本空间 S 上的一个概率函数 : ω S Pr ω 0, 且 Σ ω S Pr ω = 1. 定义 :S 的一个子集 E S 称为一个事件事件 E 的概率 Pr E = σ ω E Pr[ω]

7 基于集合论的概率计算定理 1: 设 E 是样本空间 S 中的一个事件, 事件 തE( 事件 E 的补事件 ) 的概率为 : Pr തE = 1 Pr[E] 定理 2: 设 E 1 和 E 2 是样本空间 S 中的事件, 那么 : Pr E 1 E 2 = Pr E 1 + Pr E 2 Pr[E 1 E 2 ]

8 均匀分布定义 : 假设 S 是一个含 n 个元素的样本空间. 均匀分布 (uniform distribution) 赋给 S 中每个结果 1/n 的概率. 举例 : 对于均匀的硬币 Pr H = Pr T = 1 2 举例 : 公平的骰子 Pr X = 1 6, X = 1 6 均匀分布下事件的概率可通过对其中的元素计数求得

9 条件概率与独立性条件概率定义 : 设 E 和 F 是事件, 且 Pr F > 0. E 在给定 F 条件下的概率, 记作 Pr E F, 定义为 Pr E F = Pr E F Pr F 独立性定义 : 事件 E 和 F 是独立的, 当且仅当 Pr E F = Pr E Pr F E F S

10 例 10 在至少有一个男孩的条件下, 有两个孩子的家庭正好均是男孩的条件概率? 假设 BB, BG, GB, 和 GG 是等可能的

11 例 11 一个有两个孩子的家庭有四种情形 (BB, GG, BG, GB), 假设是等可能的事件 E 是两个孩子的家庭有两个男孩, 事件 F 是两个孩子的家庭至少有一个男孩事件 E 和 F 是否独立?

12 12 例 : 三门问题

13 例 : 三门问题 13 假设你正在参加一个有奖游戏你被要求在三扇门中选择一扇, 其中一扇后面有一辆车, 其余两扇后面则是山羊 ; 你选择了一道门 ; 然后知道门后面有什么的主持人, 开启了另一扇后面有山羊的门他然后问你 : 你想改变主意而选择剩下来的这个门吗? 问题是 : 改变选择对你来说有利吗?

14 例 : 三门问题 14 定义随机实验结果为 ( 车在哪个门后, 开始选哪个门, 主持人开哪门 ) Pr 改变选择而赢 = Pr A, B, C + Pr A, C, B + Pr B, A, C + Pr B, C, A + Pr C, A, B + Pr C, B, A = = 2 3

15 贝叶斯定理设 E 和 F 是样本空间 S 中的事件, Pr E 0, Pr F 0, 则 Pr F E = = Pr[E F] Pr F Pr E Pr[E F] Pr F Pr E F Pr F +Pr[E തF]Pr[ തF]

16 贝叶斯定理的推导由条件概率定义 Pr F E Pr E = Pr F E = Pr E F = Pr E F Pr F 又 Pr[E] = Pr E F (E തF) = Pr E F + Pr E തF = Pr E F Pr F + Pr[E തF] Pr[ തF]

17 贝叶斯定理一些常用说法 Pr[A] 是 A 的先验概率之所以称为先验是因为它不考虑任何 B 方面的因素 Pr[A B] 是已知 B 发生后 A 的条件概率或后验概率 Pr[B A] 是已知 A 发生后 B 的条件概率或后验概率 Pr[B] 是 B 的先验概率, 也作标准化常量 (normalizing constant)

18 贝叶斯定理的应用假设有一种罕见的疾病,100,000 人只有 1 人会得这种病如果某人得了此病, 检测准确率高达 99%; 如果某人没有得此病, 检测准确率为 99.5%. 疾病检测呈阳性, 得此病的概率多大? 疾病检测呈阴性, 没有得此病的概率多大? 解 : 设 D 是此人得此病的事件,E 是疾病检测呈阳性的事件需要计算 Pr[D E], Pr[ഥD തE]

19 贝叶斯定理的应用 ( 续 ) Pr D = = , Pr ഥD = 1 Pr D = Pr E D =0.99, Pr തE D = 0.01, Pr E ഥD =0.005, Pr തE ഥD = Pr D E = Pr[E D] Pr D Pr E D Pr D +Pr[E ഥD]Pr[ഥD] = 呈阳性, 也不必太担心!

20 贝叶斯定理的应用 ( 续 ) Pr ഥD തE = Pr[ തE ഥD] Pr ഥD Pr തE ഥD Pr ഥD +Pr[ തE D]Pr[D] = Pr D തE = 1 Pr ഥD തE = 呈阴性, 高枕无忧!

21 随机变量 21 定义 : 一个随机变量 (random variable) 是从样本空间到实数集的一个函数, 也就是对每个可能结果指派一个实数随机变量是一个函数, 不是一个变量

22 随机变量 22 抛一枚骰子, 令 X = 出现的点数, 则 X 是一 r.v. X 的取值为 1,2,3,4,5,6 {X 4} 表示事件 : 点数不超过 4 {X 为偶数 } 表示事件 : 点数为偶数设离散型随机变量 X 的所有可能取值为 x 1, x 2,, x n, 并设 P(X = x n ) = p n n = 1, 2,, 则称上式为 X 的分布律, 常表示为 X x 1 x, 2 P p 1 p, 2 x n p n

23 二项分布 23 若随机变量 X 的分布律为 P X = i = C(n, i)p i 1 p n i, i = 0, 1,, n 则称 X 服从参数为 n, p 的二项分布 ( 其中 n 为自然数,0 p 1 为参数 ), 记作 X B(n, p) 随机变量的分布完整刻画了一个随机变量

24 例 24 假设一个硬币被掷 3 次. 令 X(t) 是头像在结果 t 中出现的次数那么随机变量 X(t) 取值如下因此,X(t) 的 ( 概率 ) 分布为

例 25 假设姚明罚球的命中率为 0.9, 求他两次独立罚球命中次数 X 的分布解 :X 的取值为 0,1,2. P X = 0 = 1 0.

25 例 25 假设姚明罚球的命中率为 0.9, 求他两次独立罚球命中次数 X 的分布解 :X 的取值为 0,1,2. P X = 0 = = P X = 1 = = P X = 2 = = 0. 81

26 随机变量分布特征的刻画如何刻画随机变量取值分布的整体特征? 平均取值? 当以概率加权之离散程度? 当以平均取值为基准, 考虑偏差程度

27 期望值定义 : 对于定义在样本空间 S 上的一个随机变量 X, 其期望值为以概率加权的随机变量平均取值 X ω Ex X (deviation) Ex[X] = ω S X ω Pr[ω] 称为 X 在 ω 处的偏差

28 例例 : 求扔一个骰子所得点数的期望值 Ex X = = 21 6 = 7 2 例 : 扔三个硬币, 求头面朝上硬币个数的期望值 Ex X = 1 [X HHH + X HHT + X HTH + X HTT + 8 X THH + X THT + X TTH + X TTT ] = = 3 2

29 例例 : 求扔一个骰子所得点数的倒数的期望值 Ex 1 X = = Ex X Ex 1 X

30 例例 : 求扔两个骰子所得点数之和的期望值 Pr X = 2 = Pr X = 12 = 1 36 Pr X = 3 = Pr X = 11 = 1 18 Pr X = 4 = Pr X = 10 = 1 12 Pr X = 5 = Pr X = 9 = 1 9 Pr X = 6 = Pr X = 8 = 5 36 Pr X = 7 = 1 6

31 例 : 猴子打字 31 一猴子在只含 26 个小写字母的键盘打字, 每次均独立随机敲击一个键如果该猴子敲击了 10 6 次键盘, 问单词 proof 期望出现多少次? 解 : 定义指示随机变量 X i 如下 : X i = ቊ 1 i 到 i + 4 个字母为 proof 0 否则令 X 表示 proof 出现的次数, 则 X = σ i=1 X i E X = E X i i=1 = i= P X i = 1 =

32 期望值的等价定义定理 : 对于任意随机变量 R Ex R = x Pr[R = x] x range(r)

33 条件期望给定一个随机变量 R,R 在已知事件 A 条件下的期望值是 R 在 A 中结果上的取值的概率加权平均值 : Ex R A = r Pr[R = r A] r range(r) 例 : 已知一个公平骰子投出的点数不小于 4 点, 此条件下投出的点数的期望值是多少?

34 全期望公式

35 ҧ ҧ 例 :Mean Time to Failure A computer program crashes at the end of each hour of use with probability p, if it has not crashed already. What is the expected time until the program crashes? Ex[C]: C is the number of hours until the first crash A: the event that the system fails on the first step A: to be the complementary event Ex C = Ex C A Pr A + Ex C Aҧ Pr Aҧ Ex C A = 1 Ex C A = 1 + Ex[C] Ex C = 1 p

36 期望的线性特性定理 : 对于样本空间 S 上的一组任意的随机变量 X i, (i = 1,2,, n) 和任意实数 a, b, 有 Ex X 1 + X X n = Ex X 1 + Ex X Ex X n Ex[aX + b] = aex[x] + b 由上述定理可知, 扔两个骰子所得点数之和的期望值等于第一个骰子点数期望值与第二个骰子点数期望值之和, 即 7/2 + 7/2 = 7.

37 例 :Expected Value in the Hatcheck Problem 负责寄存帽子的服务生把帽子搞乱了, 只能随机发还问他可以期望还对几个? 令 X i = 1 若第 i 个客人拿到他的帽子 ; 否则 = 0 X = X 1 + X X n Ex X i = 1 Pr X i = Pr X i = 0 = 1 n Ex X = Ex X 1 + Ex X Ex X n = n 1 n = 1

38 例 : 平均计算复杂度例 : 线性搜索算法的平均复杂度给定一个实数 x 及一个长度为 n 的列表, 线性搜索算法依次检查列表中的元素, 看是否为 x, 直至找到或者所有元素都查完了而未找到 x 只考虑比较操作的次数若 x 处于第 i 个位置, 则需要 2i+1 次比较 ; 若 x 不在列表中, 则需要 p 为 x 在列表中的概率 2n+2 次 q = 1-p

39 独立随机变量样本空间 S 上的随机变量 X 和 Y 若满足 Pr[X = r 1 且 Y =

40 方差样本空间 S 上的随机变量 X 的方差 (variance) Var X = Ex[ X Ex X 2 ] Var X = Ex X Ex X 2 = ω S X ω Ex X 2 Pr[ω] 方差是随机变量 X 在 ω 处的偏差的平方的加权平均 Var[X] 称为 X 的标准差 (standard deviation) 记为 σ X ( 或者 σ(x))

41 方差定理 : 样本空间 S 上的随机变量 X 的方差 Var X = Ex X 2 Ex 2 [X] 例 : 扔一个骰子所得点数的方差 Var X = Ex X 2 Ex 2 X 2 = = 35 12

42 Bienaymé s formula 对于样本空间 S 上独立的随机变量 X 和 Y 有 Var X + Y = Var X + Var Y 并可推广至 n 个两两相互独立的随机变量 Var X 1 + X X n = Var X 1 + Var X Var X n

43 Bienaymé s formula 例 : 求扔两个骰子点数之和的方差第一个骰子点数与第二个骰子点数两个随机变量相互独立 ; 故可使用 Bienaymé 公式 Var X 1 + X 2 = Var X 1 + Var X 2 =

44 概率化方法 (Probabilistic Method) 44 一种用概率证明存在性的方法先驱者 :Paul Erdős 定理 : 如果随机地从集合 S 中选取一个元素, 此元素不具有一个特定性质的概率小于 1, 则 S 中存在具有这条性质的元素

45 例 :Ramsey 数 45 Ramsey 定理 : 任意 6 个人中, 必有 3 个人互相认识或互不认识图论语言 : 对 K 6 2- 边着色, 则存在同色的 K 3 Ramsey 数 R(k, k): 最小的 n, 使得对 K n 的任意 2- 边着色中, 均存在同色的 K k

46 例 :Ramsey 数 46 定理 (Erdős 1947) n 如果 k k 21 2 < 1, 则存在对 K n 的某种 2- 边着色, 其不含同色的 K k 子图证 : 对每一条边 e K n 独立随机着色, 即以 1/2 的概率着红色,1/2 的概率着蓝色给定一 K k 子图, P 该 K k 同色 = 2 1 k 2 P 存在同色 K k 子图 n k 21 k 2 < 1 (Union bound) P 不存在同色 K k 子图 > 0, 从而存在对 K n 的某种 2- 边着色, 其不含同色的 K k 子图

47 作业见课程网站

PowerPoint Presentation

PowerPoint Presentation 南京大学计算机科学与技术系离散概率离散数学课程组南京大学计算机科学与技术系提要离散数学 : 离散概率直觉概率分析 : 三门问题直觉的形式化 : 概率空间条件概率与贝叶斯定理随机变量及其期望与方差三门问题 (Monty Hall Problem) 三门问题 (Monty Hall Problem) 假设你正在参加一个有奖游戏你被要求在三扇门中选择一扇, 其中一扇后面有一辆车, 其余两扇后面则是山羊