русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Марковские цепи


Дата добавления: 2013-12-23; просмотров: 1670; Нарушение авторских прав


Марковские цепи и непрерывные цепи Маркова

 

 

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью. Для такого процесса моменты t1,t2,…, когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t, а номер шага 1, 2,…,k,…Случайный процесс в этом случае характеризуется последовательностью состояний S(0), S(1), S(2),…, S(k),…, где S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы после первого шага; S(k) - состояние системы после k-го шага.

Событие {S(k) =Si}, состоящее в том, что сразу после k-го шага система находится в состоянии Si (i = 1, 2,…), является случайным событием. Последовательность состояний S(0), S(1), S(2),…, S(k),… можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью если для каждого шага вероятность перехода из любого состояния Si в любое Sj не зависит от того, когда и как система пришла в состояние Si. Начальное состояние S(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятности Pi(k) того, что после k-го шага (и до (k+ 1)-го) система S будет находиться в состоянии Si (i = 1, 2,…n). Очевидно, что для любогоk

n

Pi(k)=1.

i = 1

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

 

P1(0),P2(0),…, Pi(0),…,Pn(0).

В частном случае, если начальное состояние системы S в точности известно S(0)= Si, то начальная вероятность Pi(0) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на k-ом шаге из состояния Si в состояние Sj называется вероятность того, что система S после k-го шага окажется в состоянии Sj при условии, что непосредственно перед этим (после (k- 1)-го шага) она находилась в состоянии Si. Поскольку система может пребывать в одном из n состояний, то для каждого момента времени t необходимо задать n2 вероятностей перехода Pij, которые удобно представить в виде следующей матрицы:



 

P11 P12 … P1n

P21 P22 … P2n

Pij║ = … … … …

Pi1 Pi2 … Pin

… … … …

Pn1 Pn2 … Pnn

где Pij - вероятность перехода за один шаг из состояния Si в состояние Sj;

Pii - вероятность задержки системы в состоянии Si.

Эта матрица называется переходной или матрицей переходных вероятностей. Если переходные вероятности не зависят от номера шага (от времени), а зависят только от того, из какого состояния в какое осуществляется переход, то соответствующая цепь Маркова называется однородной.

Переходные вероятности однородной марковской цепи Pijобразуют квадратную матрицу размера n×n. Отметим некоторые ее особенности:

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

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

3. Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

n

Pij = 1,i =1,…,n;

j = 1

4. По главной диагонали матрицы переходных вероятностей стоят вероятности Piiтого, что система не выйдет из состояния Si, а останется в нем.

Если для однородной марковской цепи заданы начальное распределение вероятностей и матрица переходных вероятностей, то вероятности состояний системы Pi(k) (i= 1,…,n;j= 1,…, n) определяются по рекуррентной формуле:

 

n

Pi(k) = ∑ Pj(k- 1)∙Pij,(i= 1,…, n; j= 1,…, n).

j = 1

 



<== предыдущая лекция | следующая лекция ==>
Основные понятия марковских процессов | Непрерывные цепи Маркова


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.