讨论 13：随机算法分析与近似算法

Union Bound 部分：

1. 图 G 共有 n·n = n² 个可能的（左顶点, 右顶点）对，其中 n² − (n² − n + 1) = n − 1 对不是边。由于 π(i) 与 σ(i) 分别在左右顶点上均匀随机且相互独立，(π(i),σ(i)) 在全部 n² 个对上均匀分布。因此 \[ \Pr[X_i = 1] = \frac{n-1}{n^2} = \frac{1}{n} - \frac{1}{n^2}. \]

2. 对 n 个指示变量 X₁, ..., Xₙ 应用联合界： \[ \Pr[M \text{ is not a perfect matching}] = \Pr\!\left[\sum_{i=1}^n X_i \ge 1\right] \le \sum_{i=1}^n \Pr[X_i = 1] = n \cdot \left(\frac{1}{n} - \frac{1}{n^2}\right) = 1 - \frac{1}{n}. \]

3. 由第 2 问，M 是完美匹配的概率至少为 1/n > 0，因此 G 中必存在完美匹配。

Amplification 部分：

1. SpamBlindMatching 失败当且仅当全部 T 次独立运行均失败，故失败概率为 \[ \left(1 - \frac{1}{n}\right)^T. \]

2. 设 T = n ln(1/δ)。由于 (1 − 1/n)^n ≤ 1/e，有 \[ \left(1 - \frac{1}{n}\right)^{n \ln(1/\delta)} \le \left(\frac{1}{e}\right)^{\ln(1/\delta)} = \delta. \]

Markov 部分：

1. 设 X 以 1/2 概率取 +1、1/2 概率取 −1（Uniform ±1），则 E[X] = 0，但 Pr[X ≥ 0] = 1/2 > 0 = E[X]/0，违反 Markov 不等式。

2. 构造随机变量 X：以概率 μ/t 取值 t，以概率 1 − μ/t 取值 0。则 E[X] = t·(μ/t) + 0·(1−μ/t) = μ，且 Pr[X ≥ t] = μ/t = E[X]/t，达到 Markov 不等式的等号。

Chebyshev/袋子部分：

1. 设 Xᵢ 为第 i 次抽到红球的指示变量，则 X = X₁ + ... + X_ℓ。由期望线性性： \[ \mathbb{E}[X] = \sum_{i=1}^\ell \mathbb{E}[X_i] = \ell \cdot \frac{k}{n}. \]

2. 由样本独立性： \[ \mathrm{Var}[X] = \sum_{i=1}^\ell \mathrm{Var}[X_i] = \ell \cdot \frac{k}{n}\!\left(1 - \frac{k}{n}\right). \]

3. 算法：输出 k̂ = (n/ℓ)·X。此时 \[ \mathbb{E}[\hat{k}] = k, \quad \mathrm{Var}[\hat{k}] = \frac{n^2}{\ell^2} \cdot \ell \cdot \frac{k}{n}\!\left(1 - \frac{k}{n}\right) = \frac{kn}{\ell}\!\left(1 - \frac{k}{n}\right) \le \frac{kn}{\ell}. \] 由 Chebyshev 不等式，k̂ 偏离 k 超过 t√(kn/ℓ) 的概率至多为 1/t²。取 t = 1/√δ，则偏离超过 √(kn/ℓ)/√δ 的概率至多为 δ。为使该偏差不超过 ε√k，需 \[ \frac{1}{\sqrt{\delta}}\sqrt{\frac{kn}{\ell}} \le \varepsilon\sqrt{k} \;\Longrightarrow\; \sqrt{\frac{n}{\ell\delta}} \le \varepsilon \;\Longrightarrow\; \ell \ge \frac{n}{\varepsilon^2 \delta}. \] 取 ℓ = n/(ε²δ) 即可。

1. 将期望拆分为两部分： \[ \mathbb{E}[X] = \sum_x x \Pr[X=x] \ge \sum_{x \ge a} x \Pr[X=x] \ge \sum_{x \ge a} a \Pr[X=x] = a \sum_{x \ge a} \Pr[X=x] = a \Pr[X \ge a]. \] 两边同除以 a 即得。

2. 令 Y = (X − E[X])²，则 Y 为非负随机变量。对 Y 应用 Markov 不等式： \[ \Pr(|X - \mathbb{E}[X]| > \lambda) = \Pr((X - \mathbb{E}[X])^2 > \lambda^2) \le \frac{\mathbb{E}[(X - \mathbb{E}[X])^2]}{\lambda^2} = \frac{\mathrm{Var}[X]}{\lambda^2}. \]

3. 不要求证明。

考虑从 H 中均匀随机选取的函数是单射的概率： \[ \Pr_{h \sim H}[h \text{ is one-to-one}] = \Pr_{h \sim H}[h(x_1) \neq h(x_2) \neq \cdots \neq h(x_n)] \] \[ = 1 - \Pr_{h \sim H}\!\left[\bigvee_{i \neq j} h(x_i) = h(x_j)\right] \] \[ \ge 1 - \sum_{i \neq j} \Pr_{h \sim H}[h(x_i) = h(x_j)] \quad \text{[联合界 Union Bound]} \] \[ = 1 - \sum_{i \neq j} \sum_{c=1}^{n^3} \Pr_{h \sim H}[h(x_i) = c, h(x_j) = c] \quad \text{[全概率公式 Law of Total Probability]} \] \[ = 1 - \sum_{i \neq j} n^3 \cdot \frac{1}{(n^3)^2} \quad \text{[H 的两两独立性 Pairwise Independence]} \] \[ = 1 - n(n-1) \cdot \frac{1}{n^3} \] \[ \ge 1 - \frac{1}{n}, \] 得证。

(a) 将整数 i 初始化为 0。用另一个变量存储当前选票。对每张投给候选人 A 的选票，将 i 减 1。对每张投给候选人 B 的选票，将 i 加 1。 如果最终 i 为负，则候选人 A 获胜。如果最终 i 为正，则候选人 B 获胜。如果 i 为 0，则为平局。

(b) 设 m 是一个变量，取值为 [k] 中的数，表示当前选举的获胜者。设 i 是一个与上一部分类似的计数器。对流中的每个元素，执行以下操作：如果 i 为 0，则将 m 设为当前选票的值，并将 i 设为 1。否则如果 i > 0 且 m 等于当前选票，则将 i 加 1。否则将 i 减 1。 最后，如果存在多数获胜者，m 将包含它。但如果没有多数获胜者，m 仍然包含流中的某个元素。

解释：不妨设候选人 1 是获胜者，即获得超过一半的选票。考虑值 j：当 m = 1 时 j = i，当 m ≠ 1 时 j = −i。直观上，j 始终编码候选人 1 当前“领先”的幅度（如果幅度为负，则候选人 1 还需要 −j + 1 张选票才能领先）。我们只需证明该值在算法结束时为正。每张投给候选人 1 的选票使 j 增加 1，而投给其他候选人的选票最多使 j 减少 1（但如果例如当 m = 3 时收到候选人 2 的选票，则可能增加 j）。由于候选人 1 获得超过一半的选票，j 在算法结束时必为正。

1. 最佳遍历：A-D-C-B、D-C-B-A、B-C-D-A 或 C-D-A-B。 解释：MST 为 {(A,D), (D,C), (C,B)}。最优巡游使用了所有这些边。例如，如果从 A 开始遍历树，则唯一的遍历方式是沿着树走并按 D、C、B 的顺序访问顶点。另一种可能的遍历是从 D 开始，走到 C，然后 B，回溯，再前往 A。

注意，如果从 D 开始并先走到 A，则接下来必须访问 C，这不会产生最佳输出巡游（如第 2 问所示）。

1. 最差遍历：C-B-D-A 或 D-A-C-B。 参见上述解释。 注意，总体上最差的巡游 D-C-A-B 不可能被该算法输出，无论使用何种 DFS 遍历。

2. 近似比 12/5。 由前几问，最优巡游长度为 5（A-D-C-B-A：A-D=1, D-C=1, C-B=1, B-A=2，合计 5），而算法最差的可能输出为 12（C-B-D-A-C：C-B=1, B-D=5, D-A=1, A-C=5，合计 12）。这比 2 更差是因为我们的图不满足三角不等式，具体为 ℓ(A,C) > ℓ(A,B) + ℓ(B,C)（5 > 2+1）且 ℓ(B,D) > ℓ(A,B) + ℓ(D,A)（5 > 2+1），而这正是算法保证近似比为 2 的必要条件。

(a) 对每个街区有一个变量 xᵢⱼ，即 {xᵢⱼ | i ∈ {1, ..., m}, j ∈ {1, ..., n}}。该变量表示是否在该街区开设波霸奶茶店（xᵢⱼ = 1 表示开设，xᵢⱼ = 0 表示不开设）。

(b) min Σᵢ₌₁ᵐ Σⱼ₌₁ⁿ rᵢⱼ xᵢⱼ。该目标函数表示最小化所有开设波霸奶茶店的街区的租金总和。或者，min t 也是正确的，只要添加约束 Σ rᵢⱼxᵢⱼ ≤ t。

(c) (i) xᵢⱼ ≥ 0（或 xᵢⱼ ∈ {0,1}，或 xᵢⱼ ∈ ℤ⁺）：该约束表示每个街区要么有要么没有波霸奶茶店。 (ii) 对每个 1 ≤ i ≤ m, 1 ≤ j ≤ n： xᵢⱼ + x_{i+1,j}·𝟙{i+1≤m} + x_{i−1,j}·𝟙{i−1≥1} + x_{i,j+1}·𝟙{j+1≤n} + x_{i,j−1}·𝟙{j−1≥1} ≥ 1 该约束表示对每个街区，该街区或其相邻街区中必须有一家波霸奶茶店。𝟙{condition} 为指示函数，当条件成立时为 1，否则为 0，用于处理边缘街区可能没有全部 4 个邻居的事实。 (iii) 如果目标函数是 min t，则需要添加约束 Σᵢ₌₁ᵐ Σⱼ₌₁ⁿ rᵢⱼ xᵢⱼ ≤ t。

(d) 将所有大于或等于 1/5 的变量舍入为 1，否则舍入为 0。换言之，当且仅当 xᵢⱼ ≥ 0.2 时在街区 (i,j) 开设波霸奶茶店。

(e) 使用上一部分的舍入方案可得到 5-近似。 理由：每个约束最多包含 5 个变量，因此对每个约束，其中至少有一个变量的值 ≥ 1/5（并非所有变量都低于平均值）。舍入解的总成本最多为 5 · LP-OPT，因为对被舍入向上的任意 xᵢⱼ 有 rᵢⱼ ≤ 5rᵢⱼxᵢⱼ，而其他 (i,j) 对对舍入解的成本无贡献。由于 Integral-OPT ≥ LP-OPT（LP 是 ILP 的松弛，更一般），我们的舍入得到的值最多为 5 LP-OPT ≤ 5 Integral-OPT。因此我们得到 5-近似。