Auf der Entropie einer Summe

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) \leq H (X) + H (Y) (*)

$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$ . Bezogen auf die Summe von

n

$n$ unabhängigen Bernoulli-Zufallsvariablen

Z_{1}, \dots, Z_{n}

$Z_1, \ldots, Z_n$ ergibt sich jedoch

H (Z_{1} + Z_{2} + \dots + Z_{n}) \leq n H (Z_{1})

$H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1)$ Mit anderen Worten, die Grenze wächst linear mit

n

$n$ wenn sie wiederholt angewendet wird. Jedoch

Z_{1} + \dots Z_{n}

$Z_1 + \cdots Z_n$ wird auf einem Satz von unterstützten Größe

n

$n$ , also seine Entropie höchstens

\log n

$\log n$ . InTat, durch den zentralen Grenzwertsatz, ich nehmedass

da es im Wesentlichen auf einer Menge von Größe

H (Z_{1} + \dots + Z_{n}) \approx (1 / 2) \log n

$H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$

\sqrt{n}

$\sqrt{n}$

Kurz gesagt, die Schranke überschreitet in dieser Situation um einiges. Durch Durchsuchen dieses Blogposts erfahre ich, dass alle Arten von Grenzen für 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)$

it.information-theory shannon-entropy Robinson
quelle

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

@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

im Fall einer Summe von Bernoulli-Zufallsvariablen zu ergeben ...

H (X + Y) \leq H (X) + H (Y) - \dots

$H(X+Y) \leq H(X) + H(Y) - \ldots$

n

$n$

robinson

... es scheint mir, dass die Existenz von Ungleichungen wie

es zumindest plausibel macht, dass die von mir gesuchte Antwort existiert .

H (X + Y) \leq 3 H (X - Y) - H (X) - H (Y)

$H(X+Y) \leq 3 H(X-Y) - H(X) - H(Y)$

Robinson

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

Ich denke, in dem Fall, in dem die Varianz von jedem

im Vergleich zu

klein ist, ist Ihre Vermutung die richtige Antwort, und es ist nicht schwer, mit dem Berry-Esseen-Theorem

Z_{i}

$Z_i$

n

$n$

Sasho Nikolov

Antworten:

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 $X$ $A$ der Größe und der als die gleichmäßige Verteilung über einen Satz der Größe . $2^{H(X)}$ $Y$ $B$ $2^{H(Y)}$

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

Es gibt einige Sonderfälle, wenn vor allem, wenn und Intervalle sind (oder allgemeiner arithmetische Folgen). Es gibt einige Ergebnisse, die besagen, dass (zumindest unter bestimmten Bedingungen und wenn 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 wenn $|A+B| \ll |A|\cdot |B|$ $A$ $B$ $|A+B|$ $(G,+)$ dann sind ungefähr Untergruppen von (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,B$ $G$

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

Boaz Barak
quelle

I believe this paper by Harremoes proves that if you take a sum of $n$ Bernoulli random variables $Z_1,Z_2,...,Z_n$ , each with parameter $p$ then then entropy of $Z_1+Z_2+...+Z_n$ 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 $\frac{1}{2}\log n + O(\log n)$ , which is what you expect.

VSJ
quelle

Maybe you could use the Equation:

H (Z_{1} + Z_{2} + \dots + Z_{n}) = H (Z_{1}) + H (Z_{2}) + \dots + H (Z_{n}) - H (Z_{1} | Z_{1} + Z_{2} + \dots + Z_{n}) - H (Z_{2} | Z_{2} + Z_{3} + \dots + Z_{n}) - \dots - H (Z_{n - 1} | Z_{n - 1} + Z_{n})

$H(Z_1+Z_2+\cdots+Z_n)=H(Z_1)+H(Z_2)+\cdots+H(Z_n)-H(Z_1|Z_1+Z_2+\cdots+Z_n)-H(Z_2|Z_2+Z_3+\cdots+Z_n)-\cdots-H(Z_{n-1}|Z_{n-1}+Z_n)$

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