Энтропия свертки над гиперкубом

12

Скажем, у нас есть функция , такая, что x Z n 2 f ( x ) 2 = 1 (поэтому мы можем думать о { f ( x ) 2 } x Z n 2 как о распределении) , Естественно определить энтропию такой функции следующим образом: H ( f ) = - x Z n 2 f ( xf:Z2nRxZ2nf(x)2=1{f(x)2}xZ2n

H(f)=xZ2nf(x)2log(f(x)2).

Теперь рассмотрим свертку с самим собой: [ f f ] ( x ) = y Z n 2 f ( y ) f ( x + y ) . (Обратите внимание, что поскольку мы имеем дело с Z n 2 , то x + y = x - y )f

[ff](x)=yZ2nf(y)f(x+y).
Z2nx+y=xy

ffL2fC

H(ffff2)CH(f)

источник
Этот вопрос был опубликован в mathoverflow первого августа: mathoverflow.net/questions/103668/… (обычно это нормально для кросспоста с такой задержкой, но вы должны сказать, что делаете).
Колин МакКиллан
Извините, я не знал об этой политике.
Неравенство энтропийной мощности может быть полезно для вас: en.wikipedia.org/wiki/Entropy_power_inequality
Или Меир

Ответы:

9

Там нет такого . Определите помощью Cg:Z2nR

g(x1,,xn)={22n/3 if x1==xn=01 otherwise.

Тогда удовлетворяет gg

(gg)(x1,,xn)={24n/3+2n1 if x1==xn=022n/32+2n2 otherwise.

Пусть . Тогда есть (фактически оно экспоненциально мало по ), а примерно . Н ( е ) = Н ( г / | | г | | 2 ) О ( 1 ) п Н ( г * г / | | г * г | | 2 ) пf=g/g2H(f)=H(g/g2)o(1)nH(gg/gg2)n

Колин Маккуиллан
источник