Содержание к диссертации
Введение
Глава 1. Оптимальная оценка состояний обобщенного асинхронного потока событий 19
1.1. Постановка задачи 19
1.2. Плотность вероятностей длительности интервала между соседними событиями 22
1.3. Апостериорные вероятности состояний обобщенного асинхронного потока 29
1.3.1. Рекуррентное соотношение для апостериорных вероятностей 30
1.3.2. Явный вид апостериорных вероятноятей состояний 34
1.4. Частные и особые случаи соотношения параметров, определяющих поток событий 40
1.5. Алгоритм оптимальной оценки состояний обобщенного асинхронного потока событий 44
1.6. Вероятность ошибки при оценивании состояний обобщенного асинхронного потока событий 45
1.6.1. Условная вероятность ошибочного решения о состоянии обобщенного асинхронного потока в общем случае 47
1.6.2. Условная и безусловная вероятность ошибки о состоянии потока для частных и особых случаев 50
1.7. Оптимальная оценка состояний обобщенного асинхронного потока в условиях
непродлевающегося мертвого времени 57
1.7.1. Формирование обобщенного асинхронного потока событий с непродлевающимся мертвым временем 58
1.7.2. Апостериорные вероятности состояний обобщенного асинхронного потока с непродлевающимся мертвым временем 60
1.7.3. Алгоритм оптимального оценивания состояний потока с непродлевающимся мертвым временем 62
1.8. Результаты и выводы к первой главе 64
Глава 2. Оценивание длительности мертвого времени в обобщенном асинхронном потоке 66
2.1. Постановка задачи 66
2.2. Вывод плотности вероятностей длительности интервала между соседними событиями в потоке в условиях непродлевающегося мертвого времени 69
2.3. Совместная плотность вероятностей длительности смежных интервалов между событиями в потоке в условиях непродлевающегося мертвого времени 75
2.3.1. Выражение для совместной плотности вероятностей длительностей смежных интервалов между событиями 75
2.3.2. Условия рекуррентности наблюдаемого потока 77
2.3.3. Особые случаи 81
2.4. Оценка длительности мертвого времени методом максимального правдоподобия 85
2.4.1. Построение функции правдоподобия 85
2.4.3. Решение оптимизационной задачи 87
2.5. Оценка длительности мертвого времени методом моментов 99
2.6. Результаты и выводы ко второй главе 103
Глава 3. Результаты численных экспериментов на имитационной модели обобщенного асинхронного потока событий 104
3.1. Результаты численных расчетов апостериорных вероятностей состояний и оценок
3.2. Результаты численных расчетов оценки состояний при непродлевающемся мертвом времени 109
3.3. Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков 113
3.4. Результаты численных расчетов оценки длительности мертвого времени 116
3.4. Результаты и выводы к третьей главе 121
Заключение 123
Список использованной литературы 126
- Рекуррентное соотношение для апостериорных вероятностей
- Условная вероятность ошибочного решения о состоянии обобщенного асинхронного потока в общем случае
- Совместная плотность вероятностей длительности смежных интервалов между событиями в потоке в условиях непродлевающегося мертвого времени
- Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков
Введение к работе
Актуальность работы. Различным аспектам теории массового
обслуживания (ТМО) и ее приложениям посвящена обширная литература как
отечественных, так и зарубежных авторов. Первые задачи в области ТМО были
рассмотрены известным датским ученым А.К. Эрлангом. В последние три
десятилетия вследствие стремительного развития компьютерной техники и
информационных технологий возникла ключевая область приложений ТМО –
проектирование и создание информационно-вычислительных сетей,
компьютерных сетей связи, спутниковых сетей связи, телекоммуникационных сетей и т.п., которые можно объединить единым термином – цифровые сети интегрального обслуживания (Integrated Service Digital Networks – ISDN). Данные сети характеризуются тем, что в них по единым аппаратным средствам происходит передача различных видов информации – большие массивы данных, речь и видео в цифровой форме, факсимиле и т.д. В 80-х годах для таких сетей были созданы достаточно адекватные математические модели реальных информационных потоков, функционирующих в них, которые получили название дважды стохастических потоков. Одними из первых работ в этом направлении были работы М. М. Ньютса, Г.П. Башарина, В.А. Кокотушкина, В.А. Наумова. В дважды стохастических потоках имеет место двойная случайность: моменты наступления событий в потоке – случайны и интенсивность потока – случайный процесс. Проведенные статистические эксперименты показали возможность достаточно точной аппроксимации дважды стохастическими потоками реальных потоков в информационных сетях. Большое количество исследований дважды стохастических потоков и систем массового обслуживания с входящими дважды стохастическими потоками было проведено такими учеными как А.Ф. Терпугов, А.М. Горцев, А.А. Назаров, – в Томском государственном университете; Г.А. Медведев, А.Н. Дудин, В.И. Клименок, Г.В. Царенков – в Белорусском государственном университете; Ю.В. Малинковский – в Гомельском университете; М.А. Маталыцкий – в Гродненском университете; Г.П. Башарин, П.П. Бочаров, А.В. Печинкин – в Российском университете Дружбы народов; Н.И Головко, В.В. Катрахов, Н.А. Филинова – в Дальневосточном отделении РАН; M.F. Neuts, A.D. Banik, U.C. Gupta, D.M. Lucantoni – в США; F.A. Machihara – в Японии и другими учеными. Для реальных телекоммуникационных сетей наиболее характерны дважды стохастические потоки, интенсивность которых является кусочно-постоянным случайным процессом (MC-потоки).
Дважды стохастические потоки событий делятся на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму – потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным либо бесконечным числом состояний. В зависимости от того, каким образом происходит переход из состояния в состояние, МС-потоки можно поделить на МАР-потоки 1-го порядка и МАР-потоки 2-го порядка. К МАР-потокам 1-ого порядка относятся синхронные потоки (потоки с интенсивностью, для которой переход из
состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий), и собственно МАР-потоки, являющиеся обобщением синхронных потоков. К МАР-потокам 2-го порядка относятся:
-
асинхронные потоки (потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий); асинхронные альтернирующие потоки; обобщенные асинхронные потоки, являющиеся обобщением асинхронных потоков событий и асинхронных альтернирующих потоков событий;
-
модулированные синхронные потоки;
-
полусинхронные потоки событий (потоки, в которых для одних состояний переход происходит в моменты наступления событий, а для остальных состояний – независимо от моментов наступления событий); обобщенные полусинхронные потоки, являющиеся обобщением полусинхронных потоков событий.
Лишь незначительная часть работ посвящена системам, которые функционируют в условиях полной (когда все параметры входящего потока неизвестны) или частичной неопределенности. Но на практике параметры входящего потока событий зачастую либо известны частично, либо совсем неизвестны. И даже если все параметры, определяющие поток, известны, сделать вывод о том, в каком состоянии находится поток в текущий момент времени без наблюдений за потоком возможно только на основании априорных данных. В связи с этим описанные потоки исследуются в двух направлениях: 1) оценка состояния потока в произвольный текущий момент времени по наблюдениям за моментами наступления событий (задача фильтрации интенсивности потока); 2) оценка параметров потока по наблюдениям за моментами наступления событий.
Большинство авторов рассматривают СМО в условиях, когда все события функционирующих в СМО потоков доступны наблюдению, но в реальности наступившее событие может повлечь за собой ненаблюдаемость последующих событий. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов, которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются).
В настоящей диссертационной работе впервые исследуется обобщенный
асинхронный поток событий, являющийся обобщением асинхронного потока
событий, исследованного в диссертации Л.А. Нежельской, и асинхронного
альтернирующего потока событий, исследованного в диссертациях М.Е.
Завгородней и О.В. Ниссенбаум. При этом решается задача оптимальной
оценки состояний обобщенного асинхронного потока в условиях полной
наблюдаемости и задачи оценивания состояний и длительности
непродлевающегося мертвого времени в обобщенном асинхронном потоке, функционирующим в условиях его частичной наблюдаемости.
Цель диссертационной работы:
-
аналитическое исследование обобщенного асинхронного потока событий в условиях полной наблюдаемости и в условиях непродлевающегося мертвого времени фиксированной длительности с целью получения оптимальных оценок состояний и длительности непродлевающегося мертвого времени в потоке;
-
формулировка алгоритмов оценивания состояний и длительности непродлевающегося мертвого времени;
-
программная реализация сформулированных алгоритмов оценивания;
-
проведение статистических экспериментов на имитационной модели обобщенного асинхронного потока как в условиях полной наблюдаемости, так и в условиях его неполной наблюдаемости, с целью установления качества получаемых оценок.
В рамках указанной цели были поставлены и решены следующие задачи:
-
Нахождение аналитического решения задачи оптимальной оценки состояний обобщенного асинхронного потока (как функционирующего в условиях его полной наблюдаемости, так и в условиях непродлевающегося мертвого времени фиксированной длительности T) по наблюдениям за моментами наступления событий потока.
-
Получение аналитического решения задачи оценки длительности непродлевающегося мертвого времени в обобщенном асинхронном потоке, функционирующем в условиях непродлевающегося мертвого времени фиксированной длительности T, по наблюдениям за моментами наступления событий наблюдаемого потока.
-
Создание алгоритма оптимальной оценки состояний в обобщенном асинхронном потоке, функционирующем как в условиях его полной наблюдаемости, так и в условиях непродлевающегося мертвого времени фиксированной длительности T.
-
Создание алгоритмов оценки длительности непродлевающегося мертвого времени в обобщенном асинхронном потоке, функционирующем в условиях непродлевающегося мертвого времени фиксированной длительности T.
-
Проведение исследования качества полученных оценок, реализованных на основе имитационной модели обобщенного асинхронного потока и разработанных алгоритмов оценки состояний потока в условиях его полной наблюдаемости и оценки состояний и длительности мертвого времени в потоке, функционирующем в условиях неполной наблюдаемости.
Научная новизна результатов проведенных исследований.
Научная новизна работы состоит в решении задач оптимального оценивания
состояний обобщенного асинхронного потока, функционирующего в условиях
полной наблюдаемости, а также задач оптимального оценивания состояний и
длительности непродлевающегося мертвого времени в обобщенном
асинхронном потоке, функционирующем в условиях непродлевающегося
мертвого времени фиксированной длительности, по наблюдениям за моментами наступления событий потока.
Положения, выносимые на защиту:
-
Аналитическое решение задачи оптимальной оценки состояний обобщенного асинхронного потока, функционирующего как в условиях полной наблюдаемости, так и при наличии непродлевающегося мертвого времени фиксированной длительности T, по наблюдениям за моментами наступления событий потока.
-
Аналитическое решение задачи оценки длительности непродлевающегося мертвого времени в обобщенном асинхронном потоке, функционирующем в условиях непродлевающегося мертвого времени фиксированной длительности T, по наблюдениям за моментами наступления событий наблюдаемого потока.
-
Алгоритмы оптимальной оценки состояний в обобщенном асинхронном потоке, функционирующем как в условиях полной наблюдаемости, так и при наличии непродлевающегося мертвого времени фиксированной длительности T.
-
Алгоритмы оценки длительности непродлевающегося мертвого времени в обобщенном асинхронном потоке, функционирующем в условиях непродлевающегося мертвого времени фиксированной длительности T.
-
Результаты исследования качества полученных оценок, реализованных на основе имитационной модели обобщенного асинхронного потока и разработанных алгоритмов оценки состояний потока в условиях его полной наблюдаемости и оценки состояний и длительности мертвого времени в потоке, функционирующем в условиях неполной наблюдаемости.
Методы исследования. Для решения поставленных задач применяются методы теории вероятностей, теории массового обслуживания, теории дифференциальных уравнений, теории марковских процессов, математической статистики, линейной алгебры, численные методы. Проведение статистических экспериментов выполнено на основе имитационной модели обобщенного асинхронного потока как в условиях полной наблюдаемости, так и при наличии непродлеваюещегося мертвого времени фиксированной длительности.
Теоретическая ценность работы состоит в аналитическом решении задачи оптимальной оценки состояний обобщенного асинхронного потока по наблюдениям за моментами наступления событий потока, функционирующего в условиях полной наблюдаемости, а также в аналитическом решении задач оптимальной оценки состояний и длительности непродлевающегося мертвого времени в обобщенном асинхронном потоке в условиях его частичной наблюдаемости.
Практическая ценность работы заключается в возможности использования
разработанных алгоритмов оптимальной оценки состояний и длительности
мертвого времени в задачах проектирования СМО и СеМО, к примеру,
информационно-вычислительных сетей, сетей связи, дисциплины
обслуживания которых зависят от параметров и текущих состояний входящих потоков, а также для обработки результатов физических экспериментов, осложненных наличием мертвого времени регистрирующих приборов.
Достоверность полученных результатов подтверждается корректным
применением используемого математического аппарата, корректностью
методик исследования и проведенных расчетов, многочисленными
статистическими экспериментами, проведенными на имитационной модели обобщенного асинхронного потока как в условиях его полной наблюдаемости, так и в условиях его частичной наблюдаемости, а также согласованностью результатов диссертации с результатами, полученными другими авторами.
Личное участие автора в получении результатов, изложенных в диссертации. Постановка изложенных в диссертации задач сделана научным руководителем, д.т.н., профессором А.М. Горцевым. Доказательство и обоснование полученных в диссертации результатов, математические выкладки, численные расчеты выполнены лично автором. В совместных публикациях научному руководителю А.М. Горцеву принадлежат постановки задач и указания основных направлений исследований, а основные результаты, выкладки и численные расчеты выполнены автором.
Внедрение работы. Работа выполнена в рамках госзадания минобрнауки РФ
на проведение научных исследований в Томском государственном
университете на 2009 – 2010 годы: “Исследование математических моделей
программно-аппаратной передачи, обработки, управления и защиты
информации в телекоммуникационных сетях и компьютерных комплексах
технических и экономико-социальных систем. (1.17.09)”, номер госрегистрации
01200903817, и госзадания минобрнауки РФ на проведение научных
исследований в Томском государственном университете на 2012 – 2013 годы:
“Разработка и исследование вероятностных, статистических и логических
моделей компонентов интегрированных информационно-
телекоммуникационных систем обработки, хранения, передачи и защиты информации. (8.4055.2011)”, номер госрегистрации 01201261193, и в рамках выполнения государственного задания Минобрнауки России на 2014 г. Результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета при подготовке образовательных дисциплин “Теория игр и исследование операций” и “Имитационное моделирование” для студентов 4-го курса ФПМК.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих научных конференциях:
1) XX Белорусская зимняя школа-семинар по теории массового
обслуживания (BWWQT-2009) «Современные математические методы анализа
и оптимизации информационно-телекоммуникационных сетей», г. Минск., 26 –
29 января 2009 г.;
2) Международная конференция, посвященная 75-летию профессора, д.ф.-
м.н. Г.А. Медведева «Теория вероятностей, математическая статистика и их
приложения», г. Минск, 22 – 25 февраля 2010 г.;
-
IX Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», г. Томск, 2012г.;
-
XXII Белорусская зимняя школа-семинар по теории массового обслуживания (BWWQT-2013) «Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей», г. Минск., 28 - 31 января 2013 г.;
-
V Международная научно-практическая конференция «Актуальные проблемы радиофизики», г. Томск, 1 - 6 октября 2013 г.;
-
Научные семинары кафедры исследования операций и теории вероятностей и математической статистики ТГУ в период с 2010 по 2013 г.г.
Публикации. Основные результаты данной работы приведены в 13 научных публикациях, в т.ч. 7 статей в изданиях, входящих в список ВАК.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, трех приложений. Общий объем работы составляет 152 страницы. Работа содержит 133 страницы основного текста, в том числе 18 рисунков и 18 таблиц. Список литературы включает в себя 160 наименований.
Рекуррентное соотношение для апостериорных вероятностей
Одной из важных областей прикладной математики, использующей методы теории случайных процессов, является теория массового обслуживания (ТМО), которая представляет собой теоретические основы комплекса задач конструирования и эксплуатирования систем массового обслуживания (СМО). Случайные потоки событий являются основными элементами систем массового обслуживания и, кроме того, широко применяются в качестве математических моделей реальных процессов.
В последние три десятилетия вследствие стремительного развития компьютерной техники и информационных технологий возникла ключевая область приложений ТМО – проектирование и создание информационно-вычислительных сетей, компьютерных сетей связи, спутниковых сетей связи, телекоммуникационных сетей и т.п., которые можно объединить единым термином – цифровые сети интегрального обслуживания (Integrated Service Digital Networks – ISDN).
Различным аспектам ТМО и ее приложениям посвящена обширная литература как отечественных, так и зарубежных авторов. Базовые результаты теории массового обслуживания были сформулированы в начале 20 века. Первые задачи в области ТМО были рассмотрены известным датским ученым А.К. Эрлангом. Его первая работа была издана в 1909 году и доказывала, что телефонные звонки распределены беспорядочно во времени и подчиняются распределению Пуассона. Вследствие того, что аналогичные задачи возникают также и во многих других областях науки и техники (при исследование транспортных систем, систем связи и мн. др.), с того времени интерес к такому кругу вопросов стал возрастать. Именно на результаты А.К. Эрланга, как на базовые положения теории массового обслуживания, ссылаются специалисты, занимающиеся исследованиями подобных вопросов. Основы теории заложены в монографиях [22, 71 – 74, 80, 104, 108, 114]. Далее ТМО развивалось с изучением различных систем с приоритетами, которым посвящены монографии [10, 19, 21, 62, 75, 91]. Основные тенденции развития ТМО изложены в работе [71], методы ТМО – в монографии [72].
Пика своего развития ТМО достигла в 50-е – 70-е годы в связи с появлением одного из важнейших направлений, связанного с управляемыми системами массового обслуживания (СМО) и возрастающей актуальностью задач оптимизации. Первые работы по управляемым СМО появились в середине 60-х годов [11, 12, 17, 20, 105, 107, 131, 149, 159, 160]. С дальнейшим развитием появились наиболее полные обзоры по управляемым СМО [106, 111]. Многочисленные публикации связаны с различными оптимизационными постановками задач и их решением. Из анализа этих и последующих работ можно сделать вывод, что исследования в области управляемых СМО делятся на следующие основные направления: 1) приоритетные системы с динамическими приоритетами [60, 90, 107, 131, 150]; 2) системы с управляемыми длительностями обслуживания [63, 109, 130, 151, 156, 160]; 3) системы с управляемым входящим потоком заявок [70, 76, 146]; 4) системы с формированием очередей [70, 94, 110, 137]; 5) системы с динамической структурой [2, 37, 69, 81, 119, 142 – 145, 152, 154].
В большинстве публикаций авторы рассматривают математические модели СМО, когда все параметры системы известны. Однако на практике дело обстоит зачастую иначе и если параметры, характеризующие обслуживающее устройство, известны и не меняются со временем, то относительно интенсивностей входящих потоков этого сказать во многих случаях нельзя. Это приводит к необходимости рассмотрения дважды стохастических потоков событий [125, 138]. С другой стороны, в подавляющем большинстве работ по исследованию СМО в качестве случайных потоков событий рассматриваются пуассоновские потоки, поэтому большой интерес представляет изучение дважды стохастических потоков событий, интенсивность которых является случайным процессом. В дважды стохастических потоках имеет место двойная случайность: моменты наступления событий в потоке – случайны и интенсивность потока – случайный процесс.
По-видимому, первыми работами по изучению дважды стохастических потоков явились работы Кокса [125] и Кингмена [138], в которых дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. Проведенные статистические эксперименты [7, 23, 115] показали возможность достаточно точной аппроксимации дважды стохастическими потоками реальных потоков в информационных сетях. Дважды стохастические потоки также широко применяются как математематические модели в ряде других областей. Например, модели дважды стохастических потоков могут применяться к описанию экономических процессов [68, 77, 88, 123, 124, 127, 133, 136, 137], к описанию процесса обучения нейронной сети [121], к описанию работы центральной нервной системы [120], к описанию биофизических процессов [158], к моделированию реального траффика данных [132], к моделированию процессов плазменной турбулентности [140] и т.д.
Степень разработанности.
На рис. 1 приведена схема классификации дважды стохастических потоков событий, которые делятся на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс [112, 126, 128, 155]; ко второму – потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным либо бесконечным числом состояний. Потоки второго класса впервые введены в рассмотрение практически одновременно в 1979г. в статьях М. Ньютса [147] и Г.П. Башарина, В.А. Кокотушкина, В.А. Наумова [4, 5]. В [4, 5] введнные потоки названы МС (Markov chain)-потоками; в [147] – MVP (Markov versatile processes)-потоками. Отметим, что МС-потоки событий наиболее характерны для реальных телекоммуникационных сетей. В монографии [65] и статьях [9, 64, 66, 118, 141] проведено исследование BMAP (Batch Markovian Arrival Process)-потоков событий (потоков с кусочно-постоянной интенсивностью, в которых в момент изменения интенсивности может наступить сразу несколько событий).
Условная вероятность ошибочного решения о состоянии обобщенного асинхронного потока в общем случае
Рассмотрим числитель A1 выражения (1.3.22): A1 = a(X1 tt - At )p(X1 \)p(rm+1 \) + (X2 tt -At )p(X1 X2)p(rm+1 X2). Здесь возможны следующие варианты: 1) процесс /1() на интервале (t, t + At) не перешел во второе состояние и на этом интервале наступило событие пуассоновского потока с параметром 1 (вероятность этого варианта есть Р(\ h)p(rm+1 = 1 h) = (1 - + о(АЩх + o(At)) = X1At + o(At); 2) процесс /1() на интервале (t, t + At) перешел из второго состояния в первое, при этом сынициировалось дополнительное событие, и событие пуассоновского потока с параметром 2 не произошло (вероятность этого варианта есть P(\ I )P(W = 01 2) = M + И)(1 - + оИ) = № + И). Другие варианты имеют вероятность о(Дґ). Тогда 4 выпишется в виде 4 = Дґ[Аіш(Аі к,- - Аґ ) + qa2(X2 \tt - АҐ)] + o(At). (1.3.23) Аналогично находится выражение для знаменателя Вх выражения (1.3.22): Вх = Аі[(Х, +ра1Уй(Х1 \tt - АҐ) + (Х2 + qa2MX2 \t{ - At )] + o(At). (1.3.24) Подставляя (1.3.23), (1.3.24) в (1.3.22), учитывая при этом, что ( 2 – ) = =1–( 1t–f), и переходя к пределу при t0 (при этом также Г0 и Г0), получаем утверждение леммы. Лемма доказана.
Таким образом, в точке U (момент наступления события потока) апостериорная вероятность 00( 10 претерпевает разрыв (имеет место конечный скачок).
Полученные для этой вероятности формулы (1.3.14) и (1.3.21) определяют поведение апостериорной вероятности оо(А,1 \t) на полуинтервале [tt, ti+l) между моментами наступления событий. В качестве начального значения оо(А,1 \t0 + 0) = оо(А,1 \t0 = 0) в момент времени t0 = 0 можно выбрать априорную финальную вероятность первого состояния процесса Щ), определенную формулой (1.2.1): (й(Х1 \t0 + 0) = щ = а2 . аг + а2
Леммы 1.3.2, 1.3.3 позволяют сформулировать следующую теорему. Теорема 1.3.1. Для обобщенного асинхронного потока событий поведение апостериорной вероятности й{\\і) на временной оси определяется выражениями
Таким образом, имеем со(Хіґ)=яі для ґ ґ0 Последнее говорит о том, что при таком соотношении параметров информация о моментах наступления событий t\,..., tm не оказывает влияния на апостериорную вероятность (k\\i), т.е. в конечном итоге не влияет на качество оценивания состояний процесса X(f). Решение о том или ином состоянии обобщенного асинхронного потока выносится на основании априорных данных: если щ л2, то X(t) = Хх; в противном случае
Здесь формула (1.4.5) не вытекает из формулы (1.3.25) для общего случая. 3.2 a 0, q =l, 0 p l, ki- h=a2 - ah Тогда дифференциальное уравнение (1.3.16) примет вид: = -(1- )а1ш2 ( 1Ю , dt его решение есть m(xlW = 2 Ый±о) (146) 1 1 + (1 - /7)сх1ю(Л.11 - + 0)(ґ - ґ7-) U t tm , /=0,1,... . Формула пересчета (1.3.26) выпишется в виде а2 + (Х1-а2ЩХ1\іі-0) + X2+a2-(\-p)ala(Xl\ti-0) "" Здесь также формула (1.4.6) не вытекает из формулы (1.3.25) для общего случая. 4. h- Х2+щ +(1-2?)а2=0, 0 q \. Данное соотношение параметров имеет место только для а 0. Тогда дифференциальное уравнение (1.3.16) примет вид: (1 -д)а2 -[(1 -р)щ + (1 -д)а2У(Х1 \t\ da (kl \t) dt его решение есть d(tj) е . VC + (0( 2 + 0) G)(Xl (?) = 4cj= Vc + х (Х11 + 0) + (1.4.7) Vc - ш(А,11 f,- + 0) e-d(t,) \fc - ( {\ tt + 0) где с = (1- )а2/[(1-/?)а1 + (1- )а2], d = 2(\-q)a2/ Jc, tt t ti+l , /=0,1,... . Формула пересчета (1.3.26) примет вид: qa2+(Xl-qa2)(d(Xl\ti-0) ._ Ю( lf, + )" 2+да2-[(1- )а1 + (1-д)а2]ш( 1ґг.-0) " v"" Здесь формула (1.4.7) не вытекает из формулы (1.3.25) для общего случая. 5. Xi-X2+(Xi +(\-2q)a2 = 0, 0 р 1, q=\. Данный частный случай полностью совпадает с частным случаем 3.2. 6. Х{к2 = pqaxa2 , 0 р 1, 0 q ІЛіФ Л\Ф qu2. Последнее ограничение вытекает из того, что отмеченная связь параметров влечет за собой равенство a={\IXx){Xx-qa2){Xx+pax). Тогда афО, если X qa2. Для расчета апостериорной вероятности &(h\t) справедлива формула (1.3.25). Формула пересчета (1.3.26) при этом приобретает вид: (u(Xl\ti + 0) = Xl/(Xl+pa1) , і = 1,2,.... (1.4.8)
Таким образом, в данном частном случае апостериорная вероятность (k1t) не зависит от предыстории. Изучим смысл апостериорной вероятности (1.4.8). Подставляя в щ, опреленную в (1.2.7), rk2=pqa1a2 /11 , получаем (1.4.8). Таким образом, (o(X1ti+0) в рассматриваемом случае - апостериорная вероятность того, что процесс X(f) в момент времени tj+О находится в первом состоянии при условии, что в момент времени U наступило событие обобщенного асинхронного потока, /=1,2,... . Для общего случая (формула (1.3.26)) ооф +0) - апостериорная вероятность того, что процесс X(f) в момент времени tj+О находится в первом состоянии при условии, что в моменты времени t1,...,U-1 наступили события обобщенного асинхронного потока. Таким образом, в значении &{Xx\tt +0) “сосредоточена” вся предыстория наблюдений за потоком, начиная от момента времени t0 = 0 до момента tt. Отметим, что в рамках отмеченной связи имеют место и частные случаи 3.1, 3.2, 4, 5. Рассмотрим теперь особые случаи, когда а = 0 (в выражениях для ю1, ю2 ((1.3.25), (1.3.26)) имеет место деление на ноль). 1. p+q, 0 /? 1, 0 ? 1. Тогда h+po1= h+qa2 (вариант q=0 при этом не реализуем, т.к. в этой ситуации имеем Х2 1 , что противоречит постановке задачи). Тогда дифференциальное уравнение (1.3.16) примет вид: Ы1 = (і _ д)а _ Г(1 _ р)а + (і _ g)a2 W Ю, dt 2 l : 2J : его решение есть &{\ Ю = (1 - )а2/р + [a(h \tt + 0) - (1 - gOc /p] " 0 , (1.4.9) где $ = (l-p)al + (l-q)a2, ti t t+1 , /=0,1,... . Формула пересчета (1.3.26) выпишется в виде оо(Л \ti + 0) ,i = l,2,.... (1.4.10) l2+qa2 2. p+q, 0 /? 1, 0 1, X1=ga2 , Х2=ра1 Для расчета апостериорной вероятности &(ht) справедлива формула (1.4.9). Формула пересчета (1.3.26) при этом приобретет вид: ay(X1ti+0) = qa2/(jxx1 + qa2) , і = 1,2,.... Таким образом, в данном особом случае получили результат, аналогичный результату частного случая 6: апостериорная вероятность (o(X1t) не зависит от предыстории.
Совместная плотность вероятностей длительности смежных интервалов между событиями в потоке в условиях непродлевающегося мертвого времени
Формулы (1.6.2), (1.6.3), (1.6.5) - (1.6.9) позволяют сформировать алгоритм расчета условной вероятности вынесения ошибочного решения P0((o(X1tj+0), тг) в любой момент времени тг0 0, г = 0, 1,... : 1) в момент времени t0=0 задается (,(k1t0+0)=(,(k1t0=0)=n1; 2) по формуле (1.6.5) для /=0 рассчитывается тем самым устанавливается положение границы критической области на временной оси; 3) находится один из восьми возможных вариантов соотношения величин і и 4) для найденного варианта рассчитывается (с использованием формулы (1.6.2)) вероятность Poiilti+0), 0) в любой момент времени i (0 i ti+l - ti); при этом для третьего варианта (формула (1.6.7)) и седьмого варианта (формула (1.6.9)) может выполняться либо 0 i ti+x - ti , либо i ti+x - ti ; 5) рассчитывается вероятность (і i) в момент времени i = ti+1 - ti , т.е. (чti+1-0) (по формуле (1.6.2)); затем производится пересчет апостериорной вероятности в момент времени ti+i, т.е. находится (i\ti+i+0) (по формуле (1.6.3)); i увеличивается на единицу и алгоритм переходит на шаг 2) и т.д.
Сделаем важное замечание. В силу формулы пересчета (1.6.3) значение (іti+0) зависит от всех моментов ti,…, ti наступления событий в потоке, т.е. вся предыдущая информация “сосредоточена” в вероятности ( ti+0). Вследствие этого для определения безусловной вероятности ошибки необходимо усреднить условную вероятность ошибки P0((i\ti+0), i) по моментам наступления событий t,…, ti. Однако найти функцию распределения вероятностей моментов tu…, ti наступления событий в обобщенном асинхронном потоке в явном виде представляется затруднительным или, вообще, невозможным. Определить безусловную вероятность ошибки возможно только для некоторых частных и особых случаев.
Представляет интерес получить условные и безусловные вероятности ошибочного решения о состоянии потока для частных и особых случаев соотношения параметров i , i , i=1,2, p, q, рассмотренных в разделе 1.4.
1. x+qx= +pi , p q (соответствует частному случаю 1 в разделе 1.4). Тогда і = ї = 2/(i+2), 2=(l– q)/(p– q), a = (і+2) (р - q) 0. Так как (1t0+0)=ь то из (2) следует, что (i 0)=i для 0 0 t - t, т.е. (іtі -0)=і. Тогда из (1.6.3) вытекает, что ю(Х1ґ1+0)=тг1 и т.д. Таким образом, имеем фі\тг)=пи тг 0, /=0,1,... . Последнее говорит о том, что при таком соотношении параметров информация о моментах наступления событий t\,..., tm не оказывает влияния на апостериорную вероятность (0( 1 тг-), т.е. в конечном итоге не влияет на качество оценивания состояний процесса Щ. Решение о том или ином состоянии обобщенного асихронного потока выносится на основании априорных данных. При этом ВерОЯТНОСТЬ P0((O(Xi\tj+0), Tj) = 7Г2 , ЄСЛИ 71і 7Г2 , Либо P0((O(Xi\tj+0), Tj) = щ , если 7іі 7І2 , /=0,1,... , т.е. в данном частном случае Po((o(Xi\ti+0), тг) является безусловной вероятностью ошибочного решения. 2. Подкоренное выражение в (1.3.2) равно нулю: (h-h+an- f+4ща2 (1-р)(1-q) =0 (соответствует частному случаю 3 в разделе 1.4). Данная ситуация возможна в двух случаях: 2Л.р=\, 0 q 1, h- X2=a2-ai. Тогда а = (\-q) a2 0, coi=co2=l. При этом ф1 1 + 0) + (1 - q)a2 f1 - ф1 1 + 0)1т, Ф1 і) = Г П /л u l , 0, = 0,1,-; 1 + (1 - g)a2 [1 - co(A,1 f,- + 0)Jx (1.6.10) ш( .+0)= №+( -ga2M .-0) 1 2+да2 + (1-д)а2ю( ґг-0) Подставляя (1.6.10) в (1.6.1), находим границу критической области = 2[(1/2)-ш( К.+0)] . = 0,1, Х/ (1- r)a2 [1-00( Г,- +0)], 1
В данном случае условная вероятность ошибки P0((o(X1ti+0), тi) по-прежнему зависит от соотношения величин ю и (o(X1ti+0) и полностью совпадает с вариантами 1) - 8) для общего случая (в выражениях (1.6.6) - (1.6.9) вероятность (o(k1\ii) определяется формулой (1.6.12)). 4. h+pщ = h+qa2, p=q, 0 q 1 (соответствует особому случаю 3 в разделе 1.4). Тогда a=0 и формула (1.6.12) примет вид: (u(X1 Tt) = n1 + [(u(X1tt+0)-n1]e (1 q)(a1+a2)T- , тг- 0,/ = 0,1,.... (1.6.14) Формула пересчета сохранится в виде (1.6.13). Так как со(Х1t0+0)=я1 то из (14) следует, что co(X1 i0)=7i1 для 0 т0 t 10, т.е. со(Х1t 1 - 0)=7і1. Тогда из (1.6.13) вытекает, что ю(Х1тi)=7і1 тi 0, i=0,1,... . Получили результат, идентичный результату частного случая 1.
Алгоритмы расчета условной вероятности ошибки аналогичны алгоритму расчета вероятности P0(ю(?1ti+0), тi) для общего случая. Перейдем теперь к рассмотрению особых случаев соотношения параметров Xt, аг , /=1,2, р, q, для которых возможно вычисление безусловной вероятности ошибки. 1. l pqa , 0 p \, 0 q \, 12Ф0, l qai (соответствует частному случаю 6 в разделе 1.4). Последнее ограничение вытекает из того, что отмеченная связь параметров (здесь и далее Х2 = pqa /h) влечет за собой равенство a=(lA,i)(Xi-?a2)( h+pai). Тогда а О, если Х а2. Для расчета апостериорной вероятности &(h\Ti) справедлива формула (1.6.2). Формула пересчета (1.6.3) при этом приобретает вид: (Xl\ti+0) = nl = Xl/(Xl + pal) , і = 1,2,.... (1.6.15) В (1.6.15) fcj - апостериорная вероятность того, что процесс X(t) в момент времени tj+О находится в первом состоянии при условии, что в момент времени tt, /=1,2,... , произошло событие обобщенного асинхронного потока. Из (1.6.15) вытекает, что апостериорная вероятность ю(А,ітг-) не зависит от предыстории, т.е. обобщенный асинхронный поток событий в данном случае является рекуррентным потоком. Формула (1.6.2) при этом выписывается в виде со( ) - - - (Г , х а (1.6.16) Здесь величины а)! и ю2 определены в (1.3.25), (1.3.26). Подставляя (1.6.16) в (1.6.1), находим границу критической области т для любого интервала {U, t1+l), /=0,1,... , в виде y-lbfa-fX»,- ,) („17) с (щ-\/2)(2-щ) где c = yl(X1-X2+a1-a2)2+4a1a2(\-p)(\-q). Из (1.6.17) следует идентичность вариантов положения т на временной оси с вариантами 1) - 8) для общего случая, в которых (Х +О) нужно заменить на щ. При этом в формулах (1.6.6) — (1.6.9) условная вероятность ошибки P0((o(Xi\tj+0), тг) заменяется на уловную вероятность ошибки Ро(т), а апостериорная вероятность ю(Хітг) - на апостериорную вероятность ю(А,іт).
Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков
Для получения численных расчетов оценки состояний наблюдаемого потока при непродлевающемся мертвом времени разработан алгоритм вычисления апостериорной вероятности (\t). Программа расчета состоит из двух этапов.
Первый этап расчета предполагает имитационное моделирование обобщенного асинхронного потока событий, схемы создания непродлевающегося мертвого времени и наблюдаемого потока событий. Второй этап расчета -непосредственное вычисление вероятностей і 0, t0 t h\ (д-+0); (і0, tt t U+T; {\U+T); (i0, U+T t ti+1, /=1, 2, …, по формулам, полученным в разделе 1.7, и определение оценки X(t). Расчеты произведены для следующих значений параметров : = 4, 2 = 1, i = 0,05, 2 = 0,08, р = 0,4, q = 0,7, Т = 2 ед.времени и времени моделирования Тт =20 ед. времени. В качестве иллюстрации на рис. 3.2.1 приведена траектория (нижняя часть рис. 3.2.1) случайного процесса (f) (истинная траектория), полученная путем имитационного моделирования, где 1, 2 - состояния процесса (f), и траектория (верхняя часть рис. 3.2.1) оценки X(t), где 1, 2 - состояния оценки X(t). Вынесение решения о том или ином состоянии процесса ) производилось с шагом t = 0,05. На рис. 3.2.1 штриховкой на оси времени обозначены временные промежутки, на которых оценка состояния не совпадает с истинным значением процесса ) (области ошибочных решений). На рис. 3.2.2 приведена траектория поведения апостериорной вероятности (i\t), соответствующая полученной при имитационном моделировании последовательности моментов наступления событий t\, t2,… и
В разделе 1.7.3 приведен алгоритм оптимального оценивания состояний потока в условиях непродлевающегося мертвого времени. Для установления частоты ошибочных решений о состоянии случайного процесса (t) по наблюдениям за обобщенным асинхронным потоком, функционирующим в условиях мертвого времени (наблюдаемый поток), проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров 1, 2, 1, 2, p, q, Т ед.времени осуществляется (здесь и далее с шагом t = 0,05) моделирование наблюдаемого потока событий на заданном отрезке времени [0, T] (отдельный / й эксперимент, / = 1, 2, … ); 2) осуществляется расчет апостериорных вероятностей ( 1t) первого состояния процесса (f) на заданном отрезке времени [0, T] по формулам (1.3.25), (1.3.26) и (1.7.4) - (1.7.6) для случая присутствия мертвого времени; 3) осуществляется оценивание траектории процесса (f) (оценивание на отрезке [0, Тт ] интервалов, когда оценка X(t) принимает то или
Во-первых, отметим, что анализ проведенных многочисленных вариантов численных расчетов по оценке безусловной вероятности ошибочного решения P0(T) показывает, что оценка P0(T) является достаточно стабильной для Tm 100 113 ед.времени. Вследствие этого время моделирования Tm для всех экспериментов, результаты которых представлены в таблицах 3.2.1 – 3.2.5, было выбрано равным 100 ед.времени. Во-вторых, анализ численных результатов, приведенных в таблицах 3.2.1 – 3.2.5, показывает: 1) значение оценки безусловной вероятности ошибочного решения P0(T) увеличивается с увеличением длительности мертвого времени Т (Т = 1, 2, …, 9 ед.времени); последнее является вполне естественным, так как при увеличении длительности мертвого времени происходит увеличение потерь полезной информации о потоке событий, что в конечном итоге отрицательно сказывается на качестве оценивания; 2) при фиксированной длительности мертвого времени Т значения оценки P0(T) уменьшаются в зависимости от 1 (1 = 4, 5, 6, 7, 8), что является естественным, так как при увеличении разности 1 –2 условия различимости состояний потока улучшаются; 3) оценка дисперсии DT для всех вариантов расчета достаточно мала. . Результаты численных расчетов вероятности ошибки для общего случая и для случая рекуррентных потоков
В подразделе 1.6.1 получены формулы для условной вероятности ошибки при вынесении решения о состоянии обобщенного асинхронного потока в общем случае.
Для получения численных результатов разработан алгоритм вычисления условной вероятности ошибки P0((1ti+0), i) для общего случая, а также для частных и особых случаев. Первый этап расчета предполагает имитационное моделирование обобщенного асинхронного потока событий. Второй этап расчета – непосредственное вычисление условной вероятности ошибки P0((1ti+0), i) по формулам (1.6.6) – (1.6.9). Расчеты произведены для общего случая и для следующих значений параметров : 1=2, 2=1, 1=0,01, 2=0,02, p=0,1, q=0,9 и времени моделирования Tm =100 ед. времени. В качестве иллюстрации на рис.3.3.1 приведена траектория (верхняя часть рис. 3.3.1) случайного процесса (t), полученная путем имитационного моделирования (истинное поведение ненаблюдаемого процесса (/)), где 1, 2 - состояния процесса (t), и траектория (нижняя часть рис. 3.3.1) оценки X(t), полученной по критерию максимума апостериорной вероятности, где 1, 2 - состояния оценки i(t). Вынесение решения о состоянии процесса (t) производилось с шагом /=0,05. На рис. 3.3.1 штриховкой на оси времени обозначены временные промежутки, на которых оценка состояния не совпадает с истинным значением процесса (f) (области ошибочных решений). На рис. 3.3.2 приведена траектория поведения апостериорной вероятности ( 1г), /=0,1,…., соответствующая полученной при имитационном моделировании последовательности моментов наступления событий t1, t2,… . На рис. 3.3.3 приведена траектория условной вероятности ошибки P0(( 1tj+0), І) , /=0,1,…., соответствующая той же последовательности моментов наступления событий.
