第 7 章 离散概率
# 第 7 章 离散概率
# 7.1 离散概率引论
# 7.1.1 引言
# 7.1.2 有限概率
相关术语
- 试验
- 从一组可能的结果中得出一个结果的过程
- 样本空间
- 试验可能结果的集合
- 事件
- 样本空间的子集
#
定义711
- 事件
的概率是 是有限样本空间 - 其中的每个结果具有相等的可能性
- 事件
是 的子集
提示
- 此定义也被称为拉普拉斯定义
# 7.1.3 事件组合的概率
可以用集合和计数的方法从其他事件得到事件的概率
#
定理711
- 事件
(事件 的补事件) 的概率是
#
定理 712
- 设
和 是样本空间的事件,则
# 7.1.4 概率的推理
# 7.2 概率论
# 7.2.1 引言
提示
- 拉普拉斯定义 假定所有结果的可能性都是相等的。
- 但是许多试验结果的可能性并不相等
- 在这种情况下,需要建立新的关于事件可能性的模型
# 7.2.2 概率指派
样本空间的概率分布
- 赋给样本空间中的每个结果
一个概率 ,使得其满足以下两个条件: - 样本空间
的所有事件的集合上的函数 称为 概率分布
#
均匀分布
- 假设
是 个元素的集合。均匀分布赋给 中每个元素的概率是
#
事件的概率
- 事件
的概率是在 中的所有结果的概率之和,即
# 7.2.3 事件的组合
#
定理 721
- 如果
是样本空间 中两两不相交事件的序列,则
# 7.2.4 条件概率
#
条件概率的定义
- 设
,则给定 的情况下 的条件概率记作 ,定义为
# 7.2.5 独立性
#
事件独立的定义
- 事件
和 是独立的,当且仅当
提示
- 即
#
两两独立与相互独立
- 事件
- 是两两独立的, 当且仅当对于所有的整数对
,有下式成立 - 是相互独立的, 当且仅当下式成立
- 其中
为整数,且 相当于从事件集中取出任意数量的事件,上式均成立
- 是两两独立的, 当且仅当对于所有的整数对
# 7.2.6 伯努利试验与二项分布
每执行一次具有两种可能结果的试验就叫作一次伯努利试验
- 一次伯努利试验的一个可能的结果称为 成功 或 失败
- 一般设
为成功的概率, 为失败的概率- 则
- 则
- 一般设
#
二项分布
- 在
次独立的伯努利试验中有 次成功的概率是 - 二项分布函数定义为
# 7.2.7 随机变量
#
随机变量的定义
- 一个随机变量是从试验的样本空间到实数集的 函数
- 即一个随机变量对每个可能的结果指派一个实数值
一个随机变量是一个函数,而不是一个变量,并且它也不是随机的
# 7.2.8 生日问题
一个房间至少要多少人,两个人的生日相同的概率会大于50%
- 分析问题时,可以假设人一个个的进入房问,则当房间有
个人时,两两之间生日均不同的概率为 - 则
个人中有两个人生日相同的概率为 - 最终问题的答案是 23 个人
# 7.2.9 蒙特卡罗算法
确定性算法与概率算法
- 确定性算法
- 只要给定同样的输入,算法总是以同样的方式运行
- 概率算法
- 在一步或者多步做随机选择的算法
蒙特卡罗算法即是一种特殊的概率算法
蒙特卡罗算法
- 算法对问题总能得到答案,但是这些答案可能存在很小的出错概率
- 但当算法执行足够多的计算时,出错的概率迅速下降
- 算法首先选定迭代的次数
- 如果任何一次迭代产生答案 “真”,则最终结果为 “真”
- 如果每次迭代都产生答案 “不知道”,则最终结果为 “假”
- 这种情况下,存在出错的可能,但随着迭代次数的增加,出错的可能会迅速下降
#
应用实例:素数的概率测试
- 基本原理
- 对于一个随机选择的底
,一个合数 通过米勒测试的概率小于- 米勒测试见 P254 而练习 44
- 当进行 30 次迭代时,一个数
是合数但却被判定为素数的概率小于- 这是一个特别小概率的事件
- 对于一个随机选择的底
RSA 可以利用素数的概率测试生成大素数
- 先随机选择一个 200 位的整数
,用 30 次迭代运行素数测试算法,如果算法判定 是素数,则可以将其当成两个素数之一用在 RSA 密钥系统中 - 如果
实际上是合数,则解密过程不会产生原始的被加密信息,此时会抛弃当前密钥而重新使用两个新的可能的素数 - RSA
- 先随机选择一个 200 位的整数
# 7.2.10 概率方法
存在性证明的非构造性证明可以借助概率方法进行
#
概率方法
- 如果随机地从集合
中选取一个元素,此元素不具有某个特定特定性质的概率小于 ,则 中存在具有这条性质的元素 一定程度上借鉴了反证法的思想
#
拉姆齐数的下界
- 如果
是一个整数,且 ,则 证明可以采用概率方法
# 7.3 贝叶斯定理
# 7.3.1 引言
贝叶斯定理被广泛应用于已知部分证据来估计概率的各种领域中
- 如 P416 页的疾病检测
- 贝叶斯垃圾邮件过滤器
# 7.3.2 贝叶斯定理
#
贝叶斯定理
- 假设
和 是取自样本空间 的两个事件,且 ,则 证明可以借助集合的性质以及[条件概率](#724-条件概率)的定义
#
扩展的贝叶斯定理
-
- 分母部分等价于
- 分子部分等价于
- 分母部分等价于
# 7.3.3 贝叶斯垃圾邮件过滤器
基本原理
- 已知证据
- 特定的单词或词组在垃圾邮件中出现的概率以及在非垃圾邮件中出现的概率
- 借助已知证据来估算包含特定的单词或词组的新邮件是否为垃圾邮件
简单的贝叶斯邮件过滤器
-
- 其中
和 分别是含有字 的信息是垃圾邮件的概率和不是垃圾邮件的概率 是含有字 的邮件是垃圾邮件的概率,
- 其中
为了提高贝叶斯过滤器的性能,可以找出成对的字在垃圾邮件和不在垃圾邮件中出现的概率
# 7.4 期望值和方差
# 7.4.1 引言
# 7.4.2 期望值
#
期望和偏差的定义
-
- 一个随机变量的期望值是将样本空间中所有元素的概率与其对应的随机变量值相乘,然后再求所有乘积之和
- 期望是一个随机变量值的加权平均
- 其为随机变量值的分布提供了一个中心点
#
把随机变量值相等的试验结果分成组来求解随机变量的期望值
-
- 相当于是对 期望的定义 进行了指标替换
#
伯努利试验 (二项分布) 的期望值
-
- 证明可以借助伯努利试验的独立性及二项分布
- 也可借助于 期望的线性性质
# 7.4.3 期望的线性性质
#
期望的线性性质
-
- 可以把随机变量表示成一些很容易找到期望值的随机变量之和
# 7.4.4 平均情形下的计算复杂度
可以将算法在平均情形下的计算复杂度转变为计算一个随机变量的期望值
🔲 待做事项
- 关于插入排序平均情形复杂度的分析没看太懂
# 7.4.5 几何分布
#
几何分布的定义
几何分布用于研究在一个特定事件发生前所需要的时间 (次数)
#
# 7.4.6 独立随机变量
#
独立随机变量的定义
#
两个独立的随机变量之积的期望值
-
- 借助独立随机变量的定义和期望的定义进行证明
# 7.4.7 方差
#
方差的定义
-
- 中文翻译版的定义有错误,标准差应该定义为
- 中文翻译版的定义有错误,标准差应该定义为
#
定理 746
-
- 书中的定义有错,应该是
- 书中的定义有错,应该是
#
#
比安内梅公式
-
- 注意证明时不能直接使用数学归纳法
- 因为
两两独立并不能推出, , 与 相互独立- 参照练习33,P434
- 因为
- 注意证明时不能直接使用数学归纳法
# 7.4.8 切比雪夫不等式
#
切比雪夫不等式
-
- 其对随机变量的值与它的期望值之差超过某个指定量的概率提供了一个上限
- 证明利用集合关系
- 其中
- 其中
编辑 (opens new window)