Анализ свойств вероятностных моментов двоичных последовательностей для задач моделирования стохастических объектов

Полный текст

Введение

Анализ задач машинного моделирования реальных объектов и процессов стохастического типа способен выявить ряд требований к случайным последовательностям, обеспечивающим проявление внешней среды [1, 2]. Кроме основных статистически оцениваемых вероятностных свойств [3], достоверно известными становятся объемы требуемых выборок, временные рамки использования средств имитации, а также данные о видах и порядках вероятностных моментов.

Методы статистических испытаний (методы Монте‑Карло) в современных постановках требуют формирования многочисленных выборок случайных последовательностей разной длины [4, 5]. Уникальность необходимых вероятностных и корреляционных свойств вынуждает разработчиков имитационных экспериментов на ЭВМ подбирать адекватные этим алгоритмам программы или разрабатывать новые.

Простейшие варианты выполнения требований постановщиков задачи реализуются разработчиками машинного эксперимента выбором минимального набора последовательностей на основе схемы независимых испытаний Бернулли. Технически это достигается реализацией детерминированных алгоритмов получения псевдослучайных чисел [6, 7] или аппаратного формирования истинно случайных последовательностей [7–10], которые воспроизводят известные постулаты Голомба [10, 11], приближающие искусственный характер генерируемых последовательностей к идеальной модели случайного сигнала типа «белого шума» [7, 8].

Строгую математическую форму описания бернуллиевских свойств двоичных последовательностей дали А.Н. Колмогоров и В.А. Успенский [12]. Они определили в терминах теоретико-множественного представления и алгоритмической вычислимости три свойства случайности: типичности, хаотичности и стохастичности. Понимая под генеральной выборкой последовательность бесконечной длины, авторы алгоритмической теории случайности отнесли эти три свойства к частной выборке в виде цепочки конечной длины как фрагмента бесконечной последовательности.

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

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

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

Пример экономии ресурсов

Рассмотрим пример воображаемой ревизии последовательностей в целях снижения ресурсной нагрузки на машинный эксперимент, связанный с реализацией имитационной модели. Обобщенная схема эксперимента представлена на рис. 1.

 

Рис. 1. Обобщенная структура имитационной модели статистического типа: а – исходная форма; б – результат ревизии входных последовательностей

 

Выделим в структуре общей постановки машинного эксперимента логико-алгоритмические блоки и связи, ядро имитационной модели (ЯИМ), находящееся под воздействием некоторой области внешних возмущений и внутренних вариаций свойств ядра как динамического объекта [2]. В случае статистического характера модели эти возмущения должны проявлять случайное поведение, адекватное моделируемым реальным процессам [1].

Пусть такая структура требует совокупности из 8 фрагментов двоичных последовательностей  ,  , …,  , являющейся реализацией набора случайных последовательностей  ,  , …,   размерностью n₁, n₂, …, n₈ соответственно, с необходимыми оригинальными теоретико-вероятностными свойствами. Для их формирования надо создать алгоритмы и программы, реализация которых связана с необходимыми затратами машинной памяти и времени.

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

•  и   на длинах n₁ и n₄ статистически неразличимы с константами 1 и 0 соответственно;
•  на длине n₂ статистически не отличается от М-последовательности 5‑го порядка  ;
•  на длине n₃ статистически не отличается от элементарной последовательности типа …0101…;
•  на длине n₆ и n₇ статистически неразличима с   и  соответственно;
•  на длине n₈ статистически оригинальна (отлична) от констант 1 и 0, последовательности типа …0101…,  ,   и  .

Таким образом, для машинной реализации математической модели достаточно сформировать две оригинальные последовательности:  , совпадающую с  ,  , на длине   и   длиной n₈, а также три низкозатратных в ресурсном отношении типа   = …0101…, на протяжении n₃ тактов, вырожденных в константы   = 1 и   = 0 в течение n₁ и n₄ тактов модельного времени (см. рис. 1 б).

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

Статистически значимая однородность последовательностей

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

Основная независимая переменная   – длина частной выборки. Имитационная модель воспринимает от БП вероятность   в форме статистических оценок на момент реализации  ‑го модельного такта, т. е.  . То же самое для АП:  . Предусмотрим ограничения вида   при исследовании на однородность автокорреляционных свойств, через моментные функции второго порядка, и предел   для  . Из условий парадигмы, принятой в машинном моделировании конкретного класса стохастических объектов, задается типичный уровень значимости критерия однородности α как вероятность ошибки первого рода.

Используемый в непараметрических критериях подход [13–15] основывается на подсчетах эмпирической статистики, прямо пропорциональной средним значениям расхождений квалифицирующих параметров и обратно пропорциональной величине дисперсионного разброса оценок расхождений. Завершающей процедурой критерия является проверка гипотезы об однородности путем сравнения величины полученной статистики с критическим уровнем, учитывающим заданную значимость.

В данной задаче предусматриваются многократные испытания гипотез на основе статистики в форме отношения двух функций от n‑ожидаемого различия оценок вероятностей   и оценки стандартного отклонения этой разности, т. е.

 (1)

Эмпирический материал для этой статистики обеспечивается формированием достаточного множества выборок элементов разностной последовательности вида

(2)

длиной n при ее возрастания от 1 до  . Полученные числовые значения (1) сравниваются с некоторой критической величиной  , дающей основание принять нуль‑гипотезу   об однородности тестируемых объектов или, отвергнув ее, выбрать конкурирующую гипотезу   согласно условиям:

 (3)

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

Рассмотрим применимость классических вероятностных моментов конечных порядков, уделив особое внимание двоично структурированным формам последовательностей.

Начальные вероятностные моменты

Принято [14–16] начальный вероятностный момент порядка r дискретной случайной величины A представлять в виде

 (4)

где u – количество уровней дискретности;   – вероятность принятия величиной A уровня  ; порядок r определен на множестве натуральных чисел.

Минимальное значение   соответствует бинарному характеру величины A. Уменьшив на единицу оба предела суммирования в (4) и определив бинарность A алфавитом   для  , представим следующее распределение вероятностей:  , где  .

Если полагать   и  , то справедливо следующее утверждение: начальный момент двоичной случайной величины A любого сколь угодно высокого конечного порядка r в виде натурального числа равен начальному моменту этой величины первого порядка, допускающий выражение в форме математического ожидания и вероятности появления единицы вида:

  и  .

Система k случайных дискретных величин   многоуровневого типа ( ) характеризуется смешанным начальным моментом

 (5)

где   – порядок момента как сумма порядков   элементов   системы.

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

 

или через математическое ожидание и вероятность появления совокупности из r единиц:

  (6)

Описанный момент ориентирован на единичные значения двоичных переменных. Однако наряду с моментом вида (6) имеют право на самостоятельное использование начальные моменты, допускающие инверсные значения двоичных переменных:

 (7)

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

Из одинаково сформированных групп случайных элементарных переменных БП и АП, согласно выбранному начальному вероятностному моменту, достаточно образовать разностную последовательность (2) вида  , чтобы через средние значения и среднеквадратические отклонения множества частных сумм элементов разности   образовать ряд статистик (1) критерия однородности для всех частных выборок размерности n от 1 до критического значения. Алгоритмически очевидно применение описанных вероятностей элементарных и сложных событий   и   как начальных вероятностных моментов конечного порядка в роли квалифицирующих параметров   или   статистического критерия, определенного выражениями (1)–(3).

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

Имитационная модель как объект использования случайных последовательностей может требовать однородности не по начальному, а по центральному вероятностному моменту r‑го порядка общего вида   [13–16]. В этом случае двоичные формы элементарных переменных в событии центрального момента   не позволяют свести процедуру тестирования на однородность к таким же простым и технологичным действиям с вероятностями, как это достигается при задании квалифицирующих параметров начальными моментами. Однако, используя выражение центрального момента через оператор математического ожидания  , можно получить его разложение на ряд начальных моментов r‑го и меньших порядков. Так, в литературе по теории вероятностей [14–17] приведены примеры разложения нескольких центральных моментов малого порядка на начальные:

 (8)

Известно также общее выражение центрального момента через начальные:

 (9)

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

 

Рис. 2. Образование связей в сложных событиях: а – для равноправных элементарных переменных; б – в последовательностях

 

Применительно к процессам интересующие нас события  , где  , разделяются однонаправленным дискретным временем  , дисциплинирующим формирование системы случайных двоичных величин. Кроме этого, для полноты описания смешанными вероятностными моментами свойства последовательности необходимо ввести управляющие факторы временного расстояния в виде сдвигов элементов относительно друг друга на кратные   тактов. Один из вариантов задания неанализируемых позиций двоичных комбинаций реализуется допустимостью условия  . Однако в этом случае двоичный алфавит элементов последовательности для начальных моментов спровоцирует противоречие «ноль в нулевой степени». В целях его устранения изменим принадлежность   с множества натуральных чисел (в частности, с фиксированного значения 1) к множеству неотрицательных целых чисел 0 и 1, что позволит считать  и  . На рис. 2 б приведен фрагмент расположения событий последовательного характера, участвующий в образовании вероятностного момента, в данном примере 4-го порядка.

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

 

дающих неизменное  ‑кратное вхождение r‑ой степени вероятности появления 1 со знаком минус или плюс в зависимости от четности/нечетности порядка r. Например, при   это  , а   дает  .

Анализ разложений центральных моментов на начальные для двоичных последовательностей

Описанные особенности первого и двух последних слагаемых в сумме (9) в виде вероятностей характерны как для двоичной последовательности, так и в классическом теоретико‑вероятностном случае в виде начальных моментов равноправных абстрактных событий. То же самое касается части  ‑кратных вероятностей плотных наборов из   двоичных символов последовательности и соответствующих начальных моментов абстрактных событий при  , т. е.  ,   и  ,  .

Недостаточность описания центральных моментов последовательности в (8) и (9) проявляется при   и  . В этих случаях требуется включение не более ( )‑кратных вероятностей комбинаций двоичных переменных, собранных в систему элементов с организацией пропусков тактового времени, нарушающих плотность набора анализируемых переменных.

Введенное переопределение элементарных порядков с   на   допускает задание произведения   для плотных r‑ичных наборов и   для разреженных. Общий вид формул определения смешанных моментов как начальных, так и центральных применительно к двоичным значениям   и   представим в виде:

 (10)

 (11)

где           r-разрядное двоичное целое число;

    частный (фактический) порядок момента как сумма единичных значений  ;

   центрированные величины   относительно общего математического ожидания  .

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

Например, при   второе слагаемое в разложении (9) для   обуславливает 3‑кратное вхождение  . Для абстрактной системы событий   это обеспечивается комбинациями  ,   и  . В последовательности (при ее стационарности) первые две комбинации дают компонент  , третья комбинация соответствует начальному моменту второго порядка, в общем случае отличному от моментов первых двух комбинаций того же второго порядка. Обозначим этот начальный момент   как вероятность совпадения по 1 двух переменных, разделенных двумя тактами реализации последовательности в дискретном времени за счет задания  .

Нетрудно показать, что реальная случайная переменная A эквивалентна абстрактной системе   равноправных событий (см. рис. 2 а) в случае применимости к ним двоичного алфавита. Согласно замечанию о начальном моменте двоичной случайной величины допустимо считать  , где r – натуральное число. Тогда разложение (9) центральных моментов на начальные запишется в следующей вероятностной форме:

 (12)

Конкретные виды связей центральных вероятностных моментов первых четырех порядков с начальными моментами для двоичной переменной и r‑ичной системы двоичной последовательности представлены в табл. 1. Из таблицы видно, что эти разложения существенно отличаются при   слагаемыми, записанными в суммах на позициях между   или   и  .

 

Таблица 1 Выражения центральных моментов через начальные для двоичной случайной величины и системы двоичных величин последовательности ( )

	Для двоичной A	Для двоичной системы

 

Для численного определения центрального момента r-го порядка двоичной последовательности требуется найти все   начальных моментов частных порядков от 1 до r. Например, при   необходимо определить   вероятностей и в кратном количестве включить их в   как слагаемые и вычитаемые (см. верхние скобки) в следующем виде:

 ,

что свидетельствует о неприменимости известного представления (8) и в общей форме (9) к рассматриваемым последовательным событиям.

Наборы из символов 1 и неопределенных символов (обозначенных точками), образующие необходимые сложные события последовательности для определения начальных моментов, входящих в центральный момент до 6-го порядка, приведены в табл. 2. Центральный момент  наряду с  включает в себя наборы из всех меньших порядков. Количество дополнительных наборов для данного порядка r относительно   обозначено  , а общая сумма   приведена как  .

 

Таблица 2 Комбинации двоичных переменных сложных событий при определении связи начальных моментов двоичной последовательности с центральными для  

r	Частный порядок
	1	2	3	4	5	6
2	1	11	–	–	–	–	2	2
3	–	1.1	111	–	–	–	2	4
4	–	1..1	1.11, 11.1	1111	–	–	4	8
5	–	1…1	1..11, 11..1, 1.1.1	1.111, 111.1, 11.11	11111	–	8	16
6	–	1….1	1…11, 1..1.1, 11…1, 1.1..1	1..111, 1.1.11, 1.11.1, 111..1, 11.1.1, 11..11	1.1111, 1.111, 1.1111, 111.1,	111111	16	32

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

Формирование последовательностей сложных событий совпадения двоичных элементов для критерия однородности

Следует подчеркнуть, что для работы критерия однородности по вероятностным моментам не требуется вычислять числовые значения моментов, например в виде оценок соответствующих вероятностей. Достаточно воспроизвести сами последовательности событий по обеим тестируемым последовательностям и использовать их в качестве входных данных для работы критерия: образовать разность   по (2), оценить среднее, дисперсию   для статистики (1), получить цепочку реализации испытаний гипотез (3) и выбрать результат в виде   (или «не менее  »).

Последовательно формируемые случайные отсчеты  …, принимающие двоичные значения, объединяются конъюнкцией в группы, образующие сложные события (6) и/или (7), с учетом задержек между ними и инверсий. Варианты аппаратного формирования событий 4-го порядка представлены на рис. 3. Образование произведения элементарных переменных в прямой форме показано на рис. 3 а. Участие элементарных переменных в сочетании прямой и инверсной форм изображено схемой на рис. 3 б. Пример формирования неплотного набора элементарных переменных в прямой форме путем добавления задержки между первой и третьей переменными представлен на рис. 3 в для начального момента 3-го (частного) порядка.

 

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

 

Краткая методика определения критической длины значимо однородных последовательностей по начальному вероятностному моменту. Заданным порядком r и конкретным видом начального вероятностного момента определяем необходимую функцию преобразования вида (6) обеих последовательностей на основе операций сдвигов, конъюнкции и, в необходимых случаях для вида (7), инверсии. Вероятность полученных комбинаций двоичных переменных представляет заданный начальный момент. Из последовательностей полученных событий от обеих тестируемых последовательностей образуем разностную последовательность, элементы которой используем как входные данные для статистического критерия. Проводим серию итераций по вычислению статистики, величины которой сравниваются с критическим уровнем, образуя испытания гипотез. Результатом этих итераций является цепочка (3) принятия нуль‑гипотезы, классифицирующая свойство однородности тестируемых последовательностей с заданной значимостью по заданному начальному вероятностному моменту. Событие нарушения условия непротиворечивости нуль‑гипотезы фиксируется как наступление критической длины частной выборки, превышение которой интерпретируется как прекращение однородности.

Краткое дополнение к методике определения критической длины значимо однородных последовательностей по заданному центральному вероятностному моменту. Используя оператор математического ожидания (11), получаем разложение заданного смешанного центрального момента r-го порядка на множество из   начальных моментов, вид которых определен в табл. 2 как содержимое клеток с единичными наборами частных порядков. Определяем все необходимые функции преобразования видов начальных моментов с размерностью частных порядков от 1 до r, входящих в заданный центральный момент. Проводим необходимое количество серий итераций вычислений статистик для всех сформированных начальных моментов по вышеописанной методике. В результате проведенных в полном объеме серий тестовых итераций формируется множество значений критических длин, минимальная величина которых является искомой критической. За ее пределами тестируемые последовательности интерпретируются как неоднородные по заданному центральному вероятностному моменту.

Заключение

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

Выбор начального момента в качестве основного квалифицирующего ограничения однородности допускает однократное проведение цепочки испытаний гипотез. В случае выбора центрального момента работа критерия существенно усложняется необходимостью проверки однородности для всех порядков от 1 до r включительно. Полная аналитическая форма связи центрального момента r‑го порядка с начальными для двоичной последовательности еще не установлена. Однако логика заполнения полученной в работе табл. 2 на алгоритмическом уровне вполне заменяет математическое выражение в задаче практической реализации критерия.

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

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

Приведенный материал может быть использован для синтеза аппаратных или программных анализаторов моментов и моментных функций как на ПЭВМ, так и с использованием многопроцессорных средств. Выявленные особенности аналитических связей начальных и центральных вероятностных моментов двоичных последовательностей (6), (7), (10)–(12) и табл. 2 достаточно полно задают арифметико-логические алгоритмы обработки моментных функций, ориентированные, например, на ресурсы программируемых интегральных схем в форме «системы‑на‑кристалле».

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

Об авторах

Валерий Михайлович Кузнецов

Казанский национальный исследовательский технический университет им. А.Н. Туполева

Автор, ответственный за переписку.
Email: kuznet_evm@mail.ru

(д.т.н., доцент), профессор кафедры «Компьютерные системы».

Россия, 420111, г. Казань, ул. К. Маркса, 10

Валерий Андреевич Песошин

Казанский национальный исследовательский технический университет им. А.Н. Туполева

Email: pesoshin-kai@mail.ru

(д.т.н., доцент), профессор кафедры «Компьютерные системы».

Россия, 420111, г. Казань, ул. К. Маркса, 10

Артем Ильдарович Гумиров

Казанский национальный исследовательский технический университет им. А.Н. Туполева

Email: neporebrik@mail.ru

старший преподаватель кафедры «Компьютерные системы».

Россия, 420111, г. Казань, ул. К. Маркса, 10

Дарья Вадимовна Ширшова

Казанский национальный исследовательский технический университет им. А.Н. Туполева

Email: einstein_darya@mail.ru

старший преподаватель кафедры «Компьютерные системы»

Россия, 420111, г. Казань, ул. К. Маркса, 10

Список литературы

Дополнительные файлы