L'augmentation de l'entropie de marche aléatoire

Question

Soit $ P $ une matrice de transition d'une marche aléatoire dans un undirected (ne peut pas régulière) graphique $ G $. Soit $ \ pi $ soit une distribution sur V $ (G) $. L'entropie de Shannon de $ \ pi $ est défini par

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

Comment prouvez-nous que $ H (P \ pi) \ ge H (\ pi) $?

Answer 1

Est-ce même vrai? Considérons un graphe non orienté qui est une étoile. C'est un sommet central $ V_0 $ est relié à tous les autres sommets V_1 $, V_2, \ points, V_ {n-1} $, et il n'y a pas d'autres bords dans le graphique. Ensuite, si vous commencez avec une répartition égale sur $ V_1, V_2, \ ldots, V_ {n-1} $, après une étape tout le poids est sur le sommet central V_0 $ de $. Ainsi, en une seule étape l'entropie est passée de $ \ log (n-1) $ à 0 $.