ОТНОСИТЕЛЬНАЯ АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК

  • А. К. Мельников НТЦ ЗАО «ИнформИнвестГрупп»
Ключевые слова: Вероятность, статистика, точное распределение, точное приближение, вектор кратности типов, линейное уравнение, алгоритмическая сложность

Аннотация

Рассматривается относительная алгоритмическая сложность расчета точных распределений вероятностей значений статистик и их точных приближений. В качестве точных приближений распределений вероятностей значений статистик рассматривают-ся их Δточные распределения, отличающиеся от точных распределений не более чем на заранее заданную, сколь угодно малую величину Δ. Показывается, что основой метода рас-чета точных распределений вероятностей значений статистик является перечисление элементов области поиска решений линейного уравнения, составляемого из векторов кратности типов, каждый элемент которого представляет число вхождения элементов определенного типа в рассматриваемую выборку. Одновременно показывается, что длярасчета точных приближений распределения вероятностей значений статистик применя-ется метод ограничения области поиска решений. Приводится разбиение области пара-метров, представляемых объемом выборок и мощностью алфавита, для которых рас-сматриваются распределения вероятностей значений статистик, на непересекающиеся области предельных и точных распределений. Оценка относительной алгоритмической сложности расчета точных распределений вероятностей значений статистик и их точ-ных приближений проводится для параметров расположенных на верхней границе области точных распределений, определяемой соотношением Фишера. Для оценки алгоритмической сложности расчета точных приближений распределения вероятностей значений стати-стик в качестве параметра ограничения области поиска решений линейного уравнения, составленного из векторов кратности типов, используется значение статистики макси-мальной частоты, вероятность превышение которого меньше заранее заданной, сколь угодно малой величины Δ. Приводятся примеры расчета значений параметра ограничения области поиска решений линейного уравнения кратности типов для значений параметров объема выборки и мощности алфавита, связанных соотношением Фишера, определяющим границу раздела областей параметров применения точных и предельных распределений. Приводится наглядная иллюстрация ограничение области поиска решения линейного урав-нения кратности типов для мощности алфавита равной трем. Приведены значения отно-шения алгоритмической сложности расчетов точных распределений вероятностей значе-ний статистик к алгоритмической сложности расчета их точных приближений для мощ-ностей алфавита от 2 до 256 и объемов выборок, соответствующих соотношению Фишера. Показано, что алгоритмическая сложность расчета точных распределений вероятно-стей значений статистик на много порядков превосходит сложность расчета их точных приближений и это отношение увеличивается с увеличением мощности алфавита.

Литература

1. Chepovskiy A.M. Informatsionnye modeli v zadachakh obrabotki tekstov na estestvennykh yazykakh [Information models in tasks of processing of natural language texts]. Moscow: Natsional'nyy otkrytyy universitet «INTUIT», 2015, 228 p. ISBN 978-5-9556-0176-2.
2. Fisher R. A. Statisticheskie metody dlya issledovateley [Statistical methods for research work-ers]: transl. from engl. Moscow: Gosstatizdat, 1958, 73 p.
3. Feller V. Vvedenie v teoriyu veroyatnostey i ee prilozheniya [Introduction to probability theo-ry and its applications]. In 2 vol. Vol. 1: transl. from engl. Moscow: Mir, 1984, 528 p.
4. Kramer G. Matematicheskie metody statistiki [Mathematical methods of statistics]. Moscow: Mir, 1975, 648 p.
5. Mel'nikov A.K., Ronzhin A.F. Obobshchennyy statisticheskiy metod analiza tekstov, osnovannyy na raschete raspredeleniy veroyatnosti znacheniy statistik [Generalized statistical method of text analysis based on calculation of probability distributions of statistical values], Informatika i ee primeneniya [Informatics and its applications], 2016, Vol. 10, Issue 4, pp. 91-97. ISSN 1992-2264.
6. Borovkov A.A. Veroyatnostnye protsessy v teorii massovogo obsluzhivaniya [Probabilistic processes in queuing theory]. Moscow: Nauka, 1972, 367 p.
7. Kendall M.G., St'yuart A. Teoriya raspredeleniy [Distribution theory]. Moscow: Nauka, 1966, 302 p.
8. Beirlant J., Goegebeur Y., Teugels J., Segers J. Statisticas of Extremes: Theory and Applica-tions. Wiley, Chichester, 2004.
9. Ivchenko G.I., Medvedev Yu.I. Vvedenie v matematicheskuyu statistiku [Introduction to math-ematical statistics]. Moscow: LENARD, 2017, 608 p. ISBN 978-5-9710-4535-9.
10. Mel'nikov A.K. Primenenie tochnykh i predel'nykh priblizheniy raspredeleniy veroyatnostey znacheniy statistik pri reshenii zadachi obrabotke tekstov [Application of exact and limit ap-proximations of statistics probability distributions for the problem of text processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (202), pp. 114-135.
11. Mel'nikov A.K. Sravnenie effektivnosti obrabotki tekstov pri primenenii v statisticheskikh kriteriyakh tochnykh i predel'nykh priblizheniy bazovykh raspredeleniy veroyatnostey znacheniy testovykh statistik [Comparison of the efficiency of text processing when using ac-curate and limiting approximations of basic probability distributions for test statistics in statis-tical criteria], Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied and in-dustrial mathematics], 2018, Vol. 25, Issue 4, pp. 375-378. ISSN 0869-8325. Available at: https://tvp.ru/conferen/vsppmXIX/repso114.pdf (accessed 14 January 2019).
12. Pearson K. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables in such that it can be reasonably supposed to have arisen from random sampling, Philos. Mag. Ser. 5, 1900, Vol. 50, No. 302, pp. 157-170.
13. Smith P.F., Rae D.S., Manderscheid R.W., Silbergel D.S. Exact and approximate distributions of the chi-squared statistic for equiprobability, Commun. Stat., 1979, Vol. 8, No. 2, pp. 131-149.
14. Mel'nikov A.K. Metodika rascheta raspredeleniy veroyatnostey znacheniy statistik, blizkikh k ikh tochnym raspredeleniyam [Methods for calculating probability distributions of statistical values close to their exact distributions], Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied and industrial mathematics], 2017, Vol. 24, Issue 5, pp. 320-323. Available at: http://tvp.ru/conferen/vsppmXVIII/kisso075.pdf (accessed 13 July 2018).
15. Mel'nikov A.K. Metodika rascheta raspredeleniya veroyatnostey znacheniy simmetrichnykh additivno razdelyaemykh statistik, priblizhennykh k ikh tochnomu raspredeleniyu [Method of calculating the probability distribution of values of symmetric additive-separated statistics, ap-proximated to their exact distribution], Nauchnyy vestnik NGTU [Science bulletin of the Novo-sibirsk state technical university], 2018, No. 1 (70), pp. 153-166. ISBN 1814-1196. Doi: 10.17212/1814-1196-2018-1-153-166.
16. Mel'nikov A.K. Napravlenie modernizatsii chastotnogo metoda rascheta tochnykh raspredeleniy veroyatnostey znacheniy statistik [Direction of modernization of the frequency method for calculating exact probability distributions of statistical values], Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied and industrial mathematics], 2017, Vol. 24, Issue 5, pp. 324-325. Available at: https://tvp.ru/conferen/vsppmXVIII/kisso073.pdf (accessed 12 July 2018).
17. Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti simmetrichnykh additivno razdelyaemykh statistik i oblast' primeneniya predel'nykh raspredeleniy [The com-plexity of calculating exact probability distributions of symmetric additively separated statis-tics and the scope of limit distributions], Doklady TUSUR [Proceedings of Tomsk State Uni-versity of Control Systems and Radioelectronics]. Tomsk, 2017, Vol. 20, No. 4, pp. 126-130. ISSN 1818-0442.
18. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2018664980. Raschet veroyatnostey znacheniy statistiki maksimal'noy chastoty. Pravoobladatel' Mel'nikov A.K. Avtor: Mel'nikov A.K. i Zelyukin N.B. Zayavka № 2018662123. Data postupleniya 01 noyabrya 2018 g. Data gosudarstvennoy registratsii v Reestre programm dlya EVM 27 noyabrya 2018 g. [Certificate of state registration of computer software № 2018664980. Calculation of probabilities of maximum frequency statistics. Proprietor – A.K. Melnikov. Authors: A.K. Melnikov and N.B. Zeliukin. Ap-plication № 2018662123. Date of filing – November 01, 2018. Date of state registration in the Reg-ister of computer software – November 27, 2018].
19. Zelyukin N.B., Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti znacheniy statistik i oblast' primeneniya predel'nykh raspredeleniy [The complexity of calcu-lating accurate probability distributions of statistical values and the scope of application of limit distributions], Elektronnye sredstva i sistemy upravleniya: Mater. dokladov XIII Mezhdunar. nauch.-prakt. konf. (29 noyabrya – 1 dekabrya 2017 g.) [Electronic facilities and control systems: reports of the XIIIth International scientific and practical], 29th November – 1st December, 2017]: In 2 part. Part 2. Tomsk: V-Spektr, 2017, S. 84-90. Available at: https://storage.tusur.ru/files/115115/2017-2.pdf (accessed 13 July 2018).
20. Mel'nikov A.K. Avtomatizatsiya protsedury analiza soobshcheniy na gibridnykh vysokoproizvoditel'nykh vychislitel'nykh kompleksakh [Automation of the message analysis proce-dure on hybrid high-performance computing systems], Superkomp'yuternye tekhnologii (SKT-2016): Mater. 4-y Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Supercomputing technologies (SKT-2016): Proceedings of the 4th all-Russian scientific and technical conference]: In 2 vol. Vol. 1. Rostov-on-Don: Izd-vo YuFU, 2016, pp. 69-73. ISBN 978-5-9275-2039-8.
Опубликован
2020-05-02
Выпуск
Раздел
РАЗДЕЛ I. МОДЕЛИ, МЕТОДЫ И ТЕХНОЛОГИИ ИНТЕЛЛЕКТУАЛЬНОГО УПРАВЛЕНИЯ