Описание информационных систем с помощью теории Марковских случайных процессов

У теории вероятности очень интересная история. Корни науки уходят далеко в глубь веков, в древнейших государствах – Китае, Индии, Египте, Греции использовались некоторые элементы теории вероятности для переписи населения и даже для определения численности войск неприятеля.

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

1. Сколько раз надо бросить две игральные кости, чтобы случаев выпадения сразу двух шестерок было больше половины от общего числа бросаний?

2. Как справедливо разделить поставленные на кон двумя игроками деньги, если они по каким-либо причинам прекратили игру преждевременно?

Эти задачи послужили поводом для первоначального введения понятия «математическое ожидание» и формулирования основных теорем сложения и перемножения вероятностей. Вскоре были определены практические приложения: страхование, демография и т.д.

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

Дальнейшие успехи развития теории вероятностей связаны с П. Лапласом, К. Гауссом, С. Пуассоном и др.

В России математик В.Я. Буняковский в начале 19 в. написал первый учебник по теории вероятностей и разработал ее терминологию в современном виде. П.А. Чебышев, А.А. Марков и А.М. Ляпунов ввели понятие «случайной величины», с которой начала развиваться новая ветвь теории вероятности – теория случайных процессов.

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

 

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

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

Процесс перехода называется цепью.

Определение цепи Маркова

Имеется некоторая физическая система, имеющая конечное число к всех возможных фазовых состояний . Пусть в зависимости от вмешательства случая система шаг за шагом (в моменты времени t₀<t₁<t₂…) скачкообразно меняет свое фазовое состояние, то есть имеют место переходы Q₀ ® Q₁ ® …, где Q_n=Q(t_n) –состояние системы через n шагов, а Q₀=Q(t₀) – начальное состояние системы.

                                            ,               (1)

где - одно из возможных пространств состояний .

Вероятность перехода на m-шаге (условная вероятность):

                                              .           (2)

Таким образом, для вычисления совместных вероятностей Р(Q₀,..,Q_n) необходимо задать начальное состояние системы и указать физический механизм осуществления смены состояний, позволяющий вычислить вероятности перехода .

1. Частный (вырожденный) случай цепи Маркова. Смена всех состояний происходит независимо, то есть вероятность какого-либо состояния на m-м шаге не зависит от того, в каких состояниях находилась система в предыдущие моменты времени.  – последовательность независимых испытаний.

2. Вероятность фазового состояния параметра Q_n в момент времени t_n зависит лишь от того, в каком состоянии находилась система в непосредственно предшествующий ему момент времени t_n-1, и не зависит от того, в каких состояниях находилась система в более ранние моменты времени t₀,…,t_n-2.

                                       .                         (3)

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

                                        .                (4)

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

Простейшей вероятностной характеристикой случайного процесса служит набор вероятностей состояний P₁(t), P₂(t),... P_n(t), где P_i(t) – вероятность перехода системы в состояние S_i в момент времени t. Условие нормировки P₁+P₂+...+P_n=1.

Если в процессе функционирования система оказывается в состоянии S_i, то вероятность перехода ее в состояние S_j в общем случае зависит не только от состояния S_i, но и от предыдущего состояния.

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

 

Потоки событий

 

Переход системы в некоторое состояние является событием.

Последовательность переходов системы в состояние S_i представляет собой поток событий.

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

Интервалы времени t₁, t₂,... t_n ординарного потока могут быть одинаковыми или различными, дискретными или непрерывными, случайными или неслучайными.

Если интервалы времени t₁, t₂,... t_n – неслучайные величины, то поток называется регулярным или детерминированным, и этот поток описывается путем задания значений T₁,T₂,... T_n.

Если T₁,T₂,... T_n являются случайными, то поток называется случайным и он характеризуется законом распределения величин T₁,T₂,... T_n.

На практике часто встречаются системы, в которых T_i – непрерывная случайная величина. В этих случаях система может быть описана плотностью вероятности f(t ₁, t ₂,... t _n), где t _i – конкретное значение случайной величины T_i.

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

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

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

Если случайные величины t_i независимые, то такой поток называется потоком с ограниченным последействием и плотность вероятности этого потока равна произведению плотностей вероятности:

                                                 f (t ₁, t ₂,... t _n) = f ₁ (t ₁) f ₂ (t ₂)... f_n (t _n)     (5)

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

                                                             f_i (t _i) = f (t _i)                              (6)

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

 

Пуассоновский поток

Потоки случайных событий называются пуассоновскими, если число событий потока m, попадающих на любой участок t, распределен по закону Пуассона

                                                            P_m= e^-a,                                           (7)

где а – среднее число событий, находящихся на участке t.

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

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

Просеянные потоки

Процесс переходов системы с дискретным временем функционирования может рассматриваться как воздействие дискретного потока событий, которое характеризуется тем, что в моменты времени t₁, t₂,... t_n события происходят с вероятностью P _i. Функция распределения такого потока:

                                                                                       (8)

Просеяние потока событий S₁, S₂,... S_n, которые наступают в определенные моменты времени с вероятностями p₁, p₂,... p_n, означает преобразование этих вероятностей в , ,... . Если поток является стационарным, то эти вероятности равны: = =...=1-p.

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

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

Если в простейшем потоке сохранить только каждое третье событие, то получим поток Эрланга III порядка и т.д. В общем случае, потоком Эрланга k -порядка называется простейший поток, полученный исключением (k- 1 ) событий и сохранением k -го события.