Aumento de la entropía de caminata aleatoria

Question

Sea $ P $ una matriz de transición de una caminata aleatoria en una (puede que no sea regular) Gráfico $ G $. Deje que $ pi $ sea una distribución en $ V (g) $. La entropía Shannon de $ pi $ se define por

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

¿Cómo demostramos que $ h (p pi) ge h ( pi) $?

Answer 1

¿Es esto incluso cierto? Considere un gráfico no dirigido que es una estrella. Es decir, un vértice central $ V_0 $ está conectado a todos los demás vértices $ V_1, V_2, DOTS, V_ {N-1} $, y no hay otros bordes en el gráfico. Luego, si comienza con una distribución igual en $ v_1, v_2, ldots, v_ {n-1} $, después de un paso, todo el peso está en el vértice central $ v_0 $. Entonces, en un paso, la entropía ha pasado de $ log (N-1) $ a $ 0 $.