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

9

Скажем, у нас есть функция f:Z2nR такой, что

xZ2nf(x){12n,22n,,2n2n},
а также f является распределением, т. е. xZ2nf(x)=1,

Энтропия Шеннона f определяется следующим образом:

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

Позволять ϵбыть постоянным Скажем, мы получилиϵ-шумная версия f(x)т.е. мы получаем функцию f~:Z2nR такой, что |f~(x)f(x)|<ϵ для каждого xZ2n, Какое влияние шум оказывает на энтропию? То есть мы можем связатьH(f~) "разумной" функцией ϵ а также H(f), такие как:

(1ϵ)H(f)<H(f~)<(1+ϵ)H(f),
или даже,
(1ϵcn)dH(f)<H(f~)<(1+ϵcn)dH(f),
для некоторых констант c,d,

Редактировать: пытаясь почувствовать влияние шума на энтропию Шеннона, любую «разумную» добавку, связанную с H(f~) также было бы очень интересно.


источник

Ответы:

8

Такая граница не возможна. Рассмотрим случай, когдаf распределение, равномерное по некоторому набору S размера 2δn, и разреши f~ быть распределение, которое с вероятностью δ выводит равномерно распределенный элемент Sи в противном случае выводит равномерно распределенную строку.

Нетрудно понять, что вы можете получить от f в f~ вам нужен только шум максимум (1δ)2δn, Однако,H(f)=δn пока H(f~)(1δ+δ2)n, Таким образом, вы получаете разницу(1δ)2n для сколь угодно маленьких δ для чрезвычайно низкого уровня шума.

В частности, вы можете установить δ=log(1/ε)nи получить шум ε и разница энтропии n2log(1/ε),

Или меир
источник
1
Вы имеете в виду примерно ϵn, правильно? В любом случае, я думаю, что это может помочь спрашивающему ответить и о аддитивной границе, а не только о мутлипативной границе (я знаю, что он спрашивал конкретно о мультипликативной).
Дана Мошковиц
Спасибо за исправление. Я не знаю, каков ответ на аддитивную границу.
Или Меир
Спасибо за ответ Или! Безнадежно получить мультипликативную оценку функции с энтропией0, Однако как насчет функций с энтропией больше 0? Можно ли тогда получить такую ​​оценку?
@DanaMoshkovitz - случай аддитивной границы действительно очень актуален. Я добавлю это к вопросу. Спасибо за указание на это!
@OrMeir - Немного подправив ваш пример, вы получите функцию, которая противоречит первому типу мультипликативной границы, которую я просил (даже для функций с H(f)0), однако я не смог найти такой пример для второго типа мультипликативной границы, о которой я спрашивал (предполагая, H(f)0). Любые идеи?