Problem 1
(1)
设每次合成仙丹为一次尝试。 在每次尝试中：
- 合成成功：概率为 $ p $。
- 产生 $ 1 $ 份仙丹。
- 消耗 $ 2 $ 份仙果。
- 合成失败：概率为 $ 1-p $。
- 产生 $ 0 $ 份仙丹。
- 消耗 $ 1 $ 份仙果。
我们关注的是平均每份仙果可以得到多少仙丹。这可以理解为仙丹产出的期望值与仙果消耗的期望值之比。
每次尝试中，获得的仙丹数量的期望值 $ \mathbb{E}[\text{仙丹}] $ 为： $$ \mathbb{E}[\text{仙丹}] = 1 \cdot p + 0 \cdot (1-p) = p $$
每次尝试中，消耗的仙果数量的期望值 $ \mathbb{E}[\text{仙果}] $ 为： $$ \mathbb{E}[\text{仙果}] = 2 \cdot p + 1 \cdot (1-p) = 2p + 1 - p = p + 1 $$
那么，平均每份仙果可以得到的仙丹数量为： $$ \frac{\mathbb{E}[\text{仙丹}]}{\mathbb{E}[\text{仙果}]}= \frac{p}{p+1} $$
因此平均一份仙果可以得到 $ p / (p+1) $ 份仙丹。
(2)
商品价格 $ P_{现}=2\,\text{元/份} $，初始资金 $ C_{0}=1000\,\text{元} $。设现在购买 $ x $ 份商品，则 $ 0 \le x \le \dfrac{C_0}{P_{现}} = 1000 / 2 = 500 $。 当前交易后，剩余现金为 $ 1000 - 2x $ 元，持有商品 $ x $ 份。
Case 1：为了最大化最终金钱，最优策略是在一周后将所有商品卖出。共有两种情况，概率均为 $ \dfrac{1}{2} $：
- 一周后商品价格涨至 $ 4 $ 元/份。 卖出 $ x $ 份商品，获得 $ 4x $ 元。最终金钱为 $ 1000+2x $ 元。
- 一周后商品价格跌至 $ 1 $ 元/份。卖出 $ x $ 份商品，获得 $ x $ 元。最终金钱为 $ 1000 - x $ 元。
最终金钱的期望值 $ \mathbb{E}[\text{金钱}] $ 为： $$ \mathbb{E}[\text{金钱}] = \frac{1}{2}(1000 + 2x) + \frac{1}{2}(1000 - x) = \frac{1}{2}(2000 + x) = 1000 + \frac{x}{2} $$ 为了最大化 $ \mathbb{E}[\text{金钱}] $，我们需要最大化 $ x $。根据 $ 0 \le x \le 500 $， $ x $ 的最大值为 $ 500 $。
因此，策略为：
- 现在：购买 $ 500 $ 份商品。
- 一周后：无论商品价格涨跌，卖出所有 $ 500 $ 份商品。
- 若价格为 $ 4 $ 元/份，最终得到 $ 500 \times 4 = 2000 $ 元。
- 若价格为 $ 1 $ 元/份，最终得到 $ 500 \times 1 = 500 $ 元。 此时期望金钱为 $ 1000 + 500/2 = 1250 $ 元。
Case 2：为了最大化最终商品数量，最优策略是在一周后将所有现金和商品都转换为商品。共有两种情况，概率均为 $ \dfrac{1}{2} $：
- 一周后商品价格涨至 $ 4 $ 元/份 (概率 $ 1/2 $)。此时拥有 $ (1000 - 2x) $ 现金和 $ x $ 份商品。卖出 $ x $ 份商品，获得 $ 4x $ 元。总现金为 $ (1000 - 2x) + 4x = 1000 + 2x $ 元。用所有现金购买商品，可购买 $ (1000 + 2x) / 4 = 250 + x/2 $ 份商品。
- 一周后商品价格跌至 $ 1 $ 元/份 (概率 $ 1/2 $)。此时拥有 $ (1000 - 2x) $ 现金和 $ x $ 份商品。卖出 $ x $ 份商品，获得 $ x $ 元。总现金为 $ (1000 - 2x) + x = 1000 - x $ 元。用所有现金购买商品，可购买 $ (1000 - x) / 1 = 1000 - x $ 份商品。
最终商品数量的期望值 $ \mathbb{E}[\text{商品}] $ 为： $$ \mathbb{E}[\text{商品}] = \frac{1}{2}(250 + \frac{x}{2}) + \frac{1}{2}(1000 - x) = \frac{1}{2}(1250 - \frac{x}{2}) = 625 - \frac{x}{4} $$ 为了最大化 $ \mathbb{E}[\text{商品}] $，我们需要最小化 $ x $。根据 $ 0 \le x \le 500 $， $ x $ 的最小值为 $ 0 $。
因此，策略为：
- 现在：不购买任何商品。此时现金为 $ 1000 $ 元，持有 $ 0 $ 份商品。
- 一周后：无论商品价格涨跌，用所有现金购买商品。
- 若价格为 $ 4 $ 元/份，用 $ 1000 $ 元购买 $ 1000 / 4 = 250 $ 份商品。
- 若价格为 $ 1 $ 元/份，用 $ 1000 $ 元购买 $ 1000 / 1 = 1000 $ 份商品。 此时期望商品数量为 $ 625 - 0/4 = 625 $ 份。
(3)
马尔可夫不等式：我们需要对于每个 $ a\in \mathbb{R}_{>0} $ 找出对应的随机变量 $ X $ 满足 $$ \mathbb{P}[X\geq a] = \dfrac{\mathbb{E}[X]}{a} $$ 直接取 $ X=a $ 即可，显然成立。
切比雪夫不等式：同样直接取 $ X=a $。那么 $ \mathbb{P}[\left| X-\mathbb{E}[X] \right|\geq a]=0 $，同时 $ \mathrm{Var}(X)=0 $（因为 $ X $ 为常数），因此可以取到等号。或者更直接地由于这是马尔可夫不等式的直接推论，两者取等条件相同。
Problem 2
冒泡排序一次操作减少一个逆序对，因此实际上我们需要分析的是一个随机排列中逆序对数量 $ X $。需要分别求出 $ \mathbb{E}[X] $ 和 $ \mathrm{Var}[X] $。
(1)
求解 $ \mathbb{E}[X] $。我们直接定义指示变量 $ \mathbb{I}_{i,j}=[i< j\land a_{i}>a_{j}] $，表示 $ (a_{i},a_{j}) $ 构成一个逆序对。于是 $$ X = \sum_{1\leq i< j\leq n}\mathbb{I}_{i,j} $$ 根据期望的可加性 $$ \mathbb{E}[X] = E\left[ \sum_{1\leq i< j\leq n}\mathbb{I}_{i,j} \right] = \sum_{1\leq i< j\leq n}\mathbb{E}[\mathbb{I}_{i,j}] $$ 对于单个指示变量的期望，$ \mathbb{E}[\mathbb{I}_{i,j}]=\mathbb{P}(a_{i}>a_{j}) $。由于排列随即均匀，对于任意一个数它出现在位置 $ i $ 和 $ j $ 的概率是相同的，所以 $ \mathbb{P}(a_{i}>a_{j})= \frac{1}{2} $，所以 $$ \mathbb{E}[X] = \sum_{1\leq i< j\leq n} \dfrac{1}{2} = \dfrac{n(n-1)}{4} $$
(2)
求解 $ \mathrm{Var}[X] $。由于 $ \mathrm{Var}[X]=\mathbb{E}[X^{2}]-(\mathbb{E}[X])^{2} $，因此我们求出 $ \mathbb{E}[X^{2}] $ 即可。同理 $ (1) $，我们得到 $$ X^{2} = \left( \sum_{1\leq i< j\leq n}\mathbb{I}_{i,j} \right)^{2} = \sum_{1\leq i< j\leq n}\mathbb{I}_{i,j} + \sum_{(i,j)\neq(k,l)}\mathbb{I}_{i,j}\mathbb{I}_{k,l} $$ 根据期望的可加性，我们直接考虑计算 $ \mathbb{E}[\mathbb{I}_{i,j}\mathbb{I}_{k,l}] $。我们发现每对不同的 $ (i,j),(k,l) $ 会被重复计算两次，因此我们令 $ i< k $，最后计数乘以 $ 2 $ 即可。分类讨论：
- 若 $ (i,j),(k,l) $ 没有重叠，那么共 $ \binom{ n }{ 4 }\times 3 $ 种选择，对期望贡献为 $ \frac{3\binom{ n }{ 4 }}{4} $。
- 若 $ \{ i,j \}\cap \{ k,l \}\neq \emptyset $，分别考虑 $ 3 $ 种重合方式，每种有 $ \binom{ n }{ 3 } $ 种选择，发现对期望的贡献为 $$ \left( \dfrac{1}{3} + \dfrac{1}{6} + \dfrac{1}{3} \right) \cdot \binom{ n }{ 3 } = \dfrac{5}{6}\binom{ n }{ 3 } $$ 综上，得到 $$ \mathbb{E}[\mathbb{I}_{i,j}\mathbb{I}_{k,l}] = 2\left[ \dfrac{3}{4}\binom{ n }{ 4 } + \dfrac{5}{6}\binom{ n }{ 3 } \right] = \dfrac{3}{2}\binom{ n }{ 4 } + \dfrac{5}{3}\binom{ n }{ 3 } $$ 得到 $$ \mathbb{E}[X^{2}] = \dfrac{n(n-1)}{4} + \dfrac{3}{2}\cdot \dfrac{n(n-1)(n-2)(n-3)}{24} + \dfrac{5}{3}\cdot \dfrac{n(n-1)(n-2)}{6} = \dfrac{n(n-1)(9n^{2}-5n+10)}{144} $$ 从而 $$ \mathrm{Var}[X] = \mathbb{E}[X^{2}] - (\mathbb{E}[X])^{2} = \dfrac{n(n-1)(9n^{2}-5n+10)}{144} - \dfrac{n^{2}(n-1)^{2}}{16} = \dfrac{n(n-1)(2n+5)}{72} $$
Problem 3
(1)
要证明 $ \mathbb{E}[\hat{m}]=m $，我们只需要证明 $ \mathbb{E}[2^{X}-1]=m $，即 $ \mathbb{E}[2^{X}]=m+1 $。我们设 $ X_{k} $ 为接受第 $ k $ 个输入后计数器的值，定义 $ T_{k}=\mathbb{E}[2^{X_{k}}] $，只需要证明 $ T_{m}=m+1 $ 即可。现在我们求 $ T_{k} $ 的递推式。
考虑在第 $ k $ 个输入时计数器的变化，$ k-1 $ 个输入之后计数器的值为 $ X_{k-1} $，那么第 $ k $ 个输入到达时：
- 以 $ \mathbb{P}=2^{-X_{k-1}} $ 的概率变为 $ X_{k}=X_{k-1}+1 $。
- 以 $ \mathbb{P}=1-2^{-X_{k-1}} $ 的概率还是 $ X_{k}=X_{k-1} $。
那么我们得到对于给定 $ X_{k-1}=x $，有 $$ \mathbb{E}[2^{X_{k}}\mid X_{k-1}=x] = 2^{-x}\cdot 2^{x+1} + (1-2^{-x})\cdot 2^{x} = 1 + 2^{x} $$ 这就得到了 $$ T_{k} = \mathbb{E}[2^{X_{k}}] = \mathbb{E}[1+2^{X_{k-1}}] = T_{k-1} + 1 $$ 再带入 $ T_{1}=2 $，显然就得到了 $ T_{m}=m+1 $，于是我们就证明了输出的 $ \hat{m} $ 是无偏的。
(2)
我们先考虑求出 $ \mathbb{E}[\hat{m}^{2}]=\mathbb{E}[(2^{X}-1)^{2}] $，核心在于求出 $ \mathbb{E}[2^{2X}] $。类似 $ (1) $，令 $ S_{k}=\mathbb{E}[2^{2X_{k}}] $，考虑求出其递推式。
对于 $ X_{k-1}=x $，有 $$ \mathbb{E}[2^{2X_{k}}\mid X_{k-1}=x] = 2^{-x}\cdot 2^{2x+2} + (1-2^{-x})\cdot 2^{2x} = 3\cdot 2^{x} + 2^{2x} $$ 从而 $$ S_{k} = S_{k-1} + 3T_{k-1} = S_{k-1} + 3k $$ 带入 $ S_{1}=4 $，得到 $$ \mathbb{E}[2^{2X_{m}}] = S_{m} = \dfrac{3}{2}m^{2} + \dfrac{3}{2}m + 1 $$ 于是 $$ \mathbb{E}[\hat{m}^{2}] = \mathbb{E}[(2^{X}-1)^{2}] = S_{m} - 2T_{m} + 1 = \dfrac{3}{2}m^{2} - \dfrac{1}{2}m $$ 以及 $$ \mathrm{Var}[\hat{m}] = \mathbb{E}[\hat{m}^{2}]-\mathbb{E}[\hat{m}]^{2} = \dfrac{1}{2}m^{2} - \dfrac{1}{2}m \leq \dfrac{m^{2}}{2} $$ 带入切比雪夫不等式，得到 $$ \mathbb{P}[\left| \hat{m}-m \right| \geq \varepsilon m] \leq \dfrac{\mathrm{Var}[\hat{m}]}{(\varepsilon m)^{2}} = \dfrac{\dfrac{1}{2}m^{2} - \dfrac{1}{2}m}{(\varepsilon m)^{2}} < \dfrac{1}{2\varepsilon^{2}} $$ 因此上界为 $ \dfrac{1}{2\varepsilon^{2}} $。
(3)
显然 $ \mathbb{E}[\hat{m}^{*}]=m $，我们需要求出 $ \mathrm{Var}[\hat{m}^{*}] $。根据方差的性质，我们有 $$ \begin{align*} \mathrm{Var}[\hat{m}^{*}] & = \mathrm{Var}\left[ \dfrac{1}{t}\sum_{i=1}^{t}\hat{m}_{i} \right] \\ & = \dfrac{1}{t^{2}}\mathrm{Var}\left[ \sum_{i=1}^{t} \hat{m}_{i} \right] \\ & = \dfrac{1}{t^{2}}\sum_{i=1}^{t} \mathrm{Var}[\hat{m}_{i}] \\ & = \dfrac{1}{t}\mathrm{Var}[\hat{m}] \end{align*} $$ 重新带入切比雪夫不等式，就得到了 $$ \mathbb{P}[\left| \hat{m}^{*}-m \right| \geq \varepsilon m] \leq \dfrac{\mathrm{Var}[\hat{m}^{*}]}{(\varepsilon m)^{2}} < \dfrac{1}{2t\cdot\varepsilon^{2}} $$ (4)
取 $ \varepsilon=0.1 $，我们需要 $$ \dfrac{1}{2\times 0.1^{2}\times t} < 1\% \implies t > 5000 $$ 至少 $ 5000 $ 次实验。
存储需要 $ 5000\times\lceil \log_{2}\lceil \log_{2}m \rceil \rceil $ 比特。
Problem 4
(1)
根据提示，我们假设在 $ H_{0}=H^{*} $ 时取到最大值，定义 $ \mathcal{P}' $ 为包含 $ H^{*} $ 作为子图。由于 $ H^{*}\subseteq H $，因此若 $ G $ 满足 $ \mathcal{P} $，那么一定满足 $ \mathcal{P}' $，这就得到了 $$ \mathbb{P}[G \text{ satisfies } \mathcal{P}] \leq \mathbb{P}[G \text{ satisfies } \mathcal{P}'] $$ 我们接着考虑 $ G $ 中包含的和 $ H^{*} $ 同构的图的数量 $ X $，显然有 $ \mathbb{P}[G\text{ satisfies }\mathcal{P}']=\mathbb{P}[X\geq 1] $。
计算 $ X $ 的期望，有 $$ \mathbb{E} [X] = \binom{ n }{ \left| V(H^{*}) \right| } p(n)^{\left| E(H^{*}) \right| } $$ 带入 $ p(n)< n^{-1 / r(H)} $，以及 $ r(H)= \frac{\left| E(H^{*}) \right|}{\left| V(H^{*}) \right|} $，得到 $$ p(n)^{\left| E(H^{*}) \right| } < n^{- \left| E(H^{*}) \right|/{r(H)} } = n^{-\left| V(H^{*}) \right| } $$ 因此 $$ \mathbb{E}[X] < \binom{ n }{ \left| V(H^{*}) \right| } \cdot n^{-\left| V(H^{*}) \right| } = \dfrac{n^{\underline{\left| V(H^{*}) \right| }}}{\left| V(H^{*}) \right| !}\cdot n^{-\left| V(H^{*}) \right| } < \dfrac{1}{\left| V(H^{*}) \right| !} $$ 在 $ n\to \infty $ 时显然也有 $ \dfrac{1}{\left| V(H^{*}) \right|!}\to 0 $。
于是根据马尔可夫不等式，得到 $$ \mathbb{P}[G\text{ satisfies }\mathcal{P}']=\mathbb{P}[X\geq 1] \leq \mathbb{E}[X] \to 0 $$ 从而得到了 $$ \mathbb{P}[G\text{ satisfices }\mathcal{P}] \to 0 $$
(2)
首先同理第一问，计算 $ X $ 的期望 $$ \mathbb{E}[X] = \sum_{i=1}^{m} \mathbb{E}[X_{i}] = m\cdot p(n)^{\left| E(H) \right| } $$ 接着由于需要计算方差，我们考虑 $ \mathbb{E}[X^{2}] $，有 $$ \mathbb{E}[X^{2}] = \mathbb{E}\left[ \left( \sum_{i=1}^{m}X_{i} \right)^{2} \right] = \sum_{i=1}^{m} \sum_{j=1}^{m} \mathbb{E}[X_{i}X_{j}] $$ 并且其中 $ X_{i}X_{j}=1 $ 代表 $ G\text{ contains }S_{i}\cup S_{j} $，因此 $ \mathbb{E}[X_{i}X_{j}]=\mathbb{P}[G\text{ contains }S_{i}\cup S_{j}] $。
带入方差表达式得到 $$ \begin{align*} \text{Var}[X] & = \mathbb{E}[X^{2}] - (\mathbb{E}[X])^{2} \\ & = \sum_{i,j\in[m_{n}]}\mathbb{P}[G\text{ contains }S_{i}\cup S_{j}] - (\mathbb{E}[X])^{2} \\ & < \sum_{i,j\in[m_{n}]}\mathbb{P}[G\text{ contains }S_{i}\cup S_{j}] \\ & < \sum_{i,j\in[m_{n}]:E(S_{i}\cap S_{j})\neq \emptyset} \mathbb{P}[G\text{ contains }S_{i}\cup S_{j}] \end{align*} $$ (3)
首先根据容斥原理，$ S_{i}\cup S_{j} $ 包含 $ 2E(H)-e $ 条边。那么根据定义，我们就有 $$ \mathbb{P}[G\text{ contains }S_{i}\cup S_{j}] = p(n)^{2\left| E(H) \right| - e} = \Theta(p(n)^{2\left| E(H) \right| - e}) $$ 并且 $ S_{i}\cup S_{j} $ 有 $ 2\left| V(H) \right|-v $ 个点，因此从 $ n $ 个点中分配 $ S_{i}\cup S_{j} $ 中的点，有 $ \binom{ n }{ 2\left| V(H) \right|-v } $ 种方案，再在这些点中分配 $ S_{i}\cap S_{j} $ 中的点以及分别 $ S_{i},S_{j} $ 的点，合计方案数为 $$ \begin{align*} & \binom{ n }{ 2\left| V(H) \right| - v } \cdot \binom{ 2\left| V(H) \right| - v }{ v } \cdot \binom{ 2\left| V(H) \right| - 2v }{ \left| V(H) \right| - v } \\ & < n^{2\left| V(H) \right| - v}\cdot \dfrac{(2\left| V(H) \right| -v)^{\underline{v}}\cdot (2\left| V(H)-2v \right|) ^{\underline{\left| V(H) \right| - v}}}{(2\left| V(H)-v \right| )!\cdot v!\cdot (\left| V(H)-v \right| )!} \\ & = \mathcal{O}(n^{2\left| V(H) \right| - v}) \end{align*} $$
(4)
我们只需证明 $ \text{Var}[X]=o((\mathbb{E}[X])^{2}) $ 即可。
首先，注意到 $ \mathbb{E}[X] = \Theta(n^{|V(H)|} p(n)^{|E(H)|}) $。
对于方差，利用 $ (2) $ 的结论，当 $ i \neq j $ 且 $ E(S_i \cap S_j) = \emptyset $ 时，$ X_i $ 和 $ X_j $ 独立，因此 $$ \text{Var}[X] \leq \mathbb{E}[X] + \sum_{i,j \in [m_n]: E(S_i \cap S_j) \neq \emptyset} \mathbb{P}[G \text{ contains } S_i \cup S_j] $$ 根据 $ (3) $ 的结论，对于每个固定的 $ (v, e) $（其中 $ v $ 和 $ e $ 分别是 $ S_i \cap S_j $ 的点数和边数，且 $ 1 \leq e \leq 2|E(H)|-1 $），有
- 满足条件的 $ (i,j) $ 对数为 $ \mathcal{O}(n^{2|V(H)|-v}) $
- 每对的概率为 $ \Theta(p(n)^{2|E(H)|-e}) $
因此 $$ \begin{align*} \text{Var}[X] &\leq \mathbb{E}[X] + \sum_{v,e} \mathcal{O}(n^{2|V(H)|-v} p(n)^{2|E(H)|-e}) \\ &= \mathbb{E}[X] + \sum_{v,e} \mathcal{O}\left((n^{|V(H)|} p(n)^{|E(H)|})^2 \cdot n^{-v} p(n)^{-e}\right) \\ \end{align*} $$
对于 $ H $ 的任意子图 $ H_0 $，若 $ |V(H_0)| = v $，$ |E(H_0)| = e $，则根据 $ r(H) $ 的定义 $$ \frac{e}{v} \leq r(H) \quad \Rightarrow \quad e \leq r(H) \cdot v $$ 当 $ p(n) \gg n^{-1/r(H)} $ 时，存在 $ \epsilon > 0 $ 使得 $ p(n) > n^{-1/r(H)+\epsilon} $（当 $ n $ 充分大）。因此 $$ n^{-v} p(n)^{-e} < n^{-v} \cdot n^{e(1/r(H)-\epsilon)} = n^{e/r(H) - v - e\epsilon} $$
由于 $ e \leq r(H) \cdot v $，即 $ e/r(H) \leq v $，所以 $ e/r(H) - v - e\epsilon \leq -e\epsilon < 0 $。因此 $ n^{-v} p(n)^{-e} \to 0 $。
由于 $ (v,e) $ 的可能取值是有限的（$ \mathcal{O}(1) $ 种），我们得到 $$ \text{Var}[X] = o((\mathbb{E}[X])^2) $$ 从而由切比雪夫不等式 $$ \mathbb{P}[X=0] \leq \mathbb{P}[|X - \mathbb{E}[X]| \geq \mathbb{E}[X]] \leq \frac{\text{Var}[X]}{(\mathbb{E}[X])^2} \to 0 $$ 因此 $$ \mathbb{P}[X \geq 1] = 1 - \mathbb{P}[X=0] \xrightarrow{n \to \infty} 1 $$ 这就完成了证明。