Efficient Computation of the Bergsma-Dassios Sign Covariance

Abstract

In an extension of Kendall's $\tau$, Bergsma and Dassios (2014) introduced a covariance measure ${\tau }^{\ast }$ 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^{\ast }$, the empirical version of ${\tau }^{\ast }$, requires $O(n^4)$ operations. We derive an algorithm that computes the statistic using only $O(n^2\log (n))$ operations.

Improved formatting, added reference to R package implementing the algorithm, and added additional experiments

References in corpus (1)

• A consistent test of independence based on a sign covariance related to Kendall's tau