1
$\begingroup$

Say you have positive $\{a_i\}_{i=1}^n$ and you have $p_i=\frac{a_i}{\sum_{i=1}^na_i}$, then assume you have a $C$ such that $C<2a_n\ll\sum_{i=1}^na_i$ (that is $C$ is not very large), then define $q_i=\frac{a_i}{C+\sum_{i=1}^na_i}$ and $q_{n+1}=\frac{C}{C+\sum_{i=1}^na_i}$. Does Shannon entropy of $q$ dominate entropy of $p$?

Take $C=a_n+\log_2^ka_n$ for any fixed $k$. Now does Shannon entropy of $q$ dominate entropy of $p$ after certain $n$?

There are two cases to consider. Case $(1)$ $a_{i+1}=a_i+O(\log^ka_i)$ Case $(2)$ $a_{i+1}=a_i+O(a_i)$.

When can one expect Shannon entropy to be dominant in sequences of these types? Clearly in this post Entropy dominance, one criteria for negative result is given.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I'll show that Yes, if you rule out an event of sufficiently small probability then the entropy decreases.

I'll change the notation around a bit so that my $p_1,\dots,p_n$ correspond to your $q_{n+1},\dots,q_1$.

Suppose $\sum_{i=1}^n p_i=1$ and we are given that the event corresponding to $p_1$ did not occur. Then the new probability of the event corresponding to $p_k$, $k\ne 1$, is $$ \hat p_k = \frac{p_k}{1-p_1}. $$ So the new entropy $H(\hat p)$ is (where $S(p)=-\log_2(p)$ and $q$ is the experiment that only determines whether $p_1$ occurs) $$ \sum_{k=2}^n S\left(\frac{p_k}{1-p_1}\right)\frac{p_k}{1-p_1} = \frac1{1-p_1}\sum_{k=2}^n [S(p_k)-S(1-p_1)]{p_k} $$ $$ = \frac1{1-p_1}\left(\sum_{k=2}^n S(p_k)p_k - (1-p_1)S(1-p_1)\right) = \frac1{1-p_1}\left(H(p) - S(p_1)p_1 - (1-p_1)S(1-p_1)\right) $$ $$ = \frac1{1-p_1}\left(H(p) - H(q)\right) \le H(p)\quad\text{(as we want) iff } $$ $$ \frac{H(q)}{p_1}\ge H(p). $$ The function $p_1\mapsto H(q)/p_1$ is $$ p_1\mapsto -\log_2(p_1) - \frac{1-p_1}{p_1}\log_2(1-p_1) $$ which goes to infinity as $p_1\rightarrow 0$, whereas $H(p)$ is bounded by $\log_2 n $, so it is enough to take $p_1\le 1/n$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The following property also seems true. If $m+1\leq n$, then let $p$ correspond to $\{a_i\}_{i=1}^{m}$, $q$ correspond to $\{a_i\}_{i=1}^{m+1}$, $r$ correspond to $\{a_i\}_{i=1}^{n}$ and $s$ correspond to $\{a_i\}_{i=1}^{n+1}$ where $a_i$ satisfy properties above. Is it true that, $H(q)-H(p)>H(s)-H(r)$? Should I formulate another question. $\endgroup$
    – Turbo
    Commented Dec 24, 2014 at 11:35
  • $\begingroup$ Sure you can formulate another one, maybe make sure to write something about what the difficulty seems to be $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Dec 24, 2014 at 16:01
  • $\begingroup$ The difficulty seems to be because if you add two variables that are close enough, the entropy may not noticeably change to be always strictly increasing. That is my intuition on these finite sequence artificial probability distribution. However I cannot rule out the fact that may be we can make the entropy strictly increasing by adding new variables somehow so that the variables $a_i$ do not converge to any limit. It would be interesting design sequences that diverge whose entropy is strictly increasing while the increase becomes smaller as $n$ increases. Thought that would be interesting. $\endgroup$
    – Turbo
    Commented Dec 24, 2014 at 17:09
  • $\begingroup$ added mathoverflow.net/questions/191438/… $\endgroup$
    – Turbo
    Commented Dec 24, 2014 at 22:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .