指示变量法

0. 引入

指示变量法 可以利用期望线性性，快速计算期望，本文将介绍几个经典的例子。
我们知道

X = \sum_{i \in I} X_{i} \Rightarrow E (X) = \sum_{i \in I} E (X_{i})

那么，就可以通过找到 $X = \sum_{i \in I} X_{i}$ 而计算 $E (X)$ ，一般地，有三个条件：

能够找到 $X = \sum_{i \in I} X_{i}$ 这样的分解
计算 $E (X_{i})$ 比直接计算 $E (X)$ 容易
计算出 $E (X_{i}) = f (i)$ 后，对 $f (i)$ 求和容易，即计算 $\sum_{i \in I} f (i)$ 容易，特别地，若 $f (i) = C$ ，则 $\sum_{i \in I} f (i) = | I | C$

指示变量法指导我们如何寻找满足条件 2 的分解，然而不能保证满足条件 3。在快速排序一节中，可以看到 $\sum_{i \in I} f (i) = | I | C$ 可能没有封闭表达式，但能够渐进分析。

对于事件 $A$ ，定义其指示变量

X_{A} = [A] = {\begin{cases} 1 & if A_{i} \\ 0 & if \overset{―}{A_{i}} \end{cases}

立刻有

E (X_{A}) = P r (A)

如果能找到一系列事件 $A_{i}, i \in I$ ，满足 $X = \sum_{i \in I} X_{A_{i}}$ ，则 $E (X) = \sum_{i \in I} P r (A_{i})$ ，那么将 $X_{A_{i}}$ 简记作 $X_{i}$ ，条件 2 自然满足。如果 $A_{i}$ 是同质的，那么 $P r (A_{i})$ 是常数，条件 3 也将满足。

这就是指示变量法，你早已在伯努利实验的期望中使用了它。

1. 逆序数

问题

数列 ${a_{n}}$ 是集合 $[n] = {x ∣ x \in Z^{+}, x \leq n}$ 的等概随机排列， $π (i)$ 表示 $i$ 在数列 ${a_{n}}$ 中的位置，是 $[n]$ 到 $[n]$ 的双射，实际上 $π^{- 1} (i) = a_{i}$

逆序对是满足 $i < j$ 且 $π (i) > π (j)$ 的数对，逆序数是逆序对的总数，求逆序数的期望值。

用指示变量法解逆序数问题有两种方式，一种是元素视角，另一种是位置视角。

元素视角

我们考虑每对元素是否形成了逆序对，例如 $1$ 的位置是否在 $2$ 的位置之后。
令

A_{i j} 表示 π (i) > π (j)

则由对称性，

P r (A_{i j}) = \frac{1}{2}

逆序对总数：

X = \sum_{1 \leq i < j \leq n} X_{i j}

所以：

E (X) = \sum_{1 \leq i < j \leq n} \frac{1}{2} = \frac{n (n - 1)}{4}

位置视角

我们考虑每对位置上是否形成了逆序对，例如位置 $1$ 的元素是否比位置 $2$ 的元素大。
令

A_{i j} 表示 π^{- 1} (i) > π^{- 1} (j) \Leftrightarrow a_{i} > a_{j}

则

P r (A_{i j}) = \frac{1}{2}

逆序对总数：

X = \sum_{1 \leq i < j \leq n} X_{i j}

所以：

E (X) = \sum_{1 \leq i < j \leq n} \frac{1}{2} = \frac{n (n - 1)}{4}

总结

对于数列相关的问题，元素视角和位置视角都值得尝试，常常有某一种更好。由于逆序数问题中，元素和位置有良好的对偶性，因此两个视角均可行，且形式完全相同。

2. 快速排序 1

问题

这里研究随机化的快速排序：对于每一个子问题，等概随机地选择主元。我们希望研究这个随机算法所选主元总数的期望。

快速回顾一下快速排序算法，可以知道每个元素最多被选为主元一次。如果某个元素从未被选为主元，那么大小上相邻的两个元素一定被选为了主元。因此，一共至少 $⌊ \frac{n}{2} ⌋$ 个主元，最多可能需要 $n - 1$ 个主元，那么期望一定介于 $⌊ \frac{n}{2} ⌋$ 和 $n - 1$ 之间。

简化模型，设被排序的数列 ${a_{n}}$ 是集合 $[n] = {x ∣ x \in Z^{+}, x \leq n}$ 的等概随机排列，沿用逆序对问题的 $π$ 记号。

设随机变量 $X$ 为主元总数，事件 $A_{i}$ 为 “ $a_{i}$ 是主元”， $X_{i}$ 是 $A_{i}$ 的指示变量，那么

X = \sum_{i = 1}^{n} X_{i}

我们把那些不是主元的元素看作 广义主元，它们在成为递归树的叶子节点时被 “广义选择” 为 “主元”，那么每个元素恰好被广义选取一次。

现在设 $a_{m}, a_{n}$ 在大小上与 $a_{i}$ 相邻，则 “ $a_{i}$ 不是主元” 等价于 “ $a_{i}$ 是 ${a_{m}, a_{i}, a_{n}}$ 中最后被广义选择的。

由于主元的选择是等概随机的，经过思考，可以知道：

P r (A_{i}) = 1 - \frac{1}{3} = \frac{2}{3}

我们假设 $n \geq 2$ ，对于最小元素 $1$ 和最大元素 n，它们只有一个相邻元素，故对应的 $P r (A_{i}) = \frac{1}{2}$ ，而不是 $\frac{2}{3}$

故

E (X) = \sum_{i = 1}^{n} P r (A_{i}) = (n - 2) \cdot \frac{2}{3} + 2 \cdot \frac{1}{2} = \frac{2 n - 1}{3}

3. 快速排序 2

注：本节内容改编自杨宽老师的 SJTU CS1212 slides

问题

现在研究快速排序的时间复杂度。

快速排序的时间复杂度主要来源于比较元素，因此可以用比较的总次数 $T$ 衡量一次快速排序算法运行的时间。类似逆序对，总次数可以分解为每对元素的比较次数，即

X_{i j} = # of comparisons between a_{i} and a_{j}

T (n) = \sum_{1 \leq i < j \leq n} X_{i j}

基本事实

下面给出几个事实：

$X_{i j} \in {0, 1}$
不妨设 $a_{i} < a_{j}$ ，则某个轮次中 $a_{i}$ 与 $a_{j}$ 产生比较，等价于 $a_{i}$ 或 $a_{j}$ 是当轮的主元，且任意满足 $a_{i} < a_{k} < a_{j}$ 的 $a_{k}$ 都尚未被选为主元，否则 $a_{i}$ 和 $a_{j}$ 已经被分开
不妨设 $a_{i} < a_{j}$ ，由于 $a_{i}$ 与 $a_{j}$ 终要分开，要么被其他主元分开，要么两者直接比较，最终 $X_{i j} = 1$ 等价于任意满足 $a_{i} < a_{k} < a_{j}$ 的 $a_{k}$ 都未被选为主元，直到 $a_{i}$ 或 $a_{j}$ 成为主元，也就等价于， $a_{i}$ 或 $a_{j}$ 是 ${a_{k} ∣ a_{i} \leq a_{k} \leq a_{j}}$ 中最先成为主元的。

可以发现，定义 $X_{i j} = # of comparisons between a_{i} and a_{j}$ 是 位置视角
相应地，元素视角的定义是

X_{i j} = # of comparisons between i and j

元素视角下，第三个事实是：

$X_{i j} = 1$ 等价于 $i$ 或 $j$ 是 ${i, i + 1, \dots, j}$ 中最先成为主元的

把“ $i$ 或 $j$ 是 ${i, i + 1, \dots, j}$ 中最先成为主元的”作为事件 $A_{i j}$ ，这就是说 $E (X_{i j})$ 是 $A_{i j}$ 的指示变量。

明显，元素视角对于这个问题更好，因为它提供了已知序关系，让 $A_{i j}$ 的表述更简单，也让计算更具确定性，所以采用元素视角。

计算

由于主元的选择是等概随机的，故：

E (X_{i j}) = P r (A_{i j}) = \frac{2}{j - i + 1}

T (n) = \sum_{1 \leq i < j \leq n} \frac{2}{j - i + 1}

当然，采用位置视角也是可以的：

E (X_{i j}) = P r (A_{i j}) = \frac{2}{| {a_{k} ∣ a_{i} \leq a_{k} \leq a_{j}} |}

T (n) = \sum_{1 \leq i < j \leq n} \frac{2}{| {a_{k} ∣ a_{i} \leq a_{k} \leq a_{j}} |} = \sum_{1 \leq i < j \leq n} \frac{2}{j - i + 1}

得到上式的第二个相等关系实际上需要隐式地采用元素视角。因此，在快速排序的问题上，元素视角和位置视角没有本质不同，两者给出的答案本质相同。

对于这个结果，可以作渐进分析，得到快速排序时间复杂度的经典结论：

H_{n} = \sum_{i = 1}^{n} \frac{1}{i} \approx \ln n + γ

T (n) = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1} = 2 \sum_{i = 1}^{n - 1} [H (n - i + 1) - 1] \leq 2 \sum_{i = 1}^{n - 1} [H (n) - 1] \leq 2 n \ln n

4. 最小元素

问题

从集合 $[n]$ 中，等概随机地选择大小为 $k$ 的子集，求子集最小元素的期望

直接计算

记子集最小元素为随机变量 $X$

P (X = i) = \frac{(\binom{n - i}{k - 1})}{(\binom{n}{k})}

E (X) = \sum_{i = 1}^{n - k + 1} i P (X = i) = \sum_{i = 1}^{n - k + 1} \frac{i (\binom{n - i}{k - 1})}{(\binom{n}{k})}

这个式子的进一步处理有较强技巧性，下面展示指示变量法如何巧妙解决问题。

我们把 $[n]$ 看作 $n$ 个位置，对于被选入子集的位置，将在该位置上放置 $1$ ，反之放置 $0$ ，形成 $0 / 1$ 数列。

容易证明原问题与下面的问题等价：

序列 ${a_{n}}$ 的前 k 个元素是 $1$ ，后 $n - k$ 个元素是 $0$ ， ${b_{n}}$ 是 ${a_{n}}$ 的等概随机排列，映射函数是 $σ$ ，设 ${b_{n}}$ 中 $1$ 的最小位置为随机变量 $X$ ，形式化地，

X = min_{a_{i} = 1} σ (i) = min_{1 \leq i \leq k} σ (i)

例如，当 ${b_{n}} = 0, 0, 1, 1, 1, 0$ 时， $n = 6, k = 3, X = 3$

求 $E (X)$

接下来的处理方法分为位置视角和元素视角，有较大区别。

位置视角

令事件 $A_{i}$ 表示 $\forall x \leq i, b_{x} = 0$ ，指示变量为 $X_{i}$
那么，

X = 1 + \sum_{i = 1}^{n} X_{i}

E (X) = 1 + \sum_{i = 1}^{n} P r (A_{i}) = \sum_{i = 1}^{n - k} \frac{(\binom{n - i}{k})}{(\binom{n}{k})}

换元，令 $j = n - i$

\sum_{i = 1}^{n - k} \frac{(\binom{n - i}{k})}{(\binom{n}{k})} = \frac{1}{(\binom{n}{k})} \sum_{j = k}^{n - 1} (\binom{j}{k}) = \frac{(\binom{n}{k + 1})}{(\binom{n}{k})} = \frac{n - k}{k + 1}

E (X) = 1 + \frac{n - k}{k + 1} = \frac{n + 1}{k + 1}

实际上，若采用位置视角，则不必转化问题，直接在原问题上将 $A_{i}$ 设为事件 ${1, 2, \dots, i}$ 中元素均未被选入子集即可。但元素时间必须转化问题，因为原问题没有”元素“的概念。为了对照，这里提前转化了问题。

元素视角

令事件 $A_{i}$ 表示 $σ (i) \leq X$ ，指示变量为 $X_{i}$
那么，

X = \sum_{i = 1}^{n} X_{i}

若 $i \leq k, a_{i} = 1$ ， $P r (A_{i}) = \frac{1}{k}$ ，因为 $A_{i}$ 的含义是， $σ (i)$ 是像集 $σ ([k])$ 的最小值

若 $i > k, a_{i} = 0$ ， $P r (A_{i}) = \frac{1}{k + 1}$ ，因为 $A_{i}$ 的含义是， $σ (i)$ 比 $k$ 个 $1$ 在 ${b_{n}}$ 中都更靠前，即 $σ (i)$ 是像集 $σ ([k] \cup i)$ 的最小值

故

E (X) = \sum_{i = 1}^{n} P r (A_{i}) = \sum_{i = 1}^{k} P r (A_{i}) + \sum_{i = k + 1}^{n} P r (A_{i}) = \frac{k}{k} + \frac{n - k}{k + 1} = \frac{n + 1}{k + 1}

总结

最终，我们解决了问题，并且获得了一个组合恒等式：

\sum_{i = 1}^{n - k + 1} \frac{i (\binom{n - i}{k - 1})}{(\binom{n}{k})} = \frac{n + 1}{k + 1}

在这个问题中，位置视角与元素视角大相径庭，后者非常巧妙，得到结果也更直接，无需对组合式求和。