РАСЧЕТ КОЛИЧЕСТВА РЕШЕНИЙ УРАВНЕНИЯ ПЕРВОЙ КРАТНОСТИ ТИПОВ В УСЛОВИЯХ ОГРАНИЧЕНИЙ НА ЧАСТОТУ ВСТРЕЧАЕМОСТИ ЗНАКОВ АЛФАВИТА

  • A.K. Мельников
Ключевые слова: Вероятность, статистика, точное распределение, точное приближение, вектор кратности типов, линейное уравнение, алгоритмическая сложность

Аннотация

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

Литература

1. Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti simmetrichnykh
additivno razdelyaemykh statistik i oblast' primeneniya predel'nykh raspredeleniy [The complexity
of calculating the exact probability distributions of symmetric additive-separated statistics
and the application of limit distributions], Doklady TUSUR [Proceedings of Tomsk State
University]. Tomsk, 2017, Vol. 20, No. 4, pp. 126-130. ISSN 1818-0442.
2. 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 distribution of statistical values]
Informatika i ee primeneniya [Informatics and its applications], 2016, Vol. 10, Issue 4,
pp. 91-97. ISSN 1992-2264.
3. Melnikov A.K. Application of the calculation method of near-exact statistics probability distributions,
Obozrenie prikladnoy i promyshlennoy matematiki [Review of Applied and Industrial
Mathematics], 2018, Vol. 25, Issue 2, pp. 153-154. ISSN 0869-8325. Available at:
https://tvp.ru/conferen/vsppmXIX/repso050.pdf (accessed 24 January 2019).
4. Yudin D.B., Yudin A.D. Matematiki izmeryayut slozhnost' [Mathematicians measure complexity].
Moscow: Knizhnyy dom "LIBROKOM", 2018, 192 p. ISBN 978-5-397-06042-4.
5. Borovkov A.A. Matematicheskaya statistika [Mathematical statistics]. Novosibirsk: Izd-vo IM
SORAN, Nauka, 1997, 772 p.
6. Kolchin V.F., Sevast'yanov B.A., Chistyakov V.P. Sluchaynye razmeshcheniya [Random
placements]. M.: Nauka, Glavnaya redaktsiya fiziko-matematicheskoy literatury, 1976, 224 p.
7. Sachkov V.N. Vvedenie v kombinatornye metody diskretnoy matematiki [Introduction to combinatorial
methods of discrete mathematics]. Moscow: Nauka. Gl. red. fiz.-mat. lit., 1982, 384 p.
8. Zuev Yu.A. Sovremennaya diskretnaya matematika: Ot perechislitel'noy kombinatoriki do
kriptografii XXI veka [Modern discrete mathematics: From enumerative combinatorics to
cryptography of the XXI century]. Moscow: LENARD, 2019, 720 p. (Fundamentals of
Information security No. 17). ISBN 978-5-9710-5660-7.
9. Zuev Yu.A. Sovremennaya diskretnaya matematika: Ot perechislitel'noy kombinatoriki do
kriptografii XXI veka. Bolee 700 zadach s resheniyami [Sovremennaya diskretnaya
matematika: Ot perechislitel'noy kombinatoriki do kriptografii XXI veka]. Moscow:
LENARD, 2019, 304 p. (Osnovy zashchity informatsii No. 18). ISBN 978-5-9710-5662-1.
10. Kholl M. Kombinatorika [Combinatorial theory]. Moscow: Mir, 1970, 424 p.
11. http://www.problems.ru/view_problem_details_new.php?id=30719.
12. Endryus G. Teoriya razbieniy [The theory of partitions]: transl. from engl. Moscow: Nauka.
Gl. red. fiz.-mat. lit., 1982, 256 p.
13. Dzh. Riordan. Vvedenie v kombinatornyy analiz [Introduction to combinatorial analysis].
Moscow.: Izd-vo inostrannoy lit., 1963, 288 p.
14. Dzh. Riordan. Kombinatornye tozhdestva [Combinatorial identities]. Moscow: Nauka. Gl. red.
fiz.-mat. lit., 1982, 255 p.
15. Fisher R.A. Statisticheskie metody dlya issledovateley [Statistical methods for research workers]:
transl. from engl. Moscow: Gosstatizdat, 1958, 73 p.
16. Mel'nikov A.K. Otnositel'naya algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy
raspredeleniy veroyatnostey znacheniy statistik [Relative algorithmic complexity of exact approximations
for probability distributions of statistics values], Modeli, metody i tekhnologii
intellektual'nogo upravleniya (IU-2019): Mater. 12-y Mul'tikonferentsii po problemam
upravleniya (MKPU-2019) [Models, methods and technologies of intelligent management (IU-
2019): Materials of the 12th Multi-Conference on Management Problems (ICPU-2019)]: i
n 4 vol. Vol. 1. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2019, pp. 108-112. ISBN 978-5-
9275-3189-9.
17. Mel'nikov A.K. Otnositel'naya algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy
raspredeleniy veroyatnostey znacheniy statistik [Relative algorithmic complexity of exact approximations
for probability distributions of statistics values], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2019, No. 7 (209), pp. 35-45.
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 27noyabrya 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. Application № 2018662123. Date of filing – November 01, 2018.
Date of state registration in the Register of computer software – November 27, 2018].
19. Mel'nikov A.K. Metodika rascheta raspredeleniya veroyatnostey znacheniy simmetrichnykh
additivno razdelyaemykh statistik, priblizhennykh k ikh tochnomu raspredeleniyu [A method
for calculating the probability distribution of values of symmetric additively separated statistics
that are close to their exact distribution], Nauchnyy vestnik NGTU [Science bulle-tin of the
Novosibirsk state technical university], 2018, No. 1 (70), pp. 153-166. ISBN 1814-1196. Doi:
10.17212/1814-1196-2018-1-153-166.
20. Hutchinson T.P. 1979. The validity of the chi-squared test when expected frequencis are small:
A list of recent research references, Commun. Stat. A Theor., Vol. 8, No. 4, pp. 327-335.
Опубликован
2021-02-25
Выпуск
Раздел
РАЗДЕЛ II. МАТЕМАТИЧЕСКОЕ И СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ СУПЕРКОМПЬЮТЕРОВ