Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm sorry for having open two questions which have been solved by elementary counter-examples provided by @AnthonyQuas. Actually I'm not an expert in information theory and I expected that a positive answer to these questions could be derived from a general Fano-like inequality. Now I'm convinced that there's no such a general answer to these questions, and then I'm focusing on the particular example in which I'm interested.

Let $(p_n)_{n \geq 0}$ be a sequence of numbers in $[0,1]$ with $p_0=1$. For every $n \geq 0$, let $X_n$ be a random variable distributed on $\{0, \ldots, n\}$ according to the law given by $$\Pr(X_n=0)=p_n \qquad \text{and } \quad \Pr(X_n=k)=(1-p_n)\cdots(1-p_{n-k+1})p_{n-k} \quad \text{for } 1 \leq k \leq n.$$

The dependence between the $X_n$ does not matter in my question below, and one can see $(X_n)$ as a Markov chain defined by $X_0 \equiv 0$ and by the Markov step
$$X_{n+1} = \begin{cases} 0 & \text{with probability } p_{n+1} \\ X_n + 1 & \text{with probability } 1- p_{n+1} \end{cases}.$$

It is easy to derive the following recursive relation about the entropy of $X_n$: $$H(X_{n+1}) = h(p_{n+1}) + (1-p_{n+1}) H(X_n),$$ which provides the formula $$H(X_n) = h(p_n) + (1-p_n)h(p_{n-1}) + (1-p_n)(1-p_{n-1})h(p_{n-2}) + \cdots + (1-p_n)\cdots(1-p_{2})h(p_{1}),$$ where $h(\theta)=-\theta \log(\theta) -(1-\theta)\log(1-\theta)$ is the entropy of a Bernoulli variate with parameter $\theta$.

Figures below show some examples of the law of $X_n$. For $p_n=\frac{1}{(n+1)^\alpha}$ with $\alpha > 1$:

alpha greater 1

For $p_n=\frac{1}{n+1}$, the law of $X_n$ is uniform:

alpha equal 1

For $p_n=\frac{1}{(n+1)^\alpha}$ with $0 < \alpha <1$:

enter image description here

Now let us assume $p_n \in ]0,1[$ for $n \geq 1$. Note that the above expression of $H(X_n)$ can be written $$H(X_n)=\mathbb{E}\left[\frac{h(p_{n-X_n})}{p_{n-X_n}}\right].$$ Moreover, let us assume $\boxed{\sum p_n = \infty}$ and $\boxed{p_n \to 0}$ (for instance when $p_n=\frac{1}{(n+1)^\alpha}$ with $0 < \alpha \leq 1$). By Borel-Cantelli's lemma, one has $\boxed{H(X_n) \to \infty}$.

Given any functions $g_n \{0, \ldots, n\} \to \{0, \ldots, n\}$, and setting $Y_n=g_n(X_n)$ and $\delta_n=\Pr\bigl(Y_n \neq X_n\bigr)$, I'm looking for an inequality such as $$\frac{H(X_n \mid Y_n)}{H(X_n)} \leq f(\delta_n) \qquad \text{for } n \text{ sufficiently large}$$ where $f$ is a positive function such that:

  1. $\limsup_{\delta \to 0} f(\delta) <1$,

  2. or, strongly, $\lim_{\delta \to 0} f(\delta) =0$.

More precisely I am interested in the case when $\boxed{\sum p_n = \infty}$ and $\boxed{\sum p_n^2 < \infty}$, for instance when $p_n=\frac{1}{(n+1)^\alpha}$ with $\frac12 < \alpha \leq 1$.

share|cite|improve this question
Hi @Stéphane. I'm pretty sure you can package the previous counterexamples to fit this framework. What I have in mind is taking a sequence $p_n$ that looks like $1/n$ for huge blocks, but very occasionally has medium size blocks of $n^{-2/3}$. If you choose a large $n$ and calculate the distribution, what you see will be approximately a uniform distribution, or a fast and very large drop in probability followed by a uniform distribution (depending where you start). In the second case, you should be back in the context of the previous counterexamples. – Anthony Quas Oct 14 '13 at 16:04
Héhé, do you want to watch your own idea: Thank you, I will try to think about this during the next days. – Stéphane Laurent Oct 14 '13 at 22:10
@AnthonyQuas I have reread your comment. Do you agree your proposal does not provide a distribution like the one you had in mind ? This gives a distribution with peaks, as shown in my link. This is easy to understand from the recurrence relation $\Pr(X_n=0)=p_n$ and $\Pr(X_n=k)=(1-p_n)\Pr(X_{n-1}=k)$ for $k\neq 0$. I have not found yet a candidate to a counter-example allowing easy calculations. – Stéphane Laurent Nov 9 '13 at 18:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.