Неравенство логарифмической суммы - Log sum inequality

В неравенство логарифмической суммы используется для доказательства теорем в теория информации.

утверждение

Позволять ${displaystyle a_ {1}, ldots, a_ {n}}$ и ${displaystyle b_ {1}, ldots, b_ {n}}$ быть неотрицательными числами. Обозначим сумму всех ${displaystyle a_ {i}}$s пользователем ${displaystyle a}$ и сумма всех ${displaystyle b_ {i}}$s пользователем ${displaystyle b}$. Неравенство логарифмической суммы утверждает, что

${displaystyle sum _ {i = 1} ^ {n} a_ {i} log {frac {a_ {i}} {b_ {i}}} geq alog {frac {a} {b}},}$

с равенством тогда и только тогда, когда ${displaystyle {frac {a_ {i}} {b_ {i}}}}$ равны для всех ${displaystyle i}$, другими словами ${displaystyle a_ {i} = cb_ {i}}$ для всех ${displaystyle i}$.^[1]

(Возьмите ${displaystyle a_ {i} log {frac {a_ {i}} {b_ {i}}}}$ быть ${displaystyle 0}$ если ${displaystyle a_ {i} = 0}$ и ${displaystyle infty}$ если ${displaystyle a_ {i}> 0, b_ {i} = 0}$. Это предельные значения, полученные, поскольку соответствующее число стремится к ${displaystyle 0}$.)^[1]

Доказательство

Обратите внимание, что после установки ${displaystyle f (x) = xlog x}$ у нас есть

${displaystyle {egin {align} sum _ {i = 1} ^ {n} a_ {i} log {frac {a_ {i}} {b_ {i}}} & {} = sum _ {i = 1} ^ {n} b_ {i} fleft ({frac {a_ {i}} {b_ {i}}} ight) = bsum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} fleft ({frac {a_ {i}} {b_ {i}}} ight) & {} geq bfleft (sum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} { frac {a_ {i}} {b_ {i}}} ight) = bfleft ({frac {1} {b}} sum _ {i = 1} ^ {n} a_ {i} ight) = bfleft ({frac {a} {b}} ight) & {} = alog {frac {a} {b}}, конец {выровнен}}}$

где неравенство следует из Неравенство Дженсена поскольку ${displaystyle {frac {b_ {i}} {b}} geq 0}$, ${displaystyle sum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} = 1}$, и ${displaystyle f}$ выпуклый.^[1]

Обобщения

Неравенство сохраняется при ${displaystyle n = infty}$ при условии, что ${displaystyle a$ и ${displaystyle b$.^{[нужна цитата ]}Приведенное выше доказательство справедливо для любой функции ${displaystyle g}$ такой, что ${displaystyle f (x) = xg (x)}$ выпукла, как и все непрерывные неубывающие функции. Обобщения на неубывающие функции, отличные от логарифма, даны в Csisz r, 2004.

Приложения

Неравенство логарифмической суммы может использоваться для доказательства неравенств в теории информации. Неравенство Гиббса заявляет, что Расхождение Кульбака-Лейблера неотрицательно и равно нулю в точности, если его аргументы равны.^[2] Одно доказательство использует неравенство логарифмической суммы.

Доказательство[1]

Позволять ${displaystyle P = (p_ {i}) _ {iin mathbb {N}}}$ и ${displaystyle Q = (q_ {i}) _ {iin mathbb {N}}}$ быть pmfs. В неравенстве логарифмической суммы подставим ${displaystyle n = infty}$, ${displaystyle a_ {i} = p_ {i}}$ и ${displaystyle b_ {i} = q_ {i}}$ получить ${displaystyle mathbb {D} _ {mathrm {KL}} (P | Q) Equiv sum _ {i} p_ {i} log _ {2} {frac {p_ {i}} {q_ {i}}} geq 1log {гидроразрыв {1} {1}} = 0}$ с равенством тогда и только тогда, когда ${displaystyle p_ {i} = q_ {i}}$ для всех я (как оба ${displaystyle P}$ и ${displaystyle Q}$ сумма к 1).

Неравенство также может доказывать выпуклость расходимости Кульбака-Лейблера.^[3]

Заметки

использованная литература

• Томас М. Кавер; Джой А. Томас (1991). Элементы теории информации. Хобокен, Нью-Джерси: Wiley. ISBN  978-0-471-24195-9.
• Чишер, И.; Шилдс, П. (2004). «Теория информации и статистика: Учебное пособие» (PDF). Основы и тенденции в теории коммуникации и информации. 1 (4): 417–528. Дои:10.1561/0100000004. Получено 2009-06-14.
• Т.С. Хан, К. Кобаяши, Математика информации и кодирования. Американское математическое общество, 2001. ISBN  0-8218-0534-7.
• Материалы курса теории информации, Университет штата Юта [1]. Проверено 14 июня 2009.
• Маккей, Дэвид Дж. (2003). Теория информации, логический вывод и алгоритмы обучения. Издательство Кембриджского университета. ISBN  0-521-64298-1.