Многоуровневое расщепление в методе Монте-Карло для оценки вероятностей редких событий в пермутационных тестах

Введение. Пермутационные тесты широко применяются при проведении статистического анализа, например, когда нарушаются предположения параметрических тестов или распределение данных неизвестно. Заметим, что в случае применения классических пермутационных тестов могут возникнуть проблемы при попытке оценки вероятностей редких событий с высокой относительной точностью. Это приводит к трудностям при использовании поправки на множественную проверку статистических гипотез. В работе предлагается оригинальный метод оценки произвольно малых P-значений в пермутационных тестах, который основан на многоуровневом расщеплении в методе Монте-Карло. Метод. Представленный метод включает дробление исходного пространства перестановок на непересекающиеся уровни по значениям статистики. Метод дает возможность свести задачу оценки исходной вероятности редкого события к задаче оценки обычных условных вероятностей для каждого уровня. Использование метода позволяет эффективным образом оценивать искомые P-значения, сохраняя баланс между временем работы и уровнем относительной ошибки. Основные результаты. Работа метода продемонстрирована в применении к задаче оценки произвольных P-значений двухвыборочного теста Колмогорова–Смирнова. Сравнение результатов работы метода с истинными P-значениями подтвердило практическую сходимость метода. Показаны примеры превосходства предлагаемого метода над альтернативными асимптотическими подходами. Обсуждение. Предлагаемый метод выявил существенный потенциал применения в широком спектре научных областей, таких как системная биология, иммунология и других. Метод может быть адаптирован для использования в различных случаях статистическог о анализа, который требует работы с вероятностями редких событий в пермутационных тестах.

1. Good P. Permutation Tests: A Practical Guide to Resampling Methods for Testing Hypotheses. Springer Science & Business Media, 2013.

2. Pesarin F., Salmaso L. Permutation Tests for Complex Data: Theory, Applications and Software. John Wiley & Sons, 2010. 448 p.

3. Hammersley J. Monte Carlo Methods. Springer Science & Business Media, 2013. 178 p.

4. Kalos M.H., Whitlock P.A. Monte Carlo Methods. John Wiley & Sons, 2009. 215 p.

5. Trendelkamp-Schroer B., Noé F. Efficient estimation of rare-event kinetics // Physical Review X. 2016. V. 6. N 1. P. 011009. https://doi.org/10.1103/physrevx.6.011009

6. Lestang T., Ragone F., Bréhier C.-E., Herbert C., Bouchet F. Computing return times or return periods with rare event algorithms // Journal of Statistical Mechanics: Theory and Experiment. 2018. V. 2018. N 4. P. 043213. https://doi.org/10.1088/1742-5468/aab856

7. Caron V., Guyader A., Zuniga M.M., Tuffin B. Some recent results in rare event estimation // ESAIM: Proceedings. 2014. V. 44. P. 239– 259. https://doi.org/10.1051/proc/201444015

8. L’Ecuyer P., Demers V., Tuffin B. Splitting for rare-event simulation // Proc. of the 2006 Winter Simulation Conference. 2006. P. 137–148. https://doi.org/10.1109/wsc.2006.323046

9. Glasserman P., Heidelberger P., Shahabuddin P., Zajic T. Multilevel splitting for estimating rare event probabilities // Operations Research. 1999. V. 47. N 4. P. 585–600. https://doi.org/10.1287/opre.47.4.585

10. Botev Z.I., Kroese D.P. An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting // Methodology and Computing in Applied Probability. 2008. V. 10. N 4. P. 471–505. https://doi.org/10.1007/s11009-008-9073-7

11. Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E. Equation of state calculations by fast computing machines // The Journal of Chemical Physics. 1953. V. 21. N 6. P. 1087–1092. https://doi.org/10.1063/1.1699114

12. Hastings W.K. Monte Carlo sampling methods using Markov chains and their applications // Biometrika. 1970. V. 57. N 1. P. 97–109. https://doi.org/10.2307/2334940

13. Kolmogorov A. Sulla determinazione empirica di una legge di distribuzione // Giornale dell’Istituto Italiano degli Attuari. 1933. V. 4. P. 83–91.

14. Smirnoff N. Sur les Écarts de la courbe de distribution empirique // Matematicheskii Sbornik. 1939. V. 48. N 1. P. 3–26.

15. Virtanen P., Gommers R., Oliphant T.E., Haberland M., Reddy T., Cournapeau D., Burovski E., Peterson P., Weckesser W., Bright J. et. al. SciPy 1.0: fundamental algorithms for scientific computing in Python // Nature Methods. 2020. V. 17. N 3. P. 261–272. https://doi.org/10.1038/s41592-019-0686-2