|
DOI: 10.14489/vkit.2021.06.pp.039-048
Мельников А. К.
ВЫБОР МЕТОДА РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ ДИСКРЕТНЫХ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК
(с 39-48)
Аннотация. Рассмотрены методы расчета точных приближений распределений вероятностей значений статистик, в качестве которых используются ∆-точные распределения. Они отличаются от точных распределений не более чем на заранее заданную сколь угодно малую величину ∆, определяющую точность приближений. На основе сравнения вычислительной сложности методов расчета первой и второй кратности делается вывод о предпочтительном использовании метода второй кратности, позволяющего при одинаковых ограничениях вычислительного ресурса и точности вычислять точные приближения распределений для большего числа выборок с большими значениями параметров.
Ключевые слова: вероятность; статистика; точное распределение; точное приближение; вектор кратности типов; система линейных уравнений; алгоритмическая сложность; вычислительный ресурс.
Melnikov А. K.
ABOUT CHOOSING THE METHOD OF EXACT APPROXIMATIONS OF DISCRETE STATISTICS PROBABILITY DISTRIBUTIONS
(pp. 39-48)
Abstract. In the paper, we consider the methods of exact approximations of statistics probabilities distribution. As the exact approximations, we consider ∆-exact distributions. The difference between the ∆-exact distributions and the exact approximations does not exceed a predefined arbitrary small value ∆ that defines the accuracy of the approximations. Besides, we consider the methods of the first and second multiplicity, which use statistic characteristics of samples. The first multiplicity method is based on the properties of the components of the first multiplicity vector, which are nonnegative integer solutions of a linear equation. The linear equation relates the alphabet sign frequency and the sample size. The second multiplicity method is based on the solution of a system of linear equations. The linear equations of the system relate the sample size and the alphabet cardinality with the number of the alphabet signs that have equal frequency in the sample. For the considered methods of exact approximations, we give expressions to estimate the computational complexity of exact approximations of distributions for any sample parameters. To provide the approximations accuracy of 10–5, and the computing resource with the performance of 1018 operations per second, we calculated the sample parameters. For these samples, we can calculate the exact approximations of distributions, using the considered methods, the available computing resource, and the declared accuracy. We formed the parameter regions for the samples, and the exact approximations of distributions can be calculated for these samples with the help of various methods. We compared the regions themselves and with the so-called region of uncertainty, which is limited from above not more than 5-fold excess of the sample size over the alphabet cardinality. On the base of the comparison of the parameter regions of the samples, which are suitable for calculation of the exact approximations of the distributions, we compared their calculation methods. It is shown that owing to the second multiplicity method, we can make calculations for all values of the alphabet cardinality from 2 to 256. In contrast to the second multiplicity method, the first multiplicity method does not allow calculations for the alphabet cardinality over 73. The parameter region of the samples, which are suitable for calculation of the limit approximations of the distributions by the second multiplicity method, contains the complete parameter region of the samples, suitable for calculation of the limit approximations of the distributions by the first multiplicity method, and exceeds it more than in 52 times. Owing to the comparison of the methods of exact approximations, it is proved that if we have the same computing resource, we can calculate the exact approximations with the help of the second multiplicity method for a greater number of samples with the increased parameters in comparison with the first multiplicity method. Hence, to calculate the exact approximations of statistics probability distributions, we choose the second multiplicity method. Practical significance of the research is possibility of calculation of the maximal values of the sample parameters. The current technological level of computer systems allows calculation of the exact approximations of the distributions for these values, which provide the minimal loss of criteria efficiency in comparison with the limit approximations used for the sample parameters. The scientific novelty of the research is the comparative analysis of the methods of exact approximations of distributions for calculation of distributions for the sample parameters, which do not allow calculation of the exact distributions due to their high computational complexity.
Keywords: Probability; Statistics; Exact distribution; Exact approximation; Vector of type order; System of linear equations; Algorithmic complexity; Computing resource.
А. К. Мельников (АО «Вычислительные решения», Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
А. K. Melnikov (SC “Computing Solutions”, Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Мельников А. К. Сравнение эффективности обработки текстов при применении в статистических критериях точных и предельных приближений базовых распределений вероятностей значений тестовых статистик // Обозрение прикладной и промышленной математики. 2018. Т. 25, вып. 4. С. 375 – 378.
2. Мельников А. К. Применение точных распределений в процедуре двухэтапной обработки текстов // Обозрение прикладной и промышленной математики. 2018. Т. 25, вып. 2. С. 89 – 95.
3. Зелюкин Н. Б., Мельников А. К. Сложность расчета точных распределений вероятности значений статистик и область применения предельных распределений // Электронные средства и системы управления: материалы докл. XIII Междунар. науч.-практ. конф. (29 ноября – 1 декабря 2017 г.). № 1–2. Томск: Томский гос. ун-т систем управления и радиоэлек-троники, 2017. С. 84 – 90.
4. Мельников А. К. Сложность расчета точных распределений вероятности симметричных аддитивно разделяемых статистик и область применения предельных распределений // Доклады ТУСУР. 2017. Т. 20, № 4. С. 126 – 130.
5. Шурыгин В. А. Сложностный метод теории алгоритмов. М.: ЛЕНЕРД, 2020. 376 с.
6. Чеповский А. М. Информационные модели в задачах обработки текстов на естественных языках. М.: Национальный открытый университет «ИНТУИТ», 2015. 228 с.
7. Pearson K. On the Criterion that a Given System of Deviations from the Probale in the Case of a Correlated System of Variables in Such that it Can be Reasonably SupPosed to Have Arisen From Random Sampling // Phil. Mag. 1900. V. 50, pp. 157 – 170.
8. Мельников А. К. Анализ точных и предельных приближений распределений вероятностей значений статистик // Суперкомпьютерные технологии (СКТ–2018): матер. 5-й Всерос. науч.-техн. конференции: в 2 т. Ростов-на-Дону; Таганрог: Изд-во Южного федерального университета, 2018. Т. 1. С. 100 – 104.
9. Мельников А. К., Ронжин А. Ф. Обобщенный статистический метод анализа текстов, основанный на расчете распределений вероятности значений статистик // Информатика и ее применения. 2016. Т. 10, вып. 4. С. 91 – 97, ISSN 1992-2264. DOI 10.14357/19922264160409
10. Зуев Ю. А. Современная дискретная математика: от перечислительной комбинаторики до криптографии XXI века. М.: ЛЕНАРД, 2019. 720 с.
11. Мельников А. К. Направление модернизации частотного метода расчета точных распределе-ний вероятностей значений статистик // Обозрение прикладной и промышленной математики. 2017. Т. 24, вып. 5. С. 324–325.
12. Эндрюс Г. Теория разбиений: пер. с англ. М.: Наука. Гл. ред. физ.-мат. лит., 1982. 256 с.
13. Мельников А. К. Методика расчета распределения вероятностей значений симметричных аддитивно разделяемых статистик, приближенных к их точному распределению // Научный вестник НГТУ. 2018. № 1(70). С. 153 – 166. DOI 10.17212/1814-1196-2018-1-153-166
14. Мельников А. К. Алгоритмическая сложность расчета точных приближений распределений вероятностей значений статистик // Суперкомпью-терные технологии: сб. трудов молодых ученых / под ред. академика РАН И. А. Каляева. Ростов-на-Дону; Таганрог: Изд-во Южного федерального университета, 2020. С. 66 – 70.
15. Мельников А. К. Алгоритмическая сложность расчета точных приближений распределений вероятностей значений статистик методом решения уравнения первой кратности типов // Изв. ЮФУ. Технические науки. Тематический выпуск. Суперкомпьютерные технологии. 2021. № 7, ноябрь (217). С. 52 – 67. DOI 10.18522/2311-3103-2020-7-52-67
16. Melnikov A. K. Application of the Calculation Method of Near-Exact Statistics Probability Distributions // Обозрение прикладной и промышленной математики. 2018. Т. 25, вып. 2. С. 153–154.
17. Свидетельство о государственной регистрации программы для ЭВМ 2018664980 Российская Федерация. Расчет вероятностей значений статистики максимальной частоты / А. К. Мельников, Н. Б. Зелюкин; заявитель и правообладатель А. К. Мельников; заявл. 01.112018; опубл. 27.11.2018. 1 с.
18. Мельников А. К. Расчет количества решений уравнения первой кратности типов в условиях ограничений на частоту встречаемости знаков алфавита // Изв. ЮФУ. Технические науки. Тематический выпуск. Суперкомпьютерные технологии. № 7, ноябрь (217), С. 68 – 78. DOI 10.18522/2311-3103-2020-7-68-78
19. Свидетельство о государственной регистрации программы для ЭВМ 2021612036 Российская Федерация. Расчет числа решений линейного уравнения первой кратности типов / А. К. Мельников; заявитель и правообладатель. № 2021611083; заявл. 02.02.2021; опубл. 10.022021. 1 с.
20. Свидетельство о государственной регистрации программы для ЭВМ № 2020664143 Российская Федерация. Расчет числа решений системы линейных уравнений второй кратности типов / А. В. Колодзей, А. К. Мельников; заявитель и правообладатель А. В. Колодзей. № 2020662473; заявл. 19.10.2020; опубл. 09.11.2020. 1 с.
21. Фишер Р. А. Статистические методы для исследователей / пер. с англ. М.: Госстатиздат, 1958. 73 с. (Fisher R. A. Statistical Methods for Research Workers. 12th ed. Edinburgh: Oliver and Boyd, 1954. 356 p.).
22. Neyman F., Pearson E. S. On the Use and Interpretation of Certain Test Criteria for Purposes of Statistical Inference // Biometrika. 1928. 20-A. pp. 175 – 240; 264 – 299.
1. Mel'nikov A. K. (2018). Comparison of the efficiency of text processing when using exact and limiting approximations of the basic probability distributions of test statistics values in statistical criteria. Obozrenie prikladnoy i promyshlennoy matematiki, Vol. 25, (4), pp. 375 – 378. [in Russian language]
2. Mel'nikov A. K. (2018). Applying Exact Distributions in a Two-Step Word Processing Procedure. Obozrenie prikladnoy i promyshlennoy matematiki, Vol. 25, (2), pp. 89 – 95. [in Russian language]
3. Zelyukin N. B., Mel'nikov A. K. (2017). The complexity of calculating exact probability distributions of statistical values and the scope of application of limiting distributions. Electronic means and control systems: collection of materials of reports of the XIII International Scientific and Practical Conference, in 2 parts. pp. 84 – 90. Tomsk: Tomsk State University of Control Systems and Radioelectronics. [in Russian language]
4. Mel'nikov A. K. (2017). Complexity of calculating exact probability distributions of symmetric additively separable statistics and the scope of application of limiting distributions. Doklady TUSUR, Vol. 20, (4), pp. 126 – 130. [in Russian language]
5. Shurygin V. A. (2020). Complexity method of the theory of algorithms. Moscow: LENERD. [in Russian language]
6. Chepovskiy A. M. (2015). Information models in natural language word processing problems. Moscow: Natsional'niy otkrytiy universitet «INTUIT». [in Russian language]
7. Pearson K. (1900). On the Criterion that a Given System of Deviations from the Probale in the Case of a Correlated System of Variables in Such that it Can be Reasonably SupPosed to Have Arisen From Random Sampling. Philosophical Magazine, Vol. 50, pp. 157 – 170.
8. Mel'nikov A. K. (2018). Analysis of Exact and Limiting Approximations of Probability Distributions of Statistic Values. Supercomputer technologies (SKT-2018): materials of the 5th All-Russian scientific and technical conference: in 2 volumes. Vol. 1, pp. 100 – 104. Rostov-na-Donu; Taganrog: Izdatel'stvo Yuzhnogo federal'nogo universiteta. [in Russian language]
9. Mel'nikov A. K., Ronzhin A. F. (2016). Generalized statistical method of text analysis based on the calculation of probability distributions of statistical values. Informatika i ee primeneniya, Vol. 10, (4), pp. 91 – 97, ISSN 1992-2264. [in Russian language] DOI 10.14357/19922264160409.
10. Zuev Yu. A. (2019). Modern discrete mathe-matics: from enumeration combinatorics to cryptography of the XXI century. Moscow: LENARD. [in Russian language]
11. Mel'nikov A. K. (2017). The direction of modernization of the frequency method for calculating the exact probability distributions of the values of statistics. Obozrenie prikladnoy i promyshlennoy matematiki, Vol. 24, (5), pp. 324 – 325. [in Russian language]
12. Endryus G. (1982). Partition theory. Moscow: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury. [in Russian language]
13. Mel'nikov A. K. (2018). Method for calculating the probability distribution of the values of symmetric additively separated statistics, close to their exact distribution. Nauchniy vestnik NGTU, 70(1), pp. 153 – 166. [in Russian language] DOI 10.17212/1814-1196-2018-1-153-166
14. Kalyaev I. A. (Ed.), Mel'nikov A. K. (2020). Algorithmic complexity of calculating exact approximations of probability distributions of statistical values. Supercomputer technologies: collection of works of young scientists, pp. 66 – 70. Rostov-na-Donu; Taganrog: Izdatel'stvo Yuzhnogo federal'nogo universiteta. [in Russian language]
15. Mel'nikov A. K. (2021). Algorithmic complexity of calculating exact approximations of probability distributions of statistics values by solving an equation of the first multiplicity of types. Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskiy vypusk. Superkomp'yuternye tekhnologii, 217(7), pp. 52 – 67. [in Russian language] DOI 10.18522/2311-3103-2020-7-52-67
16. Melnikov A. K. (2018). Application of the Calculation Method of Near-Exact Statistics Probability Distributions. Obozrenie prikladnoy i promyshlennoy matematiki, Vol. 25, (2), pp. 153–154.
17. Mel'nikov A. K., Zelyukin N. B. (2018). Calculating the probabilities of the maximum frequency statistics. Certificate of state registration of the computer program No. 2018664980. Russian Federation. [in Russian language]
18. Mel'nikov A. K. Calculation of the number of solutions to the equation of the first multiplicity of types under conditions of restrictions on the frequency of occurrence of alphabet characters. Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskiy vypusk. Superkomp'yuternye tekhnologii, 217(7), pp. 68 – 78. [in Russian language] DOI 10.18522/2311-3103-2020-7-68-78
19. Mel'nikov A. K. (2021). Calculation of the number of solutions to a linear equation of the first multiplicity of types. Certificate of state registration of a computer program No. 2021612036. Russian Federation. [in Russian language]
20. Kolodzey A. V., Mel'nikov A. K. (2020). Calculation of the number of solutions of a system of linear equations of the second multiplicity of types. Certificate of state registration of the computer program No. 2020664143. Russian Federation. [in Russian language]
21. Fisher R. A. (1958). Statistical Methods for Researchers. Moscow: Gosstatizdat. [in Russian language]
22. Neyman F., Pearson E. S. (1928). On the Use and Interpretation of Certain Test Criteria for Purposes of Statistical Inference. Biometrika, (20-A), pp. 175 – 240; 264 – 299.
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 450 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2021.06.pp.039-048
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 450 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2021.06.pp.039-048
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»