A Fast and Exact Randomisation Test for Comparing Two Systems with Paired Data

The randomisation test with B trials has been used in the information retrieval (IR) field for comparing two systems with paired data (i.e., a common set of topics). It approximates the exact randomisation test whose time complexity is O(2ⁿ) for n topics. In this paper, we first show that the counting operation for obtaining the exact p-value in a randomisation test can be reduced to a subsequence sum enumeration problem that can be solved by dynamic programming. By taking advantage of this observation along with the fact that we only require a small number of significant digits in IR evaluation measure scores, we demonstrate that the time complexity of the exact randomisation test can be reduced to O(mn), where m is the maximum subsequence sum of the paired score differences. Hence, researchers can utilise our test if they want to avoid random sampling and/or normality assumptions and want a fast and reliable test. In addition, we utilise Vandermonde's convolution in order to theoretically explain a known fact, namely, that the sign test is a special case of the exact randomisation test.