Problem 1
(1)
总共有 $ N=\binom{ n }{ 2 } $ 对点。设 $ X_{ij}=\mathbb{I}[(i,j)\in E_{n}] $。那么 $ \mathbf{E}[X_{ij}]=p $。并且 $$ \left| E_{n} \right| = \sum_{1\leq i< j\leq n} X_{i} $$ 由于边与边之间独立，因此 $ X_{i} $ 是独立同分布，并且可积，那么根据强大数定律，就有 $$ \dfrac{\sum X_{i}}{N} = \dfrac{\left| E_{n} \right| }{\binom{ n }{ 2 } } \xrightarrow{a.s.} \mathbf{E}[X_{i}]=p $$ (2)
设 $ \mathcal{C}_n $ 为 $ V_n $ 中所有大小为 $ 3 $ 的子集的集合，也就是所有无序三元组 $ \{i, j, k\} $。集合大小 $ |\mathcal{C}_n| = \binom{n}{3} $。
对于任意 $ \alpha = \{i, j, k\} \in \mathcal{C}_n $，定义指示变量 $ Y_\alpha $ $$ Y_\alpha = X_{ij} X_{jk} X_{ki} $$ 由于 $ X $ 相互独立，因此 $$ \mathbf{E}[Y_{\alpha}] = \mathbf{E}[X_{ij}]\mathbf{E}[X_{jk}]\mathbf{E}[X_{ki}]=p^{3} $$ 由于三角形总数满足 $ \left| T_{n} \right|=\sum_{\alpha \in \mathcal{C}_{n}}Y_{\alpha} $，那么根据期望的线性性，有 $$ \mathbf{E}[\left| T_{n} \right| ] = \sum_{\alpha \in \mathcal{C}_{n}} \mathbf{E}[Y_{\alpha}] = \binom{ n }{ 3 } p^{3} $$ 接着考虑 $ \left| T_{n} \right| $ 的方差。分析两个不同三元组 $ \alpha $ 和 $ \beta $ 的协方差 $$ \text{Conv}(Y_{\alpha},Y_{\beta}) = \mathbf{E}[Y_{\alpha}Y_{\beta}] - \mathbf{E}[Y_{\alpha}]\mathbf{E}[Y_{\beta}] $$ 假如 $ \alpha,\beta $ 没有公共边，那么相互独立，协方差为零。如果 $ \left| \alpha \cap\beta\right|=2 $，有公共边，那么一共涉及了五条不同的边，从而 $$ \mathbf{E}[Y_{\alpha}Y_{\beta}]=p^{5} \implies \text{Conv}(Y_{\alpha},Y_{\beta}) = p^{5}-p^{6} $$ 并且存在公共边的 $ \alpha,\beta $ 的数量是 $ O(n^{4}) $ 级别的，因为一共涉及到了 $ 4 $ 个点的选择。
因此 $$ \text{Var}(\left| T_{n} \right| ) = \binom{ n }{ 3 } \text{Var}(Y_{\alpha}) + O(n^{4})\cdot(p^{5}-p^{6}) \leq C\cdot n^{4} $$ 考察随机变量 $ Z_{n}=\left| T_{n} \right| / \binom{ n }{ 3 } $。我们有 $$ \text{Var}(Z_{n}) = \dfrac{1}{\binom{ n }{ 3 }^{2}} \text{Var}(\left| T_{n} \right| ) = \dfrac{O(n^{4})}{O(n^{6})} = O(n^{-2}) $$ 从而对于任意 $ \varepsilon>0 $，都有 $$ \mathbb{P}(\left| Z_{n} - \varepsilon\right| \geq \varepsilon) \leq \dfrac{\text{Var}(Z_{n})}{\sigma^{2}} \leq \dfrac{K}{n^{2}\varepsilon^{2}} $$ 从而 $$ \lim_{n \to \infty} \mathbb{P}\left( \left| \frac{|T_n|}{\binom{n}{3}} - p^3 \right| \ge \varepsilon \right) = 0 $$ 就证明了依概率收敛。
(3)
根据 $ (2) $ 我们得到了 $$ \mathbb{P}\left( \left| \frac{|T_n|}{\binom{n}{3}} - p^3 \right| \ge \varepsilon \right) \leq \dfrac{K}{\varepsilon^{2}n^{2}} $$ 其中 $ K $ 是一个和 $ n $ 无关的常数。
我们将这个概率对所有的 $ n $ 求和，得到 $$ \sum_{n=1}^{\infty} \mathbb{P}\left( \left| \frac{|T_n|}{\binom{n}{3}} - p^3 \right| \ge \varepsilon \right) \leq \dfrac{K}{\varepsilon^{2}}\sum_{n=1}^{\infty} \dfrac{1}{n^{2}} < \infty $$ 利用 Borel-Cantelli Lemma，设事件 $ A_{n}=\left\{ \left| \frac{|T_n|}{\binom{n}{3}} - p^3 \right| \ge \varepsilon \right\} $，就得到了 $$ \mathbb{P}(A_{n}\text{ i.o}) = 0 $$ 从而说明存在 $ N_{0} $ 使得当 $ n>N_{0} $，必然有 $$ \left| \dfrac{\left| T_{n} \right| }{\binom{ n }{ 3 } }-p^{3} \right| < \varepsilon $$ 这正是几乎处处收敛的定义，因此 $$ \dfrac{\left| T_{n} \right| }{\binom{ n }{ 3 } } \xrightarrow{a.s.} p^{3} $$
Problem 2
(1)
首先证明下界。由于 $ p(x)=\mathbb{P}(X=x) $ 是一个概率，因此 $ p(x)\in(0,1) $，从而 $ -p(x)\log_{2}p(x)\geq0 $，因此求和必定非负。
接着证明上界。将 $ H(X) $ 理解为期望，有 $$ H(X) = \sum_{x \in A}p(x)\log_{2}\left( \dfrac{1}{p(x)} \right) = \mathbf{E}\left[ \log_{2}\left( \dfrac{1}{p(X)} \right) \right] $$ 其中 $ \dfrac{1}{p(X)} $ 是一个随机变量。考虑函数 $ f(t)=\log_{2}t $，其二阶导 $ f''(t)=-\dfrac{1}{t^{2}\ln 2}< 0 $，$ f(t) $ 是凹函数，从而根据琴生不等式，有 $$ \mathbf{E}\left[ \log_{2}\left( \dfrac{1}{p(X)} \right) \right]\leq \log_{2}\left( \mathbf{E}\left[ \dfrac{1}{p(X)} \right] \right) $$ 其中 $$ \mathbf{E}\left[ \dfrac{1}{p(X)} \right] = \sum_{x \in A} \mathbb{P}(X=x)\cdot \dfrac{1}{\mathbb{P}(X=x)} = \left| A \right| $$ 带入就得到了 $$ H(X) \leq \log_{2}\left| A \right| $$ 在所有 $ p(x) $ 全都相等时取到等号。由于 $ \sum p(x)=1 $，因此取等时 $ p(x)=\frac{1}{\left| A \right|} $。也就是 $ X $ 服从均匀分布时熵最大。
(2)
根据定义，有 $$ \log_{2}\mathbb{P}(X) = \log_{2}\left( \prod_{i=1}^{n} \mathbb{P}(X_{i}) \right) = \sum_{i=1}^{n} \log_{2}\mathbb{P}(X_{i}) $$ 令 $ Z_{i}=-\log_{2}\mathbb{P}(X_{i}) $。由于 $ X_{i} $ 独立同分布，因此 $ Z_{i} $ 也独立同分布。
注意到 $ Z_{i} $ 的期望正是 $ H(X_{i}) $ 的定义： $$ \mathbf{E}[Z_{i}] = \sum_{x \in A}\mathbb{P}(X_{i}=x)\cdot (-\log_{2}\mathbb{P}(X_{i}=x)) = H(X_{i}) $$ 由于 $ A $ 是有限集，因此 $ \mathbf{E}[Z_{i}] $ 存在上界，$ \mathbf{E}[|Z_{i}|]< \infty $。从而根据弱大数定律，有 $$ \dfrac{1}{n}\sum_{i=1}^{n} Z_{i} \xrightarrow{P} \mathbf{E}[Z] $$ 带回就得到了 $$ -\dfrac{1}{n}\log_{2}\mathbb{P}(\vec{X})\xrightarrow{P} H(X) $$ (3)
如果 $ \vec{x}\in A_{\varepsilon}^{(n)} $，那么带入定义，化简可得 $$ 2^{-n(H(X)+\varepsilon)} \leq \mathbb{P}(\vec{X}=\vec{x}) \leq 2^{-n(H(X)-\varepsilon)} $$ 首先证明上界。考虑 $$ \mathbb{P}(A_{\varepsilon}^{(n)}) = \sum_{\vec{x}\in A_{\varepsilon}^{(n)}}\mathbb{P}(\vec{X}=\vec{x}) \geq \sum_{\vec{x}\in A_{\varepsilon}^{(n)}}2^{-n(H(X)+\varepsilon)} = \left| A_{\varepsilon}^{(n)} \right| \cdot 2^{-n(H(X)+\varepsilon)} $$ 由于 $ \mathbb{P}(A_{\varepsilon}^{(n)})\leq 1 $，就得到了 $$ \left| A_{\varepsilon}^{(n)} \right| \cdot 2^{-n(H(X)+\varepsilon)} \leq 1 \implies \left| A_{\varepsilon}^{(n)} \right| \leq 2^{n(H(X)+\varepsilon)} $$ 接着证明下界。根据 $ (2) $，我们知道对于给定 $ \varepsilon>0 $，存在 $ N\in \mathbb{N} $ 使得当 $ n>N $ 时 $$ \mathbb{P}(A_{\varepsilon}^{(n)}) > 1-\varepsilon $$ 从而 $$ \left| A_{\varepsilon}^{(n)} \right| \cdot 2^{-n(H(X)-\varepsilon)} > 1-\varepsilon \implies \left| A_{\varepsilon}^{(n)} \right| > (1-\varepsilon)\cdot 2^{n(H(X)-\varepsilon)} $$ 综上，证明了 $$ (1-\varepsilon)\cdot 2^{n(H(X)-\varepsilon)} < \left| A_{\varepsilon}^{(n)} \right| \leq 2^{n(H(X)+\varepsilon)} $$
Problem 3
(1)
根据提示，设 $ X_{n} $ 为从 $ (0,0) $ 出发，长度为 $ n $ 的开放路径个数。当 $ \left| C_{0,0} \right|=\infty $ 说明至少存在一条经过远点的无限长的路径，从而 $$ \mathbb{P}(\left| C_{0,0} \right| =\infty) \leq \lim_{ n \to \infty } \mathbb{P}(X_{n}\geq 1) $$ 根据马尔可夫不等式，就得到了 $$ \mathbb{P}(\left| C_{0,0} \right| =\infty) \leq \lim_{ n \to \infty } \mathbb{P}(X_{n}\geq 1) \leq \lim_{ n \to \infty } \mathbf{E}[X_{n}] $$ 我们目标是证明 $ \lim_{ n \to \infty }\mathbf{E}[X_{n}]=0 $。
考虑计算长度为 $ n $ 的路径总数。除了第一步，剩下的每一步都不能走回头路，只有 $ 3 $ 个方向可选，因此至多只能有 $ 4\times 3^{n-1} $ 条路径。由于每一段路相互独立，因此一条长度为 $ n $ 的路径开放的概率为 $ p^{n} $，因此 $$ \mathbf{E}[X_{n}] \leq (4 \times 3^{n-1}) \cdot p^{n} = \dfrac{4}{3}(3p)^{n} $$ 由于 $ p < \frac{1}{3} $，从而 $$ \lim_{ n \to \infty } \mathbf{E}[X_{n}] \leq \lim_{ n \to \infty } \dfrac{4}{3}(3p)^{n} = 0 $$**(2)**
设一条路关闭的概率为 $ q=1-p $，那么根据题设，有 $ q< \frac{1}{10} $。
设 $ N_{n} $ 为对偶网络中长度为 $ n $ 且包含原点的回路总数。对于任意一条长度为 $ n $ 的回路，其关闭的概率均为 $ q^{n} $。
设事件 $ B=\{ \left| C_{0,0} \right|<\infty \} $。根据提示中的 Lemma，$ B $ 发生等价于 $ \tilde{\mathbb{Z}}^{2} $ 中存在一条闭合回路 $ \gamma $ 满足 $ \gamma $ 包围原点并且 $ \gamma $ 上每一条边对应 $ \mathbb{Z}^{2} $ 中的边均关闭。根据 Union Bound，事件 $ B $ 发生的概率存在上界 $$ \mathbb{P}(B) \leq \sum_{n} N_{n}\cdot q^{n} $$ 我们考虑估计一个 $ N_{n} $ 的上界。因为回路必然经过 $ x $ 轴（指 $ \tilde{\mathbb{Z}}^{2} $ 上的 $ x $ 轴），所以不妨在 $ x $ 轴上选择路径起点。因为总长度为 $ n $，所以到原点距离不能超过 $ n $，从而最多只有 $ 2n $ 种选择。同样第一步有 $ 4 $ 个方向，往后每一步只有 $ 3 $ 种方向，这样可以估计出 $ N_{n} $ 的一个粗略的上界 $$ N_{n} \leq 2n \cdot (4 \times 3^{n-1}) $$ 从而由于一个环的长度至少为 $ 4 $，所以直接从 $ n=4 $ 开始求和即可 $$ \begin{align*} \mathbb{P}(B) & \leq \sum_{n=4}^{\infty} 2n \cdot(4 \times 3^{n-1})\cdot q^{n} \\ & < \frac{8}{3}\sum_{n=4}^{\infty} n\cdot \left( \frac{3}{10} \right)^{n} < 1 \end{align*} $$ 因此 $$ \mathbb{P}(\left| C_{0,0} \right| > \infty) = 1-\mathbb{P}(\left| C_{0,0} \right| < \infty) > 0 $$ (3)
首先当 $ p< p^{*} $ 时，令事件 $ E=\{ \exists v\in \mathbb{Z}^{2},\left| C_{v} \right|=\infty \} $，那么 $ E=\bigcup_{v\in \mathbb{Z}^{2}}\{ \left| C_{v} \right|=\infty \} $。
由于二维网格具有平移不变性，所以此时 $ \mathbb{P}(\left| C_{v} \right|=\infty)=\mathbb{P}(\left| C_{0,0} \right|=\infty)=0 $。那么根据 Union Bound，就有 $$ \mathbb{P}(E) \leq \sum_{v \in \mathbb{Z}^{2}} \mathbb{P}(\left| C_{v} \right| =\infty) = \sum_{v \in \mathbb{Z}^{2}} 0 = 0 $$ 当 $ p>p^{*} $ 时，我们证明事件 $ E $ 是一个尾事件。$ E $ 等价于网格中存在无穷多的点联通，根据图的性质，改变有限条边的状态并不会改变 $ E $。
形式化地描述，将 $ \mathbb{Z}^2 $ 中的边集进行可数编号，记为序列 $ \{X_n\}_{n \ge 1} $，其中 $ X_n $ 为第 $ n $ 条边的状态。$ \{X_n\} $ 为独立同分布序列。事件 $ E $ 的发生与否不依赖于任意有限条边的状态（修改有限条边不会改变是否存在无限连通分量这一性质）。因此对于任意 $ n $， $ E \in \sigma(X_{n+1}, X_{n+2}, \dots) $，即 $ E $ 是尾事件。
那么根据 Kolmogorov 0-1 律，有 $ \mathbb{P}(E)\in \{ 0,1 \} $。我们只需要验证 $ \mathbb{P}(E)\neq 0 $ 即可。显然 $ \{ \left| C_{0,0} \right|=\infty \}\subseteq E $，从而根据单调性 $$ \mathbb{P}(E) \geq \mathbb{P}(\left| C_{0,0} \right| =\infty) > 0 $$ 从而 $ \mathbb{P}(E)=1 $，证毕。
Problem 4.1
(1)
首先由于 $ \mathbb{P}(\left| Y \right|\geq t)=\mathbb{P}(Y\geq t) + \mathbb{P}(Y \leq -t) $，分别考虑这两个概率。
对于任意 $ \lambda >0 $，根据单调性有 $$ \{ Y\geq t \} \iff \{ e^{ \lambda Y } \geq e^{ \lambda t } \} $$ 利用马尔可夫不等式，有 $$ \mathbb{P}(Y\geq t) = \mathbb{P}(e^{ \lambda Y }\geq e^{ \lambda t } ) \leq \frac{\mathbf{E}[e^{ \lambda Y }]}{e^{ \lambda t }} $$ 带入次高斯条件就有 $$ \mathbb{P}(Y\geq t) \leq \dfrac{\mathbf{E}[e^{ \lambda Y }]}{e^{ \lambda t }} \leq e^{ \alpha^{2}\lambda^{2}-\lambda t } $$ 而指数中的二次函数存在最小值 $ \alpha^{2}\lambda^{2}-\lambda t\geq -\frac{t^{2}}{4\alpha^{2}} $，从而 $$ \mathbb{P}(Y\geq t) \leq \exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} $$ 对于 $ mk\mathbb{P}Y\leq-t $，考虑随机变量 $ -Y $，利用对称性同样有 $$ \mathbb{P}(Y\leq -t)=\mathbb{P}(-Y\geq t) \leq \exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} $$ 因此 $$ \mathbb{P}(\left| Y \right| \geq t) \leq 2\exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} $$ (2)
由于直接带入积分只能得到 $ O(n) $ 量级的 $ \alpha $ 的界，因此考虑使用截断法。
将积分区间分成 $ [0,\delta] $ 和 $ (\delta,\infty) $ 两段。在 $ t $ 比较大的时候再考虑使用 $ (2) $ 中给出的上界，$ t $ 比较小的时候直接使用概率不超过 $ 1 $ 的限制，那么就有 $$ \begin{align*} \mathbf{E}[\max_{i\in[n]}\left| Y_{i} \right|] & = \int_{0}^{\infty} \mathbb{P}(\max_{i\in[n]}\left| Y_{i} \right| >t) \mathrm{d}t \\ & = \int_{0}^{\delta} \mathbb{P}(\dots)\mathrm{d}t + \int_{\delta}^{\infty} \mathbb{P}(\dots)\mathrm{d}t \\ & \leq \int_{0}^{\delta} 1\cdot \mathrm{d}t + \int_{\delta}^{\infty} \left( \sum_{i\in[n]} \mathbb{P}(\left| Y_{i} \right| > t)\right) \mathrm{d}t \\ & \leq \delta + \int_{\delta}^{\infty} \left( \sum_{i\in[n]}2\exp \left\{ -\frac{t^{2}}{4\alpha_{i}^{2}} \right\} \right) \mathrm{d}t \\ (\alpha=\max_{i\in[n]}\alpha_{i}) & \leq \delta + 2n\int_{\delta}^{\infty} \exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} \mathrm{d}t \end{align*} $$ 我们需要估算 $ \int_{\delta}^{\infty} e^{ -t^{2}/4\alpha^{2} } \mathrm{d}t $。由于在积分区间上 $ t>\delta $，因此 $$ \begin{align*} \int_{\delta}^{\infty} \exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} \mathrm{d}t & \leq \frac{1}{\delta} \int_{\delta}^{\infty} t\exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} \mathrm{d}t \\ & = \frac{1}{2\delta}\int_{\delta}^{\infty} \exp \left\{ -\frac{t^{2}}{4\alpha^{2}} \right\} \mathrm{d}t^{2} \\ & = \frac{2\alpha^{2}}{\delta} \exp \left\{ -\frac{\delta^{2}}{4\alpha^{2}} \right\} \end{align*} $$ 带回原式就有 $$ \mathbf{E}[\max\left| Y_{i} \right| ] \leq \delta + 2n\cdot \frac{2\alpha^{2}}{\delta}\cdot \exp \left\{ -\frac{\delta^{2}}{4\alpha^{2}} \right\} $$ 我们选取 $ \delta $ 使得 $ \exp \left\{ -\frac{\delta^{2}}{4\alpha^{2}} \right\} = \frac{1}{2n} $，那么 $$ \delta=\alpha \sqrt{ 4\ln(2n) } = 2\alpha \sqrt{ \ln(2n) } $$ 带入有 $$ \mathbf{E}[\max\left| Y_{i} \right| ] \leq 2\alpha \sqrt{ \ln(2n) } + \frac{\alpha}{\sqrt{ \ln(2n) }} = \alpha \sqrt{ \ln(2n) } \left( 2 + \frac{1}{\ln(2n)} \right) $$ 由于 $ \ln(2n)>1 $，因此括号内是有界常数；并且 $ \sqrt{ \ln(2n) } <2\sqrt{ \ln n } $。所以存在常数 $ C $ 使得 $$ \mathbf{E}[\max_{i \in[n]}\left| Y_{i} \right| ] \leq C\sqrt{ \ln n }\cdot\max_{i} \alpha_{i} $$
Problem 4.2
(1)
根据定义，有 $$ F(x) = \mathbb{P}(X\leq x) = \mathbf{E}[\mathbb{I}_{X\leq x}] $$ 引入 $ X_{1}',\dots,X_{n}' $，这时 $ F(x) $ 也可以看成新样本的经验分布函数 $ F_{n}'(x) $ 的期望。 $$ F(x) = \mathbf{E}{F_{n}'(x)} = \mathbf{E}\left[ \frac{1}{n}\sum_{i=1}^{n} \mathbb{I}_{X'_{i}\leq x} \right] $$ 要处理的左式为 $$ \begin{align*} \text{LHS} & = \mathbf{E}\left[\sup_{x \in \mathbb{R}}\left| F_{n}(x)-F(x) \right| \right] \\ & = \mathbf{E}\left[\sup_{x \in \mathbb{R}}\left| F_{n}(x)-\mathbf{E}[F'_{n}(x)] \right| \right] \end{align*} $$ 由于对 $ X' $ 求期望时 $ X $ 可以看作常数，因此 $ F_{n}(x)-\mathbf{E}[F'_{n}(x)]=\mathbf{E}[F_{n}(x)-F_{n}'(x)]|_{X'} $。由于函数 $ g(X)=\sup_{x}\left| X(x) \right| $ 是一个凸函数，因此根据琴生不等式，就有 $$ \mathbf{E} \left[ \sup_{x} |\mathbf{E}' [F_n(x) - F'_n(x)]| \right] \le \mathbf{E} \left[ \mathbf{E}' \left[ \sup_{x} |F_n(x) - F'_n(x)| \right] \right] $$ 其中 $ \mathbf{E}' $ 表示对 $ X' $ 求的期望。
现在我们只需要分析 $ \left| F_{n}(x)-F_{n}'(x) \right| $，带入得到 $$ F_n(x) - F'_n(x) = \frac{1}{n} \sum_{i=1}^n \mathbb{I}_{X_i \le x} - \frac{1}{n} \sum_{i=1}^n \mathbb{I}_{X'_i \le x} = \frac{1}{n} \sum_{i=1}^n (\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) $$ 带回不等式就得到了 $$ \text{LHS} \leq \mathbf{E}\left[ \sup_{x}\left| \frac{1}{n}\sum_{i=1}^{n} (\mathbb{I}_{X_{i}\leq x} - \mathbb{I}_{X_{i}'\leq x}) \right| \right] = \frac{1}{n} \mathbf{E} \left[ \sup_{x\in\mathbb{R}} \left| \sum_{i=1}^n (\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) \right| \right] $$
(2)
设 $ Z_{i}=\mathbb{I}_{X_{i}\leq x}-\mathbb{I}_{X'_{i}\leq x},W_{i}=\varepsilon_{i}Z_{i} $。由于 $ X $ 和 $ X' $ 独立同分布，因此根据对称性，如果交换 $ X $ 和 $ X' $，那么 $ Z_{i} $ 就会变成 $ -Z_{i} $，这意味着 $ Z_{i} $ 是一个关于 $ 0 $ 对称的随机变量。
引入 $ \varepsilon_{i} $ 后，若 $ \varepsilon_{i}=1 $，那么 $ W_{i}=Z_{i} $；否则 $ W_{i}=-Z_{i} $，这时由于 $ Z_{i} $ 和 $ -Z_{i} $ 同分布，因此 $ Z_{i} $ 和 $ W_{i} $ 也同分布。所以乘以 $ \varepsilon_{i} $ 不改变分布，因此 $ Z_{i} $ 和 $ W_{i} $ 具有相同的分布。
接着我们目标证明 $ \mathbf{E} \left[ \sup_{x} |F_n(x) - F(x)| \right] \le \frac{2}{n} \cdot \mathbf{E} \left[ \sup_{x} \left| \sum_{i=1}^n \varepsilon_i \cdot \mathbb{I}_{X_i \le x} \right| \right] $，根据第一小问，已经有 $$ \text{LHS} \leq \frac{1}{n} \mathbf{E} \left[ \sup_{x\in\mathbb{R}} \left| \sum_{i=1}^n (\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) \right| \right] $$ 根据刚才的性质，我们可以将求和式中的 $ (\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) $ 替换为 $ \varepsilon_{i}(\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) $，因为不仅同分布而且 $ i $ 之间也相互独立。于是右侧就变为了 $$ \frac{1}{n} \mathbf{E} \left[ \sup_{x\in\mathbb{R}} \left| \sum_{i=1}^n \varepsilon_{i}(\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) \right| \right] $$ 将内侧求和展开，得到了 $$ \sum_{i=1}^{n} \varepsilon_{i}(\mathbb{I}_{X_{i}\leq x}-\mathbb{I}_{X'_{i}\leq x}) = \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} - \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}'\leq x} $$ 从而 $$ \begin{align*} \sup_{x\in\mathbb{R}} \left| \sum_{i=1}^n (\mathbb{I}_{X_i \le x} - \mathbb{I}_{X'_i \le x}) \right| & = \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} - \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}'\leq x} \right| \\ & \leq \sup_{x \in \mathbb{R}} \left( \left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} \right| +\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}'\leq x} \right| \right) \\ & \leq \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} \right| + \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X'_{i}\leq x} \right| \end{align*} $$ 从而 $$ \begin{align*} \text{LHS} & \leq \frac{1}{n}\mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} \right| + \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X'_{i}\leq x} \right| \right] \\ & = \frac{1}{n}\mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} \right| \right] + \frac{1}{n}\mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X'_{i}\leq x} \right| \right] \\ & = \frac{2}{n}\mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \sum_{i=1}^{n} \varepsilon_{i}\mathbb{I}_{X_{i}\leq x} \right| \right] \end{align*} $$ 证毕。
Problem 4.3
设 $ a_{i}=\mathbb{I}_{x_{i}\leq x}-\mathbb{I}_{x_{i}\leq y} $，那么 $ Z_{x}-Z_{y}=\sum_{i=1}^{n}\varepsilon_{i}a_{i} $。再令 $ \sigma=\sqrt{ \sum_{i=1}^{n}a_{i}^{2} } $，那么 $$ Z=\dfrac{\sum_{i=1}^{n} \varepsilon_{i}a_{i}}{\sigma} = \sum_{i=1}^{n} \varepsilon_{i}\left( \frac{a_{i}}{\sigma} \right),\quad \sum_{i=1}^{n} \left( \frac{a_{i}}{\sigma} \right)^{2}=1 $$ 计算 $ Z $ 的矩生成函数，有 $$ \mathbf{E}[e^{\lambda Z}] = \mathbf{E}\left[ \exp\left( \lambda \sum_{i=1}^n w_i \varepsilon_i \right) \right] = \mathbf{E}\left[ \prod_{i=1}^n \exp( \lambda w_i \varepsilon_i ) \right] $$ 其中 $ w_{i}=\frac{a_{i}}{\sigma} $。
利用提示中的式子进行放缩，得到 $$ e^{ \lambda w_{i}\varepsilon_{i} } \leq \lambda w_{i}\varepsilon_{i} + e^{ (\lambda w_{i}\varepsilon_{i})^{2} } \implies \mathbf{E}[e^{ \lambda w_{i}\varepsilon_{i} }] \leq \mathbf{E}[\lambda w_{i}\varepsilon_{i}] + \mathbf{E}[e^{ (\lambda w_{i}\varepsilon_{i})^{2} }] $$ 其中 $ \mathbf{E}[\lambda w_{i}\varepsilon_{i}]=0 $ 并且 $ \mathbf{E}[e^{ (\lambda w_{i}\varepsilon_{i})^{2} }]=\mathbf{E}[e^{ \lambda^{2}w_{i}^{2} }]=e^{ \lambda^{2}w_{i}^{2} } $。带入就有 $$ \mathbf{E}[e^{\lambda w_i \varepsilon_i}] \le e^{\lambda^2 w_i^2} $$ 带回就有 $$ \begin{align*} \mathbf{E}[e^{ \lambda Z }] & =\prod_{i=1}^{n} \mathbf{E}[e^{ \lambda w_{i}\varepsilon_{i} }] \\ & \leq \prod_{i=1}^{n} e^{ \lambda^{2}w_{i}^{2} } \\ & = \exp\left( \lambda^{2}\sum_{i=1}^{n} w_{i}^{2} \right) \\ & = \exp(\lambda^{2})\quad \left( \sum_{i=1}^{n} w_{i}^{2}=1 \right) \end{align*} $$ 证毕。
Problem 4.4
(1)
定义映射 $ \Phi:\mathbb{R}\to \mathbb{R}^{n} $，对于任意 $ x \in \mathbb{R} $，有 $$ \Phi(x) = \left( \frac{1}{\sqrt{ n }}\mathbb{I}_{x_{1}\leq x},\frac{1}{\sqrt{ n }}\mathbb{I}_{x_{2}\leq x}, \dots, \frac{1}{\sqrt{ n }}\mathbb{I}_{x_{n}\leq x}\right) $$ 从而题目中给的距离可以重写为 $$ d(x,y) = \| \Phi(x)-\Phi(y) \|_{2} $$ 根据三角不等式，对于任意向量 $ u,v,w\in \mathbb{R}^{n} $，都有 $$ \| u-v \| \leq \| u-w \| + \| v-w \| $$ 从而带入就有 $$ d(x,y) \leq d(x,z) + d(z,y) $$ 证毕。
(2)
设经验分布函数 $ F_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}_{x_{i}\leq x} $。我们化简距离公式，不妨先假设 $ x\geq y $，那么 $ \mathbb{I}_{x_{i}\leq x}-\mathbb{I}_{x_{i}\leq y}=\mathbb{I}_{y< x_{i}\leq x} $，从而 $$ [d(x,y)]^{2}=\frac{1}{n}\sum_{i=1}^{n} \mathbb{I}_{y< x_{i}\leq x} = F_{n}(x) - F_{n}(y) $$ 对于 $ x< y $ 也同理，就得到了 $$ d(x,y) = \sqrt{ \left| F_{n}(x)-F_{n}(y) \right| } $$ 我们首先构造 $ n+1 $ 个点的集合 $ S_{0} $。由于 $ F_{n}(x) $ 是一个阶梯函数，只在 $ x_{1},\dots,x_{n} $ 共 $ n $ 个点处发生跳跃，值域为 $ \left\{ 0,\frac{1}{n},\frac{2}{n},\dots,1 \right\} $。我们构造 $ S_{0}=\{ x_{1},\dots,x_{n} \}\cup \{ x_{\min}-1 \} $，大小为 $ n+1 $。这样对于任意 $ x \in \mathbb{R} $，其 $ F_{n} $ 值必然等于 $ S_{0} $ 中某一点的 $ F_{n} $ 值，也就是 $ \exists y\in S_{0} $，使得 $ F_{n}(x)=F_{n}(y)\implies d(x,y)=0< \varepsilon $。从而用 $ n+1 $ 个点实现 $ 0 $ 误差覆盖。
针对 $ \frac{2}{\varepsilon^{2}} $，我们考虑分割值域，将 $ [0,1] $ 分割成长度为 $ \varepsilon^{2} $ 的小区间。令 $ m=\left\lceil \frac{1}{\varepsilon^{2}} \right\rceil $，构造区间 $ J_{k}=[(k-1)\varepsilon^{2},k\varepsilon^{2}],k\in[m] $。设 $ F_{n}(x) $ 的值域为 $ U $，对于每一个区间 $ J_{K} $，如果和 $ U $ 存在交集，那么就从其中随机选择一个点加入 $ S_{\varepsilon} $，这样一共选出了 $ m $ 个点。由于 $$ \left| S_{\varepsilon} \right| \leq \left\lceil \frac{1}{\varepsilon^{2}} \right\rceil < \frac{1}{\varepsilon^{2}} + 1 \leq \frac{2}{\varepsilon^{2}} $$ 因此这时集合大小不超过 $ \frac{2}{\varepsilon^{2}} $。
这时对于任意 $ x \in \mathbb{R} $，$ F_n(x) $ 必然落在某个区间 $ J_k $ 中。因为 $ F_n(x) $ 存在，所以 $ J_k \cap U $ 非空，我们在 $ S_\varepsilon $ 中一定选了一个对应的代表 $ y_k $。 此时，$ F_n(x) $ 和 $ F_n(y_k) $ 都在长度为 $ \varepsilon^2 $ 的区间 $ J_k $ 内，所以 $$ |F_n(x) - F_n(y_k)| \le \varepsilon^2 \implies d(x,y_{k})=\sqrt{ \left| F_{n}(x)-F_{n}(y_{k}) \right| }\leq \sqrt{ \varepsilon^{2} }=\varepsilon $$ 综上，取 $ n+1 $ 和 $ \frac{2}{\varepsilon^{2}} $ 无论哪个集合，均能满足条件，证毕。
(3)
根据定义，有 $ d(x,y_{k}(x))\leq \varepsilon_{k},d(x,y_{k-1}(x))\leq\varepsilon_{k-1} $。那么根据三角不等式，就有 $$ d(y_{k-1}(x),y_{k}(x)) \leq d(y_{k-1}(x),x) + d(x,y_{k}(x)) \leq \varepsilon_{k-1}+\varepsilon_{k} $$ 其中 $ \varepsilon_{k-1}+\varepsilon_{k}=3\cdot 2^{-k} $。
确界 $ \sup_{x \in \mathbb{R}} $ 实际上只需要在覆盖集 $ S_{\varepsilon_k} $ 和 $ S_{\varepsilon_{k-1}} $ 的元素对中寻找。定义集合 $ A = \{ (u, v) : u \in S_{\varepsilon_{k}}, v \in S_{\varepsilon_{k-1}}, d(u, v) \le 3 \cdot 2^{-k} \} $，根据包含关系，原式中的 $ \sup $ 肯定被 $ A $ 中的最大值控制，也就是 $$ \sup_{x \in \mathbb{R}} \left| Z_{y_{k-1}(x)}-Z_{y_{k}(x)} \right| \leq \max_{(u,v)\in A}\left| Z_{u}-Z_{v} \right| $$ 我们考虑 $ A $ 的集合大小。根据 $ 4.(2) $ 中的结论，有 $$ \left| A \right| \leq \left| S_{\varepsilon_{k}} \right| \cdot \left| S_{\varepsilon_{k-1}} \right| \leq \frac{2}{(2^{-k})^{2}}\cdot \frac{2}{(2^{-(k-1)})^{2}} = 2\cdot 4^{k}\cdot 2 \cdot 4^{k-1} = 4^{2k} $$ 根据第 $ 3 $ 问的结论，化简得到 $ \frac{Z_{u}-Z_{v}}{\sqrt{ n }\cdot d(u,v)} $ 是一个参数为 $ 1 $ 的次高斯变量，从而 $ Z_{u}-Z_{v} $ 是一个参数为 $ \sigma_{u,v}=\sqrt{ n }\cdot d(u,v) $ 的次高斯变量。根据条件就有 $ \sigma_{\max}\leq \sqrt{ n }\cdot 3 \cdot 2^{-k} $。共有 $ \left| A \right| $ 个次高斯变量，那么根据 $ 21(2) $，就有 $$ \begin{align*} \mathbf{E}[\max_{(u,v)\in A}\left| Z_{u}-Z_{v} \right| ] & \leq C\cdot \sqrt{ \ln \left| A \right| }\cdot \sigma_{\max} \\ & \leq C\cdot \sqrt{ 2k\cdot \ln 4 } \cdot (3\sqrt{ n } \cdot 2^{-k}) \\ & = (3\sqrt{ 2 \ln 4 }C)\cdot \sqrt{ n }\cdot \sqrt{ k }\cdot 2^{-k} \end{align*} $$ 令 $ C'=3\sqrt{ 2 \ln 4 }C $，也是一个和 $ n,k $ 无关的常数，从而就得到了 $$ \mathbf{E} \left[ \frac{1}{\sqrt{n}} \sup_{x \in \mathbb{R}} |Z_{y_{k-1}(x)} - Z_{y_k(x)}| \right] \le \frac{1}{\sqrt{n}} \cdot C' \sqrt{n} \sqrt{k} 2^{-k} = C' \sqrt{k} 2^{-k} $$
(4)
#TODO
(5)
首先我们证明 $$ \mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \frac{1}{\sqrt{ n }} Z_{x} \right| \right] \leq 2 + 2C' $$ 根据 $ 4.(2) $，对于 $ \varepsilon_{k}=2^{-k} $，存在集合 $ S_{\varepsilon_{k}} $。对于任意 $ x $，设 $ y_{k}(x) $ 为 $ S_{\varepsilon_{k}} $ 中距离 $ x $ 最近的点。
考虑截断法。令 $ k^{*} $ 为满足 $ \varepsilon_{k}< \frac{1}{n} $ 的最小的 $ k $。当 $ k \ge k^* $ 时，由于 $ d(x, y_k(x)) < \frac{1}{n} < \frac{1}{\sqrt{n}} $，这意味着对于当前的固定样本，$ \mathbb{I}_{x_i \le x} $ 与 $ \mathbb{I}_{x_i \le y_k(x)} $ 完全一致，因此 $ Z_x = Z_{y_{k^*}(x)} $。 利用裂项求和 $$ Z_{x} = Z_{y_{0}(x)} + \sum_{k=1}^{k^{*}} (Z_{y_{k}(x)} - Z_{y_{k-1}(x)}) $$ 两边取绝对值，除以 $ \sqrt{n} $、取上确界并求期望 $$ \mathbf{E}\left[ \sup_{x} \left| \frac{Z_{x}}{\sqrt{n}} \right| \right] \le \mathbf{E}\left[ \sup_{x} \frac{|Z_{y_{0}(x)}|}{\sqrt{n}} \right] + \sum_{k=1}^{\infty} \mathbf{E}\left[ \sup_{x} \frac{|Z_{y_{k}(x)} - Z_{y_{k-1}(x)}|}{\sqrt{n}} \right] $$ 对于 $ k=0 $，根据 $ 4.(4) $ 的结论 $ \mathbf{E}[|Z_x|] \le 2\sqrt{n} $。从而 $$ \mathbf{E}\left[ \sup_{x} \frac{|Z_{y_{0}(x)}|}{\sqrt{n}} \right] = \frac{1}{\sqrt{n}}\mathbf{E}[|Z_{y_{0}}|] \le \frac{2\sqrt{n}}{\sqrt{n}} = 2 $$ 利用 $ 4.(3) $ 的结论 $ \mathbf{E}[\dots]\leq C'\sqrt{ k }2^{-k} $，有 $$ \sum_{k=1}^{\infty} \mathbf{E}\left[ \sup_{x} \frac{|Z_{y_{k}(x)} - Z_{y_{k-1}(x)}|}{\sqrt{n}} \right] \le \sum_{k=1}^{\infty} C' \sqrt{k} 2^{-k} = C' \sum_{k=1}^{\infty} \sqrt{k} 2^{-k} $$ 由于级数 $ \sum_{k=1}^{\infty} \sqrt{k} 2^{-k} $ 收敛且和小于 $ 2 $，故上式 $ \le 2C' $。
合并就得到了 $$ \mathbf{E}\left[ \sup_{x \in \mathbb{R}}\left| \frac{1}{\sqrt{ n }} Z_{x} \right| \right] \le 2 + 2C' $$ 根据 $ 2.(2) $ 的结论，有 $$ \begin{aligned} \mathbf{E}\left[ \sup_{x}|F_{n}(x) - F(x)| \right] & \le \frac{2}{n} \mathbf{E}\left[ \sup_{x} \left| \sum_{i=1}^{n} \varepsilon_{i} \mathbb{I}_{X_{i} \le x} \right| \right] \\ & = \frac{2}{\sqrt{n}} \mathbf{E}\left[ \sup_{x} \left| \frac{1}{\sqrt{n}} Z_{x} \right| \right] \\ & \le \frac{2}{\sqrt{n}} (2 + 2C') = \frac{4 + 4C'}{\sqrt{n}} \end{aligned} $$ 令 $ C''=4+4C' $，与 $ n $ 无关，即证 $$ \mathbf{E}\left[ \sup_{x \in \mathbb{R}}|F_{n}(x) - F(x)| \right] \le \frac{C''}{\sqrt{n}} $$