A Fast Algorithm for Computing Martingale Difference Correlation

Martingale difference divergence and martingale difference correlation have been widely adopted in measuring the departure of conditional mean independence between a scalar response variable and a vector predictor variable. The computation of sample martingale difference divergence is implemented directly accordingly to its definition typically requires O(n²) cost, where n is the sample size, which greatly limits the use of the distance covariance for large data. To calculate the sample martingale difference divergence between two univariate random variables, a simple, exact O(nlog(n)) algorithm is developed. The proposed algorithm essentially consists of one sorting step, so it is easy to implement. The numerical simulation results show that the proposed algorithm is significantly faster than the brute force method, which enables researchers to explore complicated dependence structures in large datasets.