сгм. РГР_СГМ. Сети связи и системы коммутации

• Название: Сети связи и системы коммутации
• Дата: 03.11.2019
• Размер: 0.75 Mb.
• Имя файла: РГР_СГМ.docx
• Тип: Документы; #93232
• страница: 2 из 4

В данном подразделе рассмотрены основные математические операции выполняемые в редакторе Mathcad, более полный справочник функций приведен в приложении А.
2 Теоретический раздел
2.1 Однородные цепи Маркова
Понятие дискретного случайного процесса в дискретном времени.

Пусть имеется некоторая система, множество состояний которой является дискретным (конечным или счетным): W = {w₁, w₂, …}. Случайные события, приводящие к переходу системы от состояния к состоянию, происходят в дискретные моменты времени t₀, t₁, t₂,…, которые будем называть шагами и обозначать их в дальнейшем номером шага: n = 0, 1, 2, 3, …

Обозначим через S(n) состояние системы на n-м шаге. Запись S(n) = w_j означает, что на n‒м шаге система находится в состоянии wj. Непосредственный переход из состояния w_i в состояние w_j будем обозначать через w_i → w_j.

На каждом шаге система может находиться только в одном состоянии (множество состояний называют иногда фазовым пространством).

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

Марковская цепь относится к классу случайных процессов с дискретными состояниями и дискретным временем.
2.2. Переходные вероятности между состояниями

Из любого состояния w_i на n-м шаге система может с некоторыми вероятностями перейти в другие состояния или с определенной вероятностью остаться в нем. Здесь могут быть два основных случая.

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

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

2. Вероятности состояний на n-м шаге зависят от состояния на предыдущем, (n-1)-м шаге.

Марковская цепь относится к классу случайных процессов, вероятности состояний которых на n-м шаге зависят от состояния на предыдущем шаге.

Непосредственные переходы между состояниями описываются переходными вероятностями.

Переходной вероятностью (вероятностью перехода) на n-м шаге называется условная вероятность непосредственного перехода w_i → w_j на n-м шаге при условии, что на (n -1)-м шаге система находилась в состоянии w_i:



где S(n) и S(n -1) - обозначение случайного состояния на n-м и (n -1)-м шаге соответственно.
2.3 Понятие однородной цепи Маркова. Граф состояний

Однородной цепью Маркова называется случайный процесс с дискретными состояниями и с дискретным временем, вероятности состояний которого на любом шаге определяются только состоянием на предыдущем шаге:



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

Таким образом, вероятности p_i1, p_i2, p_i3, … образуют распределение вероятностей попадания из состояния w_i в состояния w₁, w₂, w₃, … за один шаг. Это распределение не зависит от номера шага, на котором происходит переход.

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

В случайном процессе с дискретными состояниями и с дискретным временем можно выделить три части: прошлое, настоящее и будущее относительно некоторого шага n (рисунок. 2.1).


Прошлое (n₀)

Настоящее (n₀)

Будущее (n>n₀)


Рисунок 2.1 – Разбиение случайного процесса на три части
Однородная Марковская цепь обладает свойством независимости будущего от прошлого при фиксированном настоящем. Будущее процесса (системы) зависит только от настоящего и не зависит от прошлого, то есть не зависит от того, каким путем система попала в настоящее. Таким образом, можно сказать, что при фиксированном настоящем будущее и прошлое однородной цепи Маркова независимы. Это свойство принято называть отсутствием последействия или Марковским свойством.

Марковское свойство может быть определено также следующим образом: для любого шага n₀ вероятность любого состояния системы в будущем (то есть при n > n₀) зависит только от ее состояния в настоящем (то есть при n=n₀) и не зависит от того, когда и каким образом система пришла в это состояние.

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

Каждому ребру приписывается переходная вероятность. Если ребро отсутствует, то переходная вероятность равна нулю. Возможные задержки в прежнем состоянии изображают стрелкой – петлей.

Пример. На рисунке 2.2 приведен граф из трех состояний. Множество состояний системы W = {w1, w2, w3}. Переходные вероятности: p₁₁ = 1/2, p₁₂= 1/2, p₂₁= 1/4, p₂₂ = 1/2, p₂₃ = 1/4, p₃₁ = 2/3, p₃₃ = 1/3.


w₁

w₃

1/2

1/2

1/3


w₂

1/2

1/4


1/4


2/3


Рисунок 2.2 – Пример графа из трех состояний
2.4 Среднее число шагов нахождения в состоянии


p_ii
На рисунке 2.3 приведена часть графа состояний, относящаяся к состоянию w_i. Указаны две вероятности: вероятность p_ii того, что состояние не изменится за один шаг, и вероятность 1 - p_ii того, что состояние изменится за один шаг (p_ii < 1).


w_i

1 – p_ii

Рисунок 2.3. – Часть графа состояний, относящаяся к состоянию w_i
После попадания в состояние w_i система будет находиться в нем случайное число шагов. Найдем среднее число шагов (или математическое ожидание числа шагов) нахождения в состоянии w_i., которое будем обозначать .

Обозначим через q_ii(n) вероятность того, что на n-м шаге система будет в состоянии w_i при условии, что до n-го шага система не покидала это состояние.

Пусть процесс начинается также в состоянии w_i, то есть начальная вероятность q_ii (0) = 1. Выпишем очевидные соотношения:





Среднее число шагов нахождения в состоянии w_i до выхода из него определяется суммой этих вероятностей, которая представляет собой сходящийся геометрический ряд (геометрическую прогрессию):

. (2.1)

Таким образом, среднее число шагов нахождения в состоянии w_i до выхода из него будет

Из этой формулы следует: чем больше вероятность p_ii, тем больше среднее время нахождения в состоянии w_i. Эта зависимость иллюстрируется таблице 2.1

Таблица 2.1. Зависимость среднего числа шагов нахождения в состоянии w_i от вероятности p_ii.

pii	0,01	0,1	0,5	0,9	0,99
	1,01	1,11	2,0	10,0	100,0

2.5 Классификация состояний

Рассмотрим следующие типы (классы) состояний: достижимые, сообщающиеся, несущественные и существенные, эргодическое множество и поглощающие состояния.

Состояние w_j достижимо из состояния w_i, если за некоторое число шагов система переходит из w_i в w_j, то есть существует такое n, что p_ij(n) > 0, где p_ij (n) – вероятность того, что S(n) = w_j при условии, что начальным является состояние w_i: p_ij (n) = p[S(n) = w_j / S(0) = w_i]. Состояние w_j не достижимо из состояния w_i, если не существует такого числа шагов n, при котором p_ij (n) > 0.

Смысл достижимости: если из w_i можно по стрелкам пройти в w_j, то со-стояние w_j достижимо из w_i.

На рисунке 2.4 состояние w₄ достижимо из состояния w₁, однако w₁ не достижимо из w₄.


w₁

W₂

W₃

W₄


Рисунок 2.4 – Пример достижимых и не достижимых состояний


w₁

W₂

W₃

W₄



Рисунок 2.5 – Пример взаимно достижимых состояний

Состояние w_i называется несущественным, если имеется такое состояние w_j и такое число шагов m, что p_ij (m) > 0, однако p_ji (n) = 0 при любом n. Состояние w_i называется существенным, если не имеется таких состояний w_j, то есть любое состояние, достижимое из w_i, сообщается с этим состоянием w_i.

Смысл этих состояний. Для несущественного состояния w_i имеется достижимое из него состояние w_j, однако w_i не достижимо из w_j. Иными словами, из каждого несущественного состояния система каким-либо образом может уйти в одно из существенных состояний и больше никогда в это несущественное состояние не вернется.

Несущественные и существенные состояния образуют соответственно множества несущественных и существенных состояний. Попав в множество существенных состояний, система никогда из него не выйдет.

На рисунке 2.6 состояния w₁ и w₂ являются несущественными, а состояния w₃, w₄, w₅ образуют множество существенных состояний.


w₁

w₂

w₅

w₄

w₃

Несущественные

состояния




Существенные

состояния

Рисунок 2.6 – Пример существенных и несущественных состояний
Теорема. При n → ∞ конечная цепь Маркова будет находиться только в существенных состояниях.

Смысл теоремы: если начальным является несущественное состояние, то с течением времени вероятность нахождения в несущественных состояниях стремится к нулю, то есть при n → ∞ конечная цепь Маркова будет находиться только в существенных состояниях.

Эргодическое множество состояний – это множество существенных сообщающихся состояний.


w₁

w₂

w₁

w₂

w₃
Смысл эргодического множества: из любого состояния можно попасть в любое другое состояние и из этого множества нельзя выйти (после попадания в него), то есть система, попадающая в эргодическое множество, никогда его не покидает. На рисунке 2.7 приведены два процесса состояния с эргодическим множеством состояний.



а)

б)


Рисунок 2.7 – Два примера эргодического множества состояний

Поглощающим называется состояние, если система после попадания в это состояние из него не выходит. Если w_i – поглощающее состояние, то переходные вероятности p_ii = 1 и p_ij = 0 для всех j ≠ i.

Цепь Маркова с поглощением – это цепь, множество состояний которой содержит хотя бы одно поглощающее состояние.

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

Матрица переходных вероятностей является матричной характеристикой переходов между состояниями однородной марковской цепи: P = ||p_ij||.

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

1) свойством неотрицательности, p_ij ≥ 0;

2) свойством нормированности: сумма элементов любой строки равна 1 или , где ‒ столбец, все элементы которого равны 1.

Каждая i ‒ я строка представляет собой распределение условных вероятностей перехода p_i1, p_i2, p_i3, …

Если множество состояний является конечным, то матрица переходных вероятностей является квадратной.

Замечание. После составления матрицы переходных вероятностей целесообразно сделать проверку условия |E – P| = 0, где E – единичная матрица.
2.7 Вероятности состояний однородной цепи Маркова

Вероятностью состояния на произвольном шаге называется вероятность того, что на n-м шаге система будет в состоянии w_j при условии, что состояние w_i было начальным: p_ij (n) = p[S(n) = w_j / S(0) = w_i], где S(0) - состояние системы на начальном шаге.

Выведем рекуррентную формулу для вычисления этих вероятностей.

Пусть состояние w_i является начальным. На (n – 1)-м шаге система будет

находиться в состоянии w_k с вероятностью p_ik(n - 1), из которого на n-м шаге она попадает в состояние w_j. Поэтому вероятность попадания в состояние w_j через состояние w_k равна p_ik(n-1) p_kj. По формуле полной вероятности вероятность попадания в состояние w_j на n-м шаге

(2.2)

Замечание. Суммирование ведется по всему множеству состояний.

Для нахождения вероятностей состояний и других характеристик системы в переходном и стационарном режимах целесообразно пользоваться методами матричного исчисления. Будем записывать вероятности состояний цепи Маркова p_ij(n) в виде матрицы: P(n) = ||p_ij(n) ||.

Формула (2.2) для вероятности p_ij(n) в матричном виде запишется следующим образом:

P(n) = P(n – 1) P. (2.3)

Каждый элемент матрицы P(n) представляет собой произведение i-й строки матрицы P(n – 1) на j-й столбец матрицы P.

Замечания. 1. Получено прямое уравнение А.Н.Колмогорова для Марковской цепи в отличие от обратного уравнения: P(n) = P P(n - 1).

2. Уравнение А.Н.Колмогорова в более общем виде

а) в развернутой форме: ;

б) в матричной форме: P(m + n) = P(m) P(n).

Для однородной Марковской цепи матрицы вероятностей состояний на первом, втором и т.д. шагах имеют вид:

P(1) = P(0) P = E P = P; P(2) = P(1) P = P²;

P(3) = P(2) P = P³; P(4) = P(3) P = P⁴; … P(n) = P(n -1) P = Pⁿ,

где P(0) = E – единичная матрица.

Замечания. 1. Принято, что P(0) = P⁰ = E является единичной матрицей.

2. Матрица P(n) является стохастической.

На начальном шаге (n = 0) начальным может быть не одно, а несколько состояний. В этом случае задают начальные вероятности состояний. Начальная вероятность p_i(0) состояния w_i – это вероятность того, что в начале процесса, то есть на начальном шаге, система находится в состоянии w_i:

p_i(0) = p[S(0) = w_i]. Будем записывать начальные вероятности в виде распределения (строки): .

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



для всех i, где – столбец, все элементы которого равны 1.

Если начальным является одно определенное состояние w_i, то элемент, соответствующий этому состоянию, равен 1, то есть p_i(0) =1, а остальные элементы равны нулю. Например, если начальным является первое состояние, то .

Распределение вероятностей состояний на n-м шаге будем записывать в виде сроки: . Очевидно, что j-й элемент этой строки равен произведению строки на j-й столбец матрицы P, или

(2.4)
Запишем эту рекуррентную формулу для n = 1, 2, 3, 4, … и для общего случая:

…

Замечание. Строка является стохастической.

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

Таблице 2.2 – Формулы для вычисления вероятностей состояний при разных начальных условиях

Матрица вероятностей состояний цепи Маркова при начальных условиях P(0) = E	P(n) = Pn
Распределение вероятностей состояний цепи Маркова при заданном начальном распределении

2.8 Предельные вероятности эргодической цепи Маркова

Эргодическая цепь Маркова – это такая цепь, множество состояний которой образует одно эргодическое множество.

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

Синонимы: финальная вероятность, стационарная вероятность.

Смысл предельной вероятности: есть средняя доля числа шагов нахождения в состоянии w_j при бесконечном протекании процесса.

Теорема о существовании и единственности предельных вероятностей. Для эргодической однородной цепи Маркова существует единственное пре-дельное распределение вероятностей состояний, не зависящее от начального состояния:

(2.5)

Теорема приведена без доказательства.

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

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

2. Иногда эргодическую цепь определяют через существование предельных вероятностей: цепь Маркова называется эргодической, если для нее существуют предельные вероятности, не зависящие от начального состояния.

Поскольку вероятности не зависят от начального состояния, то они не зависят и от начального распределения, то есть

где ‒ распределение предельных вероятностей состояний.

Следующая теорема связывает распределение и матрицу P.

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

(2.6)

Доказательство. Устремив n →∞ в (2.4), получим:

то есть

Теорема доказана.

Замечание. Распределение называют также финальным, стационарным, предельным, инвариантным; иногда его называют еще неподвижным вектором матрицы P.

Смысл теоремы. Матричное уравнение (2.6) представляет собой однородную систему линейных алгебраических уравнений относительно неизвестных . Число неизвестных равно числу уравнений.

Система уравнений (2.6) относительно неизвестных является однородной, поэтому она совместна, однако ее решение является неопределенным, то есть решений бесконечно много. Неопределенность системы обусловлена тем, что строки матрицы P являются линейно зависимыми: на них наложена одна связь, а именно, свойство нормированности стохастической матрицы (сумма элементов любой строки равна 1). Поэтому ранг матрицы системы уравнений на единицу меньше числа неизвестных.

Добавив условие нормированности, или линейно независимое уравнение , получим систему уравнений, ранг которой равен числу неизвестных. Эта система уравнений является неоднородной, ее решение является единственным. Полученную систему уравнений можно решить известными методами, например, методом Гаусса. Если из системы убрать любое линейно зависимое уравнение, то получим систему m уравнений с m неизвестными, и ее можно решить методом Крамера.

2.9 Вычисление предельных вероятностей

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

Первая формула основана на обращении матриц:

(2.7)

где – матрица, полученная из исходной матрицы P вычеркиванием j-й строки и j-го столбца; E – единичная матрица; я строка матрицы P без элемента p_jj;

– столбец, все элементы которого равны 1.

Исходным уравнением для вывода этой формулы является равенство (2.6). Запишем это равенство, выделив в нем состояние w_j:



где – j –й столбец матрицы без элемента;

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



Строка в левой и правой части полученного равенства состоит из одного элемента (числа ) и строки Приравняем строки из левой и правой части равенства:



Преобразуем это равенство:



Умножим обе части последнего равенства на столбец справа, все элементы которого равны 1, что приводит к суммированию элементов строк:



Прибавим к левой и правой части вероятность :



С учетом условия нормированности имеем: Поэтому



откуда получаем формулу (2.7):

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

Замечание. Размеры перемножаемых матриц согласованы.

Вторая формула основана на вычислении определителей и приведена без вывода:

(2.8)

где определитель матрицы E – P_j.

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

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

(2.9)
где