# Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $$p =(p_1,...p_n)$$, $$p_i>0$$, $$\sum p_i = 1$$ and a matrix $$M_{ij}$$, which is doubly stochastic: $$\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$$.

Question 1 Just apply matrix M to a vector $$p$$ , i.e. $$q = Mp$$ (i.e. $$q_i = \sum_j M_{ij} p_j$$) is it true that entropy of new vector $$q$$ is greater then of original vector $$p$$ ? I.e.

$$H(q) = -\sum_i q_i ln(q_i) > -\sum_i p_i ln(p_i) = H(p)$$

Question 2 Is there a simple proof of it ? (It might follow from the Gibb's inequality, but it does not seem obvious for me).

Question 3 What are generalizations, in view of meta-principle "entropy always grows" that might be an example of some more general phenomena ?

Motivation: There is a meta-principle that entropy grows is some natural systems, matrix applied to a vector is probably the most simple system one can consider (Markov chain), so the question above arises. After some thinking one can restrict from all matrices to doubly stochastic, because $$M^n v$$ tends to a uniform distribution (which has maximal entropy of all) only for doubly stochastic $$M$$ , so it cannot be true for general $$M$$.

This is a particular case of the following general principle. On the one hand, a bistochastic matrix $$M$$ has the property that for every non-negative vector (say, a probability vector), $$Mp\succ p$$. On another hand, the order $$\succ$$ can be defined by $$x\succ y$$ iff $$\sum_if(x_i)\le\sum_if(y_i)$$ for every convex function $$f$$.

Now, use the fact that $$f=-H$$ is convex.

For proofs, see my book Matrices (Springer-Verlag GTM #216, second edition) at sections 6.5 (Proposition 6.4) and 8.5 (Theorem 8.5).

Edit (at Alexander's request.) Let $$\alpha\ne1$$ be a positive parameter. The Renyi entropy is $$\frac1{1-\alpha}\log\sum_jp_j^\alpha.$$ The map $$p\mapsto Mp$$ does increase Renyi entropy. Proof: if $$\alpha>1$$, the map $$t\mapsto t^\alpha$$ is convex, and $$s\mapsto\frac1{1-\alpha}\log s$$ is increasing. If instead $$\alpha<1$$, the map $$t\mapsto t^\alpha$$ is concave, and $$s\mapsto\frac1{1-\alpha}\log s$$ is decreasing.

• Thank you. That seems to cover Renyi entropy also, is not it? – Alexander Chervov Dec 1 '18 at 19:32
• @AlexanderChervov. Yes, see my edit. – Denis Serre Dec 2 '18 at 7:23
• Thank you ! I should buy your book ))) – Alexander Chervov Dec 11 '18 at 19:04
• @AlexanderChervov. It is concise, and stands at the graduate level at every chapter but the two first. Visit also my web page perso.ens-lyon.fr/serre/DPF/exobis.pdf with 469 exercises (up today) which display additional material. – Denis Serre Dec 11 '18 at 19:27
• Great collection of exercises ! I sent you a mail may be you add some from that... – Alexander Chervov Dec 11 '18 at 20:04

This is a particular case of a well-known monotonicity property of the Kullback-Leibler divergence $$D(\cdot\|\cdot)$$. Namely, if $$\alpha$$ and $$\beta$$ are any two distributions on the same (say, finite) space $$X$$, and $$P$$ is a Markov operator on $$X$$, then $$D(\alpha\|\beta) \ge D(\alpha P\|\beta P) \;.$$ In your case double stochasticity of $$P$$ means that its stationary distribution is the uniform distribution $$m_X$$ on $$X$$, whereas $$D(\alpha \| m_X) = \log \text{card} X - H(\alpha) \;.$$

The answer to Question 1 is yes as long as $$p$$ is not the uniform distribution $$(\frac{1}{n},\frac{1}{n},\ldots,\frac{1}{n})$$.

The proof (Question 2) is quite simple:

Recall from the Birkhoff–von Neumann theorem that every doubly stochastic matrix $$M$$ is a convex combination of permutation matrices. We can interpret this as saying that there is a distribution $$\theta$$ on the set of all permutations of $$A:=\{1,2,\ldots,n\}$$ such that whenever $$\mathbf{x}$$ is a random variable from $$A$$ and $$\pmb{\pi}$$ is a random permutation of $$A$$ with distribution $$\theta$$ independent of $$\mathbf{x}$$, and we set $$\mathbf{y}:=\pmb{\pi}(\mathbf{x})$$, then we have \begin{align} \mathbb{P}(\mathbf{y}=i\,|\,\mathbf{x}=j) &= M_{i,j} \;. \end{align} Note that if $$\mathbf{x}$$ is distributed as $$p$$, then $$\mathbf{y}$$ is distributed as $$q:=Mp$$, so $$H(\mathbf{x})=H(p)$$ and $$H(\mathbf{y})=H(q)$$.

Now, \begin{align} H(\mathbf{y},\pmb{\pi}) &= H(\mathbf{y}) + H(\pmb{\pi}\,|\,\mathbf{y}) \;, \\ H(\mathbf{y},\pmb{\pi}) &= H(\pmb{\pi}) + \underbrace{H(\mathbf{y}\,|\,\pmb{\pi})}_{H(\mathbf{x})} \;, \end{align} which implies \begin{align} H(\mathbf{y}) &= H(\mathbf{x}) + H(\pmb{\pi}) - H(\pmb{\pi}\,|\,\mathbf{y}) \\ &= H(\mathbf{x}) + I(\mathbf{y};\pmb{\pi}) \end{align} where $$I(\mathbf{y};\pmb{\pi})$$ is the mutual information between $$\mathbf{y}$$ and $$\pmb{\pi}$$. We know that $$I(\mathbf{y};\pmb{\pi})\geq 0$$ with equality if and only if $$\mathbf{y}$$ and $$\pmb{\pi}$$ are independent, which is the case if and only if $$\mathbf{x}$$ has the uniform distribution. Q.E.D.

For Question 3, suppose that $$M$$ is merely a positive stochastic matrix (not doubly stochastic). Let $$r$$ denote the unique stationary distribution of $$M$$. Then we have a similar entropy increase'' principle if we replace entropy with (minus) the Kullback-Leibler divergence relative to $$r$$. There is a nice discussion on this in the book of Cover and Thomas.

This is true, except that we have equality when $$p$$ is the uniform distribution, which is the limit distribution of your matrix. (Proof in here, 15.5, for example.)

Whenever $$p_i\geq 1/n$$, it is not so hard to show that $$q_i\leq p_i$$, and when $$p_i\leq 1/n$$, we have $$q_i\geq p_i$$. From there, it follows that $$-\sum_i p_i \ln (q_i) \leq -\sum_i q_i \ln (q_i)$$, and this gives the result combined with Gibbs'.