# Discrete entropy of the integer part of a random variable

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 $$$$H(\lfloor X \rfloor) = - \sum_{n\in\mathbb{Z}} \mathbb{P}( \lfloor X \rfloor = n ) \log( \mathbb{P}( \lfloor X \rfloor = n ) ),$$$$ 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.

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. For $$n\in S_2$$ such that $$n\ge n_0$$, $$-\log p_n<2\log n, 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).

• What are some examples of distributions where the entropy is not well-defined?
– user44143
Aug 4, 2020 at 10:53
• That's a cute trick effectively, for a neat proof. Thanks! Aug 4, 2020 at 23:21
• @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. Aug 5, 2020 at 1:20

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

$$\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.

• 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?
– user44143
Aug 4, 2020 at 16:28
• @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".
– Mark
Aug 4, 2020 at 16:57
• @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? Aug 4, 2020 at 17:30
• 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.
– R W
Aug 4, 2020 at 22:57
• @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. Aug 5, 2020 at 0:03