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

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

Заявление

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

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

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

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

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

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

${\begin{aligned}\sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}&{}=\sum _{i=1}^{n}b_{i}f\left({\frac {a_{i}}{b_{i}}}\right)=b\sum _{i=1}^{n}{\frac {b_{i}}{b}}f\left({\frac {a_{i}}{b_{i}}}\right)\\&{}\geq bf\left(\sum _{i=1}^{n}{\frac {b_{i}}{b}}{\frac {a_{i}}{b_{i}}}\right)=bf\left({\frac {1}{b}}\sum _{i=1}^{n}a_{i}\right)=bf\left({\frac {a}{b}}\right)\\&{}=a\log {\frac {a}{b}},\end{aligned}}$

где неравенство следует из неравенства Йенсена, поскольку ${\frac {b_{i}}{b}}\geq 0$, $\sum _{i=1}^{n}{\frac {b_{i}}{b}}=1$, и $f$ является выпуклым.

Обобщения

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

Другое обобщение принадлежит Даннану, Неффу и Тилю, которые показали, что если $a_{1},a_{2}\cdots a_{n}$ и $b_{1},b_{2}\cdots b_{n}$ являются положительными действительными числами с $a_{1}+a_{2}\cdots +a_{n}=a$ и $b_{1}+b_{2}\cdots +b_{n}=b$, и $k\geq 0$, затем $\sum _{i=1}^{n}a_{i}\log \left({\frac {a_{i}}{b_{i}}}+k\right)\geq a\log \left({\frac {a}{b}}+k\right)$.

Приложения

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

showДоказательство
Let $P=(p_{i})_{i\in \mathbb {N} }$ and $Q=(q_{i})_{i\in \mathbb {N} }$ be pmfs. In the log sum inequality, substitute $n=\infty$, $a_{i}=p_{i}$ and $b_{i}=q_{i}$ to get $\mathbb {D} _{\mathrm {KL} }(P\|Q)\equiv \sum _{i}p_{i}\log _{2}{\frac {p_{i}}{q_{i}}}\geq 1\log {\frac {1}{1}}=0$ with equality if and only if $p_{i}=q_{i}$ for all i (as both $P$ and $Q$ sum to 1).

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

Ссылки

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