Infinite Divisibility of Information
Cheuk Ting Li · IEEE Transactions on Information Theory · 2021
We study an information analogue of infinitely divisible probability distributions, where the i.i.d. sum is replaced by the joint distribution of an i.i.d. sequence. A random variable$X$is called informationally infinitely divisible if, for any$n\ge 1$, there exists an i.i.d. sequence of random variables$Z_{1},\ldots,Z_{n}$that contains the same information as$X$, i.e., there exists an injective function$f$such that$X=f(Z_{1},\ldots,Z_{n})$. While there does not exist such informationally infinitely divisible discrete random variable, we show that any discrete random variable$X$can be divided into arbitrarily many identical pieces with a multiplicative penalty to the entropy, that is, if we remove the injectivity requirement on$f$, then there exists i.i.d.$Z_{1},\ldots,Z_{n}$and$f$satisfying$X=f(Z_{1},\ldots,Z_{n})$, and the entropy satisfies$H(X)/n\le H(Z_{1})\le 1.59H(X)/n+2.43$bits. Furthermore, we study the case where$X=(Y_{1},\ldots,Y_{m})$is itself an i.i.d. sequence,$m\ge 2$, for which the multiplicative gap 1.59 can be replaced by$1+5\sqrt {(\log m)/m}$. This means that as$m$increases,$(Y_{1},\ldots,Y_{m})$becomes closer to being spectral infinitely divisible in a uniform manner. This can be regarded as an information analogue of Kolmogorov’s uniform theorem. Applications of our result include independent component analysis and distributed storage with a secrecy constraint.