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

Естественно, что для любого момента времени сумма вероятностей всех состояний равна единице (как сумма вероятностей полной группы несовместных событий):

2. Дискретный Марковский процесс, цепь Маркова

Пусть в некоторой системе происходит с.п. с дискретными состояниями и дискретным временем, т.е. переход системы из одного состояния в другое происходит только в определённые моменты времени . Эти моменты называют шагами процесса (обычно разности смежных моментов наблюдения равны постоянному числу – длине шага, принимаемого в качестве единицы времени); начало процесса.

Этот с.п. можно рассматривать как последовательность (цепь) событий .

начальное состояние системы, т.е. перед 1-м шагом; состояние системы после 1-го шага, состояние системы после 2-го шага и т.д.), т.е. событий вида где .

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью (цепь Маркова).

Отметим, что марковский цепь, в которой условные вероятности состояний в будущем зависят только от состояния на последнем этапе (и не зависят от предыдущих), называют простой цепью Маркова. (А.А. Марков 1856-1922- русский математик).

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

исправная работа;

профилактический осмотр и обслуживание;

ремонтная работа;

списание за негодностью;

Граф состояние работы изображен на рисунке

Рис. 1.11.(А.А. Белов, и др.)

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

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

Рис.1.12(Белов…)

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

Основной задачей исследования является нахождение вероятностей состояния на любом м шаге. Будем вычислять вероятности состояний дискретной системы

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

---

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

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

.

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

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

м шаге, в состояние м шаге она была в состоянии , т.е.

(43) ,

где первый индекс указывает на номер предшествующего, а второй индекс на номер последующего состояния системы.

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

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

(44) .

Элементы матрицы обладают основными свойствами обычных квадратных матриц и дополнительно следующими свойствами:

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

Вероятность состояния системы на следующем шаге определяется по рекуррентной формуле:

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

.

Имеет место утверждение.

Теорема 17.1. Для матрицы перехода вероятностей за шагов справедлива формула

(45) ,

где .

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

где

при этом, по определению матрицы перехода известно, что при любом .

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

Пример 3. Задана матрица перехода

.

Найти матрицы переходных вероятностей .

На основании правила умножения двух матриц получим

.

Задание. Проверьте, что верно равенство

.

Следует отметить, что конечная дискретная цепь Маркова представляет с собой дальнейшее обобщение схемы Бернулли, к тому же на случай зависимых испытаний; независимые испытания являются частным случаем марковской цепи. Здесь под «событием»

---

понимается состояние системы, а под «испытанием» понимается изменение состояния системы.

Если «испытания» (опыты) являются независимыми, то появление определённого события в любом опыте не зависит от результатов ранее произведённых испытаний.

Задания. а) Заданы матрицы переходов

1. ;

2. ;

3. .

Найти в каждом случае матрицу .

Ответы: а) 1. ;

2. ;

3.

в) Заданы матрицы переходов

; .

Найти .

Ответы: в) 1. ; 2. ;

3. .

Замечание. В общем случае дискретная марковская цепь представляет собой марковский случайный процесс, пространство состояний которого конечно или счётное, а множество индексов - множество всех неотрицательных целых чисел или его некоторое подмножество (конечное или счётное). Мы можем говорить об как об исходе го испытания.

Часто пространство состояний процесса удобно отожествить с множеством неотрицательных целых чисел и в этих случаях говорят, что находится в состоянии , если .

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

(46) .

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

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

Обычно вероятности объединяют в квадратную матрицу (конечную или счётную) в зависимости от рассматриваемого процесса:

,

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

В матрице я строка представляет собой распределение вероятностей с.в. при условии, что . Если число состояний, конечно, то - конечная квадратная матрица, порядок которой (число строк) равен числу состояний.

Естественно, что вероятности удовлетворяют следующим двум условиям:

а) ,

б) при каждом фиксированном

Условие б) отражает тот факт, что каждое испытание вызывает некоторый переход из одного состояния в другое состояние. Для удобства обычно говорят также о переходе и в том случае, когда состояние остаётся неизменным. Имеет место утверждение.

Теорема 17.2. Процесс полностью определён, если заданы вероятности (46), т.е.

,

и распределение вероятностей случайной величины .

Доказательство. Покажем, что для любого конечного как вычисляются вероятности

(47) ,

так как по формуле полной вероятности любые другие вероятности, относящиеся случайным величинам , могут быть получены суммированием слагаемых (членов) вида (47).

---

По определению условной вероятности имеем

(48)

.

Но по определению марковского процесса получим

(49)

Поставляя равенство (49) в (48) получим

(50) .

Продолжая этот процесс последовательно, получим:

(51) .

Процесс полностью определён. Что требовалась доказать.

3. Примеры Марковских цепей

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

А. Пространственно однородные марковские цепи

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

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

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

1. Определим процесс , положив с заданным начальным значением . Матрица переходных вероятностей этого процесса имеет вид

Тот факт, что в этом процессе у матрицы все строки одинаковы, означает , что случайная величина не зависит от с.в. .

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

.

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

Следовательно, матрица переходных вероятностей будет иметь вид

(52)

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

где и .

4. Расчет цепи Маркова для стационарного режима

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

(53) .

К этим уравнениям надо добавить нормировочное условие , отбросив любое (одно) из уравнений. Полученная система уравнений с неизвестными имеет единственное решение.

Пример 4. Вычислительная машина находится в одном из следующих состояний:

система исправно работает;

система неисправна, тестируется;

система неисправна, настраивается программное обеспечение;

---

система находится на профилактике;

система ремонтируется, модернизируется;

Размеченный граф состояний системы показан на рисунке

(Кн. Белов …стр 63)

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

Решение. Рассмотрим состояние системы в размеченном графе. В это состояние направлено две стрелки, следовательно, на основании (53) в левой части уравнения для

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

Аналогично запишем ещё три уравнения для оставшихся состояний (вершин графа):

В качестве пятого уравнения возьмём нормировочное уравнение . При решении системы уравнение для отбрасываем. Его можно в конце использовать для контроля полученного решения. Таким образом, перепишем систему уравнений в виде:

В результате решения системы методом подстановок получим:

.

Замечание. Для решения этого примера нам не потребовались вероятности «задержек»

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

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

Найти предельные (финальные) вероятности.

Решение. Сначала построим граф состояний (см.рис.).

Рис. 1.15из книги Белов и…стр.64

Пронумеруем состояний системы по числу неисправных ЭВМ:

ни одной неисправной; одна неисправна;

две неисправны; все три неисправны;

Для того чтобы система перешла из состояния в состояние , нужно, чтобы одна из трёх ЭВМ за время вышла из строя.

Эта вероятность в соответствии с законом распределения Бернулли равна Аналогично, находим:

.

Для того, чтобы система из состояния перешла в состояние нужно, чтобы неисправная ЭВМ за время была отремонтирована (событие А), а две исправные не вышли из строя (событие В). Тогда получим

Аналогично находим:

.

Рассуждая подобным образом, находим:

Составим матрицу переходов при и :

.

Для рассматриваемого примера система уравнений (53) может быть записана в следующем виде:

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

На этом мы закончим этот раздел и для читателей рекомендуем в целях более подробного ознакомления с этим важным разделом теории вероятностей обратиться к фундаментальным книгам [Гнеденко, Феллер и Карлин и др.].

В завершении этой тематики рассмотрим кратко понятие о непрерывном Марковском процессе и системы уравнения Колмогорова.

---

Смотрите также файлы

• 16-17 с рисунками.doc

• 18-19 с рисунками.doc

• 18-19.doc

• 13-15_ГОТОВЫЙ!!!.doc

• Экономика. Учебное пособие 2011.doc