Suppose that $A$ is a stochastic matrix. We know that if $A$ is doubly stochastic, then $H(Ap)\geq H(p)$ where $H$ is Shannon entropy and $p$ is a probability vector. Is the converse true? i.e., if $H(Ap)\geq H(p)$ then $A$ is doubly stochastic.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Consider any $n \times n$ left stochastic matrix $A$, i.e. each column sums up to $1$. We argue that if $H(Ap) \geq H(p)$ for all probability distributions $p$, then $A$ is doubly stochastic.
Take $p$ to be the uniform distribution. Then $H(Ap) \geq H(p)$ implies that $Ap = p$, since the uniform distribution on $[n]$ is the unique maximizer of Shannon entropy among all probability distributions on $[n]$.
Since $p = \frac{1}{n} 1$ (the all ones vector), we have that $A1 = 1$ -- all rows sum up to $1$. Thus, $A$ is doubly stochastic.
$\begingroup$
$\endgroup$
5
If expressed in terms of majorization of vectors, at least for finite dimensional probability vectors, I think it is known that (Horn's Lemma?) $q\prec p$ if and only if there is a doubly stochastic matrix $D$ with $q=Dp.$ Since permuting the entries does not change entropy this should do it.
-
$\begingroup$ I am sorry, I don't see how "this should do it". $\endgroup$ Oct 7, 2020 at 2:48
-
$\begingroup$ Thank you! Is it possible to introduce a reference including the proof of this lemma? $\endgroup$– AramOct 7, 2020 at 4:30
-
$\begingroup$ @IosifPinelis, I am having trouble substantiating my claim. I may delete it. What about the other answer? Do you think that's correct? $\endgroup$– kodluOct 8, 2020 at 3:35
-
2$\begingroup$ @kodlu : Yes, I think it's correct, except that "the uniform distribution on $[n]$ maximizes Shannon entropy among all probability distributions on $[n]$" should be replaced by "only the uniform distribution on $[n]$ maximizes Shannon entropy among all probability distributions on $[n]$". $\endgroup$ Oct 8, 2020 at 13:09
-