Efficient computation of the Bergsma-Dassios sign covariance

Abstract

In an extension of Kendall’s τ$$\tau $$, Bergsma and Dassios (Bernoulli 20(2):1006–1028, 2014) introduced a covariance measure τ∗$$\tau ^*$$ for two ordinal random variables that vanishes if and only if the two variables are independent. For a sample of size n, a direct computation of t∗$$t^*$$, the empirical version of τ∗$$\tau ^*$$, requires O(n4)$$O(n^4)$$ operations. We derive an algorithm that computes the statistic using only On2log(n)$$O \left( n^2\log (n)\right) $$ operations.