Теория случайных процессов (1042226), страница 5
Текст из файла (страница 5)
В силу первого утверждения найдутся вершины j и k , такие, что i → j → k . Поскольку i — существенная вершина, найдется путь возврата из k в i:i → j → k → ... → i. Таким образом, из всякой вершины k , в которую возможен переход из вершины j , возможно и возвращение,т. е. j — существенная вершина.3) Смысл этого утверждения состоит в том, что за несущественной вершиной могут следовать несущественные вершины,но обязательно следует хотя бы одна сщественная.Пусть за несущественной вершиной следует последовательность несущественных (и тогда попарно различных) вершин: i →→ j1 → j2 → ...
→ jk . Но таких вершин может быть лишь конечное число, поэтому на некотором шаге (например, k -м) окажется,что список несущественных вершин исчерпан. Согласно первомуутверждению существует вершина, следующая за jk -й, и этавершина может быть только существенной.Из основной теоремы (ОТ) вытекают следующие утверждения.а) Множество вершин S ГС разбивается на два подмножества — существенных (Sc ) и несущественных (Sн ) вершин.б) Множество Sc замкнуто в том смысле, что если системав процессе эволюции окажется в состоянии i ∈ Sc , то в силуутверждения 2) ОТ она никогда его не покинет.в) Множество Sн открыто в том смысле, что в силу утверждения 3) ОТ при старте из несущественного состояния системаобязательно перейдет из Sн в Sc .г) Множество Sн может быть пустым (например, на рис. 10),тогда как согласно ОТ множество Sc всегда содержит хотя быодну вершину.21Рис.
10д) Отношение сообщаемости на множестве Sc обладает свойствами рефлексивности, симметричности и транзитивности, поэтому Sc можно разбить на замкнутые классы сообщающихсяЛекция 5. Анализ структуры пространства состояний33вершин, называемые классами эквивалентности (КЭ). КЭ, состоящий из одной вершины, и сама такая вершина называютсяпоглощающими.Универсальный алгоритм построения КЭ изложен в [1],но если ГС не очень сложен, то можно строить их в соответствии с определением.
Берется произвольная вершина i ∈ Sc , и кней присоединяются все вершины, сообщающиеся с i (т. е. всевершины, принадлежащие контуру Ïn (i, i)). В результате будетполучен K1 — первый КЭ. Если множество вершин K1 6= S , товыбирается произвольная вершина j ∈ S\K1 и к ней присоединяются все вершины, сообщающиеся с j (т. е.
все вершины, принадлежащие контуру Пn (j , j)). В результате будет получен K2 —Tвторой КЭ; очевидно, K1 K2 = ∅. Этот процесс продолжаетсядо тех пор, пока не будут исчерпаны все существенные вершины,т. е. пока не будут построены все попарно непересекающиеся КЭ,образующие разбиение множества Sc . На рис. 9 ГС имеет дваКЭ: K1 = {2, 3, 4}, K2 = {1}.Структура класса эквивалентностиРассмотрим ГС ДЦМ, состоящей из единственного КЭ(рис. 11) со множеством вершин Sc . Он разбивается на d = 4циклических подкласса (ЦП) Ck , k = 0, 1, ... , d − 1, обладающиеследующими свойствами:• в пределах каждого ЦП вершины не связаны дугами ине имеют петель,• подклассы циклически замкнуты, т.
е. C0 → C1 → C2 →→ ... → Cd−1 → C0 .12C03C145C26Рис. 112 Г.А. Соколов7C334Разд. 2. Дискретные цепи МарковаКЭ с d > 1 ЦП называются циклическими; КЭ, которыйне является циклическим, другими словами, состоящий из единственного подкласса C0 = Sc , называется регулярным. Легкопроверить, что наличие хотя бы одной петли в ГС КЭ являетсядостаточным условием его регулярности. Действительно, любойКЭ может быть либо циклическим (d > 1), либо регулярным.Если вершина i имеет петлю, то никакое истинное подмножествомножества вершин этого КЭ, содержащее вершину i, не можетбыть ЦП; следовательно, последовательности, состоящей хотябы из двух ЦП, не существует, т.
е. данный КЭ не являетсяциклическим и поэтому регулярен.Алгоритм построения последовательности ЦП КЭВведем предварительно два полезных понятия:• если i — вершина ГС, то Γ (i) = {j : pij > 0} — образвершины i;S• если C — подмножество вершин ГС, то Γ (C) =Γ (i) —i∈Cобраз подмножества C .Шаг 1. Выбираем произвольную вершину i ∈ Sc и образуем подмножество S0 = {i}.Шаг 2. Строим последовательность Sk = Γ (Sk−1 ), k = 1, 2, ... ,до тех пор пока впервые Sk не пересечется хотя бы с однимиз предшествующих Sk−1 , Sk−2 , ... , S0 .Шаг 3. Если Sk = S0 , то требуемая последовательность построена:C0 = S0 , C1 = S1 , ...
, Ck−1 = Sk−1 , d = k.Если Sk 6= S0 , но Sk пересекается с Sk1 , Sk2 , ... , то эти подмножества исключаютсяпоследовательности, SkSSиз построеннойSзаменяется на Sk Sk1 Sk2 ... , члены полученной последовательности нумеруются заново числами 0, 1, 2, ... и процесспродолжается согласно шагу 2.Пример 5.1. Рассмотрим КЭ на рис. 11 и воспользуемсяизложенным алгоритмом.Шаг 1. Выбираем вершину i = 1 и формируем множество S0 == {1}.Шаг 2.
Строим последовательноS1 = Γ (S0 ) = {3} ⇒ S2 = Γ (3) = {4} ⇒⇒ S3 = Γ (4) = {5, 6, 7} ⇒ S4 = Γ (5, 6, 7) = {1, 2}.Лекция 5. Анализ структуры пространства состояний35Шаг 3. S4 пересекается,Sно не совпадает с S0 ⇒ S0 исключаем,S4 заменяем на S4 S0 = S4 и после перенумерации получаем последовательностьS0 = {3} ⇒ S1 = {4} ⇒ S2 = {5, 6, 7} ⇒ S3 = {1, 2}.Шаг 4. В соответствии с шагом 2 строим S4 = Γ (1, 2) = {3}и обнаруживаем S3 = S0 ⇒ конец ⇒ последовательностьЦПК имеет видC0 = {3} ⇒ C1 = {4} ⇒ C2 = {5, 6, 7} ⇒ C3 = {1, 2}.Пример 5.2. ГС (рис.
12) отличается от ГС предыдущегопримера лишь наличием петли (6,6).2134567Рис. 12Шаг 1. Выбираем вершину 1 и формируем множество S0 = {1}.Шаг 2. Строим последовательно — см. пример 5.1:S1 = {3} ⇒ S2 = {4} ⇒ S3 = {5, 6, 7} ⇒ S4 = {1, 2, 6}.Шаг 3. S4 пересекается, но не совпадает с S0 ⇒ построеннаяпоследовательность Si корректируется: S0 = {3} ⇒ S1 == {4} ⇒ S2 = {1, 2, 5, 6, 7}.Шаг 4.
В соответствии с шагом 2 алгоритма строим множествоS3 = {1, 2, 3, 6}, которое пересекается с S2 и S3 ⇒вновькорректируется последовательность Si :S0 = {4} ⇒ S1 = {1, 2, 5, 6, 7} ⇒ S2 = {1, 2, 3, 5, 6, 7}.Шаг 5. В соответствии с шагом 2 алгоритма строим множествоS3 = {1, 2, ... , 7}, которое пересекается со всеми предыдущими, и после корректировки получаем2*36Разд. 2.
Дискретные цепи МарковаS0 = {1, 2, ... , 7} ⇒ S1 = {1, 2, ... , 7} ⇒ S1 = S0 ⇒конец ⇒ последовательность ЦПК состоит из единственного подкласса, совпадающего с Sc .Классификация ДЦМЦепи, для которых Sн = ∅, а Sc образует единственный КЭ,называются неразложимыми, или неприводимыми (НЦ). НЦмогут быть регулярными (НРЦ), если КЭ — регулярный, илициклическими (НЦЦ), если КЭ — циклический. Цепь, содержащая как существенные, так и несущественные состояния,называется разложимой (РЦ), или приводимой. РЦ может включать ровно один КЭ — тогда она называется моноэргодической(МЦ), — либо два или более КЭ — тогда она называетсяполиэргодической (ПЦ).
МЦ может быть регулярной (МРЦ),если КЭ — регулярный, или циклической (МЦЦ), если КЭ —циклический. ПЦ может быть регулярной (ПРЦ), если все КЭ —регулярные, циклической (ПЦЦ), если все КЭ — циклические,или смешанной (ПСЦ), если цепь содержит хотя бы один регулярный и хотя бы один циклический КЭ. Частным случаемМЦ и ПЦ являются моноэргодическая поглощающая (МПЦ)и полиэргодическая поглощающая (ППЦ) цепи, когда каждыйКЭ является поглощающим.Схема классификации цепи представлена на рис. 13.ЦМНЦНРЦРЦНЦЦМЦМРЦМЦЦПЦПРЦМПЦППЦРис.
13ПЦЦПСЦ37Лекция 5. Анализ структуры пространства состоянийКаноническая нумерация состоянийи каноническая форма МВПРассмотрим наиболее общий тип ДЦМ — ПЦ с L КЭ,занумерованными в произвольном порядке числами 1, 2, ... , L.Каноническая нумерация состояний (вершин ГС) осуществляется по следующему правилу: сначала в соответствии с номерамиКЭ произвольно нумеруются существенные состояния (вершиныГС) числами 1, 2, ... , Nс ; затем также произвольно нумеруются несущественные состояния (вершины ГС) числами Nс + 1,Nс + 2, ... , N . Канонической нумерации состояний (вершин ГС)однозначно соответствуют канонические формы МВП и матрицысмежности ГС A = (aij ), где aij = 1, если i → j , и aij = 0, еслиi не влечет j .Пример 5.3. Пусть ГС ДЦМ представлен на рис.
14. Требуется дать полный структурный анализ (ПСА), т. е:• построить разбиение множества всех состояний S на подмножества существенных Sc и несущественных Sн состояний,а также разбиение Sc на классы эквивалентности;• построить для каждого КЭ последовательность его ЦПК;• определить тип цепи и построить МВП в каноническойформе.Итак, по определению Sc = {1, 2, 3, 4, 5, 6}, Sн = {7, 8, 9}.Sc разбивается на три КЭ: K1 = {1, 2}, K2 = {3, 4, 5}, K3 = {6} —все они, очевидно, регулярные ⇒ цепь является полиэргодической регулярной. МВП в канонической форме имеет вид1234567891/3 2/3 T10000002 1000000003 000 1 /2 1 /2 00004 00 1/2 0 1/2 T200 00 1 /2 1 /2 0T30005 T6 00000100000 1 /3 1 /3 1 /3 0007 000R 0 0 1 /3 Q 1 /38 1 /31 /3 1 /3 00000 1 /3 091.Блок T управляет переходами на множестве существенных состояний. Он, в свою очередь, разбивается на три блока Ti ,38Разд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
