Об энтропии суммы

12

Ищу ограничение на энтропии суммы двух независимых дискретных случайных величин и . Естественно, Однако применительно к сумме независимых бернуллиевских случайных величин это дает Другими словами, граница увеличивается линейно с при многократном применении. Однако поддерживается для набора размера , поэтому его энтропия не больше . На самом деле, по центральной предельной теореме, я предполагаю, чтоX Y H ( X + Y ) H ( X ) + H ( Y ) ( ) n Z 1 , , Z n H ( Z 1 + Z 2 + + Z n ) n H ( Z 1 ) n Z 1 + ZH(X+Y)XY

H(X+Y)H(X)+H(Y)      ()
nZ1,,Zn
H(Z1+Z2++Zn)nH(Z1)
nZ1+ZnnlognH(Z1++Zn)(1/2)logn так как он по существу поддерживается на наборе размера .n

Короче говоря, граница в этой ситуации значительно превышает. Просматривая этот пост в блоге , я понял, что возможны все виды границ ; есть ли граница, которая дает правильную асимптотику (или, по крайней мере, более разумную асимптотику) при многократном применении к сумме случайных величин Бернулли?()H(X+Y)

Robinson
источник
2
Я не уверен, что вы действительно спрашиваете. Если вы хотите получить верхнюю оценку H (X + Y) в терминах H (X) и H (Y), которая применима к любым двум независимым дискретным случайным величинам X и Y, то H (X + Y) ≤H (X) ) + H (Y) явно лучшее, что вы можете получить; рассмотрим случай, когда суммы x + y различны, когда x лежит в области поддержки X, а y - в области поддержки Y. Если вы примените эту общую оценку к очень особому случаю, то естественно, что вы получите очень свободная связь.
Tsuyoshi Ito
1
@TsuyoshiIto - хорошо, одна возможность для ответа, который был бы отличным, - это неравенство типа где слагаемые после минуса равны нулю в случае, если вы описать и сложить, чтобы дать лучшее масштабирование с в случае суммы случайных величин Бернулли ...H(X+Y)H(X)+H(Y)n
Робинсон
1
... мне кажется, что существование неравенств, подобных делает хотя бы правдоподобным ответ, который я ищу, существует. H(X+Y)3H(XY)H(X)H(Y)
Робинсон
2
Это означает, что то, что вы ищете, не является верхней границей H (X + Y) в терминах H (X) и H (Y) . Пожалуйста, отредактируйте вопрос.
Tsuyoshi Ito
1
я думаю, что в случае, когда дисперсия каждого мала по сравнению с ваше предположение является правильным ответом, и его нетрудно уточнить, используя теорему Берри-Эссеена нZin
Сашо Николов

Ответы:

19

XA2H(X)YB2H(Y)

|A+B||A||B||A+B||A||B|H(X+Y)H(X)+H(Y)

|A+B||A||B|AB|A+B|(G,+)|A+B|=O(|A|+|B|)A,BG

A[a..b]B[0..c](1/2)lognc=1a=0b=kk=1,...,n1akkbk+k|A+B||A|+c

Боаз Барак
источник
5

nZ1,Z2,...,ZnpZ1+Z2+...+Znnpnp12logn+O(logn)

VSJ
источник
0

Может быть, вы могли бы использовать уравнение:

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

Это выглядело бы как термин, который вы упомянули в комментариях, к сожалению, я не знаю результатов о количестве отрицательных терминов или глубоких границах для них.

стог
источник