Неравенство логарифмической суммы - 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{aligned}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}},end{aligned}}}$

где неравенство следует из Неравенство Дженсена поскольку ${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<infty }$ и ${displaystyle b<infty }$.^{[нужна цитата ]}Приведенное выше доказательство справедливо для любой функции ${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 {frac {1}{1}}=0}$ с равенством тогда и только тогда, когда ${displaystyle p_{i}=q_{i}}$ для всех я (как оба ${displaystyle P}$ и ${displaystyle Q}$ сумма к 1).

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

Заметки

1. Обложка и Томас (1991), п. 29. Ошибка sfnp: цель отсутствует: CITEREFCoverThomas1991 (Помогите)
2. Маккей (2003), п. 34.
3. Обложка и Томас (1991), п. 30. Ошибка sfnp: цель отсутствует: CITEREFCoverThomas1991 (Помогите)

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

• Томас М. Кавер; Джой А. Томас (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.