ПОРІВНЯЛЬНИЙ АНАЛІЗ МЕТОДІВ ТЕСТУВАННЯ НЕЗАЛЕЖНОСТІ ПОСЛІДОВНОСТЕЙ ПСЕВДОВИПАДКОВИХ ЧИСЕЛ
COMPARATIVE ANALYSIS OF METHODS FOR TESTING THE INDEPENDENCE OF PSEUDO-RANDOM NUMBER SEQUENCES
Сторінки: 258-265. Номер: №6, 2023 (329) 
Автори:
ОДЕГОВ МИКОЛА
Державний університет інтелектуальних технологій і зв’язку
https://orcid.org/ 0000-0001-5526-2487
onick_64@ukr.net
ГАДЖИЄВ МАТІН
Державний університет інтелектуальних технологій і зв’язку
http://orcid.org/0000-0001-7280-3863
gadjievmm@ukr.net
КАЛІНІНА ТЕТЯНА
Державний університет інтелектуальних технологій і зв’язку
https://orcid.org/0000-0002-3184-3604
kalininat384@gmail.com
ПЕТРОВИЧ ЯННА
Державний університет інтелектуальних технологій і зв’язку
https://orcid.org/0009-0008-8939-2333
yanna-petrovich@ukr.net
АНДРІЙЧЕНКО КИРИЛО
Державний університет інтелектуальних технологій і зв’язку
almelovetm@gmail.com
NICK ODEGOV, MATIN HADZHYIEV, TETIANA KALININA, YANNA PETROVICH, KYRYLO ANDREICHENKO
State University of Intellectual Technologies and Communication
DOI: https://www.doi.org/10.31891/2307-5732-2023-329-6-258-265
Анотація мовою оригіналу
У задачах статистичного та імітаційного моделювання можуть використовуватись послідовності псевдовипадкових чисел дуже великої довжини. При цьому виникає необхідність вирішення задач класу Big Data. Вирішення таких задач іноді потребує дещо нехтувати точністю рішень, щоб отримати практично прийнятні результати досліджень у прийнятний час.
На даний час розроблена значна кількість систем тестування послідовностей псевдовипадкових чисел (ПВЧ) на відповідність досить умовному поняттю «випадковості», тобто неможливості прогнозувати їх окремі значення. Хоча, ПВЧ при цьому генеруються за допомогою регулярних алгоритмів. Парадигмою даної роботи є вимога відповідності емпіричних функцій розподілення ПВЧ теоретичним функціям розподілення.
Для одновимірних (маргінальних) розподілень дана задача вирішується досить просто. Більш складною є задача встановлення характеристик статистичної залежності або незалежності ПВЧ. Для пари ПВЧ довжини N найбільш логічним є метод повної перевірки їх незалежності (МПВ). Суть даного методу полягає у встановленні відхилення добутків значень ймовірностей від теоретичних. Даний метод зводиться до алгоритмів порядку NxN.
У попередніх роботах розглядались алгоритми методу критерія сум (МКС), який зводиться до аналізу сум значень ПВЧ. При цьому у випадку статистичної незалежності розподілення суми матиме вид згортки маргінальних розподілень. Порядок даного алгоритму лише N.
У даній роботі виконано порівняльний аналіз МПВ та МКС за показниками надійності та швидкості. Штучна залежність ПВЧ при цьому моделювалась внесенням певного рівня кореляції. Порівняльний аналіз показав, що за показником надійності обидва методи приблизно однакові. За показником швидкості МКС на порядки (пропорційно N ) є більш ефективним, ніж МПВ.
Остаточно зроблено висновок, що для задач моделювання класу Big Data слід віддавати перевагу МКС.
Ключові слова: випадкові числа, імітаційне моделювання, кореляція, статистична незалежність, генератори випадкових чисел, рівномірне розподілення, критерій Колмогорова.
Розширена анотація англійською мовою
Very long sequences of pseudorandom numbers can be used in statistic and simulation modeling tasks. At the same time, there is a need to solve problems of the Big Data class. Solving such problems sometimes requires a slight disregard for accuracy in order to obtain practically acceptable research results in an acceptable time.
Currently, a significant number of systems for testing sequences of pseudo-random numbers (PRN) has been developed for compliance with the rather conventional concept of “randomness”, that is, the impossibility of predicting their individual values. However, PRNs are generated using regular algorithms. The paradigm of this work is the requirement to match the empirical distribution functions of PRN with the theoretical distribution functions.
For one-dimensional (marginal) distributions, this problem is solved quite simply. The task of establishing the characteristics of statistical dependence or independence of PRN is more difficult. For a pair of PRNs of length N, the most logical method is the method of complete verification of their independence (CVM). The essence of this method is to establish the deviation of the products of the imperial values of the probabilities from the theoretical ones. This method is reduced to NxN algorithms.
In previous works, the algorithms of the sum criterion method (SCM) were considered, which is reduced to the analysis of the sums of PRN values. At the same time, in the case of statistical independence, the sum distribution will have the form of a convolution of marginal distributions. The order of this algorithm is only N.
In this paper, a comparative analysis of CVM and SCM was performed based on reliability and speed indicators. At the same time, the artificial dependence of PRN was modeled by introducing a certain level of correlation. Comparative analysis showed that both methods are approximately the same in terms of reliability. In terms of speed, the SCM is orders of magnitude (in proportion to N ) more efficient than the CVM one.
Finally, it was concluded that ISS should be preferred for Big Data modeling tasks.
Keywords: random numbers, simulation modeling, correlation, statistical independence, random number generators, uniform distribution, Kolmogorov criterion.
