第二章 离散数学的度量2.1 概率论基本知识2.1.1 样本空间与随机事件1. 随机试验具有随机性、结果事先不可预测的试验用字母 E 表示。2. 样本空间 Ω随机试验所有可能结果构成的集合Ω 是其中单个结果叫做样本点。书中4个例子理解样本空间可以从三个层次把握试验先行先明确随机试验 E 的规则也就是“怎么试、试几次、观察什么”样本空间才有确定的含义。结果穷尽样本空间必须把试验所有可能的结果都收进来不能遗漏也不能把不可能出现的结果放进去。结果互斥任意两个不同的样本点不能同时发生一次试验的结果有且只有一个样本点与之对应。用集合的语言来说样本空间Ω就是随机试验 E 的全体可能结果组成的集合其中每一个元素 ω 称为一个样本点。样本空间可以是有限的也可以是无限的样本点可以是数值也可以不是数值例如抛硬币得到的 H 和 T 就只是符号。需要特别区分两个容易混淆的记号Ω表示整个样本空间大写集合ω表示其中的一个样本点小写元素二者是“整体与个体”的关系写作 ω ∈ Ω。下面结合书中的 4 个例子逐一说明样本空间是如何构造出来的抛 1 枚硬币Ω {H, T}其中 H 表示正面T 表示反面。抛 2 枚硬币Ω {HH, HT, TH, TT}每个样本点按“第一枚、第二枚”的顺序记录结果。二元信源发 1 个符号Ω {0, 1}。二元信源发 2 个符号Ω {00, 01, 10, 11}共 2² 4 个样本点。从这 4 个例子可以看出抛 1 枚硬币与二元信源发 1 个符号本质上是同一个样本空间只是符号的写法不同抛 2 枚硬币与二元信源发 2 个符号同理。样本点的个数由试验的“次数”和每次的可能结果数共同决定若每次有 k 种可能、独立进行 n 次则样本空间共有 kn 个样本点。3. 随机事件【定义 2.1核心考点】样本空间Ω的任一子集 E ⊆ Ω就称为随机事件简称事件。简单理解事件就是由样本点组成的子集。举例抛一枚硬币事件 E {H}正面朝上。抛两枚硬币E {HH, HT}第一枚硬币正面朝上。一句话核心随机试验的全部结果放进集合就是样本空间从里面挑一部分样本点构成子集就是随机事件这是信息论里描述信源输出符号随机性的基础。• 抛一枚硬币事件 E\{H\}正面朝上• 抛两枚硬币E\{HH,HT\}第一枚硬币正面朝上随机试验全部结果放进集合就是样本空间从里面挑一部分样本点构成子集就是随机事件这是信息论里描述信源输出符号随机性的基础。2.1.2 概率的有关概念1. 概率对样本空间Ω中任意事件 EP[E]简写 p(E)满足 3 条公理非负性0 ≤ P[E] ≤ 1概率取值一定在 0 到 1 之间。归一性P[Ω] 1整个样本空间所有可能结果发生的概率等于 1。可列可加性对于互不相容互斥n ≠ m 时 En ∩ Em ∅的事件序列有P[⋃n1∞ En] ∑n1∞ P[En]2. 条件概率p(B|A)事件 A 已经发生的前提下事件 B 发生的概率。公式课本圈出的条件概率公式p(B|A) p(AB) / p(A)其中 p(A) 0变形得到乘法公式p(AB) p(A) · p(B|A) p(B) · p(A|B)事件相互独立重要推论若 A、B 相互独立A 发不发生不会影响 B 发生的可能性p(B|A) p(B)乘法公式简化为p(AB) p(A)p(B)条件概率示意图维恩图用维恩图理解条件概率可以按下面的方式对应各个区域方框代表原始样本空间Ω也就是所有可能结果的全体对应概率 p(Ω) 1。两个圆分别代表事件 A 和事件 B圆内的点就是各自包含的样本点圆的面积可以直观理解为对应事件的概率大小。黑色相交阴影就是 A、B 同时发生的区域也就是交集 AB对应联合概率p(AB)。几何理解原本全集是样本空间Ω求 p(B|A) 的时候样本空间缩小为 A只看 A 里面同时也属于 B 的部分也就是交集 AB。因此条件概率本质上是在“缩小后的样本空间 A”上重新做一次归一化分母从 p(Ω) 变成 p(A)分子则取交集部分的 p(AB)。这也正好解释了公式的由来在 A 已经发生的前提下B 发生的可能性等于“A 与 B 同时发生”占“A 发生”的比例即 p(AB) / p(A)。从维恩图上看条件概率的求解可以拆成三步锁定新全集既然 A 已经发生就把观察范围限制在圆 A 内部圆外的样本点全部不再考虑。找出有利区域在圆 A 内部只有落在圆 B 里的那部分才满足“B 发生”也就是交集 AB。做比例运算用交集 AB 的概率除以圆 A 的概率得到 p(B|A) p(AB) / p(A)。由此还能得到两个常用结论当 A、B 互不相容时交集为空p(AB) 0于是 p(B|A) 0当 A、B 相互独立时p(AB) p(A)p(B)代入公式恰好得到 p(B|A) p(B)与前面的独立推论一致。3. 联合概率事件 A 和事件 B 同时发生的概率叫做联合概率记作p(AB)也常写作 p(A ∩ B)。它描述的是两个事件“一起发生”的可能性对应维恩图中两个圆相交的那块阴影区域。核心公式p(AB) p(A) · p(B|A) p(B) · p(A|B)这个公式由条件概率公式 p(B|A) p(AB) / p(A) 两边同乘 p(A) 直接得到前提是 p(A) 0 且 p(B) 0。概念拆解p(A)事件 A 发生的先验概率边缘概率也就是在不考虑 B 的情况下A 本身发生的可能性。p(B|A)在 A 已经发生的条件下 B 发生的概率即条件概率。p(AB)A、B 两件事一起发生的概率即联合概率。理解p(A)p(B|A)先让 A 发生再在 A 发生的前提下让 B 发生两步的可能性相乘就是 AB 同时发生的概率。p(B)p(A|B)先让 B 发生再在 B 发生的前提下让 A 发生路径不同但结果一样所以两条式子相等。换句话说乘法公式给出了“分步计算联合概率”的方法把同时发生拆成先后两步用第一步的概率乘以第二步的条件概率即可。当 A、B 相互独立时p(B|A) p(B)公式退化为p(AB) p(A)p(B)与前面独立性的结论完全一致。小例子一批产品中A 表示“抽到次品”p(A) 0.1已知抽到次品时B 表示“该产品来自甲车间”p(B|A) 0.4。那么“抽到的产品既是次品又来自甲车间”的联合概率为 p(AB) p(A) · p(B|A) 0.1 × 0.4 0.04。2.1.3 全概率公式和贝叶斯公式本节围绕完备事件组、全概率公式、贝叶斯公式三个核心概念展开。全概率公式解决“由因求果”的问题贝叶斯公式解决“由果溯因”的问题而完备事件组是这两个公式成立的前提。1. 完备事件组样本空间的划分设 a1, a2, …, aN 是样本空间 Ω 的一组事件若满足以下两个条件就称它为完备事件组两两互斥ai ∩ aj ∅任意 i ≠ j。事件之间没有交集不能同时发生。全部合起来等于整个样本空间⋃n1N an Ω。 一句话理解把整个样本空间切分成 N 块互不重叠拼起来正好是全集。2. 全概率公式公式p(B) ∑i1N p(ai) p(B|ai)含义事件 B 可以从不同原因 a1, a2, …, aN 发生。把每一条原因发生的概率乘以在该原因下 B 发生的条件概率全部相加就得到 B 总的发生概率。方向由因求果。已知各个原因求最后结果 B 发生的总概率。课本例题三种行人 a1, a2, a3 构成完备事件组乞丐得到捐款为事件 B。p(a1) 0.1p(B|a1) 0.2p(a2) 0.6p(B|a2) 0.8p(a3) 0.3p(B|a3) 0.9代入全概率公式p(B) 0.1 × 0.2 0.6 × 0.8 0.3 × 0.9 0.773. 贝叶斯公式逆概率公式一般形式p(ai|B) p(ai) p(B|ai) / ∑k1N p(ak) p(B|ak)含义已经知道结果 B 发生了反过来求这个结果是由第 ai 个原因造成的概率。方向由果溯因。已知结果反推是哪一个来源或原因导致的。例题结果乞丐已经拿到捐款反推捐款来自哪一类行人p(a1|B) 0.026p(a2|B) 0.623p(a3|B) 0.351三个后验概率之和为 1说明结果 B 一定由这三类原因之一造成只是各自占比不同。 核心对比背诵关键点公式方向已知求解全概率公式由因求果各原因概率 p(ai) 与条件概率 p(B|ai)结果 B 的总概率 p(B)贝叶斯公式由果推因结果 B 已发生以及各原因的先验概率各原因的后验概率 p(ai|B)全概率由因求果算结果 B 总的概率。贝叶斯由果推因结果已经出现反推各个原因占比。2.1.4 先验概率和后验概率1. 核心概念后验概率就是贝叶斯公式算出的 p(ai|B)。事件 B 已经发生之后反过来求造成 B 的各个原因 ai 发生的条件概率属于知道结果反推原因。先验概率事件本身自带的随机概率不需要依赖别的事件、不需要等到结果发生就可以直接得到代表事件本身固有的统计特性。简单区分先验概率接收之前就知道p(x1)、p(x2)信源发符号本身的概率。后验概率收到符号之后再推算p(xi|yj)收到 yj反推原来发的是 xi。2. 例 2.3 二元信源例题信源发送x1 0x2 1等概率发送p(x1) p(0) 0.5p(x2) p(1) 0.5信道转移条件概率发送 x 的情况下收到 yp(y1|x1) p(0|0) 0.6p(y2|x1) p(1|0) 0.4p(y1|x2) p(0|1) 0.2p(y2|x2) p(1|1) 0.8题目信宿收到符号为 1y2求原来信源发出符号 0 的概率 p(x1|y2)。套用贝叶斯公式p(x1|y2) p(x1)p(y2|x1) / [ p(x1)p(y2|x1) p(x2)p(y2|x2) ]代入数值算出p(x1|y2) 0.43同理p(x2|y2) 0.573. 例题结论收到符号 1 的时候p(x2|y2) 0.57 p(x1|y2) 0.43说明收到 1更有可能原本发送的就是符号 1。物理含义信道发送 1 收到 1 的转移概率本身比较大所以接收端判断收到的 1 大概率来自信源的符号 1。2.1.5 离散随机变量1. 随机变量的概念设随机试验 E样本空间Ω {ω}对每一个样本点 ω ∈ Ω都对应一个实数 X即建立从样本空间到实数集的单值函数X(ω)简称随机变量一般记作 X。通俗理解把试验结果样本点映射成数字不用再描述具体事件直接用数值代表结果。记号约定随机变量用大写 X、Y、Z、ξ、η 表示它的具体取值用小写 x、y、z 表示。例 2.4 掷两次骰子求和关注点不是 (5,5)、(4,6) 这种具体的抛掷组合而是点数之和这个数值和可取 2, 3, …, 12这个点数之和就是随机变量。举例映射抛硬币正面 H → 0反面 T → 1把文字结果转换成数字。2. 离散随机变量离散随机变量取值为有限个或者无限但可数的随机变量。无限但可数集合元素可以和正整数一一对应最简单的例子全体正整数。骰子点数之和的例子取值 2~12一共有限个取值属于离散随机变量。3. 累积分布函数 CDF公式F(x) P[X ≤ x]含义随机变量 X 取值小于或者等于 x的概率简称分布函数。这个定义不限于离散随机变量可以推广到所有类型的随机变量。分布函数 4 条重要性质考点非减性F(x) 是 x 的非减函数x 越大F(x) 不会变小。右连续性F(x) 是右连续的即 F(x 0) F(x)。上界limx → ∞ P[X ≤ x] F(∞) 1。下界limx → -∞ P[X ≤ x] F(-∞) 0。2.1.6 离散随机变量的统计特性一、离散随机变量的统计特性数学期望数学期望刻画的是随机变量的群体平均水平不是某一次试验的具体结果本质上是一个加权平均值权重就是对应取值发生的概率。1. 单个离散随机变量的数学期望定义 2.9若离散随机变量 X 的概率分布为 p(xn)则其数学期望定义为E[X] ∑n1N xn p(xn)含义把各个取值乘以对应概率再全部求和也就是以概率为权重的加权平均。2. 两个离散随机变量乘积的数学期望定义 2.10已知 X、Y 的联合分布为 p(xi, yj)则E[XY] ∑i1N ∑j1M xi yj p(xi, yj)3. 离散随机变量函数 f(X) 的数学期望定义 2.11不需要先求出 f(X) 的分布可以直接利用原变量 X 的概率分布计算E[f(X)] ∑i1N f(xi) p(xi)二、2.2 信息度量方法的引入信息量的直观理解例子对比“今年夏天比冬天热”几乎一定会发生属于废话信息量几乎为 0。“今年冬天比夏天热”发生概率极低非常意外携带很大的信息量。三条直观规律事件发生概率越小不确定性越大包含的信息量越多。必然发生的事件概率 1信息量等于 0。事件发生概率越大信息量越少概率越小信息量越大。信息量满足的公理条件信息量是事件概率的严格递减函数概率越小信息量越大。极限情况p 1 时信息量为 0p → 0 时信息量趋向无穷大。可加性两个独立事件同时发生的总信息量等于各自信息量相加。结论选用对数函数来刻画信息量公式形式为 -log p完美符合上面全部公理。图像特点横坐标为 p纵坐标为 -log pp 1 时信息量为 0p 越靠近 0信息量急剧变大。2.2 信息度量方法的引入前面 2.1 节建立了概率语言用样本空间描述随机试验用概率描述事件发生的可能性用随机变量把事件映射成数值。本节要回答一个更进一层的问题一条消息到底携带多少信息能不能用数学定量地度量答案是肯定的而且度量的工具正是建立在概率之上的对数函数。一、直观例子理解信息量先不急着上公式用两个消息做对比就能直观感受到“信息量”是什么。消息一今年夏天比冬天热。这属于几乎必然发生的常识大家早就预料到几乎没有信息量相当于废话。消息二今年冬天比夏天热。发生概率极低属于很反常的事件携带非常丰富的信息量。 由此得到三条直观结论越不可能概率小的消息包含的信息量越多。完全确定、必然会发生的消息信息量等于 0。消息发生的概率越大信息量越少概率越小信息量越大。二、信息量的三大公理化条件理论要求直观结论要变成可计算的量必须满足下面三条公理严格递减性信息量是事件概率的严格递减函数概率越小不确定性越大信息量就越多。极限特性事件概率 p 1必然事件信息量 0事件概率 p → 0几乎不可能发生信息量趋向无穷大。可加性两个互相独立的事件总的信息量等于两个事件各自信息量相加。三、信息量的数学刻画满足上面全部公理的函数就是对数函数即用-log p来定量描述信息量。其中可加性正是对数函数的关键优势独立事件对应概率相乘取对数后恰好变成信息量相加。图像含义图 2.4横轴事件发生概率 p纵轴-log p信息量。p 1 时曲线纵坐标为 0对应确定无疑的消息信息量为 0。p 趋近于 0 时信息量快速上升并趋近无穷对应几乎不会发生的消息信息量无穷大。四、补充理解通信角度通信里面有意义的消息必须带有随机性。如果接收方事先完全知道信源要发什么确定无疑这个通信系统就没有存在的必要。正因为信源输出带有不确定性接收方收到消息后不确定性被消除才谈得上“获得了信息”。信息论中正是利用对数函数来刻画一条消息所含信息的多少。2.3 自信息量和信息熵本节把 2.2 节“用对数函数度量信息量”的结论正式落地给出两个最基础、也是考试最常考的度量自信息量针对单个事件和信息熵针对整个信源。前者回答“一个事件发生带来多少信息”后者回答“一个信源平均每次输出多少信息”。一、自信息量单个事件公式I(xi) -loga p(xi)含义单个随机事件发生所带来的信息量同时也代表该事件本身的不确定性。事件越难发生一旦发生就越“意外”携带的信息量就越大。单位由对数的底 a 决定a 2单位为bit比特工程上最常用。a e单位为nat奈特理论推导中常用。a 10单位为det笛特较少使用。特点概率越小自信息量越大概率越大自信息量越小。必然事件 p 1 时自信息量 I -loga1 0。自信息量只和事件发生的概率有关和消息的具体语义无关。二、信息熵平均自信息量信源整体公式H(X) -∑n1N p(xn) log p(xn)含义信息熵是自信息量的数学期望是整个信源符号集合的平均值不是单次事件的信息量。它描述的是信源每输出一个符号平均能提供多少信息。信息熵的 4 层含义信源的平均自信息量。表征随机集合的平均不确定性。熵越大不确定性越强熵越小结果越容易预测。熵越大信源能够提供的平均信息量越大。补充规定0 loga0 0用来处理概率为 0 的符号避免出现 log 0 这种无意义的计算。简单例子记忆甲袋红球 0.6、白球 0.4分布更均匀熵更大不确定性更高。乙袋红球 0.9、白球 0.1明显偏向红球熵更小更容易预判结果。一句话总结自信息量度量“单个事件”的信息量信息熵度量“整个信源”的平均信息量前者是后者的求和项后者是前者的数学期望。