# Better than Mad, Derive $Q_n$

Could someone be so kind as to walk me through how to do this equation on a dataset?

on pg 5 (marked as 1277) equation 3.3 of this paper.

$$Q_n = c|x_i-x_j|_{(k)},\;\;1\leq i<j\leq n,k\approx{n\choose 2}/4$$

• Look at page 9->12 of this paper. P.S.: prepare a piece of paper and a sharp pencil. Note that the algorithm is widely implemented in open source statistical softwares (for example package robustbase in R), so given a data vector $\pmb x$ the answer to your question is robustbase::Qn(x) – user603 Nov 8 '14 at 17:44

Let's decode this:

$Q_n = c|x_i-x_j|_{(k)},\;\;1\leq i<j\leq n,k\approx{n\choose 2}/4$

into something more like an algorithm. (Edit: This doesn't describe the actual algorithm that you'd use to code calculation of $Q_n$ up - it's just an attempt to explain what the formula means.)

1. Consider just the inner term, "$|x_i-x_j|,\;\;1\leq i<j\leq n$":

Take all pairs of observations $(x_i,x_j),\; i<j$ and find their absolute difference.

2. Now, $_{(k)}$: for $k\approx{n\choose 2}/4$, take the $k$-th of those absolute differences in order from smallest to largest (i.e. take the k-th order statistic). [Roughly speaking, find the lower quartile of those absolute differences.]

3. multiply by $c$ (the default given in the paper is the asymptotic correction factor for $\sigma$ in a Gaussian, $c=1.1926$). Call the result $Q_n$.

Example:

Let's consider n=7.

There are 7$\times$6/2=21 pair-differences. Several approaches to calculating sample quantiles place the lower quartile at the 6th observation of 21 (it splits the values into the ratio 3:1 -- 5 below the quartile and 15 above it). For example, the default method in R's quantile function does this (quantile(1:21) returns 6 for the 25th percentile), and Tukey's definition of hinges does the same (fivenum(1:21) also returns 6 for the lower hinge).

Consider the data values $(18.3, 18.7, 19.2, 20.7, 22.4, 26.5, 30.1)$ (sorted for convenience).

The 21 sorted pair-differences are: $(0.4, 0.5, 0.9, 1.5, 1.7, 2, 2.4, 3.2, 3.6, 3.7, 4.1, \\\:4.1, 5.8, 7.3, 7.7, 7.8, 8.2, 9.4, 10.9, 11.4, 11.8)$

The sixth of those is $2$, so for that data, one approach to taking quartiles would put $Q_n=2c$. (I won't labour the point with multiplying by constants)

Check in R:

> x
[1] 18.3 18.7 19.2 20.7 22.4 26.5 30.1
> d = sort(abs(c(outer(x,x,"-"))[c(outer(x,x,"<"))]))
> d
[1]  0.4  0.5  0.9  1.5  1.7  2.0  2.4  3.2  3.6  3.7  4.1  4.1  5.8  7.3
[15]  7.7  7.8  8.2  9.4 10.9 11.4 11.8
> quantile(d,p=0.25)
25%
2


(Then all that remains is the multiplication by $c$, suggesting an estimated spread - essentially a robust estimate of standard deviation - of about 2.385 if we use the default $c$. As mentioned earlier, we wouldn't code a function like this for general use as it's inefficient. On small examples, like this, it's fine.)

• ok, followed you up to lower quartile. You mean the 1st quartile huh? Is that what the (n over 2)/4 represents? – thistleknot Nov 8 '14 at 23:42
• That's not $n/2$: it's a binomial coefficient. – Nick Cox Nov 9 '14 at 0:14
• I will just add that what is described here is the naive approach. In reality, you don't need to consider all O(n^2) pairs $|x_i-x_j|$ to find their kth order statistics. In fact, it is only necessary to consider $n$ well chosen entries among them so that the numerical complexity of the Qn is O(nlogn) [and not O(n^2) as would be the case if the above described approach were used]. Hence my comment to your question. I defer to the paper I linked for further explanations, it is a thing of beauty. – user603 Nov 9 '14 at 0:47
• @user603 Right; the intent was to use a step by step approach working out from the innermost part of the expression to attempt to convey the meaning of the formula, not give the actual algorithm that you'd use to code it up (which you rightly explain can be done much more efficiently). I'll make the distinction more explicit. – Glen_b Nov 9 '14 at 4:19
• @thistleknot Yes first quartile and lower quartile are the same thing ($F^{-1}(\frac{1}{4})$), though both terms can also refer to values falling below $F^{-1}(\frac{1}{4})$. – Glen_b Nov 9 '14 at 4:27