1
$\begingroup$

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)$ ?

1 Answers 1

1

$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.

http://en.wikipedia.org/wiki/Log_sum_inequality