Computer implementation of exact distribution of rank statistical criteria using dynamic programming methods

This paper considers the problem of calculating exact distributions for nonparametric rank tests in the absence of analytical solutions. The classical approach based on a complete enumeration of all possible permutations of ranks, although theoretically accurate, turns out to be practically inapplicable even for small sample sizes due to the combinatorial explosion of the number of variants. A straightforward enumeration of all possible rank permutations, which is an exact calculation method, proves computationally intractable even for small samples due to combinatorial explosion. The most well-known nonparametric rank tests lacking an analytical solution for obtaining the full distribution function are considered, including the Lehmann-Rosenblatt, Kruskal-Wallis, and Mood tests. Existing approximations (normal, chi-square) often prove unsatisfactory for small samples. This paper proposes an efficient solution based on dynamic programming, which reduces computational costs by hundreds of times compared to naive permutation generation. The methodology implemented includes generating rank sequences, calculating statistics for each sequence, and then aggregating the results to construct the distribution function. Computational experiments conducted clearly demonstrate that dynamic programming is the most effective method for generating accurate distributions. Software implementations in C++ and Python have been developed and made publicly available, and comparative testing has confirmed the expected performance advantage of C++.

1. Agamirov L.V., Agamirov V.L., Vestyak V.A. Numerical Methods and Algorithms of Calculation of Exact Distributions of Non-Parametrical Criteria Statistical Hypotheses. Aerospace MAI Journal. 2013;20(4):212–218. (In Russ.).

2. Van de Wiel M.A. The Probability Generating Function of the Freund-Ansari-Bradley Statistic. In: Memorandum COSOR: Volume 9711. Eindhoven: Technische Universiteit Eindhoven; 1997. P. 6–13.

3. Van de Wiel M.A. Exact Distributions of Multiple Comparisons Rank Statistics. Journal of the American Statistical Association. 2002;97(460):1081–1089. https://doi.org/10.1198/016214502388618898

4. Choi W., Lee J.W., Huh M.-H., Kang S.-H. An Algorithm for Computing the Exact Distribution of the Kruskal-Wallis Test. Communications in Statistics – Simulation and Computation. 2003;32(4):1029–1040. https://doi.org/10.1081/SAC-120023876

5. Meyer J.P., Seaman M.A. A Comparison of the Exact Kruskal-Wallis Distribution to Asymptotic Approximations for All Sample Sizes up to 105. The Journal of Experimental Education. 2013;81(2):139–156. https://doi.org/10.1080/00220973.2012.699904

6. Hollander M., Wolfe D. Nonparametric statistical methods. Moscow: Finansy i statistika; 1983. 518 p. (In Russ.).

7. Odiase J.I., Ogbonmwan S.M. JMASM20: Exact Permutation Critical Values for The Kruskal-Wallis One-Way ANOVA. Journal of Modern Applied Statistical Methods. 2005;4(2). https://doi.org/10.22237/jmasm/1130804820

8. Spurrier J.D. On the Null Distribution of the Kruskal-Wallis Statistic. Journal of Nonparametric Statistics. 2003;15(6):685–691. https://doi.org/10.1080/10485250310001634719

9. Streitberg B., Rohmel J. Exact Distributions for Permutation and Rank Tests: An Introduction to Some Recently Published Algorithms. Statistical Software Newsletter. 1986;12(1):10–17.

10. Divine G.W., Norton H.J., Barón A.E., Juarez-Colunga E. The Wilcoxon-Mann-Whitney Procedure Fails as a Test of Medians. The American Statistician. 2018;72(3):278–286. https://doi.org/10.1080/00031305.2017.1305291

11. Hothorn T., Hornik K., van de Wiel M.A., Zeileis A. Implementing a Class of Permutation Tests: The Coin Package. Journal of Statistical Software. 2008;28(8):1–23. https://doi.org/10.18637/jss.v028.i08

12. Antipina N.M., Zakharov V.N., Protasov Yu.M., Yurov V.M. Non-Parametric Criterion of Difference for Two Related Samples in Table Editor MS Excel. Bulletin of Moscow Region State University. Series: Economics. 2021;(2):47–55. (In Russ.). https://doi.org/10.18384/2310-6646-2021-2-47-55

13. Lehmann E.L. Testing Statistical Hypothesis. New York: Wiley; 1986. 600 p.

14. Hettmansperger Th. Statistical Inference Based on Ranks. Moscow: Finansy i statistika; 1987. 334 p. (In Russ.).

15. Kobzar A.I. Applied mathematical statistics. For engineers and researchers. Moscow: FIZMATLIT; 2006. 816 p. (In Russ.).

16. Iman R.L., Davenport J.M. New approximations to the exact distribution of the kruskal-wallis test statistic. Communications in Statistics – Theory and Methods. 1976;5(14):1335–1348. https://doi.org/10.1080/03610927608827446

17. Mood A.M. On the Asymptotic Efficiency of Certain Nonparametric Two-Sample Tests. The Annals of Mathematical Statistics. 1954;25(3):514–522.

18. Ansari A.R., Bradley R.A. Rank-Sum Tests for Dispersions. The Annals of Mathematical Statistics. 1960;31(4):1174–1189.