Композиция и декомпозиция дискретных марковских процессов и их применение тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Кистаури, Элгуджа Иванович

• Кистаури, Элгуджа Иванович
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Кистаури, Элгуджа Иванович

с т р

ВВЕДЕНИЕ.

ГЛАВА I. КОМПОЗИЦИЯ И ДЕКОМПОЗИЦИЯ ДИСКРЕТНЫХ МАРКОВСКИХ

ПРОЦЕССОВ (ДЩ) С ДИСКРЕТНЫМ ВРЕМЕНЕМ.

§1.1. Пространственное (неасимптотическое) и временное укрупнение состояний ДО

§1.2. Параллельная композиция и декомпозиция дискретных марковских процессов

1.2.1. Параллельная композиция ДМП.

1.2.2. Изоморфная параллельная декомпозиция

1.2.3. Гомоморфная параллельная декомпозиция

ДМП.%.

1.2.4. Параллельная декомпозиция с растяжением времени процессов независимых испытаний

§1.3. Последовательная композиция и декомпозиция дискретных марковских процессов

1.3.1. Последовательная композиция ЛЩ

1.3.2. Последовательная изоморфная декомпозиция ДМП.

1.3.3. Последовательная гомоморфная декомпозиция ДЩ1.

§1.4. Петельная декомпозиция дискретных марковских процессов.

§1.5. Последовательная декомпозиция ДМП на процесс независимых испытаний и систему детерминированных дискретных марковских процессов

Краткие выводы

ГЛАВА П. КОМПОЗИЦИЯ И ДЕКОМПОЗИЦИЯ ДИСКРЕТНЫХ МАРКОВСКИХ

ПРОЦЕССОВ С НЕПРЕРЫВНЫМ ВРЕМЕНЕМ.

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

§2.2. Изоморфная параллельная декомпозиция ДМП с непрерывным временем.

§2.3. Гомоморфная параллельная декомпозиция ДШ с непрерывным временем.

2.3.1. Изменение спектра инфинитезимальной матрицы при расщеплении и параллельной композиции

2.3.2. Расщепление состояний ДШ с непрерывным временем и гомоморфная декомпозиция.

Краткие выводы.

ГЛАВА Ш. ПРИМЕНЕНИЕ МЕТОДОВ КОМПОЗИЦИИ И ДЕКОМПОЗИЦИИ «ВДП

§3.1. Применение параллельной декомпозиции ДО1 с непрерывным временем при вычислении спектра инфинитезимальной матрицы и решения систем дифференциальных уравнений Колмогорова . ЮЗ

§3.2. Применение параллельной декомпозиции ДО при вычислении стационарного распределения

§3.3. О стационарном распределении возмущенных

§3.4. О стационарном распределении недекомпозируемых ДМП с дискретным временем.

§3.5. Программирование процесса декомпозиции 124 Краткие выводы

Введение диссертации (часть автореферата) на тему «Композиция и декомпозиция дискретных марковских процессов и их применение»

Дискретные однородные марковские процессы (ДМШ fШ (t дискретно или t^o), введенные впервые А.А.Марковым в работах /Чб»V?/, получили в дальнейшем интенсивное развитие в основополагающих работах советских и зарубежных авторов ^36 ' »53» 15 »19 » 51/.определим коротко однородный ДМП. Пусть t меняется дискретно, t-0,1,2, • • • и пусть задано множество состояний начальное распределение р= (F? i£ 6 ^ч) , ^^{И51 ^ l Tj , iel и стохастическая матрица J?= (F?j ^'»¿бЦ , = = V »t=о, i, L'ijfel» тогда эволюция соответствующего однородного ДМП определяется конечномерным распределением р {с w =JK , о«4 =п ^ , vu, jK 61 ■

Если t^o, то множество состояний I , начальное распределение р= (Рс е -У и стандартная матрица Pit) -^(fy^ei; определяют соответствующее конечномерное распределение однородного ДМП J ct) с непрерывным временем, t^O.Однородный ДЩ fit), t^o можно задать также множеством состояний I , начальным распределением р =• (ft j ^е X) и инфини-тезимальной матрицей В'(о) = (F!J(0);hj еТ) » где PL>j (°) О , pjto) ±о и P'fo) = - Я?к/0->з ¿1 • в этом случае стандартная матрица JrOt) определяется решением прямых или обратных систем дифференциальных уравнений Колмогорова.

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

- 5

Пространственное укрупнение состояний существует двух видов: неасимптотическое и асимптотическое. Неасимптотическое укрупнение состояний ДШ „сначала были рассмотрены в работах ВилА 9 RosentiJt /55 /% Rostn.iiM / €б / и fomey ,

Snttl/62» /( ав дальнейшем обобщены для марковских процессов с произвольным фазовым пространством Захариным Л С применением вероятностной меры, в работе Л для дщ со счетным множеством состояний, нами был предложен метод построения укрупняющих матриц,с помощью которых там же рассмотрены необходимые и достаточные условия неасимптотического укрупнения состояний ДМП \tt) , t>'0 в матричной форме. Рассмотрим задачу неасимптотического укрупнения состояний ЩI, которое в дальнейшем будет применено при исследовании некоторых видов декомпозиции.

Предположим, что имеется некоторое отображение f •• I^Io, где , тогда если VieTcJj обозначить JC£=f~4o и допустить, что , если и только если f («*) = f(A) ,то мы получим разбиение Л = № ■ £ бТа)) множества I ДШ I ш ( t меняется дискретно или t>"0 ) на непересекающиеся подмножества ЗСс , С 6- Iil; t при котором

Будем говорить, что случайный процесс f L\lb>) получен в результате пространственного неасимптотического укрупнения состояний исходного дал fit; посредством разбиения ЛС .

Согласно 1 для того чтобы процесс {Clw) являлся дискретным марковским цроцессом, необходима и достаточна инвариантность переходных вероятностей из состояния к в подмножество ttj , и

Рассмотрим неасимптотическое укрупнение с расщеплением состояний ,ВДП , имеющего множество состояний Х = {1}2; ■}•

Расщепим т- -ое состояние на > ^ , где ^ - конечное натуральное число и построим расщепленный ДЩП f с-ь; с

ГУ множеством СОСТОЯНИЙ I = {*■>&> •••) •jM-. jrrn-1;. ^ и начальным распределением р = (Pi, ,., , R^, Pm+Í,.) , где fj, = К£ , Pm.>/0 .а р = ft,." начальное распределение ДШ foto . Если . t то ст0хаотическая матрица £ строится из Р ( J? - стохастическая матрица исходного ДШ f ct; , t=0,1,2,.) добавлением новых И" столбцов и строк с учетом того, что если fit) укрупнить по разбиению у = (Г-Д, ••• i 3 i то получится fit; . Дня ДШ fit) , fc-S-o такое преобразование нужно осуществить с помощью инфинитезимальной матрицы P'fq). Расщепление состояний ДШ является полезным тогда, когда при разбиении Л£ множества состояний I ДШ |4t) , условия инвариантности переходных вероятностей из к в нарушаются для некоторым к eX¿ и , но яри выполнении определенных условий с расщеплением состояний удается построить ДШ . укрупняемый по некоторому разбиению, отличному от © . Временное укрупнение однородного ДШ f(к-j, и. =:о, !,£,•.• с множеством состояний X - •• , начальным распределением р = (p¿ ■) с е Х^) и стохастической матрицей J? = ~ (^'/»¿^заключается в следующем: из I выделяется некоторое конечное или счетное подмножество 10 и ДШ fcuo , п. = 0,1,2,. наблюдается только в те моменты, когда он находится в Х0. Как известно, при таком наблюдении мы получим моделируемый ДШ fw с множеством состояний J0 , начальным распределением р = Ut(E4-Qj-*R (1,1,7) и стохастической матрицей где Ё1= а Н , V , С) , 13. и , ^ - подматрицы 2 и подвектора р , соответствующие подмножествам 1о и 1\Х0 .

Асимптотическое укрупнение состояний ДОЛ мы не рассматриваем и отметим только, что в ряде работ ^""5 * Зд-43 » ^»50/ исследуются различные вопросы асимптотического укрупнения состояний марковских и полумарковских процессов и плодотворно используются при решении соответствующих прикладных задач.

Перейдем теперь к рассмотрению композиции ДОЗ. Параллельная композиция независимых «ВДП , к=±7уп. , т-^оо ( дискретно или непрерывно) состоит в том, что рассматривается ^ -мерный процесс [(1)И:) ^^. Легко проверить, что этот ^-мерный процесс, как в случае дискретного, так и для непрерывного Ь , является ДШ. Пусть $г(Ъ), -условный ДШ в смысле равенств

В {%и)=?г > <5= 07^/^(05

1.3.1) или

1.3.2) или же л. Р £?,(•)=А} Д (1.3.3)

- 8

Г^В.сГ^; Г2» Г^Г.

Если вероятностный процесс (^хШ является «ЩИ, где - условный дискретный марковский процесс в смысле равенств (1.3.1), (1.3.2) или (1.3.3), тогда назовем последовательной композицией и ^(Ь) .

Можно показать, что данный вид композиции справедлив при наличии некоторого детерминированного ДШ с двумя состояниями.

Нетрудно проверить, что если есть ДШ, то

- дал.

Наконец рассмотрим петельную композицию ДШ. Предположим, что процесс является ДО1,где ^¿а)- условный ДШ в смысле равенств (1.3.1),(1.3.2),(1.3.3) и наоборот, £±(0 также является условным ДУШ в смысле равенств, аналогичных (1.3.1),(1.3.2),(1.3.3), тогда назовем (^«О? петельной композицией 5j.it) и 1-0 ,

Первые исследования по декомпозиции переключательных схем были выполнены в работах /56/ и «"«*«* /6Х/,

Различные вопросы декомпозиции вероятностных автоматов рассмотрены в статьях Вахдж. М/$ р^ /64/$ ТилаЛаляен. /69/> Рц.¿сумЬо /60/^ /59/9 Гиоргадзе /7>8// и в монографии Ра£ /65/.

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

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

Определение 1.2,2. ДМП ^(-О и Уш ( Ъ дискретно или Ь>/о) с множествами состояний I и 10 являются изоморфными в узком смысле, если существует взаимнооднозначная функция {'• } что =ь с вероятностью I.

Определение 1.2.3. ДМП и ( Ь дискретно или с множествами состояний X и 1о являются изоморфными в широком смысле, если существует взаимнооднозначная функция ^ •• Г Х0 , что К^О и имеют одинаковые характеристики (множество состояний, начальное распределение и стохастическую или стандартную матрицу).

Определение 1.2.4. Пусть имеется ДМП \Ш ( 6 дискретно или Ь>/0 ) с множеством состояний X . Если существует ДМП с множеством состояний 10 » где Х0£Х такой, что | с вероятностью I, то назовем сужением ДМП .

Определение 1.2.5. Пусть имеется ДМП \ш ( Ь дискретно или ЪЪо ) с множеством состояний 1=-{1-Д-, З,--} . Если существуют независимые ДМП с множествами состояний , 1(к>с I , кгЗТТЯ ; | такие, что \сь) есть сужение в узком смысле параллельной композиции (

С¥Л>1±)), то , назовем параллельной изоморфной декомпозицией с покрытием ДМП \сь) в узком смысле.

Определение 1.2.6. Если ДМП \Ш ( •Ь дискретно или Ъ^о) изоморфен в узком смысле композиции (, . . > где

- ю к- независимые ДМП, тогда будем говорить, что | щ допускает параллельную изоморфную декомпозицию без покрытия.

Любая изоморфная модификация э ? называется параллельной изоморфной декомпозицией с покрытием или без покрытия соответственно ДМП \ (-ь; в широком смысле.

Определения 1.2.5 и 1,2,6 можно коротко так сформулировать: если с точностью изоморфизма Н ,, -. , или где > к = ^ независимые ДМП, а Н - оператор сужения, то будем говорить, что имеет место изоморфная параллельная декомпозиция с покрытием или без покрытия.

Если \ СО = -Ь С 1с1)Н:>, 1а> ш , -. • , 1(т)ш) , где ^^(.ь) , - независимые ДМП, а - оператор неасимптотического укрупнения, то будем говорить, что ^(Ь) допускает параллельную гомоморфную декомпозицию.

Если = ь))9 »1=0,1,4,. ,где ьь) и 1,кг1 - процессы независимых испытаний (ПНИ), при этом и независимы, а М - оператор моделирования (о моделировании см. временное укрупнение), тогда будем говорить, что имеет место параллельная декомпозиция с растяжением времени ПНИ.

Предположим, что с точностью изоморфизма - Н(^(Ю,$ця.)), 1Д, . , где ^¿(п.) - условный ДШ относительно ^г(п-) в смысле равенств (1.3,1), (1,3,2) и (1.3.3), тогда имеем последовательную изоморфную декомпозицию с покрытием, а если тоже является условным ДМП относительно $кл>) в смысле равенств »аналогичных

- II

1.3,1), (1.3.2) и (1.3.3), то имеем петельную изоморфную декомпозицию. В случае последовательной гомоморфной декомпозиции ^съ) = -Ь <л.)) , где и обычные ДО1, а ^сю - условный ДОП относительно в смысле равенств (1.3.1), (1.3.2) или (1.3.3).

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

1) для дискретных марковских процессов с дискретным временем вводится и изучается параллельная и последовательная композиция и декомпозиция (изоморфная декомпозиция с покрытием и без покрытия, гомоморфная и петельная декомпозиция, параллельная декомпозиция с растяжением времени процессов независимых испытаний, последовательная гомоморфная декомпозиция на процессе независимых испытаний и детерминированных ДМШ;

2) параллельная композиция и декомпозиция (изоморфная декомпозиция с покрытием и без покрытия, гомоморфная декомпозиция) дискретных, марковских процессов с непрерывным временем;

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

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

Научную новизну работы составляют :

1) введение и изучение различных видов последовательной и параллельной изоморфной и гомоморфной декомпозиции дискретных марковских процессов с дискретным или непрерывным временем;

2) декомпозиция с растяжением времени процессов независимых испытаний, декомпозиция ДШ на процесс независимых испытаний и систему детерминированных дискретных марковских процессов;

3) введение параллельной и последовательной композиции дискретных марковских процессов, что дает возможность построения этих процессов с определенными свойствами;

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

- 13 распределения невозмущенных, возмущенных и недекомпозируемых ДМП;

5) программирование процесса декомпозиции, т.е. исследование декомпозируемости заданного дискретного марковского процесса с помощью ЭВМ;

6) метод построения укрупняющих матриц при неасимптотическом укрупнении ДМП jT(i> tt ■ дискретно или tlo .

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

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

1) при построении (синтезе) дискретных марковских процессов или стохастических систем, описываемых этими процессами с определенными свойствами; .

2) при нахождении спектра инфинитезимальной матрицы или решении системы дифференциальных уравнений Колмогорова дискретных марковских процессов с непрерывным временем;

3) при вычислении стационарных вероятностей параллельно декомпозируемых дискретных марковских процессов (ДМП) Jet) » t дискретно или Ыо, а также для недекомпозируемых, возмущенных и невозмущенных ДМП ft»g , п. г о, i,£,. и при решении всех задач, связанных со стационарным распределением (вычисления среднего времени пребывания в исправном подмножестве состояний с помощью вложенной цепи Маркова дискретного полумарковского процесса, описывающего заданную стохастическую систему, при вычислении коэффициента готовности стохастической системы, при вычислении среднего или полного ожидаемого дохода системы, управляемой дискретным полумарковским процессом).

На защиту выносятся следующие основные положения и результаты:

- постановка задачи композиции и декомпозиции ДШ,имеющая прикладное значение при исследовании стохастических систем;

- параллельная гомоморфная и изоморфная декомпозиция ДШ f(-k) ( Ь дискретно или tïo);

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

- результаты по последовательной и петельной декомпозиции ДДОП , YL-Ox . ;

- применение параллельной гомоморфной и изоморфной декомпозиции «ЩИ f (-Ь) , при вычислении спектра инфините-зимальной матрицы и решения системы дифференциальных уравнений Колмогорова, при вычислении стационарного распределения ЛМП t дискретно или ) и возмущенных ДШ £сЪ) ;

- рассмотрение преобразования недекомпозируемых ДШ на декомпозируемые ДШ f0tn.) , ». , при котором стационарные распределения совпадают.

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

- 15

В первой главе рассматриваются ДЩП только с дискретным временем.

В §1.1 рассматривается разбиение множества состояний I = {±>Z> - 3" ДМП fei) на систему непересекающихся подмножеств. ЕСЛИ X КОНеЧНО, Т.е. X - I**. Л> ' • • S mj , т^оо , то с применением соответствующей форлулы комбинаторного анализа получим, что число всевозможных разбиений есть С* * 2 '

Для заданного разбиения множества состояний I ДО1 f^J назовем укрупняющими матрицы Ц^ и , если U^PI^ ,где PÄ и Р - стохастические матрицы исходного и укрупненного ДШ. Отметим, что метод, приведенный в работе ^GZ для построения Цк и A4 , не пригоден дяя ДШ со счетным множеством состояний, когда может иметь счетное количество элементов. Рассмотрим другой метод построения Ця и Vit . Пусть -ft - > l е некоторое разбиение множества I , где при этом JZcnJCj-fl , если Clj и .¡¿¡¡fj =1 • de J

Для произвольного стохастического вектора е = (е* Т), где е^фО , припишем подмножеству вероятностную меру | , Щ е5С и построим укрупняющие матрицы oteJcj ъ /; v° е*

1 xsciLZ>et

1JT«I| 1 ' 7 jJC^I

I.I.2) г,

1.1.3) где с о, ¿гзс*

Теорема 1.1.2. Для того, чтобы ДШ \ул>) допускал при любом начальном распределении пространственное укрупнение в классе ЛМП по разбиению ЛС , необходимо и достаточно выполнение условия у« = р\4 (1.1.6)

В первом пункте §1.2 устанавливается, что параллельная композиция . ? ^Ц) независимых ДОЛ к--¿Тт. есть ДДО с множеством состояний начальным распределением р^ар^в-. • в р£,н> и стохастической матрицей Р* ® • • • «В* , где ® - знак кронекерового произведения.

Выше мы уже приводили определение параллельной изоморфной декомпозиции ДОЛ , 1,2. с покрытием или без покрытия. Основным результатом п.1.2.2 является следующая теорема.

Теорема 1.2.1. Для того, чтобы ЛМП ^си,) , п^о,!,^,. . допускал параллельную изоморфную декомпозицию с покрытием на МП. , ; 9 необходимо и достаточно существование таких разбиений , летворяют следующим условиям: которые удов

- 17

I) допускает пространственное укрупнение по -Х1К\ li.il; т.

2) & - стохастически независимы относительно {с*.) ;

Стохастическая независимость относительно ^(Л) означает следующее: , е31(К) , к, для которых 0 выполняются равенства т. . га '(«О 7 Ж1 Л р{ 6 1 (1.2.7)

И т. пг п:

При доказательстве необходимости теоремы пользуемся тем, т. что, применяя определение 1.2.5, сужение параллельной композиции ••• ? Г^Ц) на подмножестве В множества "" * определяет ДМП изоморфный . Подмножество В разбивается на цилиндрические подмножества ^^ , , которые порождают разбиения , Л-^Тт. множества состояний II »удовлетворяющие условиям 1)-3).

При доказательстве достаточности нужно построить ДМП

Ю с укрупнением состояний ДШ по Ж!к) , к**, т. брать параллельную композицию [т=. ^ и, применяя свойства 2) и 3), установить справедливость определения 1.2.5.

Рассмотрим разбиения ; ¿к > множества * 1(кки , где X , а 1(Ю ={±'Аг- >МК}9 £: Мк ^ , ХТ^ь на цилиндрических подмножествах, где t { 1М».Ч : СЧ><*Г%)" *1(П)} '

Если сопоставить каждому кортежу (и, ¿2,и) номер т-1 т то (с1; , А-ЗГГ^г порождают разбиения &(с1) , оЬЗТТч. множества I , где . ¡п

И1*},Л*>= | V Л М*Л"^)'-«} (1.2.18)

Следствие 1.2.1. Для того, чтобы Щ1 , п. г о, 1,2,. . с множеством состояний 1= • допускал параллельную изоморфную декомпозицию без покрытия на ДШ <г(К)с«.) , к=¿7; , с множествами состояний 1г1)сI , Х00^!^-, — с ^о » необходимо и достаточно, чтобы он допускал пространственное укрупнение по разбиениям (1.2.18), которые являются независимы относительно ДМП .

Результаты п.1.2.2 были опубликованы нами в работе

25/.

Обобщением изоморфной параллельной декомпозиции, при которой используется оператор укрупнения Ь вместо сужения Н , является гомоморфная параллельная декомпозиция, которая исследована в пункте 1.2.3.

В пункте 1.2.4 доказывается следующая основная теорема.

Теорема 1.2.3

Ы /

Произвольный процесс независимых испытаний (ПНИ) с множеством состояний "'

- 19 начальным распределением р и стохастической матрицей £ допускает параллельную декомпозицию с растяжением времени , где Г^Г , а = {^v-, гт*** .

В §1.3 изучается последовательная декомпозиция ДО1 , ri-o, . • Выше мы уже определили последовательную композицию и декомпозицию ДЩ. Основными результатами пункта 1.3.2 являются следующие теоремы.

Теорема I.3.I. Для того, чтобы ДМП f(*o » л-о. 4,2,3,. . е I = { i j % -, 3 -, • ■• • } допускал последовательную изоморфную декомпозицию с покрытием типа I, необходимо и достаточно существование разбиений 1 и t множества I , которые удовлетворяют следующим условиям: а) ДШ допускает пространственное укрупнение по ; б) разбиения Ж и X. - стохастически независимы относительно ; в) , VStLt& и Ск&И .

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

Теорема 1.3.2. Для того, чтобы ДМП , л-о.л.г,.

0t) е I = {I') 3) •• • J допускал последовательную изоморфную декомпозицию с покрытием типа 2, необходимо и достаточно выполнение условий а) и в) предыдущей теоремы и г) если Хс » ffj^Jt; fy et » f- çl » тогда для любого фиксированного е С , отношения

Biçодинаковы V<<etK ; р - 20 д) -тг* одинаковы,

Теорема 1.3.3. Для того, чтобы ДМП FfK-J допускал последовательную изоморфную декомпозицию с покрытием типа 3, необходимо и достаточно существования разбиений Si и С »удовлетворяющих условиям а), в) ид) предыдущих теорем.

В п.1.3.3 рассматривается гомоморфная последовательная декомпозиция ЛМП , , 5) и приводятся результаты, аналогичные теоремам I.3.I, 1.3.2 и 1.3.3.

Мы уже определили петельную композицию. Соответствующие виды петельной декомпозиции содержатся в §1.4, а в §1.5 исследуется гомоморфная последовательная декомпозиция типа I ДМП на процесс независимых испытаний и детерминированных ЛМП, изученная нами в работе

28/.

Вторая глава посвящена вопросам, касающимся неасимптотического укрупнения состояний, композиции и декомпозиции ДМП с непрерывным временем ^»Zs/, в §§2.1, 2.2 содержится определение дал fct) , t^T = , неасимптотическое укрупнение состояний, параллельная композиция и изоморфная декомпозиция, которые являются аналогичными определениями §1.1, поэтому их подробно не рассматриваем. Отметим только, что параллельную изоморфную декомпозируемость для ДШ fct) , t^T можно проверить посредством начального распределения р и стандартной матрицы Pit) или же с помощью р и инфинитезимальной матрицы P'io; = (PcJ(o) j L>itl) , если соответствующим образом изменить определения стохастической независимости разбиений

15/.

В §2.3 изучается гомоморфная декомпозиция ,ЩП f (-у , teT7 • Для этой цели, используя разложение стандартной матрицы с помо

- 21 щьго спектра инфинитезимальной матрицы и изменения спектра при расщеплении состояний, обосновывается алгоритм расщепления состояний ДОЛ , Ь&Т посредством инфинитезимальной матрицы. Пусть имеется разбиение © =■ { • -j^-j-- } множества состояний I ДШ [tt)} ЬьТ . Расщепим состояния w-v el 6 В«: на два, т.е. на э■■ of*, и образуем §£ = {м.•,••••> е d}} ^-.¿i}, В,--= . Подматрицу матрицы £4°), стоящую на пересечении строк из и столбцов из Bp »обозначим через -R/i? и назовем ее правильной, если сумма всех ее строк одинакова, VB^BptO .Пусть ®,Bt

А» а расщепленный ДМП есть ^it) .

Лемма 2.3.3. Для того, чтобы ДШ £ct> был укрупним по V

6 , необходимо и достаточно, чтобы при разбиении множества состояний I ДШ \ib) по 0 все подматрицы Р'со) являлись правильными, кроме и -^Lb^ » и выполнялись следующие условия

Теорема 2.3.1. Для того, чтобы ДО1 fc-fc) допускал параллельную гомоморфную декомпозицию на т. ДШ при расщеплении произвольного числа состояний на два состояния, необходимо и достаточно выполнение условий: V

1) при расщеплении fit) по О выполняются условия леммы 2.3.3;

2) X 1Ъ> укрупним по Ж1^ , к=2Г»п. и ЗС1>с)- независимы относительно » где один из ЗС(К) может совпасть

Л/ | с О , ; з> Чх£**а"> ■

Третья глава посвящена применению гомоморфной и изоморфной параллельной декомпозиции ДО1 при вычислении спектра ин-финитезимальной матрицы и решении систем дифференциальных уравнений Колмогорова; при вычислении стационарного распределения невозмущенных и возмущенных ДШ, а также недекомпозируе-мых ДШ.

В последнем параграфе - §3.5 приводится программа процесса параллельной изоморйной декомпозиции на языке ЕЬ-1. Рассмотрим коротко основные результаты этой главы.

Оказывается, что если ДОЛ допускает параллельную изоморфную декомпозицию без локрытия на ж ? <*> , ЫгТ ; еТ {1,2, ,

V. ^ УП 2, тогда является П кратным собственным числом характеристического уравнения

- А 6^=0 , где есть $ кратное собственное

ЧИСЛО ДМП , а Мр+-Ст .

Теорема 3.1.2. Если ДШ , ЪС-Т* допускает паралгр *1 1 "— лельную гомоморфную декомпозицию на ^ Ш , Ь(г I , % ± уи ¿. о* , тогда решением системы £'&) = Р(«РУе» является где Р* стандартная матрица ДШ , а У - разбиение композиции ДОЛ , определяющее ЛМП» изоморфный

- 23

Формула (3.1.I) принимает более ясный вид тогда, когда lib) допускает изоморфную параллельную декомпозицию.

Стационарное распределение f ДМП , *=о,±»2,. со стохастической матрицей Р является решением системы алгебраических уравнений

Р(Р-Е) =о

2& = 1 . (3*2Л) I* I

Ниже всюду предполагается, что решение системы (3.2.1) существует.

Основным результатом §3.2 является следующая теорема / Л

Теорема 3.2.1. Если ДМП |"(пО , и-0.1,2,- допускает параллельную гомоморфную декомпозицию на £°(гц>, п. г о, 4,2,». к-=iTi»t > t то его стационарное распределение f определяется равенством

3.2.4) где ?llt) - стационарное распределение ^l*-) , a If - разбиение композиции ДУШ , определяющее ДШ изоморфный .

Такая же теорема справедлива также для ДШ fct) , i^T , когда находится нормированное решение системы fP'(o)=o , а если имеется параллельная изоморфная декомпозиция, то формула (3.2.1) упрощается.

В §3.3 изучаются возмущенные ДМП /30,31/. Пусть имеется стохастическая матрица Р ДМП f(^) » и £ принимает значения из интервала j-maxfi- .mtn.R,. , 1-1- mini v

3.3.8)

- 24 тогда стохастической матрицей возмущенного ДМП служит

J?e = P + fCB-E) . Оказывается, что f£= f »т.е., если £ возмущение меняется в интервале (3.3.9), то оно не влияет на стационарное распределение. В этом же параграфе, кроме £ , рас-смариваются еще возмущения X и £ , имеющие матричную форму и приводятся соответствующие результаты.

В некоторых случаях, заданный ДШ fcn) , п = 0,1, 2, . не допускающий параллельной или последовательной гомоморфной (изоморфной) декомпозиции, можно преобразовать в ДШ l0tvt) »допускающий соответствующую декомпозицию, при которой стационарные распределения совпадают, т.е. f ~ f0 I 3£/ . Эти вопросы изучены в § 3.4.

Основные результаты диссертации докладывались на семинаре "Дискретные системы" (Института кибернетики АН ГССР, Тбилиси, 1978-1983 гг.), на семинарах Института математики АН УССР (отд. теории вероятностей и математической статистики, зав.отд.академик АН УССР Королюк B.C. и отд.теории случайных процессов, зав. отд.член.-корр. АН УССР Скороход A.B.), на ХУЛ и ХУШ школах-коллоквиумах по теории вероятностей и математической статистике (Бакуриани, 1982 г., 1983 г.) и опубликованы в работах /22-33, 13, 14 / .

Заключение диссертации по теме «Теория вероятностей и математическая статистика», Кистаури, Элгуджа Иванович

- 131 -ЗАКЛЮЧЕНИЕ

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

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

2. Рассмотрен способ параллельной и последовательной композиции дискретных марковских процессов (ДМП) с дискретным временем, а для ДМП с непрерывным временем только операция параллельной композиции.

- 132

3. Исследованы различные виды гомоморфной и изоморфной параллельной декомпозиции ДМП с дискретным или непрерывным временем. Для ДМП с дискретным временем изучены три вида последовательной изоморфной и гомоморфной декомпозиции, петельная декомпозиция и последовательная декомпозиция на процесс независимых испытаний и система детерминированных ДМП. Приведена также параллельная декомпозиция с растяжением времени процессов независимых испытаний.

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

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

6. Результаты, полученные относительно вложенных идеаль

- 133 ных и возмущенных ДМП с дискретным временем,применимы для вычисления времен пребывания в "исправном" подмножестве состояний стохастической системы, описываемой соответствующим дискретным полумарковским процессом.

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

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

9. В Институте кибернетики АН ГССР, на языке ?Ь-1, на машине М-4030 нами была разработана программа, обнаруживающая параллельную изоморфную декомпозицию с покрытием и без покрытия ДМП с дискретным временем.

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

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

- 134

В заключение выражаю благодарность научному руководителю -доктору технических наук А.Х.Гиоргадзе за постановку задачи и постоянное внимание.к выполняемой работе.

Список литературы диссертационного исследования кандидат физико-математических наук Кистаури, Элгуджа Иванович, 1984 год

1. Анисимов В.В. Асимптотическое укрупнение состояний случайных процессов. - Кибернетика, К., 1973, ЖЗ,с.109-117.

2. Анисимов В.В,, Ситюк В.Н. Асимптотическое поведение неоднородного пуассоновского потока с ведущей функцией, зависящей от малого параметра, управляемого цепью Маркова.-Кибернетика, К., 1977, М, с.149-150.

3. Анисимов В.В., Ситюк В.Н. Укрупнение неоднородной цепи Маркова с редкими нестационарными интенсивностями переходов между классами. Теория вероятностей и матем.статистика, 19, 1978, с.9-17.

4. Анисимов В.В. Асимптотический анализ надежности сложных систем под воздействием неоднородных: случайных возмущений. ДАН УССР, сер.А, Ж, 1979, с.66-69.

5. Анисимов В.В., Королюк В.В. Асимптотический анализ надежности полумарковских систем. Кибернетика, К., 1983, с.98-102.

6. Беллман Р. Введение в теорию матриц. М., "Наука", 1976.

7. Гиоргадзе А.Х. Некоторые методы пространственно-временной декомпозиции вероятностных автоматов. ДАН СССР, 232, М, 1977.

8. Гиоргадзе А.Х. Об аналоге теоремы Крона-Роудза для вероятностных автоматов. ДАН СССР, 233, Ж, 1977.

9. Гиоргадзе А.Х., Джебашвили Т.Л. К вопросу о декомпозиции вероятностных автоматов. Сообщения АН ГССР, Тб., 76, $2, 1974.- 136

10. Гиоргадзе А.Х., Джебашвшш Т.Л. Декомпозиция вероятностных автоматов с расщеплением состояний. Сообщения АН ГССР, Тб., 91, Ж, 1975.

11. Гиоргадзе А.Х. Декомпозиция вероятностных автоматов. -Труды ИК АН ГССР, 2, Тб., 1977.

12. Гиоргадзе А.Х., Кистаури Э.И. Схемная декомпозиция вероятностного автомата. Изв. АН СССР, техническая кибернетика, №6, 1976.

13. Гиоргадзе А.Х., Кистаури Э.И. К вопросу о моделировании процесса независимых испытаний, Сообщения АН ГССР, Тб., 91, Ж, 1975.

14. Гиоргадзе А.Х., Кистаури Э.И., Сафиулина А.Г. О петельной декомпозиции вероятностных, автоматов. Кибернетика,К., М, 1977.

15. Гихман П.И., Скород A.B. Теория случайных процессов. М., "Наука", I, 1971.

16. Гихман П.И., Скороход A.B. Теория случайных процессов. М., "Наука", 2, 1973.

17. Гихман П.И., Скороход A.B. Введение в теорию случайных процессов. М., "Наука", 1977.

18. Дынкин Е.Б. Марковские процессы. М.: Физматгиз, 1963.

19. Дуб Дд. Вероятностные процессы. М.: ИЛ, 1956.

20. Захарин А.М. Об укрупнении состояний марковских и полумарковских процессов и применение операции укрупнения для анализа стохастических систем. Кибернетика, К., №4,1972.

21. Захарин А.М. Связь между операциями укрупнения и декомпозиции однородных марковских процессов. ДАН УССР,сер.А,1. М2, 1977.

22. Кистаури Э.И. Решение системы дифференциальных уравнений Колмогорова дня конечных однородных марковских процессов с применением собственных чисел и матриц. Сообщения АН ГССР, Тб., 82, №2, 1976.

23. Кистаури Э.И. Об укрупнении состояний цепей Маркова с непрерывным временем. Сообщения АН ГССР, Тб., 93, №2, 1976.

24. Кистаури Э.И. Параллельная композиция и декомпозиция конечных однородных марковских систем. Кибернетика, К., №4, 1977.

25. Кистаури Э.И. Декомпозиция цепей Маркова со счетным множеством состояний. Деп.ВИНИТИ, №3304-77, 1977.

26. Кистаури Э.И. Декомпозиция дискретных марковских процессов в -мерном пространстве. Сообщения АН ГССР, Тб., 95, №, 1978.

27. Кистаури Э.И. Применение параллельной изоморфной декомпозиции дискретных марковских процессов в задачах доходов.-В сб. "Теоретическая кибернетика", Тб., "Мецниереба",1980.

28. Кистаури Э.И. Декомпозиция процессов независимых испытаний. В сб. "Теоретическая кибернетика", Тб., "Мецниере-ба", 1981.

29. Кистаури Э.И. Гомоморфная декомпозиция дискретных марковских процессов с дискретным временем. Сообщения АН ГССР, Тб., 102, 1981.

30. Кистаури Э.И. Применение декомпозиции дискретных марковских процессов для вычислений финальных вероятностей. -Сообщения АН ГССР, Тб., 104, №3, 1981.

31. Кистаури Э.И. Применение декомпозиции дискретных марковских процессов при вычислении стационарного распределения. ХУ1 Всес.школа-коллоквиум по теории вероятностей и математической статистике, Бакуриани, 1982.

32. Кистаури Э.И. О стационарном распределении недекомпози-руемых дискретных марковских процессов. В сб. "Случайный анализ и симптотические задачи теории вероятностей и математической статистики",Тб., "Мецниереба", 1984.

33. Кистаури Э.И., Стуруа Т. Параллельная декомпозиция дискретных марковских процессов. Алгоритмы и программы,1(52), 1983.

34. Коваленко П.Н. Исследования по анализу надежности сложных систем. К.: Наукова думка, 1975.

35. Колмогоров А.Н. Основные понятия теории вероятностей. -М., "Наука", 1974.

36. Колмогоров А.Н. Об аналитических методах в теории вероятностей. Успехи математических наук, 5(1938), перевод статьи из Mcl-U. Алл., 104, 1931.

37. Колмогоров А.Н. Цепи Маркова со счетным множеством возможных состояний. Билл, ун-та (А), 1:3, М., 1937.

38. Колмогоров А.Н., Фомин C.B. Элементы теории функции и функционального анализа. М., "Наука", 1972.

39. Королюк B.C., Турбин А.Ф. Анализ асимптотически укрупняемых сложных систем. В кн.: Математизация знаний и научно-технический прогресс. - К.: Наукова думка, 1975.

40. Королюк B.C. Укрупнение сложных систем (методические аспекты). Кибернетика, К., № I, 1977.- 13941. Королюк B.C., Турбин А.Ф. Полумарковские процессы и их приложения. К., Наукова думка, 1976.

41. Королюк B.C., Томусяк A.A., Турбин А.Ф. Алгоритм укрупнения цепей Маркова с помощью разрежения. В кн.: Аналитические методы теории случайных процессов. К., 1978,

42. Королюк B.C., Турбин А.Ф. Фазовое укрупнение сложных систем. К.: Виша школа, 1978.

43. Лоэв М. Теория вероятностей. М.: ИЛ, 1962.

44. Марков A.A. Исследование замечательного случая зависимых испытаний. ИАН (6), I, 1906.

45. Марков A.A. Пример статистического исследования над текстом "Евгений Онегин", иллюстрирующего связь испытанийв цепь. ИАН, 7, №3, 1913.

46. Романовский В.И. Дискретные цепи Маркова. М.-Л.: Гостех-издат, 1949.

47. Сарымсаков Т.А. Основы теории процессов Маркова. М.: Гостехиздат, 1954.

48. Сильвестров Д.С. Полумарковские процессы с дискретным множеством состояний, М.: Советское радио, 1980.

49. Сильвестров Д.С. Средние моменты достижения для полумарковских процессов и сети обслуживания.EleHi- I*.f.un¿ К¿ЪелгиеМ 16 (1980) ,8/3, с 399-415.

50. Феллер В. Введение в теорию вероятностей и ее применение. М.: Мир, I, 1967.

51. Феллер В. Введение в теорию вероятностей и ее применение. М.: Мир, 2, 1967.

52. Чжун К.Л. Однородные цепи Маркова. М.: Мир, 1964.54. ft. Т^ н Sío4aíixe ^1. Wr.f,г-г- л 0 ' Л ' ^IV он .1., iss-8. '1.fam. , J7 í9ío1. КМ*. , C^09Jf Me», Jvu

53. ЬЗ. K«*«^ г., K^ -betuímamiu1. Halb*,лг Д. ivfctí л«^^ waub>M<»i*. TetnUeJL1. T^JucUo*. h ftAUcbsUcc adjltncc Pzeii , 197 f .66. M. fuwc^^s a UoxXw P^o^

54. Cess -f&^t UaJLbovcavy . ^ /t/^,1. MoJl0 J. , A^ f9fg.spec/

55. UaJittv o-09dUi, ibotAviJi HjLUCi 0», fiffhM tf-tWfccJ, AlpTjHLvisi^ UnC.yl&Lsii^ t Exrawsicm. ijo FuKciiQMl ¿yf. lAoJiXw pz*> ouiu.-Sifln 1. fifpt. HJL.