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

⇐ ПредыдущаяСтр 13 из 18Следующая ⇒

Учебные вопросы:

Теория Марковских случайных процессов.

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

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

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

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

Эргодические и поглощающие цепи.

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

Приложения Марковских процессов.

Теория Марковских случайных процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, (6.1)

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

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

. (6.2)

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

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

– последовательность независимых испытаний.

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

. (6.3)

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

. (6.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) (6.5)

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

f_i(t_i) = f(t_i) (6.6)

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

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

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

P_m= e^-^a, (6.7)

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

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

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

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

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

(6.8)

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

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

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

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

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

Марковский случайный процесс с дискретными состояниями и дискретным временем функционирования описывает систему S с конечным числом состояний. При этом переходы возможны в фиксированные моменты времени t₁, t₂, ..., t_k. Процесс, происходящий в этой системе, можно представить в виде цепочки случайных событий

S₁(0) ® S₂(1) ®... ® S_i(n) ®... ® S_n(k).

Эта последовательность называется дискретной Марковской цепью, если для каждого шага n=1, 2, ... k вероятность переходов из любого состояния (S_i®S_j) не зависит от того, как система пришла в состояние S_i. Каждому переходу системы соответствует условная вероятность

P[S_j(n)/S_i(n-1)]. (6.9)

Для каждого номера шага n возможные переходы образуют полную группу событий.

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

	P₁₁	P₁₂	...	P_1n
P_ij=	P₂₁	P₂₂	...	P_2n
	...	...	...	...
	P_n1	P_n2	...	P_nn

и вектор начального распределения вероятностей для всех состояний в момент времени t=0.

[P_i(0)]=[P₁(0)P₂(0)...P_n(0)]. (6.10)

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

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

P(A) = P(B_i)*P(A/B_i) (6.11)

После первого шага вероятность P_i может быть определена следующим образом:

P_i(1) = P_j(0)P_ji, (6.12)

где P_j(0) – вектор начальных состояний,

P_ji – строка матрицы условных вероятностей.

P_i(2) = P_j(1)P_ji = P_j(0)P_ji(1) (6.13)

После k шагов:

P_i(k) = P_j(k-1)P_ji = P_j(0)P_ji(k), (6.14)

где P_ji(k) – вероятности переходов системы из состояния S_i в S_j за k шагов.

Если возможен переход из состояния S_i в состояние S_j за k шагов, то величина P_ji(k)> 0. Если при этом возможен обратный переход за то же число шагов, то состояние S_i называется возвратным. Вероятность того, что система выйдет из состояния S_i и за k шагов вернется в него же, равна 1 для возвратных состояний.

Состояние S_i - невозвратное, если эта вероятность отлична от 1.

Состояния S_i и S_j называются сообщающимися, если возможен переход S_i®S_j за конечное число шагов.

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒