Take for example the measure $\mu(n)=n^2$ on $\{1, \ldots, N\}$ and a random variable $X$ distributed according to the probability obtained by normalizing $\mu$.

Does there exists a constant $K>0$ such that $H(X \mid X \in C) \leq K.H(X)$ for every subset $C \subset \{1, \ldots, N\}$ and every $N$ ?

I know how to prove that $H(X \mid X >n) \leq H(X)$ as well as $H(X \mid X <n) \leq H(X)$ for every $n$, and I am under the impression (intuitively) that the equality $H(X \mid X \in C) \leq H(X)$ should be more or less true for every $C$, and should be asymptotically true for large $N$.

But $H(X \mid X \in C) \leq K.H(X)$ would be enough for my goal, and I really don't know how to get such a $K$. I think this should be more generally true for $\mu(n)=f(n)$ for a class of convex functions $f$, but I would already be happy to know how to deal with the $n^2$ example.


For $\mu(n)=n^2$, a quick calculation (*) gives $H(X)\ge (1-\mathcal o(1))\log N$. On the other hand, a probability carried by a finite set $C$ has entropy at most $\log |C|$ (entropy of the equiprobable measure), so that $H(X|X\in C)\leq\log N$. This should be enough for your inequality, with $K\to 1$ for large $N$.

(*) Let $a(N)=\sum_1^N n^2=(2N^3+3N^2+N)/6$. By definition, $H(X)=\sum_1^N \frac{n^2}{a(N)}\log\frac{a(N)}{n^2}=\log a(N)-\frac2{a(N)}\sum_1^N n^2\log n$.

Now, majorize $\sum_1^N n^2\log n$ : as $x^2\log x$ is increasing on $[1,\infty)$, you have $\sum_1^N n^2\log n\le\int_1^{N+1}x^2\log x\ dx$.

But $x^2\log x$ is the derivative of $\frac{x^3}{3}\log x-\frac{x^3}{9}$, so that $\int_1^{N+1}x^2\log x\ dx=\frac{(N+1)^3}{3}\log(N+1)-\frac{(N+1)^3}{9}+\frac19$.

Finally $H(X)\ge\log a(N)-\frac{2(N+1)^3}{3a(N)}\log(N+1)+\frac{2(N^3+3N^2+3N)}{9a(N)}$.

  • $\begingroup$ Thank you. I missed this asymptotic estimate of $H(X)$. Did you get it by comparing to an integral ? I'm suspecting the same result holds whenever $\mu(n)/\mu(1:n)$ has speed $1/n$. $\endgroup$ – Stéphane Laurent Sep 29 '15 at 18:39

Here is a proof which works for a large class of measures $\mu$, including the example $\mu(n)=(n+1)^2$ of the OP. I only consider measures whose support is $\mathbb{N}=\{0, 1, \ldots\}$.

As noted by @JeanDuchon, it suffices to show that $H(X_n) = \Omega(\log n)$ (with the Big-Omega notation).

The key formula: For any random variable $X$ supported by $\{0, \ldots, n\}$, it can be shown that $$ \boxed{H(X) = \mathbb{E}\left[\dfrac{h(p_X)}{p_X}\right]} $$ where $h(p)=-p\log p -(1-p)\log(1-p)$ and $\boxed{p_k=\dfrac{\Pr(X=k)}{\Pr(X \leq k)}}$ ($(p_k)$ is called the reversed hazard rate in some papers).

I discovered this elementary but useful formula a couple of years ago. Some details are currently given on my blog (in French) and I will soon deposit a preprint or a working paper about that. I would find surprising that nobody discovered this formula before me, but oddly, I have not been able to find it in the literature.

As a consequence, given a measure $\mu$ supported by $\mathbb{N}$, the entropy of a random variable $X_n \sim \mu( \cdot \mid 0:n)$ can be written $$ H(X_n) = \mathbb{E}\left[\frac{h(p_{X_n})}{p_{X_n}}\right] $$ where $\boxed{p_k=\dfrac{\mu(k)}{\mu(0:k)}}$.

Consider the case $\mu(n) = (n+1)^2$. Then the $p_n$ (derived by @JeanDuchon) are decreasing. Since the function $h(x)/x$ is decreasing, $$H(X_n) = \mathbb{E}\left[\frac{h(p_{X_n})}{p_{X_n}}\right] > \dfrac{h(p_K)}{p_K}\Pr(X_n >K) > -\log p_K \Pr(X_n >K).$$

Moreover $-\log p_n = \Omega(\log n)$. Taking $K=[n/2]$, $$H(X_n) > -\frac{1}{2}\log p_{[n/2]} = \Omega(\log n),$$ the desired result.

This proof more generally works for $\mu(n)$ increasing in $n$, having decreasing $p_n$ (or even something weaker) and such that $-\log p_n = \Omega(\log n)$. With my (current) terminology, this implies that such a measure $\mu$ has full entropy. Roughly speaking, that means that for large $n$, you cannot approximate $X_n$ by a random variable having form $f(X_n)$ and having entropy lower than $H(X_n)$. I can also derive $H(X_n) \sim \log n$ from these investigations.

As a side note, this claim in my OP:

I know how to prove that $H(X \mid X >n) \leq H(X)$ as well as $H(X \mid X <n) \leq H(X)$ for every $n$

is also shown with the help of the integral represententation $H(X_n) = \mathbb{E}\left[\frac{h(p_{X_n})}{p_{X_n}}\right]$ (it follows from this equality and from the monotonicity of the $p_n$).


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.