Timeline for How to minimize $-\sum p_b \ln{p_b}$?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 15, 2014 at 6:31 | vote | accept | Simd | ||
| Apr 14, 2014 at 20:42 | comment | added | Bill Bradley | The construction I had in mind gives a value of $(1−\sqrt{q})\log(n)$. That is optimal from a "big O notation" perspective for fixed $q$, but maybe one could improve the constant. For $q=1/\sqrt{n}$, that would of course give a value of $2(1−\sqrt{q})\log(q)$. | |
| Apr 14, 2014 at 20:22 | comment | added | Simd | @BillBradley To make this explicit and aid my understanding, let's say $q= 1/\sqrt{n}$. What is the maximum in that case? | |
| Apr 14, 2014 at 20:18 | comment | added | Bill Bradley | If you ignore the $q$ constraint, you end up maximizing the entropy on a distribution on $n$ objects. This is maximized with a uniform distribution and a value of $-\sum p_b\log(p_b) =\log(n)$. Adding the $q$ constraint back in, the value can only get smaller. You can also construct explicit examples for a fixed value of $q$ and sufficiently large $n$ that achieve $O(\log(n))$. So the maximum is $\Theta(\log(n))$ for fixed $q$ as $n$ grows. | |
| Apr 14, 2014 at 18:24 | comment | added | Simd | Thank you! Under what conditions would $-\sum_{b \in B} p_b \ln{p_b}$ be maximized in this case? | |
| Apr 14, 2014 at 17:57 | history | answered | Tom Leinster | CC BY-SA 3.0 |