Loading...
Please wait, while we are loading the content...
Similar Documents
Sumset and Inverse Sumset Theory for Shannon Entropy
| Content Provider | Scilit |
|---|---|
| Author | Tao, Terence |
| Copyright Year | 2010 |
| Description | Let G = (G, +) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A| is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that $H(X_{1}$ + $X_{2}$) = H(X) + O(1) when $X_{1}$, $X_{2}$ are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1).When G is torsion-free, we also establish the sharp lower bound $\Ent(X+X) \geq \Ent(X) + \frac{1}{2} \log 2 - o(1)$ , where o(1) goes to zero as H(X) → ∞. |
| Related Links | http://arxiv.org/pdf/0906.4387 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/FE527692AB523000CEA396D7C818794F/S0963548309990642a.pdf/div-class-title-sumset-and-inverse-sumset-theory-for-shannon-entropy-div.pdf |
| Ending Page | 639 |
| Page Count | 37 |
| Starting Page | 603 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548309990642 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 4 |
| Volume Number | 19 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2010-07-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Iterated Sumsets Ka Shannon Entropy H Discrete Random Variable X Inverse Sumset Theory Shannon Entropy Sumset Theory Finite Set Additive Group Small Doubling Random Variables X Sumsets a |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
