随机步行的熵增加

Question

让$ p $成为无方向性随机步行的过渡矩阵 （可能不定期） 图$ g $。令$ pi $为$ v（g）$上的发行版。 $ pi $的香农熵由

$ h（ pi）= - sum_ {v in v（g）} pi_v cdot log（ pi_v）。$$

我们如何证明$ h（p pi） ge H（ pi）$？

Answer 1

这是真的吗？考虑一个无方向的图形，这是恒星。也就是说，中央顶点$ v_0 $已连接到所有其他顶点$ v_1，v_2， dots，v_ {n-1} $，并且图中没有其他边缘。然后，如果您以$ v_1，v_2， ldots，v_ {n-1} $的平等分配开始，则一步之后，所有权重都在中央顶点$ v_0 $上。因此，在一个步骤中，熵从$ log（n-1）$变成$ 0 $。