7
$\begingroup$

Let $X_n$ be i.i.d with finite variance. Let $\bar X_n=\frac 1n \sum_{i=1}^nX_i$. It is a famous result that the continuous/differential entropy of the normalized average is non-decreasing. $$\mathrm H(\sqrt n\bar X_n)\leq \mathrm H(\sqrt{n+1}\bar X_{n+1})$$

This inequality suggests the sequence converges in distribution to the max entropy distribution subject to expectation and variance constraints, known to be the corresponding normal distribution. However, there is no strictness (indeed equality can occur if all the process is already Gaussian).

Question. What prevents this monotonic sequence of entropies from converging to a smaller limit than the maximal entropy?

Added. I would like to understand the intuition behind this fact, hopefully alongside a proof sketch.

$\endgroup$
5
  • $\begingroup$ Do you have a reference to the monotonicity? Also, how is the (differential entropy?) $\mathrm H$ defined (say for non-absolutely continuous distributions)? $\endgroup$ Commented Nov 27, 2022 at 0:39
  • $\begingroup$ The normal distribution maximizes the entropy subject to constraints that specify the expectation and the variance. That any such constraints are considered is completely camouflaged by your way of stating the "famous result". Can you rephrase it to be clear about that? $\endgroup$ Commented Nov 27, 2022 at 2:30
  • 1
    $\begingroup$ @MichaelHardy better? $\endgroup$
    – Arrow
    Commented Nov 27, 2022 at 17:27
  • 1
    $\begingroup$ Hm. So your question is about the fact (1) Xn converges to something that maximizes entropy, but you want a fundamentally different answer than the pair of facts (2) Xn converges to a Gaussian and (3) Gaussians maximize entropy. Seems hard to disentangle. $\endgroup$
    – usul
    Commented Nov 27, 2022 at 21:28
  • 1
    $\begingroup$ @usul I was under the impression the entropic line of reasoning uses monotonicity, your (3), and some argument about the "gap", and combines them to prove convergence to a Gaussian. I'm asking about the "gap" argument. $\endgroup$
    – Arrow
    Commented Nov 28, 2022 at 7:10

1 Answer 1

2
$\begingroup$

$\newcommand{\de}{\delta}\newcommand{\al}{\alpha}\newcommand{\be}{\beta}\newcommand{\R}{\mathbb R}\newcommand{\vpi}{\varphi} $Without loss of generality, the variance of $X_1$ is $1$. Let $H:=\mathrm H$, which let us assume to denote the differential entropy, so that $H(X)=\int_{\mathbb R} f(x)\ln\frac1{f(x)}\,dx$ for a random variable $X$ with pdf $f$.

If the pdf of $X_1$ is bounded or, more generally, the pdf of $\bar X_k$ is bounded for some natural $k$, then, by a local limit theorem (see e.g. Theorem 7 in Section 2 of Chapter VII), the pdf (say $f_n$) of $\sqrt n\,\bar X_n$ converges uniformly on $\R$ to the standard normal pdf (say $\vpi$) as $n\to\infty$. Note that $\vpi\le1/\sqrt{2\pi}<1$. So, for all large enough $n$ we have $f_n\le1$ and hence $f_n\ln\frac1{f_n}\ge0$. So, by Fatou's lemma, \begin{equation*} \liminf_{n\to\infty}H(\sqrt n\,\bar X_n)=\liminf_{n\to\infty}\int_\R f_n\ln\frac1{f_n} \ge\int_\R \vpi\ln\frac1\vpi=H(Z) \end{equation*} if $Z\sim N(0,1)$. On the other hand, $H(\sqrt n\,\bar X_n)\le H(Z)$ for all $n$, since the variance of $\sqrt n\,\bar X_n$ is $1$ and $Z$ maximizes the differential entropy among all absolutely continuous random variables with variance $1$. So, \begin{equation*} \lim_{n\to\infty}H(\sqrt n\,\bar X_n)=H(Z). \tag{1}\label{1} \end{equation*}


Without the condition that the pdf of $\bar X_k$ be bounded for some natural $k$, the conclusion \eqref{1} can fail to hold, in a rather dramatic manner.

An example when $H(\sqrt n\,\bar X_n)=-\infty$ for all $n$, so that \eqref{1} fails to hold, is given by the formula \begin{equation*} f=\frac1s\,\sum_{k\ge1}c_k\,1_{[x_k,3x_k/2]} \end{equation*} for the pdf of $X_1$, where $s:=\sum_{k\ge1}c_k x_k/2=\pi^2/12$, $c_k:=e^{2^k}/k^2$ and $x_k:=e^{-2^k}$; of course, in this example the pdf of $\bar X_k$ is not bounded for any natural $k$.

The main idea here is that the pdf (say $f_n$) of $Y_n:=\sqrt n\,\bar X_n$ may remain very large in (say) a neighborhood of $0$, so much so that $H(Y_n)=\int f_n\ln\frac1{f_n}=-\infty$.

Details on this example: Let $\de_k:=x_k/2$. Consider the class $G$ of all pdf's $g$ such that \begin{equation*} g\ge\sum_{j\ge1}a_j\,1_{[u_j,u_j+\de_j]}, \tag{2}\label{2} \end{equation*} where \begin{equation*} a_j:=\frac{C_1}{j^p\,\de_j}\quad\text{and}\quad u_j:=\frac{\al x_j}2 \tag{3}\label{3} \end{equation*} for some real $C_1>0$, some real $p>0$, some real $\al\ge1$, and all $j\ge1$.

Clearly, \eqref{1} implies that $f\in G$. Moreover, the pdf's in the class $G$ are very lacunary, which allows us to control the convolutions of any two pdf's in $G$.

More specifically, let us show that -- crucially -- the class $G$ is closed w.r. to the convolution:

Take any $g\in G$, so that \eqref{2} and \eqref{3} hold, and then take any $h\in G$, so that \begin{equation*} h\ge\sum_{j\ge1}b_j\,1_{[v_j,v_j+\de_j]}, %\tag{2a}\label{2a} \end{equation*} where \begin{equation*} b_j:=\frac{C_2}{j^q\,\de_j}\quad\text{and}\quad v_j:=\frac{\be x_j}2 %\tag{3a}\label{3a} \end{equation*} for some real $C_2>0$, some real $q>0$, some real $\be\ge1$, and all $j\ge1$.
Note that $1_{[u_j,u_j+\de_j]}*1_{[v_j,v_j+\de_j]}\ge\frac12\,1_{[w_j,w_j+\de_j]}$, where $w_j:=\frac{(\al+\be+1) x_j}2$. So, \begin{equation*} g*h\ge\sum_{j\ge1}d_j\,1_{[w_j,w_j+\de_j]}, \end{equation*} where $d_j:=a_jb_j\de_j=\frac{C_1C_2/2}{j^{p+q}\de_j}$. Thus, indeed the class $G$ is closed w.r. to the convolution.

So, to complete the consideration of the example, it remains to show that \begin{equation*} H(g):=-\int_\R g\ln g=-\infty \tag{4}\label{4} \end{equation*} for any $g$ such that \eqref{2} and \eqref{3} hold. Take indeed any such $g$. Clearly, for some natural $j_p$ and all natural $j\ge j_p$ we have $a_j\ge1$ and hence $g\ge1$ on the interval $[u_j,u_j+\de_j]$. Also, the intervals $[u_j,u_j+\de_j]$ are pairwise disjoint. Also, $t\ln t$ is increasing in $t\ge1$. It follows that \begin{equation*} \int_\R g\ln g\,1(g\ge1)\ge \sum_{j\ge j_p}a_j\,\de_j\,\ln a_j =\sum_{j\ge j_p}\frac{C_1}{j^p}\,\ln\frac{2C_1}{j^p\,e^{-2^j}}=\infty. \tag{5}\label{5} \end{equation*} On the other hand, $t\ln t\ge-1/e$ for all real $t>0$. So, \begin{equation*} \int_\R g\ln g\,1(g<1)\ge-\frac1e\, \int_{[0,u_1+\de_1]}1>-\infty. \tag{6}\label{6} \end{equation*}

Now \eqref{4} follows from \eqref{5} and \eqref{6}. $\quad\Box$

$\endgroup$
6
  • 1
    $\begingroup$ Thanks for the answer! I edited the question to emphasize I am really interested in some intuition. Any chance for some spoonfeeding? :) $\endgroup$
    – Arrow
    Commented Nov 27, 2022 at 17:28
  • $\begingroup$ @Arrow : Intuition was not even mentioned in your original post. Anyhow, the intuition behind the example is that the pdf (say $f_n$) of $\sqrt n\,\bar X_n$ may remain very large in (say) a neighborhood of $0$, even for large $n$, so large in fact that $H(f_n)=\int f_n\ln\frac1{f_n}=-\infty$ for all $n$. Is this "spoonfeeding" enough? $\endgroup$ Commented Nov 27, 2022 at 17:59
  • 1
    $\begingroup$ @Arrow : As for the "positive" part of the answer, the answer to the question "What prevents this monotonic sequence of entropies from converging to a smaller limit than the maximal entropy?" is quite transparent from the above answer: If the pdf of $X_1$ is bounded or, more generally, the pdf of $\bar X_k$ is bounded for some natural $k$, then it is a local limit theorem and Fatou's lemma that prevent this monotonic sequence of entropies from converging to a smaller limit than the maximal entropy. $\endgroup$ Commented Nov 27, 2022 at 18:08
  • $\begingroup$ this moves my question to the local limit theorem - intuitively, why is it true? I'm trying to understand "why" there is no gap in the convergence. $\endgroup$
    – Arrow
    Commented Nov 28, 2022 at 7:08
  • 1
    $\begingroup$ @Arrow : The standard proofs of a local limit theorem (LLT) (when it holds) are by the Fourier method. Indeed, the characteristic function (c.f.) of the random variable (r.v.) $Y_n:=\sqrt n\,\bar X_n$ (assuming $X_1=0$ and $EX_1^2=1$) is of the form $\psi_n(t)=(1-t^2/(2n)(1+o(1)))^n$, which converges to $\psi(t)=e^{-t^2/2}$ as $n\to\infty$, and $\psi$ is the standard normal c.f. It remains to invert this convergence, which is the harder part. I don't know if this explanation satisfies your intuition, but I think there hardly is a better one. $\endgroup$ Commented Nov 28, 2022 at 14:36

You must log in to answer this question.

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