10
$\begingroup$

Let $X$ be a real valued random variable. Of course, the integer part $\lfloor X \rfloor$ of $X$ is a discrete random variable taking values in $\mathbb{Z}$. We can therefore define its discrete entropy \begin{equation} H(\lfloor X \rfloor) = - \sum_{n\in\mathbb{Z}} \mathbb{P}( \lfloor X \rfloor = n ) \log( \mathbb{P}( \lfloor X \rfloor = n ) ), \end{equation} which is in $[0,\infty]$ as a sum of nonnegative terms, since $- x \log x \geq 0$ for any $0 \leq x \leq 1$ (with the convention $0\log 0 = 0$).

I am looking for sufficient conditions such that $H(\lfloor X \rfloor ) < \infty$. For instance, is it sufficient to know that $X$ has a finite absolute moment $\mathbb{E}[|X|^p] < \infty$ for some $p>0$? Any condition of this type, possibly weaker, is welcome.

Motivation: There are strong connection between the differential entropy of $X$ (assuming $X$ has a pdf whose differential entropy is well-defined) and the discrete entropy of $\lfloor nX \rfloor$ when $n\rightarrow0$. This was the main topic of the 1959 paper from Alfred Rényi intitled On the dimension and entropy of probability distributions: I am questioning the assumptions under which the discrete entropy is well-defined.

$\endgroup$
0

3 Answers 3

7
$\begingroup$

Since $\lfloor X\rfloor$ has finite entropy if and only if $|\lfloor X\rfloor|$ has finite entropy, it suffices to consider random variables taking values in the natural numbers. Write $p_n$ for $\mathbb P(X=n)$ (so that $\sum_n p_n=1$). We have $X\in L^q$ if and only if $\sum p_n n^q<\infty$.

Suppose $X\in L^q$ so that $\sum p_n n^q<\infty$. Then let $S_1=\{n\colon p_n<\frac{1}{n^2}\}$ and $S_2=\{n\colon p_n\ge \frac 1{n^2}\}$. We have $$ H(X)=\sum_n -p_n\log p_n=-\sum_{n\in S_1}p_n\log p_n-\sum_{n\in S_2}p_n\log p_n. $$ Since $-t\log t$ is increasing on $[0,\frac 1e]$, the first sum is bounded above by $$ \sum_{n\in S_1}\frac{2\log n}{n^2}<\infty. $$ There exists an $n_0$ so that for $n\ge n_0$, $2\log n<n^q$. For $n\in S_2$ such that $n\ge n_0$, $-\log p_n<2\log n<n^q$, so that $$ -\sum_{n\in S_2,\,n\ge n_0}p_n\log p_n\le \sum_{n\in S_2,\,n\ge n_0}p_n n^q<\infty. $$ Hence $H(X)<\infty$. (This trick appears in a couple of papers of mine: one with Ciprian Demeter in NYJM and another more recent preprint with Tamara Kucherenko and Christian Wolf).

$\endgroup$
3
  • $\begingroup$ What are some examples of distributions where the entropy is not well-defined? $\endgroup$
    – user44143
    Aug 4, 2020 at 10:53
  • $\begingroup$ That's a cute trick effectively, for a neat proof. Thanks! $\endgroup$
    – Goulifet
    Aug 4, 2020 at 23:21
  • 2
    $\begingroup$ @MattF: are you asking for examples where the entropy is infinite? My go-to example is $P(X=n)=c/[n(\log n)^2]$ for $n\ge2$ and with suitable normalization. $\endgroup$ Aug 5, 2020 at 1:20
11
$\begingroup$

Using (say) decimal notation, ASCII encoding, and a delimiter symbol such as a space or comma, as well as the law of large numbers, one can almost surely encode $N$ independent copies of $\lfloor X \rfloor$ using $O( N {\bf E} \log( 2 + |X| ) ) + o(N)$ bits. Applying the Shannon source coding theorem, we conclude that

$$ {\bf H}( \lfloor X \rfloor ) \ll {\bf E} \log(2 + |X| )$$

which by Jensen's inequality also gives

$$ {\bf H}( \lfloor X \rfloor ) \ll_p \log(2 + {\bf E} |X|^p)$$

for any $0 < p < \infty$.

$\endgroup$
8
$\begingroup$

$\newcommand{\fx}{\lfloor X\rfloor}$ $\newcommand\Z{\mathbb{Z}}$ We shall prove more than requested: that $H(\fx)<\infty$ if $E\ln(1+|X|)<\infty$.

Indeed, let $$p_n:=P(\fx=n),$$ so that $$H(\fx)=-\sum_{n\in\Z}p_n\ln p_n.$$ Let $q\colon\mathbb R\to(0,\infty)$ be any function such that $$\sum_{n\in\Z}q(n)=1\tag{1}$$ and $$q(x)\le cq(\lfloor x\rfloor)\tag{2}$$ for some real $c>0$ and all real $x$.

Then by the Gibbs inequality for the Kullback–Leibler divergence between $(p_n)_{n\in\Z}$ and $(q(n))_{n\in\Z}$ we have $$0\le KL((p_n)_{n\in\Z}||(q(n))_{n\in\Z})=\sum_{n\in\Z}p_n\ln\frac{p_n}{q(n)}=-H(\fx)+\sum_{n\in\Z}p_n\ln\frac1{q(n)},$$ whence, in view of (2), $$H(\fx)\le\sum_{n\in\Z}p_n\ln\frac1{q(n)} \\ =\sum_{n\in\Z}\int_{[n,n+1)}P(X\in dx)\ln\frac1{q(n)} \\ \le\sum_{n\in\Z}\int_{[n,n+1)}P(X\in dx)\ln\frac c{q(x)} \\ =E\ln\frac c{q(X)}=\ln c+E\ln\frac1{q(X)}.$$ So, $$H(\fx)<\infty\quad\text{if}\quad E\ln\frac1{q(X)}<\infty.$$ Taking here e.g. $q(x)=\frac C{(1+|x|)^2}$, where $C:=1/\sum_{n\in\Z}\frac1{(1+|x|)^2}[=\frac3{\pi ^2-3}]$, we have conditions (1) and (2) satisfied. So, $$H(\lfloor X\rfloor)<\infty\quad\text{if}\quad E\ln(1+|X|)<\infty.$$ It follows that for any real $a>0$ $$H(\lfloor X\rfloor)<\infty\quad\text{if}\quad E|X|^a<\infty,$$ as was initially desired.

$\endgroup$
7
  • $\begingroup$ Is there any variable $X$ for which the $\alpha$-moment is undefined for all $\alpha>0$? Or does this imply that the entropy is in fact finite for all variables? $\endgroup$
    – user44143
    Aug 4, 2020 at 16:28
  • $\begingroup$ @MattF. If you restrict $\alpha$ to integers the answer is yes (Cauchy distribution). If you allow for fractional moments then this paper makes the answer seem to be "no". $\endgroup$ Aug 4, 2020 at 16:57
  • 1
    $\begingroup$ @MattF. : If e.g. a random variable $X$ has the pdf $f$ given by $f(x)=\frac1{2|x|\ln^2|x|}\,1\{|x|>e\}$, then $EX_+^a=EX_-^a=\infty$ for all $a>0$, where $X_+:=\max(0,X)$ and $X_-:=\max(0,-X)$. Is this what your question is about? $\endgroup$ Aug 4, 2020 at 17:30
  • $\begingroup$ Very nice. The question about the finiteness of the entropy for measures on $\mathbb Z$ with a finite logarithmic moment is more or less equivalent to that about the measures with a finite first moment on the set of words in a finite alphabet (which naturally arises in symbolic dynamics). The standard argument in the literature is the one quoted by Anthony - which I have always found somewhat artificial. $\endgroup$
    – R W
    Aug 4, 2020 at 22:57
  • 1
    $\begingroup$ @Goulifet : The Kullback--Leibler divergence is well-defined (and nonnegative), because $p_n\ln\frac{p_n}{q_n}\ge p_n-q_n$ and $\sum_n(p_n-q_n)=0$, where $q_n:=q(n)$. Cf. en.wikipedia.org/wiki/… and en.wikipedia.org/wiki/Gibbs%27_inequality. $\endgroup$ Aug 5, 2020 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.