指示变量法

2025-03-26

0. 引入

指示变量法 可以利用期望线性性，快速计算期望，本文将介绍几个经典的例子。 我们知道 那么，就可以通过找到 而计算 ，一般地，有三个条件：

  1. 能够找到 这样的分解
  2. 计算 比直接计算 容易
  3. 计算出 后，对 求和容易，即计算 容易，特别地，若 ，则

指示变量法 指导 我们如何寻找满足条件 2 的分解，然而不能保证满足条件 3。在快速排序一节中，可以看到 可能没有封闭表达式，但能够渐进分析。

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

立刻有

如果能找到一系列事件 ，满足 ，则 ，那么将 简记作 ，条件 2 自然满足。如果 是同质的，那么 是常数，条件 3 也将满足。

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

1. 逆序数

问题

数列 是集合 的等概随机排列， 表示 在数列 中的位置，是 到 的双射，实际上

逆序对是满足 且 的数对，逆序数是逆序对的总数，求逆序数的期望值。

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

元素视角

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

表示

则由对称性，

逆序对总数：

所以：

位置视角

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

表示

则

逆序对总数：

所以：

总结

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

2. 快速排序 1

问题

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

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

简化模型，设被排序的数列 是集合 的等概随机排列，沿用逆序对问题的 记号。

设随机变量 为主元总数，事件 为 “ 是主元”， 是 的指示变量，那么

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

现在设 在大小上与 相邻，则 “ 不是主元” 等价于 “ 是 中最后被广义选择的。

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

我们假设 ，对于最小元素 和最大元素 n，它们只有一个相邻元素，故对应的，而不是

故

3. 快速排序 2

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

问题

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

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

基本事实

下面给出几个事实：

  2. 不妨设 ，则某个轮次中 与 产生比较，等价于 或 是当轮的主元，且任意满足 的 都尚未被选为主元，否则 和 已经被分开
  3. 不妨设 ，由于 与 终要分开，要么被其他主元分开，要么两者直接比较，最终 等价于任意满足 的 都未被选为主元，直到 或 成为主元，也就等价于， 或 是 中最先成为主元的。

可以发现，定义 是 位置视角 相应地，元素视角的定义是

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

等价于 或 是 中最先成为主元的

把“ 或 是 中最先成为主元的”作为事件 ，这就是说 是 的指示变量。

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

计算

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

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

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

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

4. 最小元素

问题

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

直接计算

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

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

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

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

序列 的前 k 个元素是 ，后 个元素是 ， 是 的等概随机排列，映射函数是 ，设 中 的最小位置为随机变量 ，形式化地，

例如，当 时，

求

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

位置视角

令事件 表示 ，指示变量为 那么，

换元，令

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

元素视角

令事件 表示 ，指示变量为 那么，

若 ，，因为 的含义是， 是像集 的最小值

若 ，，因为 的含义是， 比 个 在 中都更靠前，即 是像集 的最小值

故

总结

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

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

评论区

最新评论

--