知识焦点
先建立概念地图
- 高斯分布
- 混合分布
- 二项分布
- 中心极限定理
- 尾概率上界
- 期望与方差
- 概率论
- 切比雪夫不等式
CS70 · 讨论课 13b
本讨论课资料包含两道概率论题目：第一题研究独立零均值高斯随机变量之和的奇次矩，以及由两个高斯密度混合而成的分布的期望、方差与正态性判定；第二题通过标准化变换与中心极限定理，证明二项分布在试验次数趋于无穷时集中在均值附近，并利用标准正态尾概率上界给出二项分布的近似界。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis13b.pdf、solutions/discussion/dis13b-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 3 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis13b.pdf、solutions/discussion/dis13b-sol.pdf令 \(X \sim \mathcal{N}(0, \sigma_X^2)\) 与 \(Y \sim \mathcal{N}(0, \sigma_Y^2)\) 为相互独立的高斯（正态）随机变量。
(a) 对任意奇数 \(k \in \mathbb{N}\)，求 \(\mathbb{E}\big[(X+Y)^k\big]\)。
(b) 设 \(f_{\mu,\sigma}(x)\) 为 \(\mathcal{N}(\mu, \sigma^2)\) 随机变量的概率密度函数，且随机变量 \(X\) 的分布密度为 \[ \alpha f_{\mu_1,\sigma_1}(x) + (1-\alpha) f_{\mu_2,\sigma_2}(x), \] 其中 \(\alpha \in [0,1]\)。计算 \(\mathbb{E}[X]\) 与 \(\operatorname{Var}(X)\)。问：\(X\) 是否一定服从正态分布？
(a) 独立高斯随机变量之和仍为正态分布；考虑均值为 0 时密度函数的对称性，以及奇函数在对称区间上积分的性质。
(b) 利用期望与方差对混合密度的线性性质，先求出 \(\mathbb{E}[X]\) 与 \(\mathbb{E}[X^2]\)，再通过 \(\operatorname{Var}(X)=\mathbb{E}[X^2]-(\mathbb{E}[X])^2\) 计算方差；判断正态性时，可考察密度函数极值点的个数。
(a) \(\mathbb{E}\big[(X+Y)^k\big] = 0\)。
由于 \(X\) 与 \(Y\) 均为高斯随机变量，故 \(Z = X + Y\) 也必为正态分布。又因为 \(Z\) 的均值为 0，其密度函数 \(f_Z\) 关于原点对称，即对任意 \(x \in \mathbb{R}\) 有 \(f_Z(x) = f_Z(-x)\)。因此 \[ \mathbb{E}\big[(X+Y)^k\big] = \mathbb{E}[Z^k] = \int_{-\infty}^{\infty} x^k f_Z(x)\,\mathrm{d}x = \int_{-\infty}^{0} x^k f_Z(x)\,\mathrm{d}x + \int_{0}^{\infty} x^k f_Z(x)\,\mathrm{d}x. \] 对第一项作变量替换 \(x \mapsto -x\)，并利用 \(f_Z(-x)=f_Z(x)\) 以及 \(k\) 为奇数时 \((-x)^k = -x^k\)，得 \[ \int_{-\infty}^{0} x^k f_Z(x)\,\mathrm{d}x = \int_{0}^{\infty} (-x)^k f_Z(-x)\,\mathrm{d}x = -\int_{0}^{\infty} x^k f_Z(x)\,\mathrm{d}x, \] 故两项之和为 0。
(b) \(\mathbb{E}[X] = \alpha \mu_1 + (1-\alpha)\mu_2\)， \[ \operatorname{Var}(X) = \alpha\big(\sigma_1^2 + \mu_1^2\big) + (1-\alpha)\big(\sigma_2^2 + \mu_2^2\big) - \big(\mathbb{E}[X]\big)^2. \] \(X\) 不一定服从正态分布。
计算如下： \[ \mathbb{E}[X] := \mu = \int_{-\infty}^{\infty} x\big(\alpha f_{\mu_1,\sigma_1}(x) + (1-\alpha) f_{\mu_2,\sigma_2}(x)\big)\,\mathrm{d}x = \alpha\int_{-\infty}^{\infty} x f_{\mu_1,\sigma_1}(x)\,\mathrm{d}x + (1-\alpha)\int_{-\infty}^{\infty} x f_{\mu_2,\sigma_2}(x)\,\mathrm{d}x = \alpha\mu_1 + (1-\alpha)\mu_2. \] \[ \operatorname{Var}(X) := \sigma^2 = \mathbb{E}[X^2] - \mu^2 = \alpha\int_{-\infty}^{\infty} x^2 f_{\mu_1,\sigma_1}(x)\,\mathrm{d}x + (1-\alpha)\int_{-\infty}^{\infty} x^2 f_{\mu_2,\sigma_2}(x)\,\mathrm{d}x - \mu^2 = \alpha\big(\sigma_1^2+\mu_1^2\big) + (1-\alpha)\big(\sigma_2^2+\mu_2^2\big) - \mu^2. \]
正态分布 \(\mathcal{N}(\mu,\sigma)\) 的密度函数在 \(x=\mu\) 处有唯一最大值。然而，例如当 \(\alpha = 1/2\)、\(\mu_1 = -10\)、\(\mu_2 = 10\)、\(\sigma_1 = \sigma_2 = 1\) 时，混合密度 \(\alpha f_{\mu_1,\sigma_1} + (1-\alpha) f_{\mu_2,\sigma_2}\) 有两个极大值点，因此不可能是高斯分布的密度函数。
解答来源：solutions/discussion/dis13b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis13b.pdf · 1 · confidence: high
本题旨在证明：当试验次数趋于无穷时，二项分布集中在均值附近。设各次试验独立同分布（i.i.d.），每次试验成功的概率为 \(1/2\)。记 \(S_n\) 为前 \(n\) 次试验中成功的次数（\(n\) 为正整数）。
(a) 计算 \(S_n\) 的均值与方差。
(b) 试用 \(S_n\) 定义 \(Z_n\)，使得 \(Z_n\) 的均值为 0 且方差为 1。
(c) 当 \(n \to \infty\) 时，\(Z_n\) 服从什么分布？
(d) 利用标准正态随机变量 \(Z\) 满足的上界 \[ \mathbb{P}[Z > z] \le \frac{1}{z\sqrt{2\pi}}\,e^{-z^2/2}, \] 近似估计 \(\mathbb{P}[S_n/n > 1/2 + \delta]\)，其中 \(\delta > 0\)。
(a) 将 \(S_n\) 写成 \(n\) 个独立伯努利随机变量之和，利用期望与方差的线性性质（注意独立时协方差为 0）。
(b) 对 \(S_n\) 作标准化变换：先减去均值，再除以标准差。
(c) 考虑中心极限定理（Central Limit Theorem）。
(d) 将事件 \(S_n/n > 1/2 + \delta\) 通过标准化改写成关于 \(Z_n\) 的尾概率，再代入题目所给的上界公式。
(a) 由于 \(S_n \sim \operatorname{Binomial}(n, 1/2)\)，故 \[ \mathbb{E}[S_n] = \frac{n}{2}, \quad \operatorname{Var}(S_n) = \frac{n}{4}. \]
(b) 定义 \[ Z_n := \frac{S_n - \mathbb{E}[S_n]}{\sqrt{\operatorname{Var}(S_n)}} = \frac{S_n - n/2}{\sqrt{n/4}} = \frac{2(S_n - n/2)}{\sqrt{n}}. \] 即先减去均值、再除以标准差对 \(S_n\) 作标准化。验证： \[ \mathbb{E}[Z_n] = \frac{1}{\sqrt{n/4}}\,\mathbb{E}\left[S_n - \frac{n}{2}\right] = \frac{1}{\sqrt{n/4}}\!\left(\mathbb{E}[S_n] - \frac{n}{2}\right) = 0, \] \[ \operatorname{Var}(Z_n) = \frac{1}{n/4}\,\operatorname{Var}\!\left(S_n - \frac{n}{2}\right) = \frac{1}{n/4}\,\operatorname{Var}(S_n) = 1, \] 其中用到 \(S_n \sim \operatorname{Binomial}(n, 1/2)\)。
(c) 由中心极限定理可知 \(Z_n \to \mathcal{N}(0,1)\)。
(d) 为应用题目所给上界，需先将事件改写为关于 \(Z_n\) 的形式： \[ \mathbb{P}\!\left[\frac{S_n}{n} > \frac{1}{2} + \delta\right] = \mathbb{P}\!\left[\frac{S_n - n/2}{n} > \delta\right] = \mathbb{P}\!\left[\frac{S_n - n/2}{\sqrt{n/4}} > 2\delta\sqrt{n}\right] \approx \mathbb{P}[Z_n > 2\delta\sqrt{n}] \le \frac{1}{2^{3/2}\delta\sqrt{\pi n}}\,e^{-2\delta^2 n}. \]
解答来源：solutions/discussion/dis13b-sol.pdf · 2 · confidence: high
题面来源：discussion/dis13b.pdf · 2 · confidence: high
Alice 正在向 Bob 发送 1000 个比特（bit）。每个比特被擦除的概率为 \(p\)，且各比特的擦除事件相互独立。
Alice 使用的编码方案最多能容忍五分之一的比特被擦除。也就是说，只要 Bob 正确接收到 1000 个比特中至少 801 个，他就能解码 Alice 的消息。
换句话说，只有当 200 个或更多比特被擦除时，Bob 才无法解码 Alice 的消息。我们将这种情况称为「通信中断」（communication breakdown），并希望通信中断的概率至多为 \(10^{-6}\)。
(a) 使用切比雪夫不等式（Chebyshev's inequality）给出 \(p\) 的上界，使得通信中断的概率至多为 \(10^{-6}\)。
(b) 按照中心极限定理（Central Limit Theorem, CLT）的思路，将擦除比例近似为一个具有适当均值和方差的高斯（正态）随机变量。利用该近似，求出 \(p\) 的一个近似上界，使得通信中断的概率至多为 \(10^{-6}\)。
你可以使用 \(\Phi^{-1}(1 - 10^{-6}) \approx 4.753\)。
对于 (a)，考虑用切比雪夫不等式处理二项随机变量 \(X\) 的尾部概率，注意将 \(P[X \geq 200]\) 转化为 \(|X - \mu_X|\) 的形式。对于 (b)，考虑将擦除数量 \(X\) 归一化为擦除比例 \(Y = X/1000\)，利用中心极限定理将其近似为正态分布，再借助标准正态分布的 CDF \(\Phi\) 与给定的分位点 \(\Phi^{-1}(1-10^{-6})\) 建立不等式。
(a) 设 \(X\) 表示被擦除的比特数。切比雪夫不等式给出： \[ P[|X - \mu_X| \geq k] \leq \frac{\sigma_X^2}{k^2}. \] 由此得到 \[ P[X \geq 200] = P[X - \mu_X \geq 200 - \mu_X] \leq P[|X - \mu_X| \geq 200 - \mu_X] \leq \frac{\sigma_X^2}{(200 - \mu_X)^2}. \] 由于 \(X \sim \text{Binomial}(1000, p)\)，我们有 \(\mu_X = 1000p\) 且 \(\sigma_X^2 = 1000p(1-p)\)。代入得 \[ P[X \geq 200] \leq \frac{1000p(1-p)}{(200 - 1000p)^2} = \frac{p(1-p)}{40(1-5p)^2}. \] 为满足目标，只需确保 \[ P[X \geq 200] \leq \frac{p(1-p)}{40(1-5p)^2} \leq 10^{-6}, \] 由此解得 \(p\) 的上界约为 \(3.998 \times 10^{-5}\)。
(b) 设 \(Y\) 为擦除比例，即 \(Y = X/1000\)。利用期望和方差的性质可得 \[ \mathbb{E}[Y] = p, \quad \text{Var}(Y) = \text{Var}(X) \cdot \frac{1}{1000^2} = \frac{p(1-p)}{1000}. \] 因此，由中心极限定理可知 \(Y\) 近似服从具有上述均值和方差的正态分布。由于我们关注的是事件 \(Y \geq 0.2\)，计算 0.2 距离均值有多少个标准差： \[ \frac{0.2 - p}{\sqrt{\frac{p(1-p)}{1000}}} = \frac{(0.2-p)\sqrt{1000}}{\sqrt{p(1-p)}}. \] 因此，失败事件的概率近似为（由 CLT） \[ 1 - \Phi\left(\frac{(0.2-p)\sqrt{1000}}{\sqrt{p(1-p)}}\right), \] 其中 \(\Phi\) 为标准正态分布的累积分布函数（CDF）。令该式不超过 \(10^{-6}\)，得到 \[ \Phi\left(\frac{(0.2-p)\sqrt{1000}}{\sqrt{p(1-p)}}\right) \geq 1 - 10^{-6}. \] 又因为 \(\Phi^{-1}(1 - 10^{-6}) \approx 4.753\)，我们求解不等式 \[ \frac{(0.2-p)\sqrt{1000}}{\sqrt{p(1-p)}} \geq 4.753, \] 得到 \(p \leq 0.1468\)。
注意，这与前面的结果相差较大。这是因为中心极限定理对尾事件的近似比马尔可夫不等式（Markov's inequality）和切比雪夫不等式更紧。不过，我们之所以能应用中心极限定理，是因为 \(n\) 足够大。
因此，为使通信中断概率达到 \(10^{-6}\)，我们并不需要 \(p\) 那么小。其他界要求概率在 \(10^{-5}\) 量级，而这里我们只需要 \(p\) 小于 0.1468。（真实界为 0.1459。）差距相当大！
解答来源：solutions/discussion/dis13b-sol.pdf · 2-4 · confidence: high
题面来源：discussion/dis13b.pdf · 3-4 · confidence: high
discussion/dis13b.pdfsolutions/discussion/dis13b-sol.pdf