# Increasing entropy of random walk in regular graph

Let $P$ be a transition matrix of a random walk in an undirected 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)$ ?

-

$P\pi$ is the distribution after taking one step in the graph. Every element after $\pi$ goes through $P$ is a weighted sum of $\pi_i$ with a row of $P$. So you can express $P\pi$ as a vector with the following elements: $\sum_i p_{j,i} \pi_i$ for every row $j$ of $P$.
You can take this sum and substitute in the entropy of $H(P\pi)$, and use the Log sum inequality to get the relation you want.