CS70 Disc 12B

1 Interesting Gaussians

1.1 问题描述

(a) 设 $ X N(0, ^2_X) $ 和 $ Y N(0, ^2_Y) $ 是独立的随机变量。求对于任何奇数 $ k $，有：$ E[(X + Y)^k] $

(b) 设 $ f_{, }(x) $ 是 $ N(, ^2) $ 随机变量的概率密度函数，且 $ X $ 按照以下分布： $ X f_{_1, 1}(x) + (1-)f{_2, _2}(x) $ 求 $ E[X] $ 和 $ (X) $。 $ X $ 是否服从正态分布？

2. 解答

(a) 计算期望值

独立性与和的分布：
- 因为 $ X $ 和 $ Y $ 是独立的高斯随机变量，所以 $ Z = X + Y $ 也服从高斯分布： $ Z N(0, ^2_X + ^2_Y) $
- 其概率密度函数 $ f_Z(x) $ 在原点是对称的，即 $ f_Z(x) = f_Z(-x) $。
期望值计算：
- 由于 $ Z $ 的概率密度函数是偶函数，若 $ k $ 是奇数，则 $ E[(X + Y)^k] $ 的计算为： $ E[(X + Y)^k] = E[Z^k] = _{-}^{} x^k f_Z(x) , dx $
- 利用对称性，有： $ E[Z^k] = {-}^{0} x^k f_Z(x) , dx + {0}^{} x^k f_Z(x) , dx $
- 这两个积分相等且符号相反，因此： $ E[(X + Y)^k] = 0 $
- 结论：对于任何奇数 $ k $：$ E[(X + Y)^k] = 0 $

(b) 计算期望值和方差

期望值的计算：
- 根据加权期望值的性质： $ E[X] = E[X_1] + (1 - ) E[X_2] = _1 + (1 - ) _2 $
方差的计算：
- 利用方差的性质： $ (X) = E[X^2] - (E[X])^2 $
- 首先计算 $ E[X^2] $：$ E[X^2] = E[X_1^2] + (1 - ) E[X_2^2] $
- 由定义： $ E[X_1^2] = (X_1) + (E[X_1])^2 = ^2_1 + _1^2 $ $ E[X_2^2] = (X_2) + (E[X_2])^2 = ^2_2 + _2^2 $
- 将其代入： $ E[X^2] = (^2_1 + _1^2) + (1 - )(^2_2 + _2^2) $
- 结合以上结果： $ (X) = E[X^2] - (E[X])^2 = (^2_1 + _1^2) + (1 - )(^2_2 + _2^2) - (_1 + (1 - ) _2)^2 $
是否服从正态分布：
- $ X $ 并不一定服从正态分布。具体而言，如果 $ = , _1 = -10, _2 = 10, _1 = _2 = 1 $，则概率密度函数的图形可能有两个峰值，表明 $ X $ 不再是正态分布。

3. 总结

对于独立的高斯随机变量 $ X $ 和 $ Y $，如果 $ k $ 为奇数，则 $ E[(X + Y)^k] = 0 $。
通过加权组合得到的随机变量 $ X $ 的期望和方差可以计算，但 $ X $ 并不一定是正态分布。

2 BinomialConcentrat

1. 问题描述

我们将证明当试验次数趋向于无穷大时，二项分布关于其均值的集中性。假设我们有独立同分布的试验，每次成功的概率为 $\frac{1}{2}$。设 $S_n$ 为前 $n$ 次试验中的成功次数（$n$ 为正整数）。

2. 问题解答

(a) 计算 $S_n$ 的均值和方差

由于 $S_n$ 服从二项分布 $Binomial(n, \frac{1}{2})$，我们有：

均值: $ E[S_n] = n = $
方差: $ Var(S_n) = n (1 - ) = n = $

(b) 定义 $Z_n$ 使其均值为0，方差为1

我们可以定义 $ Z_n = = = = $ 这样定义后，$Z_n$ 的均值和方差为：

均值: $ E[Z_n] = = = 0 $
方差: $ Var(Z_n) = = = 1 $

(c) $Z_n$ 的极限分布

根据中心极限定理，当 $n \to \infty$ 时，$Z_n$ 的分布趋向于标准正态分布： $ Z_n N(0, 1) $

(d) 使用界限估算 $P\left[\frac{S_n}{n} > \frac{1}{2} + \delta\right]$

为了应用给定的界限，我们需要将其应用于 $Z_n$。 $ P= P= P$ 接下来，我们标准化： $ = P= P$

使用已知的正态分布界限： $ P[Z > z] e^{-} (Z ) $ 可以得到： $ P e^{-} = e^{-22n} $

最终结果为： $ P e^{-22n} $

3 Erasures, Bounds, and Probabilities

1. 问题描述

Alice 向 Bob 发送了 1000 个比特，每个比特被擦除的概率为 $p$，且每个比特的擦除是独立的。Alice 使用了一种方案，只要 Bob 收到至少 801 个比特（即最多有 199 个比特被擦除），他就能够解码 Alice 的消息。

若有 200 个或更多比特被擦除，我们称此情况为“通信崩溃”。目标是将通信崩溃的概率控制在不超过 $10^{-6}$。

2. 问题解答

(a) 使用切比雪夫不等式来上界 $p$ ，使得通信崩溃的概率不超过 $10^{-6}$

设 $X$ 为擦除的比特数量的随机变量。根据切比雪夫不等式： $ P(|X - _X| k) $ 我们需要估算 $P[X \geq 200]$。于是： $ P[X ] = P[X - _X - _X] P[|X - _X| - _X] $ 根据二项分布的性质，$X \sim Binomial(1000, p)$，有：

均值: $ _X = 1000p $
方差: $ _X^2 = 1000p(1 - p) $ 代入切比雪夫不等式的公式： $ P[X ] $ 化简得到： $ P[X ] $ 我们需要满足： $ ^{-6} $ 解得 $p$ 的上界约为 $3.998 \times 10^{-5}$。

(b) 使用中心极限定理估算 $p$ 的近似界限

设 $Y = \frac{X}{1000}$，即擦除的比特所占的比例。根据期望与方差的性质，可以得到：

期望: $ E[Y] = p $
方差: $ Var(Y) = Var(X) = $ 根据中心极限定理，我们可以认为 $Y$ 近似服从正态分布，且其均值和方差分别为 $p$ 和 $\frac{p(1 - p)}{1000}$。

我们关心事件 $Y \geq 0.2$ 的概率。首先计算 0.2 相对于均值 $p$ 的标准差个数： $ = $ 根据中心极限定理，通信崩溃的概率大约为： $ P[Y ] - () $ 这里 $\Phi$ 是标准正态分布的累积分布函数。我们要求： $ 1 - () ^{-6} $ 即： $ () - 10^{-6} $ 根据已知 $\Phi^{-1}(1 - 10^{-6}) \approx 4.753$，可以得到不等式： $ $ 解得 $p \leq 0.1468$。