paper_5 第3节 Theorem 5 & charge rule
analysis
为什么 Algorithm 1 的探测次数，在期望意义下不会比最优策略差太多？
“收费 charging method”是作者用来证明近似比的一种数学分析技巧。
先导：
费用不是现实中的钱，也不是 probing cost 本身，而是一种“记账工具”。作者把算法每次 probe 节点的代价，按照规则记到一些被揭示的节点身上，最后通过统计每个节点最多被记几次，来证明总探测代价有上界。
定理 5 到底想证明什么？
定理 5 要证明：
$$
E[|S|]\leq
\left(
\frac{1}{\delta}(H(\Delta-1)+1)+1
\right)|O|
$$
这里：
- $S$：Algorithm 1 探测过的节点集合；
- $|S|$：算法的 probing cost；
- $O$：最优策略探测过的节点集合；
- $|O|$：最优策略的 probing cost；
- $\delta$：节点最小 active 概率；
- $\Delta$：图最大度。
所以定理 5 的意思是：
本文算法的期望探测次数，不会超过最优策略探测次数的
$$
\frac{1}{\delta}(H(\Delta-1)+1)+1
$$
倍。
这就是它的近似比证明。
为什么要“收费”？
因为直接比较很难。
算法每次选择节点，是根据当前状态动态决定的。
最优策略 (O) 也是一个策略，不是一个固定 CDS 集合。
所以不能像普通 CDS 那样简单比较（CDS 的大小，其大小是变化的！！！）：
$$
|S| \quad \text{和} \quad |OPT|
$$
换一种思路：
算法每 probe 一个节点，就产生 1 个单位代价。
不直接算这个代价，而是把这个代价“分摊”给一些节点。
如果能证明每个相关节点被分摊的总费用不大，那么算法总代价也不大。
这个就是 charging method。
实际上，每个节点收到的分摊 charge 是发出分摊节点的实时权重 !
这里的“费用”到底是？
易混点：
第一，真实代价
真实代价是 probing cost，算法每主动探测一个节点，代价是 1。
所以算法总真实代价是：$|S|$
第二，charge / 费用
charge 是证明时人为定义的“账”。
每次算法选择节点 ($v_i$)，会把一个数值：$w_{S_{i-1}}(v_i)$ 记到若干个节点身上。
这个 $w_{S_{i-1}}(v_i)$ 就是实时权重。
所以可以这样理解：
每次 probe 节点 ($v_i$)，它会向若干个节点收取一笔费用，每个被收费节点收到的费用大小都是 $w_{S_{i-1}}(v_i)$。
注意：
这只是证明里的虚拟费用，不是真的算法操作。
算法运行时并不会真的 charge。
charge 只是作者分析近似比的工具。
为什么费用大小用实时权重 $w_S(v)$
实时权重是“单位收益代价”的意思。 -> 即 总代价 ÷ 总收益 = 单位收益需要付出的代价
即，$ w_s(v) = \frac{1}{总收益}$
而总收益 = 信息收益 + 连通收益 = $NWS(v) + NCS(v)-1$
前面已知：
- 权重越小，说明这个节点越值得探测；
- 权重大致是“收益的倒数”。
例如灰色节点：
$$
w_S(v)=\frac{1}{NWS(v)+NCS(v)-1}
$$
如果它能带来很多收益，分母大，权重小。
现在让它给：
$$
NWS(v)+NCS(v)-1
$$
个节点收费，每个节点收费：
$$
w_S(v)
$$
那么总 charge 是：
$$
(NWS(v)+NCS(v)-1)\cdot w_S(v)
$$
代入：
$$w_S(v)=\frac{1}{NWS(v)+NCS(v)-1}$$
得到：
$$
总 charge=1
$$
刚好对应一次 probe 的真实代价 1 ！！
charging 的核心设计
希望做到：
算法每探测一次，真实代价是 1;
通过 charge，把这 1 个单位代价分摊给一些被揭示或被合并的节点。
所以设计了：
$$E[ch(v_i)] = \frac{1}{w(v_i)}$$
希望 收费节点数量的期望 = 权重的倒数 ， 为了凑出 数量 * charge = 1
即 $\frac{1}{权重} * 权重 = 1 $
每个被 charge 的节点收到的费用是：
$$w(v_i)$$
于是本轮期望总收费是：
$$E[ch(v_i)]\cdot w(v_i)=1$$
这样就把“每次 probe 的代价 1”转化成了“若干节点收到的 charge”。
为什么要维护不变式？
不变式：
$$\text{每个黑色连通分量中，恰好有一个黑色节点没有被收费。}
$$
是为了处理 灰色节点连接多个黑色分量 的情况。
想：
Algorithm 1 的一个重要任务是保证黑色节点最后连通。
灰色节点如果邻接多个黑色分量，那么探测它之后，它变黑，可以把这些分量合并。
例如有 3 个黑色连通分量：
1 | 黑色分量 C1 黑色分量 C2 黑色分量 C3 |
如果 probe 灰色节点 (u)，它变黑，就会把三个黑色分量合并成一个大分量。
作者希望 charge 过程中始终保持：
每个黑色分量里只保留一个“没被收费”的黑色节点。
why？因为后面统计总 charge 时，每个黑色节点最好只被 charge 一次，不会乱套。
为什么灰色节点收费时，要 charge ($NC_S-1$) 个黑色分量？
整个不变式最关键。
假设灰色节点 (u) 邻接 3 个黑色分量：
$$NCS(u)=3$$
根据不变式，合并前每个黑色分量中各有一个未收费黑色节点：
1 | C1 有 1 个未收费黑点 |
probe (u) 后，这 3 个分量合并成 1 个大分量。
如果什么都不做，那么大分量里会有 3 个未收费黑点。
但不变式要求：
1 | 每个黑色分量恰好 1 个未收费黑点 |
所以合并后只能留下 1 个。
就对其中：
$$NCS(u)-1=2$$
个分量里的未收费黑点进行 charge，留下1 个不 charge。
这样合并后大分量里仍然只有 1 个未收费黑点。
这就是为什么第三种收费情况里面是：
$$NC_S(v_i)-1$$
而不是：
$$NC_S(v_i)$$
三种收费情况？
情况 I：($v_i$) 是白色且 active
这时 ($v_i$) 原本未知，探测后发现它 active。
于是：
- ($v_i$) 变黑；
- 它成为一个新的黑色分量；
- 它揭示邻域中的白色节点状态。
论文规定：
($v_i$) 自己不收费，(N($v_i$)) 中的白色节点收费。
为什么 ($v_i$) 自己不收费？
因为它变成了一个新的黑色分量。为了满足不变式：
$$\text{每个黑色分量要有一个未收费黑点}$$
所以这个新黑色分量中的 ($v_i$) 就作为那个“未收费黑点”。
所以它不能被收费。
那谁收费？
它邻域中被揭示的白色节点收费。
收费数量是：
$$NWS(v_i)-1$$
因为 ($NW_S(v_i)$) 是 (N[$v_i$]) 中白色节点数量，包含 ($v_i$) 自己。
但 ($v_i$) 自己不收费，所以剩：
$$NW_S(v_i)-1$$
个节点收费。
情况 II：($v_i$) 是白色且 inactive
这时 ($v_i$) 原本未知，探测后发现 inactive。
它不会变黑，也不会形成黑色分量, 只是被移除。
直接让它自己收费。
收费数量是：
$$1$$
很好理解：
探测它花了 1 次代价，但它没有带来邻域揭示，只揭示了自己 inactive，所以费用记到它自己身上。
情况 III：($v_i$) 是灰色节点
灰色节点已经知道 active，只是还没被主动 probe。
probe 它以后：
- 它变黑；
- 它揭示邻域中的白色节点；
- 它可能把多个黑色分量合并。
所以它有两类收益：
第一类：揭示白色节点
它邻域中有：
$$NWS(v_i)$$
个白色节点。
这些白色节点被揭示，因此收费。
第二类：合并黑色分量
它邻接：
$$NC_S(v_i)$$
个黑色分量。
probe 它后，这些分量被合并成一个大分量。
为了保持不变式，只对其中：
$$NC_S(v_i)-1$$
个黑色分量里的未收费黑点收费。
留下一个未收费黑点，作为合并后大分量的未收费黑点。
所以灰色节点总共收费的节点数是：
$$NWS(v_i)+NCS(v_i)-1$$
这和灰色权重完全对应：
$$w_S(v_i)=
\frac{1}
{NWS(v_i)+NCS(v_i)-1}$$
用一个例子看灰色节点收费
假设灰色节点 (u) 周围是这样：
1 | 白色节点 a 黑色分量 C1 |
假设：
$$NW_S(u)=1$$
因为它邻域里有 1 个白色节点 (a)。
$$NC_S(u)=3$$
因为它邻接 3 个黑色分量。
那么：
$$NWS(u)+NCS(u)-1=1+3-1=3$$
所以：
$$w_S(u)=\frac{1}{3}$$
probe (u) 这一轮，真实代价是 1。
charging ？
- 白色节点 (a) 收费 ($\frac{1}{3}$)；
- 从 3 个黑色分量中选 2 个分量，各找一个未收费黑点收费 ($\frac{1}{3}$)；
- 还有 1 个黑色分量的未收费黑点保留，不收费。
总共 3 个节点被收费：
$$3\times \frac{1}{3}=1$$
刚好等于这一轮 probe 的真实代价 1。
这就是 charging 的妙处。
白色节点 active 情况为什么是期望？
对白色节点，情况有随机性。
如果 probe 白色节点 (v)：
以概率 (1-p(v))，它 inactive
收费节点数：
$$1$$
因为只给自己收费。
以概率 (p(v))，它 active
收费节点数：
$$NWS(v)-1$$
因为自己变黑且不收费，其他白色邻居收费。
所以收费节点数的期望是：
$$(1-p(v))\cdot 1+p(v)\cdot(NWS(v)-1)$$
也就是：
$$1-p(v)+p(v)(NWS(v)-1)$$
而白色节点权重定义刚好是：
$$w_S(v)=
\frac{1}
{1-p(v)+p(v)(NWS(v)-1)}$$
所以：
$$E[ch(v)]=\frac{1}{w_S(v)}$$
这就是公式 (9) 对白色节点成立的原因。
公式 (9)
公式 (9)：
$$E[ch(v_i)\mid \Gamma]=\frac{1}{w_{S_{i-1}}(v_i)}$$
这里：
- $ch(v_i)$：本轮有多少个节点被收费；
- $w_{S_{i-1}}(v_i)$：本轮每个被收费节点收到的费用；
- $\Gamma$：给定本轮之前的状态以及本轮选择了 ($v_i$)。
意思是：
本轮被收费节点数量的期望，等于权重的倒数。
于是本轮期望总收费是：
$$E[ch(v_i)]\cdot w(v_i)$$
$$
=\frac{1}{w(v_i)}\cdot w(v_i)
$$
$$=1$$
这就对应了一次 probe 的代价。
所以 charging 方法就是把：
$$\text{每次 probe 的代价 }1$$
变成：
$$\text{若干节点收到的费用总和}$$
为什么说每个节点基本只被 charge 一次？
设计规则就是为了保证：
- 白色节点被揭示后，变灰或者移除，以后不再以白色身份被 charge；
- 灰色节点第一次被揭示变灰时被 charge，以后不再被 charge；
- 白色 active 节点自己变黑时不 charge，之后如果它所在黑色分量被合并，它可能被 charge 一次；
- 被 charge 过的黑色节点不会再次被 charge；
- 通过不变式保证每个黑色分量始终只保留一个未收费黑点。
所以最终效果是：
除了最后剩下的一个黑色节点外，相关区域里的节点基本都会被恰好 charge 一次。
这就方便后面统计总 charge。
##为什么要和最优策略 (O) 联系？
作者已经把算法的探测代价转化成了节点 charge。
接下来要做的是：
证明这些被 charge 的节点，可以被最优策略 (O) 的邻域覆盖，并且每个 (v\in O) 对应的 charge 总量不会太大。
因为 (O) 是最优策略探测的节点集合。
如果能证明：
$$\text{算法总 charge}
\leq
\left(
\frac{1}{\delta}(H(\Delta-1)+1)+1
\right)|O|$$
那就得到定理 5。
后面调和数：
$$H(\Delta-1)$$
就是从“一个最优节点 (v) 的邻域中，多个节点按揭示顺序被 charge，权重最多形成 ($1+\frac12+\frac13+\cdots$)”这种分析里来的。
串起来
整个定理 5 的来龙去脉是：
1 | 目标： |
这样理解
第一，charge 是证明里的虚拟费用，不是算法真实操作。
第二，真实代价是每 probe 一个节点花费 1，作者把这个 1 分摊给被揭示的节点。
第三，每个节点收到的费用大小就是实时权重 (w_S(v))。
第四，维护不变式是为了处理黑色分量合并，避免黑色节点被重复收费，并保证最后可以统计总 charge。
直观理解
可以把 charging method 看成这样：
Algorithm 1 每次选择一个节点，是因为它能揭示白色节点或连接黑色分量。
那么这次 probe 的成本，就由这些“受益对象”来分摊。
如果一个节点收益大，它能分摊给更多对象，所以每个对象承担的费用 (w) 就小。
最后每个对象最多承担一次费用，于是总费用可控。
1 | Theorem 5 的证明主要由 charging method、Claim 1 和 Claim 2 组成。 |