During my Fall 2010 ECE 516 (Information Theory) class, the instructor asked the class to prove this seemingly trivial logarithmic inequality [1] by as many different methods and, if possible, using an information theoretic result. The given inequality comes handy to prove the Gibbs Inequality [2] [3].I could think of the following ways though the desired proof still eludes me. I would present my approach to it though:


Using series expansion:
For \forall y, the power series expansion of the function e^{y} is given by

e^{y} = 1 + y + \frac{y^2}{2!} + \frac{y^3}{3!} + \cdots

\Rightarrow e^{y} \geq 1 + y,  y \geq 0

\Rightarrow z \geq 1 + \ln{z}, e^y = z > 0

\Rightarrow -\ln{z} \geq 1 - z, z > 0

\Rightarrow \ln{\frac{1}{z}} \geq 1 - z, z > 0

\Rightarrow \ln{x} \geq 1 - \frac{1}{x}, x > 0 and where x = \frac{1}{z}
Q.E.D.


Using definite integral:
For x \geq 1, we have area under the monotonically increasing logarithmic curve lying above the x-axis given by
\displaystyle\int_{1}^{x}\ln{x}dx \geq 0, x\geq 1

\Rightarrow (x\ln{x} - x)|_{1}^{x} \geq 0, x\geq 1

\Rightarrow (x\ln{x} - x) - (0-1) \geq 0, x\geq 1

\Rightarrow (x\ln{x} - x) + 1 \geq 0, x\geq 1

\Rightarrow (x\ln{x} - x) \geq -1, x\geq 1

\Rightarrow \ln{x} \geq \frac{x-1}{x}, x\geq 1

\Rightarrow \ln{x} \geq 1-\frac{1}{x}, x\geq 1 … (1)

For 0 < x \leq 1, we have area under the monotonically increasing logarithmic curve lying below the x-axis given by

\displaystyle\int_{x}^{1}\ln{x}dx \leq 0, 0 < x \leq 1

\Rightarrow \displaystyle\int_{1}^{x}\ln{x}dx \geq 0, 0 < x \leq 1

Following similar steps as above for x \geq 1, we get,
\Rightarrow \ln{x} \geq 1-\frac{1}{x}, 0 < x \leq 1 … (2)


Result follows from (1) and (2).
Q.E.D.


Using the definition of convexity:
Let’s assume f(x) = \ln{x}-1+\frac{1}{x} where x>0, and then check the convexity of this function:

\frac{df(x)}{dx} = \frac{1}{x} - \frac{1}{x^2} \mbox{ equated to zero gives,}

x(x-1) = 0

\Rightarrow x = 1 \mbox{ is the solution. } (\because x>0)

\mbox{Now, } \frac{d^2f(x)}{dx^2}| = (\frac{-1}{x^2} + \frac{2}{x^3})

\mbox{For x = 1, } \frac{d^2f(x)}{dx^2}|_{x=1} =  -1 + 2 = 1 \mbox{, which is positive}

\Rightarrow \mbox{by definition of convexity, f(x) is convex at x = 1 for x\textgreater0}

\Rightarrow \mbox{for any x \textgreater 0, } f(x) \geq f(1)

\Rightarrow \mbox{for any x \textgreater 0, } \ln{x}-1+\frac{1}{x} \geq 0

\Rightarrow \mbox{for any x\textgreater  0, } \ln{x} \geq 1-\frac{1}{x}
Q.E.D.


Using an information theoretic result:
This is just a vaporware [4] as of now. However, as shown in [2], this logarithmic inequality can be used to prove Jensen’s Inequality [5] or properties of Kullback-Leibler distance [6]. So is it possible that one of these results can be employed to do the inverse i.e. to prove the above-mentioned logarithmic inequality?

References:
[1] Cover T. M. and Thomas J. A., “Elements of Information Theory,” Wiley-Interscience, 2nd Edition, 2006, Problem 2.13.
[2] Gibbs’ Inequality.
[3] Proof of Gibbs’ Inequality. Please note that this document misspells the inequality as Gibb’s.
[4] Vaporware.
[5] Jensen’s Inequality.
[6] Kullback-Leibler Distance.

Advertisements