On the entropy growth of sums of iid discrete random variables

Riccardo Castellano, Pavel Sekatski · 2025

Read On the entropy growth of sums of iid discrete random variables by Riccardo Castellano, Pavel Sekatski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05348.txt.

Introduction

Riccardo Castellano and Pavel Sekatski tackle a question in information theory in 2025: how fast does randomness grow when many copies of the same random draw are added up? They measure randomness with Shannon entropy, the standard score for how unpredictable a value is. Their result gives a floor for that growth as the number of copies climbs.

The floor rests on a new quantity they name the incommensurability rank of the draw. When the rank is one, older results for grid like draws already apply, and their proof builds on those known cases plus the entropy of the multinomial spread. The bound needs no appeal to the central limit theorems that many proofs in this area rely on. It gives a clean rule for a broad class of discrete draws.

Catalog record

CREATORRiccardo Castellano, Pavel Sekatski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05348

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the entropy growth of sums of iid discrete random variables Riccardo Castellano, Pavel Sekatski Abstract We derive an asymptotic lower bound on the Shannon entropy H H of sums of N N arbitrary iid discrete random variables. The derived bound H ≥ r ⁡ ( X ) 2 ​ log ⁡ ( N ) + 𝑐𝑠𝑡 H\geq\frac{r(X)}{2}\log(N)+{\it cst} is given in terms of the incommensurability rank r ⁡ ( X ) r(X) of the random variable – a positive integer quantity that we introduce. The derivation does not rely on central limit theorems, but builds upon the known expressions of the asymptotic entropy of the multinomial distribution and sums of iid lattice random variables, which correspond to the case r ⁡ ( X ) = 1 r(X)=1 . I Introduction and background Let \{X_{i}\}_{i\in\mathbb{N}} be a sequence of independent and identically distributed (iid) random variables that take values in a countable subset of real numbers \chi\subset\mathbb{R} , and have a finite variance {\rm Var}(X) . We are interested to lower bound the Shannon entropy H of the sum T_{N}:=\underset{i=1}{\overset{N}{\sum}}X_{i} with an expression of the form H(T_{N})\geq\frac{r(\chi)}{2}\log(N\lambda(X))+o(1). (1) Historically, it is the case of continuos random variables that attracted more attention Linnik 1959 ; Barron 1986 ; Artstein et al. 2004 ; Madiman and Barron 2007 . Here, it is the differential Shannon entropy h(T_{N})\to\frac{1}{2}\log(N)+\frac{1}{2}\log(2\pi e {\rm Var}(X)) that converges Barron 1986 to that of a Gaussian random variable from below Artstein et al. 2004 ; Madiman and Barron 2007 . In the case of discrete random variables, T_{N} is supported on a discrete set, which plays a crucial role for the calculation of the Shannon entropy H(T_{N}) . A bound of the form ( 1 ) is known for the particular case of lattice random variables, which we now define. Definition 1 . X is a lattice random variable , if it takes values in a lattice set \chi , i.e. such that \displaystyle\chi\subset\big\{h\,n+a:n\in\mathbb{Z}\big\} (2) for some h,a\in\mathbb{R} . The maximal span h(X)=h(\chi) is the largest real number h for which Eq. ( 2 ) can be fulfilled. Notice that random variables that only take one or two values ( |\chi|\leq 2 ) are always a lattice. Theorem 2 . Gavalakis and Kontoyiannis 2024 ; Takano 1987 Let X be a lattice random variable. Then in the N\rightarrow\infty limit H(T_{N})=\frac{1}{2}\log(N)+\frac{1}{2}\log(2\pi e \frac{{\rm Var}(X)}{h(\chi)^{2}})+o(1). (3) Upon a shift by a and a rescaling by \frac{1}{h} , irrelevant for the entropy, the values of a lattice random variable are integer n_{i}\in\mathds{Z} . Intuitively, if \chi is not an affine transformation of a set of integers, but contains numbers that are somehow incommensurable , there can only be fewer different combinations of outcomes that sum up to the same value of T_{N} , making the entropy H(T_{N}) larger. The goal of this paper is to formalize this intuition and derive a generalized version of Theorem 2 that applies for all discrete random variables. As a last preliminary result we recall that the asymptotic entropy of a multinomial distribution has a simple expression. Theorem 3 . Kaji 2015 Let \bm{n}(N,\bm{p})\in\mathbb{N}^{d} be a multinomial random variable describing N trials with d different outcomes of probabilities \bm{p}:=(p_{1},..p_{d}) . In the large N limit its entropy is given by \displaystyle H(\bm{n}(N,\bm{p}))=\frac{d-1}{2}\log(2\pi e N \sqrt[d-1]{p_{1}..p_{d}})+o(1) (4) II Incommensurable partitions and the first generalization First, we need to define some notion of “incommensurability” of the set of values \chi of the random variables X_{i} , which would quantify how far we are from the case of a lattice random variable. Consider a partition of a set \chi=\underset{j=1}{\overset{k}{\bigcup}}\chi_{j} into k disjoint subsets \{\chi_{j}\}_{j=1..k} . For each of these sets let \mathcal{S}_{m}(\chi_{j}):=\left\{\sum_{x_{i}\in\chi_{j}}n_{i}x_{i}:n_{i}\in\mathbb{N},\sum_{i}n_{i}=m\right\} (5) be the set of numbers that can be obtained by summing m , not necessarily different, numbers from \chi_{j} . For convenience we also introduce the following notation \mathbb{N}^{k}_{N}:=\left\{\bm{n}\in\mathbb{N}^{k}:\sum_{i=1}^{k}n_{i}=N\right\}, (6) for the set of natural k -vectors \bm{n} whose elements sum up to N (with 0\in\mathbb{N} ). With its help, we define the following property. Definition 4 . A collection of disjoint sets \{\chi_{j}\}_{j=1..k} of real numbers (e.g. a partition of \chi ) is called incommensurable (or k -incommensurable) if 1. All \chi_{j} are non-empty and \chi_{j}\neq\{0\} . 2. For all N\in\mathbb{N} , \bm{m},\bm{n}\in\mathbb{N}^{k}_{N} and {\bm{y}}=(y_{1},\dots,y_{k}) , {\bm{y}}^{\prime}=(y_{1}^{\prime},\dots,y_{k}^{\prime}) with y_{j}\in S_{m_{j}}(\chi_{j}) and y_{j}^{\prime}\in\mathcal{S}_{n_{j}}(\chi_{j}) we have \sum_{j=1}^{k}y_{j}=\sum_{j=1}^{k}y_{j}^{\prime}\implies y_{j}=y_{j}^{\prime}\quad\forall j\in[1..k]. (7) In words, for a random variable X taking values in \chi , which admits a k - incommensurable partition, any possible value T_{N}=t can be uniquely decomposed as t=y_{1}+\dots+y_{k} , where each y_{j} is a sum of numbers sampled from \chi_{j} and there are N sampled numbers in total. This property implies a bijection between the outcome of T_{N} and the k outcomes of the following random variables Y_{j}^{(N)}:=\underset{i=1}{\overset{N}{\sum}}X_{i}\,\mathbf{1}_{\chi_{j}}(X_{i}),\qquad\text{where}\qquad\mathbf{1}_{\chi_{j}}(x)=\begin{cases}1&x\in\chi_{j}\\ 0&\text{otherwise}\end{cases} (8) are indicator functions verifying if X_{i} takes value in \chi_{j} , and each Y_{j}^{(N)} only sums the values drawn from \chi_{j} . Some examples and observations on how to construct an incommensurable partition of \chi can be found in App. A . In all of the examples the sets \chi admit incommensurable partitions in sets \chi_{j} which are lattices. For such cases, the entropy of T_{N} can be bounded with the help theorems 2 and 3 , indeed we now prove the following bound. Theorem 5 . Let X_{1},\dots,X_{N} be a collection of iid discrete random variables taking values in the set \chi , which admits an k -incommensurable partition \{\chi_{j}\}_{j=1,\dots,k} , with p_{j}={\rm Pr}(X_{i}\in\chi_{j}) , and such that each \chi_{j} is a lattice, and \chi_{1},\dots\chi_{s} are the only sets with a single element. Then, the following bounds hold \displaystyle s=k:\,\,H\left(\sum_{i=1}^{N}X_{i}\right) \displaystyle=\frac{k-1}{2}\log\left(2\pi eN\sqrt[k-1]{p_{1}p_{2}..p_{k}}\right)+o(1) (9) \displaystyle s\leq k-1:\,\,H\left(\sum_{i=1}^{N}X_{i}\right) \displaystyle\geq\frac{k}{2}\log(2\pi e N)+\frac{1}{2}\log\left(p_{1}\dots p_{s}(1-\sum_{j=1}^{s}p_{j})\right)+\sum_{j=s+1}^{k}\frac{1}{2}\log( p_j \frac{{\rm Var}(\tilde X^{(j)})}{h(\chi_j)^{2}})+o(1) (10) \displaystyle s\leq k-2:\,\,H\left(\sum_{i=1}^{N}X_{i}\right) \displaystyle\leq\frac{k+(k-s-1)}{2}\log(2\pi e N)+\frac{1}{2}\log\left(p_{1}\dots p_{s}(1-\sum_{j=1}^{s}p_{j})\right) \displaystyle+\sum_{j=s+1}^{k}\frac{1}{2}\log( p_j^2 \frac{{\rm Var}(\tilde X^{(j)})}{h(\chi_j)^{2}})+o(1) (11) where the conditional random variables \tilde{X}^{(j)} have probability distribution fixed as {\rm Pr}(\tilde{X}^{(j)}=x)={\rm Pr}(X=x|X\in\chi_{j}) and h(\chi_{j}) is the maximal span of \chi_{j} . In addition, for s=k-1 the expression ( 10 ) is an equality. Proof. Consider the following random variables \displaystyle n_{N}^{(j)}:=\sum_{i=1}^{N}\mathbf{1}_{\chi_{j}}(X_{i})\qquad\text{with}\qquad\bm{1}_{\chi_{j}}(x)=\begin{cases}1&x\in\chi_{j}\\ 0&x\notin\chi_{j}\end{cases} (12) \displaystyle Y_{N}^{(j)}:=\sum_{i=1}^{N}X_{i}\,\mathbf{1}_{\chi_{j}}(X_{i}) (13) where n_{N}^{(j)} counts the number of times the variables X_{i} took values in each set \chi_{j} , and Y_{N}^{(j)} is the sum of these values, with T_{N}=\underset{i=1}{\overset{N}{\sum}}X_{i}=\underset{j=1}{\overset{k}{\sum}}Y_{N}^{(j)} . Since the sets \chi_{j} are incommensurable, we known that each value T_{N}=t admits a unique decomposition t=\underset{j}{\sum}y_{j} as a sum of values of the variable Y_{N}^{(j)} . Hence, there is a bijection between the random variable T_{N} and the vector of random variables \bm{Y}_{N}=(Y_{N}^{(1)},\dots,Y_{N}^{(k)}) , implying H(T_{N})=H(\bm{Y}_{N}). (14) Recall that only the first s\leq k sets \chi_{j} contain a single element x_{j}\neq 0 (by definition 4 ). These sets are special, as for them the identity Y_{N}^{(j)}=x_{j}n_{N}^{(j)} gives a bijection between Y_{N}^{(j)} and n_{N}^{(j)} . Using the chain rule we can thus write \displaystyle H(\bm{Y}_{N}) \displaystyle=H(Y_{N}^{(1)},\dots,Y_{N}^{(s)})+H(Y_{N}^{(s+1)},\dots,Y_{N}^{(k)}|Y_{N}^{(1)},\dots,Y_{N}^{(s)}) (15) \displaystyle=H(n_{N}^{(1)},\dots,n_{N}^{(s)})+H(Y_{N}^{(s+1)},\dots,Y_{N}^{(k)}|n_{N}^{(1)},\dots,n_{N}^{(s)}). (16) Here, the first term H(n_{N}^{(1)},\dots,n_{N}^{(s)}) can be readily computed. To do so we will distinguish two cases. For s=k=|\chi| , we have n_{N}^{(1)}+\dots+n_{N}^{(s)}=N and the vector (n_{N}^{(1)},\dots,n_{N}^{(s)}) follows a multinomial distribution with s=k=|\chi| outcomes of probabilities p_{1},\dots p_{s} . By Theorem 3 we find H(\bm{Y}_{N})=H(n_{N}^{(1)},\dots,n_{N}^{(s)})=\frac{k-1}{2}\log\left(2\pi eN\sqrt[k-1]{p_{1}p_{2}..p_{k}}\right)+o(1) (17) proving the theorem for the special case. For s<k , n_{N}^{(1)}+\dots+n_{N}^{(s)}\neq N in general and the

Read the complete text