L'aumento di entropia del random walk

Question

Sia $ P $ un matrice di transizione di una passeggiata casuale in un non orientato (non può regolare) grafo $ G $. Sia $ \ pi $ essere una distribuzione su $ V (G) $. L'entropia di Shannon di $ \ pi $ è definito da

$$ H (\ pi) = -. \ Sum_ {v \ in V (G)} \ pi_v \ cdot \ log (\ pi_v) $$

Come si fa a dimostrare che $ H (P \ pi) \ ge H (\ pi) $?

Answer 1

Questo è anche vero? Si consideri un grafo non orientato, che è una stella. Che è, un vertice centrale $ V_0 $ è collegato a tutti gli altri vertici $ V_1, V_2, \ dots, V_ {n-1} $, e non ci sono altri bordi nel grafico. Quindi, se si inizia con una distribuzione uniforme su $ V_1, V_2, \ ldots, V_ {n-1} $, dopo un passo tutto il peso è sul vertice centrale $ V_0 $. Quindi, in un passo l'entropia è passato da $ \ log (n-1) $ a $ 0 $.