Simultaneous computation of Kendall's tau and its jackknife variance

Understand

We present efficient algorithms for simultaneously computing Kendall's tau and the jackknife estimator of its variance.

• For the classical pairwise tau, we describe a modification of Knight's algorithm (originally designed to compute only tau) that does so while preserving its $O(n \log_2 n)$ runtime in the number of observations $n$.
• We also introduce a novel algorithm computing a multivariate extension of tau and its jackknife variance in $O(n \log_2^p n)$ time.