3

Recently I found a paper which stated that $\sqrt{n}/n$ is the maximal acceptable proportion of outliers for n given data points. Unfortunately they only quote a book, which is quite out of my price range:

http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471930946.html

Unfortunately I couldn't find anything conclusive through a google search and I hope that somebody here may point me in the right direction or at least towards an affordable book or paper, which explains the matter.

MathMajor
  • 6,478
betlor5
  • 33
  • If you give details on the paper you read, perhaps someone who knows the field can help. Certainly a page number in the book would help. – Will Jagy Dec 28 '14 at 04:06
  • The paper is: "Detecting Outliers in Frontier Models: A Simple Approach" by SIMAR written in 2003. It states on page 404: "In the statistical literature an upper bound is sometimes given for the accepted proportion of outliers; for instance, Barnett and Lewis (1995) suggests sqrt(n)/n as a reasonable upper bound”. Through this comment it seems as I missed something quite important in statistics, because it is written as if it applies to every outlier analysis. – betlor5 Dec 28 '14 at 04:18
  • Certainly you want to borrow the book, then. A firm, absolute number might have a short proof, but a "reasonable" figure will have a fairly lengthy discussion, reasons the suggested bound is big enough for their tastes, also not too big. – Will Jagy Dec 28 '14 at 04:38
  • I think it is because a common level of confidence is $95%$, giving, for $n$ large enough, a deviation of about $\frac{1.96}{2\sqrt{n}}\approx \frac{1}{\sqrt{n}}$ which is of the same order of $\frac{\sqrt{n}}{n}$. – Olivier Oloa Dec 28 '14 at 04:42
  • @OlivierOloa but shouldn't your confidence be $\frac{1.96\sigma}{\sqrt n}$ for 95%? – betlor5 Dec 28 '14 at 05:07
  • @betlor5 Yes, you mean $1.96 \sigma$, but it simplifies since here you get $1.96\sqrt{\frac{p(1-p)}{n}}$, with a maximum for $p=1/2$ giving $1.96\sqrt{\frac{1}{4n}}=\frac{1.96}{2\sqrt{n}} \approx \frac{1}{\sqrt{n}}$... – Olivier Oloa Dec 28 '14 at 05:17

1 Answers1

1

The issue is not when to consider a data point as "unlikely"" as defined by some $p$-value such as 95% (which would give a 1.96 $\sigma$ criterion. Remember, the statement is that no more than $\sqrt{n}/n$ of the samples can be considered outliers. Here is how that comes about:

First, you need to say what constitutes an outlier in an ensemble of $n$ samples. Chavaulier's principle says that a reasonable criterion is to form a boundary such that the probability of at least one of the $n$ samples would lie outside that boundary is less than $\frac{1}{2}$. To talk about that probability, you base it on a normal distribution; you estimate the mean and $\sigma$ based on the total ensemble. Thus for an ensemble of $10^6$ points that boundary might lie at $5 \bar{\sigma}$ but for 20 points it would lie at only $2 \bar{\sigma}$.

In other words, if it is reasonably likely that some sample among a million would lie more than $5\sigma$ from the mean, how could you justify rejecting a point as an outlier just because it happens to be "the one" lying that far away?

OK, now lets try to construct an ensemble such that there are more than about $\sqrt{n}$ outliers. For example, a strong try would be to take 100 points, 80 of which are tighlty clustered about $0$, and ten clustered about $+10$ and ten about $-10$. Here, we might think those 20 points would be outliers, but the presence of those points contributes $2000$ to $\sum (\mu - x_i)^2$ so the s.d. estimate is $\bar{\sigma} \approx \sqrt{20}$.

Then those points turn out to be $\frac{10}{\sqrt{20}} = \sqrt{5}$ sigmas off the mean, and in order for the $p$-value to be $\frac{1}{200}$, you need to be about $2.83 \sigma$ from the mean. So those points are not, by our criterion, outliers.

You can see that if the number of potential outliers exceeds some constant (which is roughly 1) times $\sqrt{n}$, then this same effect will cause them to lie inside the boundary of this outlier criterion. So in the end, you can't have more than about $\sqrt{n}/n$ of your samples classified as outliers.

The proof that the constant involved is $1$ would be hard, since I suspect the actual upper limit is a bit tighter (though still $\text{O}(\sqrt{n}/n)$).

Mark Fischler
  • 41,743