Infinite Divisibility of Information
Lists
Only you see this
Abstract
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> is called informationally infinitely divisible if, for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n\geq 1$</tex> , there exists an i.i.d. sequence <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Z_{1}, \ldots, Z_{n}$</tex> containing the same information as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> , i.e., there exists an injective function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X=f(Z_{1},\ldots, Z_{n})$</tex> . While there does not exist such informationally infinitely divisible discrete random variable, we show that any discrete random variable <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> can be divided into arbitrarily many identical pieces with a multiplicative penalty to the entropy, that is, if we remove the injectivity requirement on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> , then there exists i.i.d. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Z_{1}, \ldots, Z_{n}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> satisfying <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X=f(Z_{1},\ldots, Z_{n})$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$H(X)/n\leq H(Z_{1})\leq 1.59H(X)/n+2.43$</tex> . Applications include independent component analysis, distributed storage with a secrecy constraint, and distributed random number generation.
BibTeX
@article{li2022infinite,
author = {Cheuk Ting Li},
title = {{Infinite Divisibility of Information}},
journal = {IEEE Trans. Information Theory},
year = {2022},
url = {https://openreview.net/forum?id=lmMUelJhxw},
}Loading related content...