5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I am sorry, I don't see how "this should do it". $\endgroup$ Oct 7 '20 at 2:48
  • $\begingroup$ Thank you! Is it possible to introduce a reference including the proof of this lemma? $\endgroup$
    – Aram
    Oct 7 '20 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$
    – kodlu
    Oct 8 '20 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 '20 at 13:09
  • $\begingroup$ @IosifPinelis Thanks, corrected. :-) $\endgroup$ Oct 15 '20 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.