Главная » Статьи » Студентам » Имитационное моделирование

5.1 Введение в теорию марковских цепей

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

 

Стохастический процесс

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

  • дискретные и непрерывные, 
  • марковские и немарковские, и т.д.

 

Цепь Маркова

Определение 1. Последовательность состояний дискретного марковского процесса называется цепью Маркова.

Изучение цепей Маркова начнем с простого примера.

Пример 5.1. Предположим, что изменение погоды происходит не чаще одного дня. Ограничимся только тремя возможными состояниями погоды: «Солнечно», «Облачно», «Дождь». Для большей простоты, предположим, что погода каждого последующего дня устанавливается случайным образом, независимо от ее состояния в настоящий и прошедшие дни. Будем использовать мультиномиальный закон распределения (таблица 5.1).

 

Таблица 5.1. Вероятности состояний

Состояние

С

О

Д

Вероятность

1/2

1/3

1/6

 

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


 

С

О

Д

С

0.6

0.3

0.1

О

0.4

0.5

0.1

Д

0.3

0.4

0.3

Рис. 5.1. Матрица вероятностей переходов

 

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

 

Рис. 5.2. Схема торгового павильона

 

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

 

 

1

2

 

3

4

5

6

1

 

 

 

 

1

 

 

2

 

 

  1/2

 

1/2

 

3

 

1

   

 

 

 

4

1/2

 

 

 

  1/2

 

5

 

1/3  

 

1/3

 

1/3

6

 

 

 

 

 

1

 

 

Взяв за исходное состояние 1, можно представить реализацию данного процесса в следующем виде: 145256523254…

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

Определение 2. Цепью называют последовательность состояний  и процесс переходов из состояния в состояние.

В зависимости от времени пребывания системы в каждом состоянии различают процессы с дискретным и непрерывным временем.

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

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

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

Определение 3. Граф состояний системы представляет собой совокупность вершин, изображающих  возможные  состояния  системы  ,  и совокупность ветвей, изображающих возможные переходы системы из одного состояния в другое.

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

 

 

Rabota UA

 

 
 
 
 
Категория: Имитационное моделирование | Добавил: kvn2us (26.01.2009) | Автор: Кравченко Владимир Николаевич
Просмотров: 4970 | Теги: марковский процесс, цепи Маркова, матрица вероятностей переходов, Марковские цепи
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]