图熵与随机独立集

独立集可以被看作一份“相容候选清单”。发送关于 $W$ 的信息后，仍允许其中多个顶点作为真正的 $X$，因此不需要完全揭示源值。

常出现的顶点希望被更多候选清单覆盖。式 (2) 的 $a_x$ 是按某个随机独立集分布，顶点 $x$ 被包含的概率；$-\log a_x$ 衡量让这一顶点落进随机清单需要支付多少信息。图结构限制哪些顶点能共同进入一份清单，源概率则决定这些代价的权重。

两个极端校准定义方向 ​

若 $G$ 无边，可始终取 $W=V$，完全不暴露 $X$，所以 $H_G(P)=0$。若 $G$ 完全，独立集只能是单点，$W=\{X\}$，于是 $H_G(P)=H(X)$。

增加边会缩小可用独立集族，因此不能降低图熵。这里的图边表示“不能放在同一候选清单”，与信道中挑独立集的方向一致。

三点路径的非均匀分布 ​

在路径 $a-b-c$ 上，设 $P(a)=1/2,P(b)=1/4,P(c)=1/4$。独立集可扩成两个极大集合 $\{a,c\}$ 与 $\{b\}$，扩集合是对原 $W$ 的确定后处理，由数据处理不等式公理库数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。不增加互信息。因此只需考虑这两个值。

$x=b$ 时只能选 $\{b\}$，$x=a,c$ 时只能选 $\{a,c\}$，所以最优 $W$ 正好说明“是否为中点”。图熵为

用式 (2) 也可算出。令两个极大独立集的权重为 $1-t,t$，则 $(a_a,a_b,a_c)=(1-t,t,1-t)$，目标为

求导为零得到 $t=1/4$，二阶导严格为正，因而是唯一内部极小值；边界目标发散。这与互信息计算一致。

五边形中，随机化确实有作用 ​

令 $X$ 在 $C_5$ 的五个顶点上均匀。其最大独立集为五个非邻点对，每个顶点恰属于两个这样的集合。给定 $X=x$ 后，均匀选包含它的两组之一。

这使 $W$ 在五个独立集上均匀，而给定 $W$ 时 $X$ 在其中两个点上均匀。因此

任一独立集最多两点，由有限支持的最大熵界公理库Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。，任何合法 $W$ 都有 $H(X\mid W)\le 1$，所以这个值已最优。

一次确定性最小熵着色则可用色类大小 $2,2,1$，颜色熵为

比图熵大 $1/5$ bit。这里 $W$ 的熵为 ${\log }_{2}5$，甚至比颜色熵更大，但 $I(X;W)$ 更小；把式 (1) 错写成最小化 $H(W)$，就会漏掉这个区别。

证明两个定义等价 ​

先给定一个合法联合分布，令 $q_I=\text{Pr}[W=I]$、$a_x=\sum _{I\ni x}{q}_I$。固定 $x$，条件分布只能落在含 $x$ 的集合上。与原边缘分布 $q$ 相比，先把 $q$ 限制到这些集合并归一化，KL 散度公理库KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。的有限和分解给出

按 $P(x)$ 平均，得到 $I(X;W)\ge \sum _{x}P(x)\log \left(1/a_x\right)$，从而式 (1) 不小于式 (2)。

反过来，任取式 (2) 的有限目标点，写成独立集指示向量的凸组合 $a_x=\sum _{I\ni x}{q}_I$。对每个 $P(x)>0$ 的顶点，有限目标保证 $a_x>0$，定义

在 $P(x)=0$ 的顶点上，任取一个包含 $x$ 的独立集作为条件值，不使用可能为零的 $a_x$ 作除数。该条件分布合法，且每个正概率 $x$ 的条件 KL 满足 $D(P_{W\mid x}\Vert q)=\log \left(1/a_x\right)$。注意构造后的真实边缘 $q^{\prime }$ 未必等于所选参考分布 $q$；正确恒等式是

所以式 (1) 也不大于式 (2)，完成等价证明。忽略 $q^{\prime }$ 与 $q$ 的区别，会把一个有效证明误写成并不总成立的边缘一致性声明。

操作含义要配对正确的图积 ​

令 $G^{\vee n}$ 为 OR 幂：只要某一坐标的两个顶点相邻，两串就相邻。设 $H_{\chi }(G,P)$ 是所有合法确定性着色的最小颜色熵。一个标准图熵定理给出

它可解释为 OR 冲突约束下的平均前缀描述率：先对块着色，再按有限源的前缀编码界公理库无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。编码颜色，平均长度与颜色熵相差至多1位。若颜色支持至少有两点，差严格小于1；只有一种颜色时，未知块数的正码字约定用1位，外部已给定块数时也可用空描述。[1,2]

下界的机制是把一个颜色对应的独立色类投影到每个坐标；OR 独立性保证每个投影都是独立集。利用源坐标独立和信息链式法则，整块颜色熵至少为各坐标所需 $I(X_i;W_i)$ 之和。

上界以式 (1) 的最优随机独立集作乘积候选清单，用约 $2^{nI(X;W)}$ 个随机清单覆盖典型源串；每个清单是 OR 幂独立集。未被覆盖的低概率串可另加标志并直接描述，保证仍逐串正确，而其期望额外长度为 $o(n)$。这一步允许的是低概率的长描述，不是错误。

式 (3) 使用 OR 幂和平均长度；Witsenhausen 率公理库Witsenhausen 率Witsenhausen rate用强图幂的染色数定义严格零错误固定长描述率，证明极限存在，并显式构造五边形两字五色码及其精确渐近率。使用强幂和最坏固定长度。均匀五边形的两个值分别为 ${\log }_2(5/2)$ 与 ${\log }_2\sqrt{5}$，正好显示不能互换。