# Estimating entropy conditional to an event

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)}$.

• 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$. – 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$).