# Kendall's tau derivation from first principles?

I know that Kendall's tau is given by:

$$\tau = P[(x_1-x_2)(y_1-y_2)>0]-P[(x_1-x_2)(y_1-y_2)<0]$$

However I cannot see how this gives:

$$\tau = {2 \over n^2-n} \sum_{1\leq i<j\leq n}\, \operatorname{sign}(R_i-R_j)\operatorname{sign}(S_i-S_j)$$

Where $S$ and $R$ are ranks and $n$, the number of samples. Is there a standard undergraduate textbook that covers this? Clearly the first equation can be written as:

\eqalign{&\tau = \\ &\frac{1}{n}\sum_{\substack{i,j}{i\neq j}}[\operatorname{sign}(R_i-R_j)\,\operatorname{sign}(S_i-S_j)>0]-\frac{1}{n}\sum_{\substack{i,j}{i\neq j}}[\operatorname{sign}(R_i-R_j)\,\operatorname{sign}(S_i-S_j)<0].}

But there is seems to be an assumption or reason that:

$$\sum_{\substack{i,j}{i\neq j}}[\text{sign}(R_i-R_j)\text{sign}(S_i-S_j)<0] \propto -\sum_{\substack{i,j}{i\neq j}}[\text{sign}(R_i-R_j)\text{sign}(S_i-S_j)>0]$$

Tau is an "indicator" version of covariance.

Recall this image from How would you explain covariance to someone who understands only the mean:

It shows two possible configurations of pairs of points in a scatterplot. The red pairs are "positively" oriented (or "concordant"): they are at the lower left and upper right of the rectangle they delimit. The smaller x-coordinate and the smaller y-coordinate are together; the larger x-coordinate and the larger y-coordinate are together. This is a situation of positive association.

The cyan pairs are "negatively" oriented (or "discordant"): the larger of the x-coordinates is associated with the smaller of the y-coordinates, and vice versa. The association is negative.

Covariance quantifies these associations in terms of the areas of the rectangles, assigning the cyan rectangles negative areas. Kendall's Tau also quantifies these associations, but it does so in a simpler way: it just counts them. A red rectangle counts as $+1$; a cyan rectangle as $-1$. Let's call these the "signs" of the rectangles.

Any scatterplot of $n$ points $(x_i, y_i), i=1, 2, \ldots, n$ determines $\binom{n}{2}=n(n-1)/2$ such rectangles, because each rectangle is uniquely associated with an unordered pair of those points. Whereas the covariance averages the (signed) areas of these rectangles, Kendall's Tau averages their signs. That's all the formulas are doing.

There are two ways to understand the initial probability statement. One is the empirical probability. It contemplates writing each unordered pair of points in a sample, $\{(x_i,y_i), (x_j,y_j)\},\ i\ne j,$ on a slip of paper. Also on each slip write $+1$ for the concordant pairs and $-1$ for the discordant pairs. Put those slips into a box, mix them up, and randomly draw one out. The expression

$$\Pr[(x_1-x_2)(y_1-y_2) \gt 0]$$

is the chance of observing a $+1$. The other expression in the question similarly is the chance of observing a $-1$. But look at the difference this way:

$$\tau = \Pr(\text{positive association})\times(+1) + \Pr(\text{negative association})\times(-1).$$

That probability-weighted sum of values on the tickets is, by definition, an expectation. Obviously it is the expected value of the signs on those slips of paper.

$\tau$ is the average value of the signs of the rectangles in the scatterplot.

The average in the box is obtained, of course, by adding up all the values and then dividing by the number of tickets in the box. That's precisely the formula for $\tau$ in the question.

This description extends to any box of pairs of tickets constructed in this manner. Thus, $\tau$ can also be thought of as a property of any bivariate distribution. For distributions with infinite support (such as continuous distributions), it would have to be computed as a double integral rather than a sum, but that changes nothing about the underlying ideas or interpretations.

Similarly, just as any sample of a bivariate distribution has a covariance--and we hope it might have some relationship to the covariance of the underlying distribution (if a covariance exists at all!)--any sample of a bivariate distribution has a $\tau$ statistic, and we hope it might have some relationship to the $\tau$ value of the underlying distribution (which always exists, whether or not the covariance exists).