Erhöhte Entropie des Zufallsspaziergangs

Question

Sei $ p $ eine Übergangsmatrix eines zufälligen Spaziergangs in einem ungerichteten (darf nicht regelmäßig) Graph $ g $. Sei $ pi $ eine Verteilung auf $ v (g) $. Die Shannon -Entropie von $ pi $ wird durch definiert von

$$ H ( pi) =- sum_ {v in v (g)} pi_v cdot log ( pi_v). $$

Wie beweisen wir, dass $ h (p pi) ge H ( pi) $?

Answer 1

Ist das überhaupt wahr? Betrachten Sie eine ungerichtete Grafik, die ein Stern ist. Das heißt, ein zentraler Scheitelpunkt $ v_0 $ ist mit allen anderen Scheitelpunkten $ v_1, v_2, dots, v_ {n-1} $ verbunden, und es gibt keine anderen Kanten im Diagramm. Wenn Sie dann mit einer gleichen Verteilung auf $ v_1, v_2, ldots, v_ {n-1} $ beginnen, liegt das gesamte Gewicht auf dem zentralen Vertex $ v_0 $. In einem Schritt ist die Entropie von $ log (n-1) bis $ 0 $ gestiegen.