paper_5 第3节理论分析 2

引理 3

论文将 Algorithm 1 的探测节点集合与最优策略在 full realization ϕ 下探测的节点集合 O 进行比较。
需要注意的是，在 stochastic CDS 中，最优策略探测的节点集合 O 不一定等于最终 CDS，因为部分探测节点可能只是为了揭示状态信息，
尤其是为了确认 root 所在 active 连通分量的边界。

Lemma 3 是一个技术引理，用于估计找到第一个 active 节点所需的期望探测次数。
设有相互独立事件 I_1,...,I_n，事件 I_i 发生概率为 p_i，且 p=min p_i。
若 X 表示第一个发生事件的下标，则 E[X]≤1/p。
直观上，如果每次尝试成功概率至少为 p，那么第一次成功之前的期望尝试次数不超过 1/p。
该引理后续用于说明在节点 active 概率至少为 δ 的情况下，
找到一个 active 节点所需的期望探测次数至多为 1/δ。

与容错关系

这段引理未来也可能能用到容错扩展里。

比如后面要找一条增强路径 $P$，路径上的中间节点状态未知。
如果需要探测一批候选节点或候选路径中的节点，那么也会遇到类似问题：

在节点 active 概率至少为 $\delta$ 的情况下，找到一个可用 active 节点或可用增强路径的期望探测代价是多少？

不过要注意，路径成功概率通常是：
$$
\prod_{v\in P}p(v)
$$
这比单节点 active 概率更复杂。
所以如果做 2-connected 容错增强，后面可能要设计新的期望代价分析，不能直接照搬 Lemma 3。

Theorem 5

使用 charging method 证明算法的期望近似比。
将每次 probe 的待解分摊给被揭示节点，并维护“每个黑色连通分量恰好有一个未被 charge 的
黑色节点”的不变式。通过三种收费情况，可以证明算法期望探测次数等于所有节点收到的期望 charge
总和。

进一步，对最优策略中每个节点 V 的闭区域 charge 进行上届估计，得到调和函数 H($\Delta$- 1)
最终算法证明具有期望近似比：E[|S|] ≤ ((1/δ)(H(Δ-1)+1)+1)|O|。

核心总结

$H_\varphi$：root 所在 active 连通分量。
Lemma 2：证明算法输出是可行 CDS，核心是支配性 + 连通性。
Lemma 3 / Corollary 4：第一次遇到 active 节点的期望位置不超过 $1/\delta$。
Charging method：把每次 probe 的代价分摊给被揭示节点，用来分析近似比。
Theorem 5：算法期望近似比为
$$
\left(
\frac{1}{\delta}(H(\Delta-1)+1)+1
\right)
$$