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 am trying to implement a solution (working code) for the 4.1 paragraph in this paper.

The problem:

We have words with lengths for instance: $l_1$ = 1, $l_2$ = 2, $l_3$ = 3, $l_4$ = 8 and $l_5$ = 7.

These words will be part of the white-list.

We calculate the sample mean and the variance of the lengths of these words.

$\mu = \frac{1}{N}\sum_{i = 1}^N X_i$

So, $\mu = 4.2$ in our case.

Next step is to calculate the variance.

$\sigma^2 = \frac{1}{N}\sum_{i = 1}^N (X_i - \mu)^2$

So, $\sigma^2 = 7.76$

After all calculations are done we get another list of words and the goal of the algorithm is to assess the anomaly of a string with length l, by calculating the ''distance'' of the length l from the mean $\mu$ of value l of the length distribution.

This distance is expressed with the help of the Chebyshev inequality.

$p(\mid x-\mu \mid > t) < \frac{\mu^2}{t^2}$

When l is far away from $\mu$, considering the variance of the length distribution, then the probability of any (legitimate) string x having a greater length than l should be small. Thus, to obtain a quantitative measure of the distance between a string of length l and the mean $\mu$ of the length distribution, we substitute t with the difference between $\mu$ and l.

$p(\mid x-\mu \mid > \mid l-\mu \mid) < p(l)=\frac{\sigma^2}{(l-\mu)^2}$

Having the information above, if I run it with the next numbers: 1, 5, 10. I get these probabilities:

p(1) =0.757

p(5) =12.125

p(10) =0.230

Which I don't understand why some probabilities I get are bigger than 1, they are not supposed to be bigger than 1. I am trying to understand if the formulas described above are correct or maybe I am using them wrong.

Thank you.

share|improve this question
    
Did you get something out of one of the answers below? –  Did Apr 7 '11 at 8:41
    
@Didier Yes, sorry forgot to select the answer. Both answers were helpful. The most helpful statement was "The Chebyshev inequality is just useless for items within 1 standard deviation from the mean". Thanks a lot to both of you! –  Alexandru Luchian Apr 7 '11 at 12:17

2 Answers 2

up vote 1 down vote accepted

You have stated the Chebyshev inequality incorrectly in one place, but correct it later. It should be $p(\mid x-\mu \mid > t) < \frac{\sigma^2}{t^2}$ if $t$ has units like $x$. $p(l)=\frac{\sigma^2}{(l-\mu)^2}$ is not the probability of length $l$ or even $l$ or greater. It is just a limit that the number of items that far from the mean can't be more than. So yes, the Chebyshev inequality says that $p(5)<12.125$, which is a correct statement. If the mean were exactly $5$, the RHS would be infinite and $p(5)$ would still be less than that. The Chebyshev inequality is just useless for items within $1$ standard deviation from the mean. Your calculation for $p(10)$ is violated-1 item in 3 is that far away, which is greater than $0.230$. I get $\sigma^2=\frac{122}{9}, \mu=\frac{16}{3}$, which leads to $p(10)=\frac{122}{196}\approx 0.622$

share|improve this answer
    
thanks a lot. Why do you say that "The Chebyshev inequality is just useless for items within 1 standard deviation from the mean"? –  Alexandru Luchian Mar 28 '11 at 23:46
    
Because it says a probability is less than some number greater than 1 (like your p(5)). As you already know the probability is less than or equal to 1, it brings no new information. –  Ross Millikan Apr 7 '11 at 14:15

Chebyshev inequality provides an upper bound of the probability of the event you are interested in. When $t<\sigma$, this upper bound is larger than $1$. Obviously, the probability of the event is at most $1$. There is no contradiction.

Note that when $t\gg\sigma$, Chebyshev upper bound is often completely off the mark as well. The real probability can be much smaller, in fact in many situations it decreases exponentially with $t$.

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.