# Increasing entropy of random walk

Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by

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

How do we prove that $H(P\pi)\ge H(\pi)$ ?

-
cross-posted:math.stackexchange.com/questions/243298/… –  A.Schulz Nov 23 '12 at 17:50

Is this even true? Consider an undirected graph which is a star. That is, a central vertex $V_0$ is connected to all other vertices $V_1, V_2, \dots, V_{n-1}$, and there are no other edges in the graph. Then, if you start with an equal distribution on $V_1, V_2, \ldots, V_{n-1}$, after one step all the weight is on the central vertex $V_0$. So in one step the entropy has gone from $\log (n-1)$ to $0$.

-
Thank you. It turns out that if a graph is regular, then we can prove it. –  eig Nov 24 '12 at 10:03
Indeed. Section 4.4 of Elements of Information Theory, by Cover and Thomas, has this theorem as well as several generalizations that also cover the case of non-regular graphs. –  Peter Shor Nov 24 '12 at 14:53