Марковский процесс и его основные характеристики

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное

учреждение

высшего профессионального  образования

«УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО  «УдГУ»)

 

ИНСТИТУТ  ЭКОНОМИКИ И УПРАВЛЕНИЯ

 

Кафедра управления социально-экономическими системами

 

 

 

 

 

РЕФЕРАТ

по дисциплине «количественные  методы в управлении»

на тему «Марковский процесс  и его основные характеристики»

 

 

 

 

Выполнил

Студент гр.080213-11 В.С. Зайчикова

 

Руководитель

доцент кафедры А.Ф. Гольман

 

Ижевск, 2013

Содержание 

1.1.Основные понятия Марковских процессов 3

1.2 Марковский процесс с дискретным временем 6

1.3 Марковские случайные процессы с непрерывным временем 7

1.4. Цепь Маркова 8

1.5 Однородная цепь Маркова. Переходные вероятности. Матрица перехода 8

1.6 Равенство Маркова 9

 

 

 

 

 

1.1.Основные понятия Марковских процессов

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

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

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

Как указывалось, Марковские случайные  процессы относятся к частным  случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

      Случайной  функцией называется функция, значение которой при любом значении аргумента является случайной величиной (СВ). По- иному, СФ можно назвать функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид.

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

       Нетрудно заметить, что если обозначить состояние и изобразить зависимость , то такая зависимость и будет случайной функцией.

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

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

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

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

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

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей, описывающий начальное состояние системы:

 

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа:

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

 

1. Невозвратное множество:

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

2. Возвратное множество:

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

 

 

 

 

3. Эргодическое множество:

В случае эргодического  множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество:

 
При попадании системы в это  множество процесс заканчивается.

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

 

 

1.2 Марковский процесс с дискретным временем

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

Каждый  переход характеризуется вероятностью перехода Pij. Вероятность P_ij показывает, как часто после попадания в i-е состояние осуществляется затем переход в j-е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

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

 

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

 

Математический  аппарат дискретных Марковских цепей

Основным  математическим соотношением для ДМЦ  является уравнение, с помощью которого определяется состояние системы  на любом ее k-м шаге. Это уравнение  имеет вид:

и называется уравнением Колмогорова-Чепмена.

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

 

1.3 Марковские случайные процессы с непрерывным временем

Снова модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние).

Теперь  каждый переход характеризуется  плотностью вероятности перехода λ_ij. По определению:

При этом плотность понимают как распределение  вероятности во времени.

Переход из i-го состояния в j-е происходит в случайные моменты времени, которые определяются интенсивностью перехода λij.

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

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

 

 

1.4. Цепь Маркова

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

Для цепей  Маркова вероятность перейти  в какое-либо состояние    в момент   зависит только от того, в каком состоянии система находилась в момент , и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния   в состояние ).

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

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

 

1.5 Однородная цепь Маркова. Переходные вероятности. Матрица перехода

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

Случайное блуждание − пример однородной цепи Маркова с дискретным временем.

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

Матрицей  перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

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

Сумма полной  вероятности равна:

1.6 Равенство Маркова

Обозначим через    вероятность того, что в результате   шагов (испытаний) система перейдет из состояния   в состояние . Например,   – вероятность перехода за 10 шагов из второго состояния в пятое.

Подчеркнем, что при    получим переходные вероятности: 

Поставим  перед собой задачу: зная переходные вероятности    найти вероятности   перехода системы из состояния в состояние   за   шагов.

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

По формуле  полной вероятности, получим 

Эту формулу  называют равенством Маркова.

Пояснение. Введем обозначения:

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

По  формуле полной вероятности,

Или в принятых нами обозначениях

,что совпадает с формулой Маркова.

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

Действительно, положив    в равенстве Маркова

Получим

Или

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