TCS Homework 11

11.1

题目

问题 1. 证明函数族

$H = \{h_{a,b} \mid h_{a,b}(x) = a \cdot x + b, \, a \in \{0, 1\}^k, \, b \in \{0, 1\}\}$

对于范围 $R = \{0, 1\}$ 和定义域 $U = \{0, 1\}^k$ 是一个成对独立（pairwise independent）的哈希函数族。

解答

要证明函数族 $H$ 是成对独立的，需验证：对任意两个不同的输入 $x_1, x_2 \in U$（其中 $x_1 \neq x_2$)，以及任意两个输出 $y_1, y_2 \in R$，有

$\Pr_{h \in H} \left[ h(x_1) = y_1 \land h(x_2) = y_2 \right] = \frac{1}{|R|^2} = \frac{1}{4}.$

这里 $h$ 是从 $H$ 中均匀随机选取的函数，即 $h = h_{a,b}$ 且 $(a, b)$ 均匀取自 $\{0,1\}^k \times \{0,1\}$。

证明：

固定任意 $x_1 \neq x_2$ 在 $\{0,1\}^k$ 中，以及任意 $y_1, y_2 \in \{0,1\}$。定义事件：

$h_{a,b}(x_1) = a \cdot x_1 + b = y_1 \pmod{2}, \quad h_{a,b}(x_2) = a \cdot x_2 + b = y_2 \pmod{2},$

其中 $a \cdot x$ 表示二元域上的点积（即 $\sum_{i=1}^k a_i x_i \mod 2$)。

1. 建立线性方程组：
   将两个方程相减（在二元域中，加法等同于减法）：

   $(a \cdot x_1 + b) + (a \cdot x_2 + b) = y_1 + y_2 \pmod{2}.$

   化简得（注意 $b + b = 0 \pmod{2}$)：

   $a \cdot (x_1 + x_2) = y_1 + y_2 \pmod{2}. \quad (*)$

   令 $d = x_1 + x_2$ 和 $c = y_1 + y_2$。由于 $x_1 \neq x_2$，有 $d \neq 0$。方程 $(*)$ 即：

   $a \cdot d = c \pmod{2}.$

2. 分析方程的解：

   • 方程 $a \cdot d = c$ 是关于 $a$ 的线性方程。
   • 因为 $d \neq 0$，该方程在 $\{0,1\}^k$ 中恰有 $2^{k-1}$ 个解（即满足条件的 $a$ 的数量）。
   • 对每个满足 $a \cdot d = c$ 的 $a$，由原方程解出 $b$:

     $b = y_1 + a \cdot x_1 \pmod{2}.$

     此 $b$ 也满足第二个方程，因为：

     $a \cdot x_2 + b = a \cdot x_2 + (y_1 + a \cdot x_1) = a \cdot (x_1 + x_2) + y_1 = c + y_1 = (y_1 + y_2) + y_1 = y_2 \pmod{2}.$

     因此，对每个满足 $(*)$ 的 $a$，存在唯一的 $b$ 使两个事件同时成立。

3. 计算概率：

   • 满足条件的 $(a, b)$ 对的数量：$2^{k-1}$（因有 $2^{k-1}$ 个 $a$，每个对应唯一 $b$)。
   • $H$ 的总大小：$|H| = |\{0,1\}^k| \times |\{0,1\}| = 2^k \times 2 = 2^{k+1}$。
   • 概率为：

     $\Pr = \frac{\text{满足条件的 } (a,b) \text{ 对数}}{\text{总对数}} = \frac{2^{k-1}}{2^{k+1}} = \frac{1}{4}.$

因此，函数族 $H$ 是成对独立的。

11.2

题目

(a)

考虑一个在 $n + 1$ 个顶点 $0, 1, \ldots, n$ 上的随机游走 $X_0, X_1, X_2, \ldots$，其转移概率如下：

$\Pr(X_t = k | X_{t-1} = j) = \begin{cases} \frac{1}{2} & \text{如果 } j \in [1, n - 1] \text{ 且 } k = j \pm 1, \\ 1 & \text{如果 } j = 0, k = 1 \text{ 或 } j = n, k = n, \\ 0 & \text{其他情况}. \end{cases}$

设 $T_i$ 为从初始状态 $X_0 = i$ 出发，到达终点顶点 $n$ 的期望步数。证明对于所有 $i \in [0, n]$，有 $T_i \leq n^2$。

(b)

考虑以下针对 $n$ 个变量的 2-SAT 问题的随机算法。

• 1: 选择一个任意的初始赋值。
• 2: for $t = 1, 2, \ldots, 2n^2$ do
  • 3: if 当前赋值满足所有子句 then
    • 4: 立即接受。
  • 5: else
    • 6: 选择一个未被满足的子句（任意选择）。
    • 7: 以均匀概率随机选择该子句中的一个文字。
    • 8: 翻转所选文字中变量的值。
  • 9: end if
• 10: end for
• 11: 如果尚未接受，则拒绝。

使用马尔可夫不等式证明，当输入是一个可满足的实例（即存在满足赋值）时，该算法以至少 $\frac{1}{2}$ 的概率找到一个满足解（即在循环结束前接受）。

解答

(a)

考虑随机游走在顶点 $0, 1, \ldots, n$ 上，转移概率如题所述。顶点 $n$ 是吸收态（一旦到达即停留），顶点 $0$ 是反射壁（总是移动到 $1$)。设 $T_i$ 为从状态 $i$ 到达状态 $n$ 的期望步数。

定义 $T_i$ 满足以下方程：

• $T_n = 0$（因为已在终点）。
• 对于 $i = 0$，有 $T_0 = 1 + T_1$（因为从 $0$ 总是移动到 $1$，需一步）。
• 对于 $i \in [1, n-1]$，有 $T_i = 1 + \frac{1}{2} T_{i-1} + \frac{1}{2} T_{i+1}$（因为以概率 $\frac{1}{2}$ 移动到 $i-1$ 或 $i+1$，需一步）。

这是一个线性方程组。假设解的形式为二次函数 $T_i = a i^2 + b i + c$。代入边界条件求解：

• 由 $T_n = 0$，得 $a n^2 + b n + c = 0$。
• 由 $T_0 = 1 + T_1$，代入 $T_0 = c$、$T_1 = a + b + c$，得 $c = 1 + (a + b + c)$，即 $a + b = -1$（方程 (1)）。
• 对于内部点 $i \in [1, n-1]$，代入 $T_i = a i^2 + b i + c$ 到方程 $T_i = 1 + \frac{1}{2} T_{i-1} + \frac{1}{2} T_{i+1}$：

  $a i^2 + b i + c = 1 + \frac{1}{2} [a (i-1)^2 + b (i-1) + c] + \frac{1}{2} [a (i+1)^2 + b (i+1) + c].$

  展开并简化得 $c = 1 + a + c$，即 $a = -1$。
• 代入方程 (1)：$-1 + b = -1$，得 $b = 0$。
• 由 $a n^2 + b n + c = 0$，代入 $a = -1$、$b = 0$，得 $-n^2 + c = 0$，即 $c = n^2$.

因此，解为 $T_i = -i^2 + n^2 = n^2 - i^2$.
由于 $i^2 \geq 0$ 且 $i \in [0, n]$，有 $n^2 - i^2 \leq n^2$，等号成立当且仅当 $i = 0$。
故对于所有 $i \in [0, n]$，有 $T_i \leq n^2$.

(b)

假设输入是一个可满足的 2-SAT 实例（存在满足赋值）。设 $S$ 为一个固定的满足赋值。定义随机过程：

• $D_t$ 为时间 $t$ 时当前赋值与 $S$ 的汉明距离（不同变量的个数）。$D_t = 0$ 时表示找到满足赋值（算法接受）。
• $T$ 为首次命中 $D_t = 0$ 的时间（即找到满足赋值的步数）。

算法运行最多 $2n^2$ 步。目标是证明 $P(T \leq 2n^2) \geq \frac{1}{2}$，即 $P(T > 2n^2) \leq \frac{1}{2}$.

分析 $D_t$ 的变化：

• 当当前赋值不满足时，存在未满足子句。选择这样一个子句（对手任意选择），并以均匀概率随机翻转其中一个文字对应的变量。
• 由于 $S$ 满足该子句，在 $S$ 中至少有一个文字为真。翻转一个变量后，$D_t$ 变化为 $\pm 1$（因为只改变一个变量的匹配状态）。
• 考虑子句类型：
  • 若子句在 $S$ 中恰有一个真文字，则翻转后：以概率 $\frac{1}{2}$ 减少 $D_t$（翻转真文字对应的变量），以概率 $\frac{1}{2}$ 增加 $D_t$（翻转假文字对应的变量）。
  • 若子句在 $S$ 中有两个真文字，则翻转后：$D_t$ 一定减少 1（无论翻转哪个变量）。
• 对手为最大化期望时间，会选择使减少概率最小的子句。即，如果存在恰有一个真文字的子句，则选择它（此时减少概率为 $\frac{1}{2}$)；否则（所有未满足子句都有两个真文字），减少概率为 1。
• 因此，在任何状态下，减少 $D_t$ 的概率至少为 $\frac{1}{2}$，即 $P(D_{t+1} = D_t - 1) \geq \frac{1}{2}$，$P(D_{t+1} = D_t + 1) \leq \frac{1}{2}$，且 $D_t$ 变化为 $\pm 1$，边界：$D_t = 0$ 时吸收，$D_t = n$ 时下一步一定减少（因为未满足子句必有两个真文字）。

期望时间分析：
设 $E_d$ 为从距离 $d$ 出发的 $E[T]$。最坏情况下（对手使减少概率最小化），假设对于 $d \in [1, n-1]$，有 $P(\text{减少}) = \frac{1}{2}$，$P(\text{增加}) = \frac{1}{2}$。边界条件：

• $E_0 = 0$（已吸收）。
• 对于 $d = n$，有 $E_n = 1 + E_{n-1}$（因为下一步一定到 $n-1$)。
• 对于 $d \in [1, n-1]$，有 $E_d = 1 + \frac{1}{2} E_{d-1} + \frac{1}{2} E_{d+1}$.

求解该方程组：

• 递推关系：$E_{d+1} - 2E_d + E_{d-1} = -2$（整理方程得）。
• 齐次解：特征方程 $r^2 - 2r + 1 = 0$ 有重根 $r = 1$，故齐次解为 $a + b d$。
• 特解：假设 $E_d = c d^2$，代入得 $2c = -2$，即 $c = -1$。
• 通解：$E_d = a + b d - d^2$。
• 边界条件：
  • $d = 0$: $E_0 = a = 0$。
  • $d = n$: $E_n = b n - n^2 = 1 + E_{n-1} = 1 + [b (n-1) - (n-1)^2]$。
    代入化简：$b n - n^2 = 1 + b n - b - n^2 + 2n - 1$，即 $0 = -b + 2n$，得 $b = 2n$。
• 故 $E_d = 2n d - d^2 = d(2n - d)$。

由于 $d \in [0, n]$，有 $E_d = d(2n - d) \leq n \cdot n = n^2$（最大值在 $d = n$ 时取 $E_n = n^2$)。
实际中，减少概率可能大于 $\frac{1}{2}$，故 $E[T] \leq n^2$（最坏情况下等号成立）。

应用马尔可夫不等式：

• $T$ 是非负随机变量，且 $E[T] \leq n^2$。
• 算法运行 $2n^2$ 步，考虑事件 $T > 2n^2$。
• 由马尔可夫不等式：$P(T > 2n^2) \leq \frac{E[T]}{2n^2} \leq \frac{n^2}{2n^2} = \frac{1}{2}$。
• 因此，$P(T \leq 2n^2) \geq 1 - \frac{1}{2} = \frac{1}{2}$。

即，当输入可满足时，算法在 $2n^2$ 步内找到满足解的概率至少为 $\frac{1}{2}$。