Неравенство пинскеров - Википедия - Pinskers inequality

В теория информации, Неравенство Пинскера, названный в честь своего изобретателя Марк Семенович Пинскер, является неравенство что ограничивает общее расстояние вариации (или статистическое расстояние) с точки зрения Дивергенция Кульбака – Лейблера.Неравенство жестко до постоянных факторов.^[1]

Официальное заявление

Неравенство Пинскера утверждает, что если ${ displaystyle P}$ и ${ displaystyle Q}$ два распределения вероятностей на измеримое пространство ${ Displaystyle (Х, Sigma)}$, тогда

${ displaystyle delta (P, Q) leq { sqrt {{ frac {1} {2}} D _ { mathrm {KL}} (P | Q)}},}$

куда

${ displaystyle delta (P, Q) = sup { bigl {} | P (A) -Q (A) | { big |} A in Sigma { text {- измеримое событие}} { bigr }}}$

это общее расстояние вариации (или статистическое расстояние) между ${ displaystyle P}$ и ${ displaystyle Q}$ и

${ Displaystyle D _ { mathrm {KL}} (P | Q) = operatorname {E} _ {P} left ( log { frac { mathrm {d} P} { mathrm {d} Q }} right) = int _ {X} left ( log { frac { mathrm {d} P} { mathrm {d} Q}} right) , mathrm {d} P}$

это Дивергенция Кульбака – Лейблера в нац. Когда пространство образца ${ displaystyle X}$ - конечное множество, расходимость Кульбака – Лейблера задается формулой

${ Displaystyle D _ { mathrm {KL}} (P | Q) = sum _ {i in X} left ( log { frac {P (i)} {Q (i)}} right )Число Пи)!}$

Обратите внимание, что с точки зрения общая норма вариации ${ displaystyle | P-Q |}$ из подписанная мера ${ Displaystyle P-Q}$, Неравенство Пинскера отличается от приведенного выше в два раза:

${ displaystyle | P-Q | leq { sqrt {2D _ { mathrm {KL}} (P | Q)}}.}$

Доказательство неравенства Пинскера использует неравенство раздела за ж-расхождения.

История

Пинскер первым доказал неравенство с худшей константой. Неравенство в указанной форме было независимо доказано Кульбак, Csiszár, и Кемперман.^[2]

Обратная задача

Не может быть точного обратного неравенства: для каждого ${ displaystyle varepsilon> 0}$, есть раздачи ${ displaystyle P _ { varepsilon}, Q}$ с ${ displaystyle delta (P _ { varepsilon}, Q) leq varepsilon}$ но ${ Displaystyle D _ { mathrm {KL}} (P _ { varepsilon} | Q) = infty}$. Простой пример - двухточечное пространство ${ displaystyle {0,1 }}$ с ${ Displaystyle Q (0) = 0, Q (1) = 1}$ и ${ Displaystyle P _ { varepsilon} (0) = varepsilon, P _ { varepsilon} (1) = 1- varepsilon}$. ^[3]

Однако на конечных пространствах справедливо обратное неравенство ${ displaystyle X}$ с постоянной зависящей от ${ displaystyle Q}$.^[4] Более конкретно, можно показать, что с определением ${ Displaystyle альфа _ {Q}: = min _ {x in X: Q (x)> 0} Q (x)}$ у нас есть по любым меркам ${ displaystyle P}$ который абсолютно непрерывен ${ displaystyle Q}$

${ displaystyle { frac {1} {2}} D _ { mathrm {KL}} (P | Q) leq { frac {1} { alpha _ {Q}}} delta (P, Q ) ^ {2}.}$

Как следствие, если ${ displaystyle Q}$ имеет полный поддерживать (т.е. ${ displaystyle Q (x)> 0}$ для всех ${ displaystyle x in X}$), тогда

${ displaystyle delta (P, Q) ^ {2} leq { frac {1} {2}} D (P | Q) leq { frac {1} { alpha _ {Q}}} delta (P, Q) ^ {2}.}$

Рекомендации

дальнейшее чтение

• Томас М. Ковер и Джой А. Томас: Элементы теории информации, 2-е издание, Willey-Interscience, 2006 г.
• Николо Чеза-Бьянки и Габор Лугоши: Прогнозирование, обучение и игры, Cambridge University Press, 2006 г.