PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

净无乘
5 years ago
Views:

1 南京大学计算机科学与技术系离散概率离散数学课程组南京大学计算机科学与技术系

2 提要离散数学 : 离散概率直觉概率分析 : 三门问题直觉的形式化 : 概率空间条件概率与贝叶斯定理随机变量及其期望与方差

3 三门问题 (Monty Hall Problem)

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

5 进一步明确你在三扇门中挑选一扇你并不知道门内有什么主持人知道每扇门后面有什么主持人必须开启剩下的其中一扇门, 并且必须提供你换门的机会主持人永远都会挑一扇有山羊的门如果你挑了一扇有山羊的门, 主持人必须挑另一扇有山羊的门如果参赛者挑了一扇有汽车的门, 主持人随机 ( 概率均匀分布 ) 在另外两扇门中挑一扇有山羊的门你会被问是否保持原来选择, 还是选择剩下的那道门

6 直觉的概率分析四步法 1. 选定样本空间 (Find the sample space) 2. 定义相关事件 (Define events of interests) 3. 确定结果概率 (Determine outcome probabilities) 4. 计算事件概率 (Compute event probabilities)

7 第一步 : 选定样本空间试验 : 从一组可能的结果中得出一个结果的过程试验的某个特定结果通常是由若干随机因素的某种选择而导致的这里因素一 : 车在哪个门后? 因素二 : 你开始选的哪个门? 因素三 : 主持人打开哪个门? 样本空间 : 所有可能结果的集合

8 车在哪个门后开始选哪个门主持人开哪门试验结果样本空间

9 第二步 : 定义相关事件事件 : 样本空间的一个子集例如 : 车在 C 门后 :{(C, A, B), (C, B, A), (C, C, A), (C, C, B) } 第一次就选中有车的门 : {(A, A, B), (A, A, C), (B, B, A), (B, B, C), (C, C, A), (C, C, B)} 改变选择才赢的情况 : {(A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A)} 6 对 6, 似乎换不换都一样?

10 第三步 : 确定结果概率给每个边确定概率计算各结果概率 Pr A, B, B = = 1 18

11 第四步 : 计算事件概率 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

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

13 基于集合论的概率计算定理 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 ]

14 基于集合论的概率计算例 : 从不超过 100 的正整数中随机选一个, 它能被 2 或 5 整除的概率? 解 : 设 E 1 是选出一个被 2 整除的事件,E 2 是选出一个被 5 整除的事件则 E 1 E 2 是选出一个被 10 整除的事件 Pr E 1 E 2 = Pr E 1 + Pr E 2 Pr E 1 E 2 = =

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

16 条件概率定义 : 设 E 和 F 是事件, 且 Pr F > 0. E 在给定 F 条件下的概率, 记作 Pr E F, 定义为 Pr E F = Pr E F Pr F

17 条件概率离散数学 : 离散概率例 : 在至少有一个男孩的条件下, 有两个孩子的家庭正好均是男孩的条件概率? 假设 BB, BG, GB, 和 GG 是等可能的解 : 令 E 是家庭有两个男孩的事件,F 是家庭至少有一个男孩的事件我们有 E = {BB}, F = {BB, BG, GB}, E F = {BB}. Pr F = 3 4, Pr E F = 1 4 Pr E F = Pr E F Pr F = 1 3

18 贝叶斯定理离散数学 : 离散概率设 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]

19 贝叶斯定理的推导离散数学 : 离散概率由条件概率定义 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]

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

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

22 贝叶斯定理的应用 ( 续 ) 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] = 为何结果如此小? 呈阳性, 也不必太担心!

23 贝叶斯定理的应用 ( 续 ) 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 = 呈阴性, 高枕无忧!

24 举例朋友来看我, 乘坐交通工具的概率和这些工具可能晚点的概率分别是乘坐概率 : 自驾 (0.3), 公交 (0.1), 高铁 (0.4), 飞机 (0.2) 晚点概率 : 自驾 (0.3), 公交 (0.15), 高铁 (0.05), 飞机 (0.5) 朋友迟到了, 何种原因最有可能导致这种现象? 解 :A 自驾,B 公交,C 高铁,D 飞机,E 迟到 p(a)=0.3, p(b)=0.1, p(c)=0.4, p(d)=0.2; p(e A)=0.3, p(e B)=0.15, p(e C)=0.05, p(e D)=0.5; 求 p(a E), p(b E), p(c E), p(d E) 中的最大者

25 在众多线索中探究 p(a E)=90/225=2/5, p(b E)=15/225=1/15, p(c E)=20/225=4/45, p(d E)=100/225=4/9 ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( D p D E p C p C E p B p B E p A p A E p A p A E p E A p 误事的很可能是飞机!

26 贝叶斯 Spam 过滤器如何确定一个电子邮件是 Spam? 假设我们有一个垃圾邮件的集合 B 和一个不是垃圾的邮件集合 G 利用贝叶斯定理来预测一个新的电子邮件是 Spam 的概率考察一个特定的单词 w, 它在 B 和 G 中出现的次数分别为 n B (w) 和 n G (w). 设 S 是邮件为 Spam 的事件, E 是邮件内容含单词 w 的事件. 需要计算 p(s E), 需要估算 p(e S) 和 p(e ҧ S)

27 贝叶斯 Spam 过滤器估算 p(e S)= p(w) =n B (w)/ B p(e `S) =q(w) = n G (w)/ G 假设 p(s) = ½ 垃圾邮件的频率若大于某个经验值, 则被认为是 Spam

28 贝叶斯 Spam 过滤器举例 : Rolex 在 2000 封垃圾邮件的 250 个当中出现, 而在 1000 封非垃圾邮件中只有 5 封包含这个单词估计一条含有 Rolex 的消息是 Spam 的概率. 假设收到的消息是 Spam 和不是 Spam 是等可能的假设把一条消息作为 Spam 而拒绝的阈值为 0.9, 那么我们应该拒绝这条消息吗? 解 : p(rolex) = 250/2000 =0.125, q(rolex) = 5/1000 = 将含有 Rolex 的消息分类为 Spam, 并拒绝这种消息

32 课堂练习离散数学 : 离散概率

33 课堂练习离散数学 : 离散概率

34 课堂练习离散数学 : 离散概率

35 课堂练习离散数学 : 离散概率

36 事件独立性离散数学 : 离散概率定义 : 事件 E 和 F 是相互独立的当且仅当 Pr E F = Pr E Pr F 例 : 一个有两个孩子的家庭有四种情形 (BB, GG, BG,GB), 假设是等可能的事件 E 是两个孩子的家庭有两个男孩, 事件 F 是两个孩子的家庭至少有一个男孩事件 E 和 F 是否独立? 解 :Pr E = 1 4, Pr F = 3 4, Pr E F = 1 4 Pr E Pr F = = Pr[E F] 故 E 和 F 不是相互独立的

37 随机变量一个随机变量 X 是一个定义域为某样本空间 S 的函数其伴域 (codomain) 可为任意非空集合, 但通常取实数集 R 即 :X: S R 一个随机变量是一个函数它既不是一个变量, 也不是随机的

38 随机变量 ( 续 ) 举例 : 假设一个硬币被掷 3 次. 令 X(t) 是头像在结果 t 中出现的次数那么随机变量 X(t) 取值如下 : X HHH = 3, X TTT = 0, X HHT = X HTH = X THH = 2, X(TTH) = X(THT) = X(HTT) = 1. 8 种结果的每一个出现的概率为 1/8. 因此, X(t) 的 ( 概率 ) 分布 Pr X = 3 = 1 8, Pr[X = 2] = 3 8, Pr[X = 1] = 3 8

39 随机变量的分布离散数学 : 离散概率定义 : X 是样本空间 S 上的随机变量, X 的分布是形如 r, Pr X = r 的二元组集合, 其中 r X(S), Pr X = r 是 X 取值为 r 的概率

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

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

42 期望值的直接计算离散数学 : 离散概率例 : 求扔一个骰子所得点数的期望值 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

43 期望值的直接计算离散数学 : 离散概率例 : 求扔一个骰子所得点数的倒数的期望值 Ex 1 X = = Ex X Ex 1 X

44 例 : 求扔两个骰子所得点数之和的期望值 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

45 期望值的等价定义离散数学 : 离散概率定理 : 对于任意随机变量 R Ex R = x Pr[R = x] x range(r)

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

47 Law of Total Expectation

48 ҧ ҧ 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

49 期望的线性特性定理 : 对于样本空间 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.

50 例 :Expected Value in the Hatcheck Problem 负责寄存帽子的服务生把帽子搞乱了, 只能随机发还问他可以期望还对几个? 令 X i = 1 若第 i 个客人拿到他的帽子 ; 否则 = 1 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

51 独立随机变量样本空间 S 上的随机变量 X 和 Y 若满足 Pr X = r 1 且 Y = r 2 = Pr X = r 1 Pr[Y = r 2 ], 则称它们相互独立例 : 扔两个骰子, 第一个骰子点数与第二个骰子点数二者是否独立? 例 : 扔两个骰子, 第一个骰子点数与两个骰子点数之和二者是否独立? 对于样本空间 S 上独立的随机变量 X 和 Y 有 Ex[XY] = Ex[X]Ex[Y]

52 独立随机变量离散数学 : 离散概率对于样本空间 S 上独立的随机变量 X 和 Y 有 E(XY) = E(X)E(Y)

53 方差离散数学 : 离散概率样本空间 S 上的随机变量 X 的方差 (variance), 记作 V(X), 定义为方差是变量 X 在 s 处的偏差的平方的加权平均 V(X) 称为 X 的标准差 (standard deviation), 记为 σ(x).

54 方差离散数学 : 离散概率定理 : 样本空间 S 上的随机变量 X 的方差 V X = E X 2 E X 2 证明 :

55 方差离散数学 : 离散概率例 : 扔一个骰子点数的方差 V X = E X 2 E X 2 2 = = 35 12

56 Bienaymé s formula 离散数学 : 离散概率对于样本空间 S 上独立的随机变量 X 和 Y 有 V X + Y = V X + V(Y) 并可推广至 n 个两两相互独立的随机变量 V X 1 + X X n = V X 1 + V X V(X n )

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

58 切比雪夫不等式 Chebyshev s Inequality 对于样本空间 S 上随机变量 X, 和任意的正实数 r 有 p X s E X r V(X) r 2

59 利用切比雪夫不等式进行概率估算例 : 已知正常男性成人每毫升血液中白细胞数目的平均值是 7300, 标准差是 700 试利用切比雪夫不等式估算每毫升血液含白细胞数在之间的概率解 : 设 X 表示每毫升血液中白细胞个数, 则 E X = 7300, V X = σ 2 = 而 p 5200 X 9400 = p X = 1 p( X ) 又 p X = 1 9 故 p 5200 X

60 作业离散数学 : 离散概率见课程网站

PowerPoint 演示文稿

PowerPoint 演示文稿离散概率 1 回顾集合计数容斥原理鸽笼原理排列与组合提要 3 概率论贝叶斯定理期望与方差例 : 生日问题 4 有 k 个人, 设每个人的生日是 365 天的任何一天是等可能的, 求至少两人生日相同的概率解 : 令 E = { 至少两人生日相同 }, 则 ഥE = k 个人生日均不同. 显然,Pr ഥE = 365 k 365 k. 故 Pr E = 1 Pr ഥE = 1 365