О систематизации вероятностных свойств компонентов бинарной перестановочной процедуры

Оригинальная статья / Original article УДК: 519.233.5

DOI: 10.21285/1814-3520-2016-12-119-128

О СИСТЕМАТИЗАЦИИ ВЕРОЯТНОСТНЫХ СВОЙСТВ КОМПОНЕНТОВ БИНАРНОЙ ПЕРЕСТАНОВОЧНОЙ ПРОЦЕДУРЫ

© А.В. Петров1

Иркутский национальный исследовательский технический университет, 664074, Российская Федерация, г. Иркутск, ул. Лермонтова, 83.

РЕЗЮМЕ. ЦЕЛЬ. Целью исследования является нахождение методов оценивания нелинейных вероятностных зависимостей. МЕТОДЫ. Основные методы исследования - теоретический вероятностный анализ и численные методы. РЕЗУЛЬТАТЫ. Рассматривается перестановочная процедура генерирования бинарного случайного процесса. Особое внимание уделено рассмотрению и систематизации вероятностных свойств компонентов перестановочной процедуры. Проведено обобщение полученных результатов - законов распределения и автокорреляционных функций компонентов процедуры. ЗАКЛЮЧЕНИЕ. Перестановочная процедура генерирования бинарного процесса обеспечивает возможность генерирования случайных процессов с разнообразными вероятностными свойствами.

Ключевые слова: бинарный случайный процесс, характеристики взаимосвязи, генерирование, моментные функции, корреляция, метод вычисления.

Формат цитирования: Петров А.В. О систематизации вероятностных свойств компонентов бинарной перестановочной процедуры // Вестник Иркутского государственного технического университета. 2016. Т. 20. № 12. С. 119-128. DOI: 10.21285/1814-3520-2016-12-119-128

ON SYSTEMATIZATION OF THE PROBABILISTIC PROPERTIES OF BINARY PERMUTATION PROCEDURE

COMPONENTS

A.V. Petrov

Irkutsk National Research Technical University,

83, Lermontov St., Irkutsk, 664074, Russian Federation.

ABSTRACT. PURPOSE. The purpose of the study is to find the estimation methods for nonlinear probabilistic dependences. METHODS. The main research methods are theoretical probabilistic analysis and numerical methods. RESULTS. Consideration is given to the permutation procedure of generating a binary random process. Specific attention is paid to the examination and systematization of the probabilistic properties of permutation procedure components. The obtained results - distribution laws and autocorrelation functions of the procedure components - are generalized. CONCLUSION. Permutation procedure of binary process generation provides the possibility of generating random processes with various probabilistic properties.

Keywords: binary random process, relationship characteristic, generation, momentary functions, correlation, calculation method

For citation: Petrov A.V. On systematization of the probabilistic properties of binary permutation procedure components. // Proceedings of Irkutsk State Technical University. 2016, vol. 20, no. 12, pp. 119-128. (In Russian) DOI: 10.21285/1814-3520-2016-12-119-128

Введение

Рассмотренная в [1-4] процедура генерирования бинарного случайного процесса в случае двумерного вектора претендентов характеризуется присутствием определенного набора механизмов, кото-

рые по сути и формируют корреляционные зависимости. Для отыскания этих механизмов и лучшего понимания их функционирования необходимо систематизировать вероятностные свойства компонентов вектора

1

Петров Александр Васильевич, доктор технических наук, профессор кафедры автоматизированных систем, e-mail: petrov@istu.edu

Alexander V. Petrov, Doctor of technical sciences, Professor of the Department of Automated Systems, e-mail: petrov@istu.edu

information Science, Computer Engineering and Management

претендентов и генерируемых случайных процессов. В основу этой систематизации необходимо положить вероятностные свойства генерируемых случайных процес-

Предыстория возникнове

Проблема создания источников случайных цифр (чисел) была сформулирована довольно давно. И традиционно для развития научного процесса этап эйфории сменился этапом застоя и, наконец, наступило время планомерного развития. Первые применения случайных чисел связаны с методом Монте-Карло и не предъявляли особых требований к вероятностным свойствам генерируемых чисел. С появлением более сложных прикладных задач были разработаны методы генерирования гаус-совски распределенных случайных чисел с требуемой корреляционной зависимостью. И, наконец, в 1963 году М. Пелегреном [5] была сформулирована задача генерирования случайных чисел с одновременно задаваемыми законом распределения вероятностей и автокорреляционной зависимостью.

Существует много подходов к построению источников случайных цифр (чисел). В основном они связаны с техникой математических преобразований. Эти преобразования реализуют целенаправленные пересчеты исходных случайных чисел с простейшими вероятностными свойствами по специально сконструированным правилам, обеспечивающим получение требуемых вероятностных свойств. (Простейшими будем считать свойства равномерного распределения и некоррелированности генерируемых цифр).

Поставленная М. Пелегреном задача наглядно показала, что практически невозможно найти такие универсальные методы пересчета, которые бы позволили одновременно получать и заданный негаус-совский закон распределения вероятностей, и требуемую автокорреляционную функцию. Решение этой проблемы иным способом было найдено в Иркутском политехническом институте Е.И. Поповым и

сов: одномерные законы распределения вероятностей и автокорреляционные функции.

перестановочных процедур

Г.П. Хамитовым [6]. Правомочность и результативность такого подхода были независимо подтверждены и другими учеными [7, 8].

Суть этого подхода состоит в том, что, в соответствии с определением, автокорреляционный момент

Кх (г,г") = М [(Х(г') - тх ) • (Х(г") - тх )]

зависит как от величины X, так и от их расположения - г' и г". Этот факт был учтен при конструировании различных алгоритмов перестановки (упорядочения) значений случайного процесса. Сам вид правил перестановки определял форму автокорреляционной функции.

Перестановочная технология обладает широкими функциональными возможностями, легко трансформируется для генерирования многомерных случайных процессов и полей и исключительно технологична в использовании. В качестве недостатка следует назвать практическую невозможность точного задания значений автокорреляционных моментов. Последнее вряд ли следует признать существенным в силу того, что базовой сферой применения генераторов случайных чисел является численные имитационные эксперименты. А в последних одним из основных принципов их построения являются соизмеримость точности задания исходных данных, точности внутренних расчетов в имитационной модели и точности представления результатов. Разнообразие же перестановочных процедур обеспечивает возможность наиболее приемлемого варианта, включая и приемлемость по точности воспроизведения автокорреляционной зависимости.

Для того чтобы эффективно применять перестановочные процедуры, необходимо для них сформировать обоснованное понимание механизмов генерирования

случайных чисел с требуемыми законом распределения вероятностей и автокорреляционной зависимостью.

В качестве начального объекта изучения был избран простейший вариант перестановочной процедуры и элементарно простой бинарный закон распределения вероятностей. Проведенные исследования, опубликованные в [1-4], показали верность выбранного пути исследования.

Идея перестановочных процедур из [1-4, 6, 9] достаточно проста: генерируется реализация некоррелированного случайного процесса {Х(г),г е т},т = {0,1,..}, имеющая сразу же требуемый законом распределения вероятностей. Методы такой генерации широко известны. Например, метод обратных функций.

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

На начальном этапе в качестве правила перестановок выбиралась физически обоснованная «минимизация модуля первой разности», к примеру. Испытывались и другие критерии сравнения. Часть из них дала результат - вводилась зависимость по форме автокорреляционной функции, совпадающая с минимизацией или максимизацией расхождения между предыдущим прогенерированным значением и выбираемым из реализации исходного процесса. Но в большинстве иных способов сравнения был получен относительно отрицательный результат - автокорреляционные коэффициенты не отражали зависимость. Относительность неудач этого вида состоит в том, что перестановки вносят зависимость, которую мы просто не умеем выявить и оценить.

Дальнейшие усилия исследователей (включая автора) были направлены на расширение функциональных возможностей перестановочных процедур. Предложены и экспериментально обоснованы возможности генерирования процессов с экспоненциальной автокорреляцией, периодически коррелированных и взаимно коррелированных процессов, многомерных процессов и полей с введением корреляции между их реализациями. Появились и возможности существенного увеличения количества управляющих введением корреляции параметров.

Следует признать, что наращивание функциональных возможностей перестановочной технологии существенно расширило сферы их применения, но не приблизило к математически описываемому пониманию сути перестановочных процедур.

В работе [9, с. 110-125] предпринята попытка описать функционирование перестановочной процедуры для бинарного случайного процесса. При этом автор конструирует специальную процедуру перестановки («скользящее упорядочение»), в которой введено понятие управляющего процесса. Очевидна полезность предложенной модели «скользящего упорядочения» для понимания процессов введения корреляционных вероятностных свойств. К сожалению, этот опыт оказался не востребованным в силу того, что носит достаточно абстрактный характер и пытается охватить все: от моделей разрушения зависимостей («скользящее перемешивание»), через модель искусственного увеличения объема выборки («имитаторы») до воспроизведения случайного процесса с заданными вероятностными свойствами («генерация»).

Таким образом, подход, изложенный в [9], является оригинальным и позволяет исследовать процесс перестановок как некую систему «участников» процедуры генерирования, не отягощенную стремлением отыскать смысловые аналогии с реальными физическими процессами.

information Science, Computer Engineering and Management

Систематизация вероятностных свойств

Пусть дан случайный процесс {Х(г),г е Т},Т = {0,1,..}, имеющий сразу

же требуемый в генерируемом процессе законом распределения вероятностей

Р {Х(г) = ]} = р, Р {Х(г) = 0} = q, р+я=1. Формируется двумерный вектор претендентов и(г) = {и](г),и2(г)}, который при запуске процедуры есть

ЩГ) = {Х(1),Х(2)}, а ¥(0) = Х(0), где {У(г),г е Т} - генерируемый бинарный процесс.

В соответствии с правилом перестановок Р один из компонентов вектора и(1) становится следующим генерируемым значением У(1). Вектор и(1) обновляется до состояния и(2) таким образом, что оставшийся компонент вектора претендентов всегда становится первым из компонентов вектора претендентов, а второй компонент - это очередное значение исходного случайного процесса {Х(г)}. Такое правило обновления вектора претендентов используется во всех перестановочных процедурах, но без закрепления за оставшимся компонентом первой позиции, что, впрочем, не отражается на результатах генерирования.

Далее работа с вектором и продолжается до получения необходимого объема генерируемой выборки.

В случае генерирования бинарного случайного процесса количество вариантов правил й равно 16-ти для двумерного вектора претендентов. При этом практически невозможно определить количество реальных механизмов (вида «минимизация модуля первой разности»), которые подпадают под какое-либо из 16-ти правил й.

Как отмечалось в [1-4], каждое правило й определяется четырьмя функциями вида

P {Y( t) = kl,ul(t +1) = k2,u2(t +1) = k3] = = P {Y(t) = kl,ul(t +1) = k2]x

xP {X

= P {Y( t) = kl,ul(t +1) = k2\Pk3 =

= Pt {kl,k2YPk^ kl,k2,k3 =0,L

Выражение (1) можно представить в виде четырех функций:

Pt (0,0 ) = fl Г Pt-i ( kl,k2 )• pk

Pt (0,1) = f2 ГPt-1 (kl,k2)• Pk

Pt (1,0) = f3 ГPt-1 (kl,k2)• Pk,

Pt (1,1) = f4 ГPt-1 (kl,k2)• Pk

Особенностью такой перестановочной процедуры является идентичность функций /1 и /4 во всех 16-ти вариантах

правил й. Эти функции всегда зависят только от определенных комбинаций из (2) и не могут выглядеть иначе как:

Р (0,0 ) = (1 - р)  р-1 (0,0) +

+

Р (1,1) = р  р -1 (0,1) + р  р -1 (1,1),

где р {Х(г) = 1} = р, Р {Х( г) = 0} = д,

р+Я=1.

Функции /2 и /3 формируются всеми возможными комбинациями неиспользованных в (3) элементов р (0,0);

(1 -р)  Р-1 (0,1); р  Р-1 (1,0);

(1-р)  Р-1 (1,1).

В табл. 1 приведены возможные комбинации функций /1 - /4.

¡0Й| Information Science, Computer Engineering and Management

Функции f1 - f4. Functions f1 - f4. Таблица 1 Table 1

Вариант Option Выражение Pt

1 Pt

Pt

Pt(1,0 = 0

Pt

2 Pt

Pt(0,1 = 0

Pt

Pt

3 Pt

Pt

Pt

Pt

4 Pt

Pt

Pt

Pt

5 Pt

Pt

Pt

Pt

6 Pt

Pt

Pt

Pt

7 Pt

Pt

Pt

Pt

8 Pt

Pt

Pt

Pt

9 Pt

Information Science, Computer Engineering and Management

Pt

Pt

Pt

10 Pt

Pt

Pt

Pt

11 Pt

Pt

Pt

Pt

12 Pt

Pt

Pt

Pt

13 Pt

Pt

Pt

Pt

14 Pt

Pt

Pt

Pt

15 Pt

Pt

Pt

Pt

16 Pt

Pt

Pt

Pt

На выходе рассматриваемых вариантов получены два процесса: {у(г)} и

{ы}(г)}. Причем последний процесс впервые рассматривается в [2]. Эти два случайных процесса в зависимости от варианта из табл. 1 могут иметь различные автокорре-

ляционные функции. Закон распределения процесса \¥(г)} при г всегда сходится к закону распределения процесса {Х(г)}. Для процесса {ы2(г)} закон распределения вероятностей может быть трех видов (в зависимости от варианта табл. 1):

- сходящийся к закону распределения вероятностей исходного процесса {Х(г)} - 4 варианта;

- зависящий от вероятности р, но отличающийся от закона распределения процесса {Х(г)} - 6 вариантов;

- не зависящий от вероятности р, но отличающийся от закона распределения процесса {Х(г)} - 4 варианта.

Во втором случае возможна генерация исходного случайного процесса {Х(г)} с такой вероятностью появления

единицы, которая обеспечит заданную вероятность р {у(г) = 1} = р.

В табл. 2 представлены виды законов распределения вероятностей случайного процесса {и(г)}и {У(г}} в зависимости от вида функций /2 и /3, то есть в зависимости от номера варианта табл. 1.

Таблица 2

Законы распределения вероятностей и автокорреляционные функции

Table 2

_Laws of probability distribution and autocorrelation functions_

Вариант Option

P{U1(t) = 1}

Rç

Ru1

1,0 0,8 0,6 0,4 0,2 0,0

0123456789 10

1,0 0,8 0,6 0,4 0,2 0,0

0123456789 10

1,0 0,8 0,6 0,4 0,2 0,0

0123456789 10

1,0 0,8 0,6 0,4 0,2 0,0

-Г+

0123456789 10

0,5

1,0 0,8 0,6 0,4 0,2 0,0 -0,2 -0,4

1,0 0,8 0,6 0,4 0,2 0,0 -0,2 -0,4

1,0 0,8 0,6 0,4 0,2 0,0

-r*

0123456789 10

1,0 0,8 0,6 0,4 0,2 0,0

0123456789 10

1,0 0,8 0,6 0,4 0,2 0,0

1,0 0,8 0,6 0,4 0,2 0,0

0123456789 10

0123456789 10

1

1

2

1

3

4

V

5

V

Information Science, Computer Engineering and Management

1,G G,8 G,6 G,4 G,2 G,G

G 1 2 3 4 5 б 7 8 9 1G

1,G G, 8 G,6 G,4 G,2 G,G

G123456789 1G

1,G G,8 G,6 G,4 G,2 G,G

G 1 2 3 4 5 б 7 8 9 1G

G123456789 1G

p2

1 - 2pq

G123456789 1G

2 - p

fr-9-Ю

10

1-pq

1,G G,8 G,6 G,4 G,2 G,G

G123456789 1G

11

G123456789 1G

12

1 + P

G 1 2 3 4 5 б 7 8 9 1G

13

1-pq

6

p

7

P

8

1

9

3

p

0

p

P

14

1,G G,8 G,6 G,4 G,2 G,G -G,2 -G,4 -G,6

1,G G,8 G,6 G,4 G,2 G,G

-p+i

G123456789 1G

15

1-pq

1,G G,8 G,6 G,4 G,2 G,G -G,2 -G,4

'2 3 4 5 б 7 8 9 1Ö

1,G G,8 G,6 G,4 G,2 G,G

G123456789 1G

16

1,G G,8 G,6 G,4 G,2 G,G

-Г+.

G 1 2 3 4 5 б 7 8 9 1G

1,G G, 8 G,6 G,4 G,2 G,G

-г*

G123456789 1G

0

2

V

1

Выводы

Таким образом, изложенные в [1-4] и представленные выше результаты позволили осуществить систематизацию вероятностных свойств компонентов вектора претендентов и генерируемых случайных про-

цессов. Это позволяет заключить, что исследование вероятностных механизмов перестановочной процедуры бинарного случайного процесса с двумерным вектором претендентов в целом завершено.

Библиографический список

1. Петров А.В. Основы теории полиномиальных стохастических взаимосвязей. Иркутск, Изд-во ИР-НИТУ, 2016. 170 с.

2. Петров А.В. О подходах к вероятностному анализу перестановочных процедур генерирования случайных процессов // Вестник ИрГТУ. 2016. № 2 (109). С. 29-38.

3. Петров А.В. Новые функциональные возможности перестановочной процедуры для бинарного случайного процесса // Вестник ИрГТУ. 2016. Т. 20. № 10. С. 119-127. 001: 10.21285/1814-3520-2016-10119-127.

4. Петров А.В. К вопросу анализа вероятностных свойств компонентов бинарной перестановочной процедуры // Вестник ИрГТУ. 2016. Т. 20. № 11. С. 102-109. 001: 10.21285/1814-3520-2016-11-102-109.

5. Пелегрен М. К вопросу моделирования физических случайных функций // Труды II Международного

конгресса Международной федерации по автоматическому управлению: в 2-х т. М.: 1965. Т. 1: Теория непрерывных автоматических систем. С. 272-280.

6. Попов Е.И., Хамитов Г.П. К вопросу моделирования случайных функций // Труды института. Иркутский политехнический институт. Иркутск, 1970. Вып. 56. С. 24-40.

7. Polge A.J., Holliday E.M., Bhagavan B.K. Generation of a pseudo-random set with desired corre-lation and probability distribution. Simulation, 1973, no. 5, pp. 138-158.

8. Кузнецов Б.Ф. Стохастические модели и методы анализа информационно-измерительных систем АСУ ТП. Ангарск: Ангарская государственная техническая академия. 2007. 180 с.

9. Хамитов Г.П. Имитация случайных процессов. Иркутск: Изд-во ИГУ, 1983. 184 с.

References

1. Petrov A.V. Osnovy teorii polinomial'nykh sto-khasticheskikh vzaimosvyazei [Fundamentals of the theory of polynomial stochastic relationships]. Irkutsk, IRNITU Publ., 2016, 170 p.

2. Petrov A.V. O podhodah k veroaytnostnomu ana-lizy perestanovochnyh procedur generirovanya sly-chajnyh processov [On approaches to the probabilistic analysis of permutable procedures of random process

Information Science, Computer Engineering and Management

generation]. Vestnik IrGTU [Proceedings of Irkutsk State Technical University]. 2016, no. 2 (109), pp. 29-38.

3. Petrov A.V. Novye funcionalnye vozmognosty perestanovochnoj procedury dly binarnogo sluchajnogo processa [New functionalities of the permutation procedure for binary random process generation]. Vestnik IrGTU [Proceedings of Irkutsk State Technical University]. 2016, vol. 20, no. 10, pp. 119-127. (In Russian) DOI: 10.21285/1814-3520-2016-10-119-127.

4. Petrov A.V. K voprosy analiza veroaytnostnomu svojstv komponentov binarnoj perestanovochnoj proce-duri [On the analysis of probabilistic properties of binary permutation procedure components]. Vestnik IrGTU [Proceedings of Irkutsk State Technical University]. 2016, vol. 20, no. 11, pp. 102-109. (In Russian) DOI: 10.21285/1814-3520-2016-11-102-109.

5. Pelegren V. K voprosy modelirovaniy fizicheskih slychajnyh funkcij [To the issue of physical random function modeling]. Trudy II Megdunarodnogo kon-gressa Megdunarodnoj federacii po avtomaticheskomu upravleniy: v 2-kh. t. [Proceedings of the II International Congress of the International Federation on Automatic

Критерии авторства

Петров А.В. сформулировал задачу, провел исследования механизмов, определяющих поведение компонентов вектора претендентов, получил результаты численных экспериментов по оценке мо-ментных функций, оценивающих характеристики взаимосвязи компонентов вектора претендентов, и осуществил их систематизацию, подготовил статью к публикации и несет ответственность за плагиат.

Конфликт интересов

Автор заявляет об отсутствии конфликта интересов.

Статья поступила 25.10.2016 г.

Control: in 2 vol.]. Moscow, 1965, vol. 1: Teoriya nepre-ryvnykh avtomaticheskikh system [The theory of continuous automatic systems], pp. 272-280.

6. Popov E.I., Khamitov G.P. K voprosu modelirovaniy sluchajnih funkcij [To the question of random function modeling]. Trudi instityta. Irkutckij polytehnicheskij institut [Proceedings of the Institute. Irkutsk Polytechnic Institute]. Irkutsk, 1970, issue 56, pp. 24-40.

7. Polge A.J., Holliday E.M., Bhagavan B.K. Generation of a pseudo-random set with desired corre-lation and probability distribution. Simulation, 1973, no. 5, pp. 138-158.

8. Kuznetcov B.F. Stohasticheskie modely I metody analiza informacionno-izmeritelnyh system ASU TP [Stochastic models and methods of analysis of information-measuring systems ACS TP]. Angarsk, An-gaqrskay gosydarstvennay tehnicheskaiy akademiy Publ., 2007, 180 p.

9. Khamitov G.P. Imitaciy sluchjnyh processov [Simulation of random processes]. Irkutsk, Izd-vo Irkutskogo universiteta Publ., 1983, 184 p.

Authorship criteria

Petrov A.V. formulated the problem, studied the mechanisms determining the behavior of the candidate vector components, obtained the results of numerical experiments on the estimation of the momentary functions that assess the relationship characteristics of the candidate vector components and carried out their systema-tization. He prepared the article for publication and bears the responsibility for plagiarism.

Conflict of interests

The author declares that there is no conflict of interests regarding the publication of this article.

The article was received 25 October 2016