Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to learn pointers to how to prove "a function $f(x)$ always greater than function $g(x)$ in a interval $(a,b)$". In other words show that $f(x) > g(x)$ in $(a,b)$.

Their end point values are same.

$$f(a) = g(a)$$ $$f(b) = g(b)$$

$f(x)$ and $g(x)$ are functions used in Decision tree induction.

$f(x)$ is information gain.

$$ f(x) = - \sum p(x)\log_2(p(x)) $$

g(x) is GINI index function.

$$ g(x) = 1 - \sum p(x)^2 $$

$p(x)$ functions are probabilities therefore $ \sum{p(x)} = 1$.

I tried to show that $f(x) - g(x) > 0$ is always true. But I think I need formal name of this approach or other approaches.

I am engineer by profession therefore I would like to learn full names of approaches to search in the internet.

I added functions and more information about this problem.

A good explanation of my problem is given here. Example is about SPAM classification. http://people.cs.vt.edu/~ramakris/Courses/CS6604/lectures/lec9/lec9.pdf

$f(x)$ and $g(x)$ functions are discrete, probabilities are computed using given data. Above link has a figure which shows that between $(0,1)$, $f(x)$ is always greater that $g(x)$.

I thought that generic answers is possible but it seems that I am mistaken. Every problem is somewhat unique.

share|improve this question
    
Nothing special about $f$ and $g$? –  J. M. Dec 12 '11 at 13:38
2  
Neither $f$ nor $g$ depends on $x$. Since they are both constants and their boundary values coincide, they're identical, so it can't be that one is greater than the other. –  joriki Dec 12 '11 at 14:11
    
@joriki corrected p(i) as p(x) –  Atilla Ozgur Dec 12 '11 at 14:13
3  
Ah, I thought the sum was over $i$. Now what's the sum over? –  joriki Dec 12 '11 at 14:14
    
I'm guessing it's really an integral from $a$ to $b$ rather than a sum, but that some probability textbook (for engineers, no doubt) didn't want any scary $\int$ signs in it. –  Thomas Andrews Dec 12 '11 at 14:42

1 Answer 1

up vote 1 down vote accepted

I am interpreting the question as follows:

Let $X$ be a finite set and let $p : X \to [0, 1]$ be a probability distribution over $X$. Define the entropy to be $H(p) = - \sum \limits_{x \in X} p(x) \ln p(x)$ and the Gini index to be $g(p) = 1 - \sum \limits_{x \in X} p(x)^2 $. Show that the entropy always dominates the Gini index; i.e., show that $H(p) \geqslant g(p)$ for all distributions $p$.

Proof. Assume without loss of generality that $p(x) > 0$ for all $x \in X$. The Gini index can be rewritten equivalently as $$ g(p) = 1 - \sum_{x \in X} p(x)^2 = \sum_{x \in X} p(x) - \sum_{x \in X} p(x)^2 = \sum_{x \in X} p(x) (1-p(x)). $$ From the standard inequality $1+z \leqslant \mathrm e^z$, we have $$ 1 + \ln p(x) \leqslant \exp(\ln p(x)) = p(x), $$ which gives $1 - p(x) \leqslant - \log p(x)$. Multiplying by $p(x) \gt 0$, we have $$ - p(x) \ln p(x) \geqslant p(x) (1 - p(x)). $$ Finally, summing over all $x \in X$, we get the claim.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.