Efficient Computation of the Bergsma-Dassios Sign Covariance

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

No reviews yet.

No comments yet.