基于置信序列的风险限制审计

# 基于置信序列的风险限制审计 ## 1. 风险限制审计基础 在选举审计场景中，我们将投票数据进行编码。把给 Alice 的投票编码为 1，给 Bob 的投票编码为 0，无效投票编码为 1/2，得到数字列表 $\{x_1, \ldots, x_N\}$。设 $\mu^\star := \frac{1}{N}\sum_{i = 1}^{N} x_i$，$(C_t)_{t = 1}^{N}$ 是 $\mu^\star$ 的 $(1 - \alpha)$ 置信序列。若要审计 “Alice 击败 Bob” 这一断言，令 $u = 1$，$A = (1/2, 1]$。我们可以无放回地依次抽样 $X_1, X_2, \ldots, X_N$，一旦 $C_t \subseteq A$，就认证该断言，此方法可将风险限制在 $\alpha$ 水平。 ### 1.1 与序贯假设检验的关系 早期的风险限制审计（RLA）未使用随时 $p$ 值，大约从 2009 年起，多数 RLA 方法采用随时 $p$ 值进行序贯假设检验。随时 $p$ 值是一个序列 $(p_t)_{t = 1}^{N}$，在原假设 $H_0$ 下，满足 $P_{H_0}(\exists t \in [N] : p_t \leq \alpha) \leq \alpha$。 对于每个原假设 $H_0 : \mu^\star = \mu$，随时 $p$ 值 $p_t \equiv p_t(\mu)$ 通常隐式定义，并产生序贯假设检验 $\varphi_{\mu}^t := 1(p_t(\mu) \leq \alpha)$。通过 “反转” 该检验可得到置信序列：$C_t := \{\mu \in [0, u] : \varphi_{\mu}^t = 0\}$。 在简单的两候选人选举中，若报告 Alice 获胜，即 $\mu^\star := \frac{1}{N}\sum_{i = 1}^{N} x_i > 1/2$。在 SHANGRLA 框架下的序贯 RLA 会提出原假设 $H_0 : \mu^\star \leq 1/2$，依次随机抽样选票，若在显著水平 $\alpha$ 下拒绝 $H_0$，则停止审计并确认报告结果；若在检查完所有选票前未拒绝 $H_0$，则可知真实结果。 而基于置信序列的选票抽样 RLA 则通过计算 Alice 得票比例 $\mu^\star$ 的 $1 - \alpha$ 下置信界，当该下置信界大于 1/2 时停止审计并确认结果；若在检查完最后一张选票前未出现此情况，则可知真实结果。这种方法无需定义原假设，也无需解释 $p$ 值，且适用于使用 “高估分类器” 方法的比较审计。 ### 1.2 多场选举的审计 多候选人、多获胜者选举的 RLA 可简化为多个两两对决，无需进行多重性调整。具体做法是检验每个报告的获胜者是否击败每个报告的失败者，当所有这些检验在水平 $\alpha \in (0, 1)$ 下拒绝各自的原假设时停止审计。 例如，在一场 $k$ 获胜者的多数选举中，报告候选人集合 $W$ 击败候选人集合 $L$（$|W| = k$，$|L| = K - k$）。对于每个 $w \in W$ 和 $\ell \in L$，将给 $w$ 的投票编码为 1，给 $\ell$ 的投票编码为 0，无效投票或给其他候选人的投票编码为 1/2，得到总体 $\{x_{w,\ell}^1, \ldots, x_{w,\ell}^N\}$。则 $w$ 击败 $\ell$ 当且仅当 $\mu_{w,\ell}^\star := \frac{1}{N}\sum_{i = 1}^{N} x_{w,\ell}^i > 1/2$。我们检验原假设 $H_{w,\ell}^0 : \mu_{w,\ell}^\star \leq 1/2$ 与备择假设 $H_{w,\ell}^1 : \mu_{w,\ell}^\star > 1/2$，当所有 $k(K - k)$ 个原假设都被拒绝时，审计停止。 若使用置信序列进行审计，设 $\{(C_{w,\ell}^t)_{t = 1}^{N}\}$ 是 $\{\mu_{w,\ell}^\star\}$ 的 $(1 - \alpha)$ 置信序列，当所有 $w \in W$ 和 $\ell \in L$ 都满足 $C_{w,\ell}^t \subseteq (1/2, u]$ 时，验证每场选举的结果。 ## 2. 设计强大的置信序列 ### 2.1 序贯假设检验与鞅 为了高效地进行 RLA，我们需要设计强大的置信序列。可通过 “反转” 序贯假设检验来构造置信序列。给定序贯假设检验 $(\varphi_{\mu}^t)_{t = 1}^{N}$，集合序列 $C_t := \{\mu \in [0, 1] : \varphi_{\mu}^t = 0\}$ 构成 $\mu^\star$ 的 $(1 - \alpha)$ 置信序列。 为设计序贯假设检验，我们先寻找能转化为强大检验的鞅。定义 $M_0(\mu) := 1$，对于 $t \in [N]$，有： $M_t(\mu) := \prod_{i = 1}^{t} (1 + \lambda_i(X_i - C_i(\mu)))$ 其中 $\lambda_i \in [0, \frac{1}{C_i(\mu)}]$ 是仅依赖于 $X_1, \ldots, X_{i - 1}$ 的调整参数，$C_i(\mu