16-19
.doc
16,17.Цепи Маркова. Дискретный или непрерывный случайный процесс X(t) называется Марковским, если для любого набора . т.е. если для , то значение ничего не добавляет (никакой информации) для определения распределения . Т.е. Марковский процесс определяется своим распределением вероятности второго порядка и, следовательно, может быть задан распределением вероятности первого порядка + вероятностями перехода. Дискретный Марковский процесс с дискретным временем называют цепью Маркова. Цепь Маркова имеет вид: – случайная величина, принимающая значения из множества Марковские цепи есть модель схемы независимых испытаний, когда существует зависимость исхода любого состояния только от исхода предыдущего. Имеем систему с дискретными состояниями. Если система в момент времени (т.е. ) находилась в состоянии , то вероятность перехода в состояние в момент зависит в общем случае от и не зависит от того, в каких состояниях система находилась в момент времени до Следовательно, цепь Маркова определяется через условные вероятности того, что система осуществит длинный переход. Цепь Маркова называется однородной, если переходные вероятности не зависят от времени, т.е.
Обозначим - вероятность перехода за один шаг. Тогда цепь Маркова будет описываться матрицей переходных вероятностей:
Матрица квадратная, неотрицательная, ∑ вероятностей по любой строке =1. Многошаговые переходные вероятности. Необходимо определить вероятность перехода системы из состояния в
|
18, Классификация состояний Смежные состояния – возможен переход за один шаг. Граф состояния системы: Вершины графа на рисунке – это состояния (все – вершины на шаге ), дуги – направление и вероятность перехода между смежными состояниями. Для построения графа Марковской цепи удобно использовать матрицу смежности. Состояние достигнуто из состояния , если такое, что . Пользуясь графовым представлением Марковского процесса, легко определить множества состояний, достижимых из фиксированного состояния . Для этого нужно найти матрицу достижимости , где - единичная матрица, - матрица смежности. Состояния и называются сообщающимися, если такое и, что . Состояние называют несущественным, если такое состояние , которое достижимо из , но состояние недостижимо из.
Все существующие состояния цепи естественно разбиваются на классы так, что все состояния принадлежащие одному классу, сообщаются, а разным классам – не сообщаются. Цепь Маркова называется неприводимой, если существует (ей соответствует) единственный класс сообщающихся состояний. Подмножество С состояний цепи Маркова называют замкнутым если никакое состояние вне С не может быть достигнуто ни из какого состояния, входящего в С.
Отражающий экран: Поглощающий экран:
|
19. Стационарное состояние цепи Маркова. Эргодические цепи Маркова.
При становится независимой от состояний и стремится к предельной вероятности: Распределение называется стационарным распределением вероятностей эргодической цепи Маркова, т.е. - вероятность того, что система будет находиться в состоянии при . При этом: Алгоритм нахождений - решение системы линейных уравнений: Цепь Маркова называется однородной, если переходные вероятности не зависят от времени, т.е. Обозначим - вероятность перехода за один шаг. Тогда цепь Маркова будет описываться матрицей переходных вероятностей: Матрица квадратная, неотрицательная, ∑ вероятностей по любой строке =1.
состояние за шагов. Цепь однородна. Оказывается, что для нахождения достаточно знать матрицу одношаговых переходов . Покажем это. Вводим промежуточный момент (шаг) : и будем рассматривать переход из в в два этапа: в за шагов, за ) шагов. Тогда из формулы полной вероятности: Следовательно элемент матрицы, полученный как произведение и , т.е. - уравнение Колмогорова-Чепмена. Т. матрица переходных вероятностей за шагов и ) шагов. Пусть , то: Если: и т.д. т.е.: Если представить исходное распределение вероятностей состояний системы в виде матрицы-строки: , то вероятности состояний системы в момент времени : Можно получить из уравнения: Марковские модели содержат полную информацию о двумерном законе распределения. Пример Марковского процесса:
Марковский процесс 2-го порядка:
Зафиксируем , . Решение определяется уравнением: , Т.е. от прошлого не зависит. Для линейных операторов второго порядка – нет, для определения состояния при необходимо знать не только , но и, например, . |