J u m p t o c o n t e n t
M a i n m e n u
M a i n m e n u
N a v i g a t i o n
● M a i n p a g e
● C o n t e n t s
● C u r r e n t e v e n t s
● R a n d o m a r t i c l e
● A b o u t W i k i p e d i a
● C o n t a c t u s
● D o n a t e
C o n t r i b u t e
● H e l p
● L e a r n t o e d i t
● C o m m u n i t y p o r t a l
● R e c e n t c h a n g e s
● U p l o a d f i l e
S e a r c h
Search
A p p e a r a n c e
● C r e a t e a c c o u n t
● L o g i n
P e r s o n a l t o o l s
● C r e a t e a c c o u n t
● L o g i n
P a g e s f o r l o g g e d o u t e d i t o r s l e a r n m o r e
● C o n t r i b u t i o n s
● T a l k
( T o p )
1
S t a t e m e n t
2
P r o o f
3
G e n e r a l i z a t i o n s
4
A p p l i c a t i o n s
5
N o t e s
6
R e f e r e n c e s
T o g g l e t h e t a b l e o f c o n t e n t s
L o g s u m i n e q u a l i t y
4 l a n g u a g e s
● Ε λ λ η ν ι κ ά
● ف ا ر س ی
● F r a n ç a i s
● 中 文
E d i t l i n k s
● A r t i c l e
● T a l k
E n g l i s h
● R e a d
● E d i t
● V i e w h i s t o r y
T o o l s
T o o l s
A c t i o n s
● R e a d
● E d i t
● V i e w h i s t o r y
G e n e r a l
● W h a t l i n k s h e r e
● R e l a t e d c h a n g e s
● U p l o a d f i l e
● S p e c i a l p a g e s
● P e r m a n e n t l i n k
● P a g e i n f o r m a t i o n
● C i t e t h i s p a g e
● G e t s h o r t e n e d U R L
● D o w n l o a d Q R c o d e
● W i k i d a t a i t e m
P r i n t / e x p o r t
● D o w n l o a d a s P D F
● P r i n t a b l e v e r s i o n
A p p e a r a n c e
F r o m W i k i p e d i a , t h e f r e e e n c y c l o p e d i a
Let
a
1
,
…
,
a
n
{\displaystyle a_{1},\ldots ,a_{n}}
and
b
1
,
…
,
b
n
{\displaystyle b_{1},\ldots ,b_{n}}
be nonnegative numbers. Denote the sum of all
a
i
{\displaystyle a_{i}}
s by
a
{\displaystyle a}
and the sum of all
b
i
{\displaystyle b_{i}}
s by
b
{\displaystyle b}
. The log sum inequality states that
∑
i
=
1
n
a
i
log
a
i
b
i
≥
a
log
a
b
,
{\displaystyle \sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}\geq a\log {\frac {a}{b}},}
with equality if and only if
a
i
b
i
{\displaystyle {\frac {a_{i}}{b_{i}}}}
are equal for all
i
{\displaystyle i}
, in other words
a
i
=
c
b
i
{\displaystyle a_{i}=cb_{i}}
for all
i
{\displaystyle i}
.
(Take
a
i
log
a
i
b
i
{\displaystyle a_{i}\log {\frac {a_{i}}{b_{i}}}}
to be
0
{\displaystyle 0}
if
a
i
=
0
{\displaystyle a_{i}=0}
and
∞
{\displaystyle \infty }
if
a
i
>
0
,
b
i
=
0
{\displaystyle a_{i}>0,b_{i}=0}
. These are the limiting values obtained as the relevant number tends to
0
{\displaystyle 0}
.)
Notice that after setting
f
(
x
)
=
x
log
x
{\displaystyle f(x )=x\log x}
we have
∑
i
=
1
n
a
i
log
a
i
b
i
=
∑
i
=
1
n
b
i
f
(
a
i
b
i
)
=
b
∑
i
=
1
n
b
i
b
f
(
a
i
b
i
)
≥
b
f
(
∑
i
=
1
n
b
i
b
a
i
b
i
)
=
b
f
(
1
b
∑
i
=
1
n
a
i
)
=
b
f
(
a
b
)
=
a
log
a
b
,
{\displaystyle {\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}}}
where the inequality follows from Jensen's inequality since
b
i
b
≥
0
{\displaystyle {\frac {b_{i}}{b}}\geq 0}
,
∑
i
=
1
n
b
i
b
=
1
{\displaystyle \sum _{i=1}^{n}{\frac {b_{i}}{b}}=1}
, and
f
{\displaystyle f}
is convex.
Generalizations [ edit ]
The inequality remains valid for
n
=
∞
{\displaystyle n=\infty }
provided that
a
<
∞
{\displaystyle a<\infty }
and
b
<
∞
{\displaystyle b<\infty }
.[citation needed ]
The proof above holds for any function
g
{\displaystyle g}
such that
f
(
x
)
=
x
g
(
x
)
{\displaystyle f(x )=xg(x )}
is convex, such as all continuous non-decreasing functions. Generalizations to non-decreasing functions other than the logarithm is given in Csiszár, 2004.
Another generalization is due to Dannan, Neff and Thiel, who showed that if
a
1
,
a
2
⋯
a
n
{\displaystyle a_{1},a_{2}\cdots a_{n}}
and
b
1
,
b
2
⋯
b
n
{\displaystyle b_{1},b_{2}\cdots b_{n}}
are positive real numbers with
a
1
+
a
2
⋯
+
a
n
=
a
{\displaystyle a_{1}+a_{2}\cdots +a_{n}=a}
and
b
1
+
b
2
⋯
+
b
n
=
b
{\displaystyle b_{1}+b_{2}\cdots +b_{n}=b}
, and
k
≥
0
{\displaystyle k\geq 0}
, then
∑
i
=
1
n
a
i
log
(
a
i
b
i
+
k
)
≥
a
log
(
a
b
+
k
)
{\displaystyle \sum _{i=1}^{n}a_{i}\log \left({\frac {a_{i}}{b_{i}}}+k\right)\geq a\log \left({\frac {a}{b}}+k\right)}
. [2]
Applications [ edit ]
The log sum inequality can be used to prove inequalities in information theory. Gibbs' inequality states that the Kullback-Leibler divergence is non-negative, and equal to zero precisely if its arguments are equal. One proof uses the log sum inequality.
The inequality can also prove convexity of Kullback-Leibler divergence.
References [ edit ]
Cover, Thomas M.; Thomas, Joy A. (1991). Elements of Information Theory . Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9 .
Csiszár, I. ; Shields, P. (2004). "Information Theory and Statistics: A Tutorial" (PDF) . Foundations and Trends in Communications and Information Theory . 1 (4 ): 417–528. doi :10.1561/0100000004 . Retrieved 2009-06-14 .
T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. ISBN 0-8218-0534-7 .
Information Theory course materials, Utah State University [1 ] . Retrieved on 2009-06-14.
MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms . Cambridge University Press. ISBN 0-521-64298-1 .
R e t r i e v e d f r o m " https://en.wikipedia.org/w/index.php?title=Log_sum_inequality&oldid=1222903390 "
C a t e g o r i e s :
● I n e q u a l i t i e s
● I n f o r m a t i o n t h e o r y
H i d d e n c a t e g o r i e s :
● C S 1 m a i n t : m u l t i p l e n a m e s : a u t h o r s l i s t
● A l l a r t i c l e s w i t h u n s o u r c e d s t a t e m e n t s
● A r t i c l e s w i t h u n s o u r c e d s t a t e m e n t s f r o m J u l y 2 0 2 0
● A r t i c l e s c o n t a i n i n g p r o o f s
● T h i s p a g e w a s l a s t e d i t e d o n 8 M a y 2 0 2 4 , a t 1 6 : 5 9 ( U T C ) .
● T e x t i s a v a i l a b l e u n d e r t h e C r e a t i v e C o m m o n s A t t r i b u t i o n - S h a r e A l i k e L i c e n s e 4 . 0 ;
a d d i t i o n a l t e r m s m a y a p p l y . B y u s i n g t h i s s i t e , y o u a g r e e t o t h e T e r m s o f U s e a n d P r i v a c y P o l i c y . W i k i p e d i a ® i s a r e g i s t e r e d t r a d e m a r k o f t h e W i k i m e d i a F o u n d a t i o n , I n c . , a n o n - p r o f i t o r g a n i z a t i o n .
● P r i v a c y p o l i c y
● A b o u t W i k i p e d i a
● D i s c l a i m e r s
● C o n t a c t W i k i p e d i a
● C o d e o f C o n d u c t
● D e v e l o p e r s
● S t a t i s t i c s
● C o o k i e s t a t e m e n t
● M o b i l e v i e w