Компьютерная реализация точного распределения ранговых статистических критериев методами динамического программирования

В рамках настоящего исследования анализируется актуальная проблема, связанная с определением точных распределений для ранговых непараметрических критериев при отсутствии замкнутых аналитических решений. Классический подход, основанный на полном переборе всех возможных перестановок рангов, хотя и является теоретически точным, оказывается практически неприменимым уже для небольших объемов выборок вследствие комбинаторного взрыва числа вариантов. Прямой перебор всех возможных перестановок рангов, являющийся методом точного расчета, оказывается вычислительно неразрешимой задачей даже для выборок небольшого объема из-за комбинаторного взрыва. Рассмотрены наиболее известные ранговые непараметрические критерии, не имеющие аналитического решения для получения полной функции распределения, такие как критерии Лемана-Розенблата, Краскела-Уоллиса и Муда. Существующие аппроксимации (нормальная, хи-квадрат) часто оказываются неудовлетворительными для малых выборок. В работе предлагается эффективное решение на основе метода динамического программирования, позволяющее в сотни раз сократить вычислительные затраты по сравнению с наивной генерацией перестановок. Реализована методика, включающая генерацию последовательностей рангов, расчет статистик для каждой из них и последующую агрегацию результатов для построения функции распределения. Проведенные вычислительные эксперименты однозначно демонстрируют, что метод динамического программирования является наиболее эффективным для генерации точных распределений. Разработаны и представлены в открытом доступе программные реализации на C++ и Python, проведено их сравнительное тестирование, которое подтвердило ожидаемое лидерство C++ с точки зрения быстродействия.

1. Агамиров Л.В., Агамиров В.Л., Вестяк В.А. Численные методы и алгоритмы расчета точных распределений непараметрических критериев проверки статистических гипотез. Вестник Московского авиационного института. 2013;20(4):212–218.

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. Холлендер М., Вулф Д. Непараметрические методы статистики. Москва: Финансы и статистика; 1983. 518 c.

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. Антипина Н.М., Захаров В.Н., Протасов Ю.М., Юров В.М. Непараметрический критерий различия для двух связанных выборок в табличном редакторе MS Excel. Вестник Московского государственного областного университета Серия: Экономика. 2021;(2):47–55. 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. Хеттманспергер Т. Статистические выводы, основанные на рангах. Москва: Финансы и статистика; 1987. 334 с.

15. Кобзарь А.И. Прикладная математическая статистика. Для инженеров и научных работников. Москва: ФИЗМАТЛИТ; 2006. 816 с.

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.