Infinite Divisibility of Information

We study an information analogue of infinitely divisible probability distributions, where the 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\geq 1$, there exists an i.i.d. sequence $Z_{1}, \ldots, Z_{n}$ containing 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 $H(X)/n\leq H(Z_{1})\leq 1.59H(X)/n+2.43$. Applications include independent component analysis, distributed storage with a secrecy constraint, and distributed random number generation.

I. Introduction

This paper seeks to answer the following question: can a piece of information be divided into arbitrarily many pieces? Is information infinitely divisible, like space and time? To answer this question, we first review the concept of infinite divisibility in probability theory.