Auf der Entropie einer Summe

12

Ich bin für eine Schranke für die Entropie H(X+Y) aus der Summe zweier unabhängiger diskreten Zufallsvariablen X und Y . Natürlich ist

H(X+Y)H(X)+H(Y)      ()
. Bezogen auf die Summe von n unabhängigen Bernoulli-Zufallsvariablen Z1,,Zn ergibt sich jedoch
H(Z1+Z2++Zn)nH(Z1)
Mit anderen Worten, die Grenze wächst linear mitn wenn sie wiederholt angewendet wird. JedochZ1+Zn wird auf einem Satz von unterstützten Größen , also seine Entropie höchstenslogn . InTat, durch den zentralen Grenzwertsatz, ich nehmedass da es im Wesentlichen auf einer Menge von Größe √ unterstützt wirdH(Z1++Zn)(1/2)logn .n

Kurz gesagt, die Schranke überschreitet in dieser Situation um einiges. Durch Durchsuchen dieses Blogposts erfahre ich, dass alle Arten von Grenzen für H ( X + Y ) möglich sind. Gibt es eine Grenze, die die richtigen Asymptoten (oder zumindest vernünftigere Asymptoten) ergibt, wenn sie wiederholt auf die Summe der Bernoulli-Zufallsvariablen angewendet werden?()H(X+Y)

Robinson
quelle
2
Ich bin nicht sicher, was Sie wirklich fragen. Wenn Sie eine Obergrenze für H (X + Y) in Bezug auf H (X) und H (Y) wünschen, die auf zwei unabhängige diskrete Zufallsvariablen X und Y anwendbar ist, dann gilt H (X + Y) ≤ H (X) ) + H (Y) ist eindeutig das Beste, was Sie bekommen können; Betrachten Sie den Fall, in dem die Summen x + y alle verschieden sind, wenn x über der Unterstützung von X und y über der Unterstützung von Y liegt. Wenn Sie diese allgemeine Grenze auf einen sehr speziellen Fall anwenden, erhalten Sie natürlich eine sehr lose gebunden.
Tsuyoshi Ito
1
@TsuyoshiIto - Nun, eine Möglichkeit für eine Antwort, die großartig wäre, ist eine Ungleichung wie wobei die Terme nach dem Minus in dem von Ihnen beschriebenen Fall Null sind und addieren, um eine bessere Skalierung mit n im Fall einer Summe von Bernoulli-Zufallsvariablen zu ergeben ...H(X+Y)H(X)+H(Y)n
robinson
1
... es scheint mir, dass die Existenz von Ungleichungen wie es zumindest plausibel macht, dass die von mir gesuchte Antwort existiert . H(X+Y)3H(XY)H(X)H(Y)
Robinson
2
Das heißt, Sie suchen nach einer Obergrenze für H (X + Y) in Bezug auf H (X) und H (Y) . Bitte bearbeiten Sie die Frage.
Tsuyoshi Ito
1
Ich denke, in dem Fall, in dem die Varianz von jedem im Vergleich zu n klein ist, ist Ihre Vermutung die richtige Antwort, und es ist nicht schwer, mit dem Berry-Esseen-TheoremZin
Sasho Nikolov

Antworten:

19

Bei solchen Fragen bekommt man oft die richtige Intuition, wenn man an "flache" Zufallsvariablen denkt. Stellen Sie sich als die gleichmäßige Verteilung über eine Menge A vorXA der Größe und der Y als die gleichmäßige Verteilung über einen Satz B der Größe 2 H ( Y ) .2H(X)YB2H(Y)

Also, die Frage Sie fragen , ist (grob gesagt) , was können Sie über die Größe sagen im Vergleich zu | A | und | B | . Im Allgemeinen (z. B. wenn es sich um zufällige Mengen handelte) haben Sie in der Tat | A + B | | A | | B | was H ( X + Y ) H ( X ) + H ( Y ) entspricht .|A+B||A||B||A+B||A||B|H(X+Y)H(X)+H(Y)

Es gibt einige Sonderfälle, wenn vor allem, wenn A und B Intervalle sind (oder allgemeiner arithmetische Folgen). Es gibt einige Ergebnisse, die besagen, dass (zumindest unter bestimmten Bedingungen und wenn | A + B | fast so klein ist, wie es sein kann) dies der einzige Fall ist. Der Bereich, in dem solche Fragen untersucht werden, ist als "additive Kombinatorik" bekannt, und einige Ergebnisse haben den Geschmack, der in einer Gruppe ( G , + ) auftritt , wenn | A +|A+B||A||B|AB|A+B|(G,+) dann sind A , B ungefähr Untergruppen von G (wie Sie in Ihrer Frage erwähnt haben, werden in Terence Taos Blog einige solche Ergebnisse erörtert; im Allgemeinen können Ergebnisse mit festgelegter Größe auf die Entropieeinstellung übertragen werden).|A+B|=O(|A|+|B|)A,BG

Der von Ihnen beschriebene Fall entspricht in etwa dem Fall, in dem ein ganzzahliges Intervall ist [ a . . b ] und B eine ganze Zahl Intervall der Form [ 0 .. c ] (in der Tat, wenn nicht versuchen , den Vorteil der Konzentration und für eine shoot zu nehmen ( 1 / 2 ) log n Entropiecodierung gebunden, müsste man c = 1 und a = 0 und b = k für k = 1 , . . .A[a..b]B[0..c](1/2)lognc=1a=0b=kk=1,...,n1akkbk+k|A+B||A|+c

Boaz Barak
quelle
5

I believe this paper by Harremoes proves that if you take a sum of n Bernoulli random variables Z1,Z2,...,Zn, each with parameter p then then entropy of Z1+Z2+...+Zn is less that the entropy of a Poisson distribution with the mean np. From a quick look at Wikipedia, it seems that for large values of np the entropy of a Poisson is 12logn+O(logn), which is what you expect.

VSJ
quelle
0

Maybe you could use the Equation:

H(Z1+Z2++Zn)=H(Z1)+H(Z2)++H(Zn)H(Z1|Z1+Z2++Zn)H(Z2|Z2+Z3++Zn)H(Zn1|Zn1+Zn)

This would look like a term you mentioned in the comments, unfortunately i don't know of results about the cardinality of the negative terms or insightful bounds on them.

Rick
quelle