Efficient inference for Kendall's tau

Kendall's tau is a nonparametric measure of correlation. We present an efficient method for computing the empirical estimate of Kendall's tau and the jackknife estimate of its variance. For datasets of fixed dimension, the algorithm's runtime is log-linear in the number of observations. This is achieved by modifying the standard algorithm for computing the empirical Kendall's tau to return estimates of the summands making up its H\'{a}jek projection.