Марковские процессы. Их математическое описание и область их применения

Санкт-Петербургский Государственный  Электротехнический Университет «ЛЭТИ»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Реферат по предмету Математический Аппарат Радиотехники

На тему: «Марковские  процессы. Их математическое описание и область их применения.»

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Ерохин А.А.

ФРТ гр.8194

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2010 год

 

ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ.

 

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

 

Понятие марковского случайного процесса.

 

     Функционирование  широкого класса систем  можно   представить как процесс   перехода   из   одного   состояния   в  другое  под воздействием  каких-либо      причин.      Например,      процесс  функционирования ЭВМ  характеризуется   тем,  что в каждый момент  времени обработкой информации  заняты те или иные блоки.  Процесс прохождения обрабатываемой   информации   по  блокам  ЭВМ   можно рассматривать как процесс  перехода системы из одного  состояния в другое. В   полной   мере   это   относится   и   к   процессу функционирования ЭВМ с точки зрения надежности.  В каждый момент времени некоторые узлы  работоспособны,  а некоторые отказали и

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

одного состояния в  другое.

     Пусть имеется   некоторая  физическая  система  S,  которая в процессе функционирования  может  принимать  различные   состояния Si. Если   состояния системы меняются  во  времени случайным образом, то процесс смены состояний можно рассматривать как случайный процесс, описываемый случайной функцией X(b).

     Полное множество  состояний  Si  исследуемой   системы  может быть либо  конечным   (i = 1, n), либо бесконечно  большим.

     Большинство  реальных   систем   имеет  дискретное  конечное пространство состояний.   Последовательность   состояний   такой системы Si (i = 1, n) и сам процесс  переходов  из  состояния  в состояние называется   цепью.   Ниже  будут  рассмотрены  только случайные цепи.

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

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

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

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

одного состояния в  другое.

 

 

 

 

МАРКОВСКИЕ СЛУЧАЙНЫЕ  ПРОЦЕССЫ

С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ  И ДИСКРЕТНЫМ ВРЕМЕНЕМ

 

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

 

    Пусть имеется некоторая система S,  которая в процессе функционирования может принимать различные состояния Si, i=1..n. Если состояния системы меняются случайным  образом,  то  последовательность состояний системы образует случайный процесс.

    Случайный процесс,  протекающий в системе S, называется марковским,  если для любого момента времени t0 вероятность любого состояния системы при t>t0 зависит только от ее состояния при t=t0  и  не зависит от того,  как и когда система пришла в это состояние.  Если число состояний Si,  которые система может принимать,  конечно,  то

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

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

    Обычно марковскую  цепь изображают в виде графа, вершины которого соответствуют возможным состояниям системы Si,  а дуги - возможным переходам системы из состояния Si -> Sj.  Каждой дуге соответствует переходная вероятность Pij(k)=P[Sj(k)/Si(k-1)] - это условная вероятность перехода системы на К-ом шаге в состояние Sj при  условии,  что на предыдущем (К-1)-ом этапе система находилась в состоянии Si.

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

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

                      ----> j

              | P11  P12 .... P1j .... P1n|

              | P21  P22 .... P2j .... P2n|    n              ____

  |Pij| =     | ..........................|  SUMMA(Pij)=1;  i=1, n

            | | Pi1  Pi2 .... Pij .... Pin|   j=1

            | | ..........................|

            i | Pn1  Pn2 .... Pnj .... Pnn|

 

    Для неоднородной  марковской  цепи требуется К  матриц,  где К - число шагов.

    Определим для   однородной марковской цепи вероятности всех состояний системы на каждом шаге по заданной матрице переходных  вероятностей |Pij|, причем известно начальное состояние системы.

    Пусть в начальный  момент t0 система находится в   состоянии  Si.

Тогда Pi(0)=1, Pj(0)=0, j=1,2,..,n, j=/=i. Найдем вероятности состояний   после   1-го   шага  P1(1)=Pi1,  P2(1)=Pi2,  ...,  Pj(1)=Pij,

...,Pn(1)=Pin.  Найдем вероятность  состояний после 2-го шага, рассматривая следующий набор гипотез:

    - после 1-го  шага система была в состоянии  S1;

    - после 1-го  шага система была в состоянии  S2;

     .............................................

    - после 1-го  шага система была в состоянии  Sn.

    Вероятности гипотез  известны и равны вероятностям состояний системы после 1-го шага.

 

    Тогда по формуле  полной вероятности:

       P1(2)=P1(1)*P11+P2(1)*P21+...+Pn(1)*Pn1

 

       P2(2)=P1(1)*P12+P2(1)*P22+...+Pn(1)*Pn2

       .......................................

               n                            ___

       Pi(2)=SUMMA [Pj(1)*Pji]             i=1,n

              j=1

    Аналогично после  3-го шага вероятности определяются  выражением

                 n                           ___

       Pi(3) = SUMMA [Pj(2)*Pji]            i=1,n

                j=1

    После К-го шага

                n                            ___

       Pi(k)= SUMMA [Pj(k-1)*Pji            i=1,n

               j=1

 

    Аналогично для  неоднородной марковской цепи

                n

       Pi(k)= SUMMA [Pj(k-1)*Pji(k)]        (2)

               j=1

 

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

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

    Эргодические  марковские цепи описываются сильно связанным  графом.  Это означает,  что в такой системе возможен переход из любого состояния Si в любое состояние Sj (i,j=1..n) за конечное число шагов.

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

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

    Для определения  стационарных вероятностей Pi нахождения  системы в состоянии Si (i=1..n) нужно составить систему n линейных однородных алгебраических уравнений с n неизвестными:

             n

       Pi= SUMMA(Pj*Pji)     i=1..n   (3)

            j=1

    Причем, искомые вероятности должны удовлетворять условию:

       n

     SUMMA(Pi) = 1

      j=1                          n

    или, что равносильно   Pi=1- SUMMA Pj          (4)

                                  j=1

                                 j=/=i

    Поэтому любое уравнение системы (3) можно  заменить  уравнением (4).

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

 

Пример.

 

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

     Продолжительность  нахождения  системы  в  каждом  состоянии кратна длительности шага дельта t.

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

 

 

                    +----+-----+-----+-----+

                    | \ j|  S1 |  S2 |  S3 |

                    |i \ |     |     |     |

                    +----+-----+-----+-----|

                    | S1 | 0,7 | 0,2 | 0,1 |

                    | S2 | 0,8 | 0,1 | 0,1 |

                    | S3 | 0,8 | 0,05| 0,15|

                    +----+-----+-----+-----+

 

     S1 - состояние, в котором реализуются задачи пользователя

     S2 -    состояние,    в   котором   реализуются   программы операционной системы

     S3 - состояние  простоя

 

 

     Граф функционирования  системы имеет вид:

 

             +-----+0,7                         +-----+0,1

             |     |                            |     |

             |  +--+--+         0,2          +--+--+  |

             +->|  S1 +--------------------->|  S2 |<-+

                |     |<---------------------|     |

                +---+-+         0,8          +-+---+

                  ^ |                          | ^

                  | |                          | |

                  | |                          | |

                  | |                          | |

                  | |                          | |

                  | |                          | |

                  | |0,1      +-----+       0,1| |

                  | +-------->|     |<---------+ |

                  +-----------|  S3 +------------+

                   0,8        |     |<-+      0,05

                              +--+--+  |

                                 |     |

                                 +-----+0,15

 

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

 

     Р1 = 0,7P1 + 0,8P2 + 0,8P3

     Р2 = 0,2P1 + 0,1P2 + 0,05P3

     Р3 = 0,1P1 + 0,1P2 + 0,15P3

     P1 + P2 + P3 = 1

 

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

     Р1 = 0,749; Р2 = 0,154; Р3 = 0,097.

 

     Коэффициент простоя процессора Кп = Р3 = 0,097.

     Коэффициент  использования Ри = 1 - Кп = 0,903,  при этом на обработку программ пользователя затрачивается 74,3%  времени,  а на обслуживание операционной

системы - 15,4%.

 

 

Непрерывные марковские цепи.

 

     Непрерывные  марковские  цепи   описывают   функционирование систем, принимающих  в  процессе работы конечное число состояний Si (i = 1,  n)  и  осуществляющих переходы из одного состояния в другое (Si --> Sj, i, j = 1, n) случайным образом в произвольный момент времени t.  Иначе говоря, время пребывания  системы  в

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

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

     Определим  для непрерывной марковской цепи вероятности всех состояний системы для любого момента времени Pi(t), i = 1,n. Так как для любого момента времени t все состояния системы образуют полную группу событий, то

                           n

                         SUMMA Pi(t) = 1

                          i=1