  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\ge1$, 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 informationally infinitely divisible discrete random
variable, we show that any discrete random variable $X$ has a bounded
multiplicative gap to infinite divisibility, 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})\le1.59H(X)/n+2.43$. We also study a new class of discrete
probability distributions, called spectral infinitely divisible distributions,
where we can remove the multiplicative gap $1.59$. Furthermore, we study the
case where $X=(Y_{1},\ldots,Y_{m})$ is itself an i.i.d. sequence, $m\ge2$, 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, distributed storage with a
secrecy constraint, and distributed random number generation.
