Дискретно-стохастические модели или P- cхемы.

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

Рассмотрим граф для этого Р - автомата.

В данном примере рассмотрен Y - детерминированный Р - автомат. Такое представление эквивалентно заданию дискретной марковской цепи с конечным множеством состояний. При исследовании вычислительных систем часто приходится сталкиваться с дискретными случайными процессами, которые определены на конечном множестве состояний. Для анализа F - автоматов широко используются дискретные марковские цепи, которые характеризуются:

1. Множеством состояний S Î {S₁, S₂, S₃, ... , S_n}.

2. Матрицей вероятностных переходов или переходных вероятностей.

3. Вектор начальных распределений.

-этот вектор определяет вероятности р_i⁰, соответствующие моменту времени t₀ при нахождении процесса в состоянии S_i.

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

Марковская цепь порождает множество реализаций вероятностных процессов f(t), которые можно представить в виде некоторой последовательности (множества) {f₁, f₂, ...}. Каждый из таких процессов происходит в соответствующие моменты времени. Начальное состояние f₀ определяется вектором начальных вероятностей p, а следующие состояния f₁, f₂, ... определяются в соответствии с матрицей переходов Р. Таким образом, состояние f₁ будет определяться как S_j, которое определяется из i-й строки матрицы Р. Процесс f(t) переходит в состояние f₁ равное S_j с вероятностью p_{i j}. Затем процесс переходит в состояние f₂ = S_k c вероятностью p_ik. В результате N таких шагов процесс попадет в состояние S_N с вероятностью p_iN.

Марковские цепи классифицируются в зависимости от возможности перехода из одного состояния в другое. Различают поглощающие и эргодические марковские цепи. Поглощающая марковская цепь содержит состояние, достигнув которого, процесс прекращается и это состояние в марковских цепях принято обозначать как S₀. Вероятность перехода p₀₀ = 1. Матрица вероятностей имеет следующий вид:

В этом смысле марковская поглощающая цепь обладает таким свойством: из какого бы состояния не начинался процесс, при N®¥ c вероятностью равной 1 этот процесс окажется в поглощающем состоянии S₀. Основная характеристика случайного процесса в марковских цепях - число пребываний процесса в состояниях S₁, ..., S_k до поглощающего состояния. Нахождение в промежуточных состояниях обычно минимизируют. Число пребываний в каждом из состояний S_i в марковских цепях является случайной величиной, которая может быть представлена в виде средних значений (математических ожиданий), дисперсий, функций распределения. Поглощающие марковские цепи широко используются в качестве временных моделей программ и вычислительных процессов. При моделировании программ состояния цепи отождествляются с блоками программ (модулями), а матрица вероятностей переходов определяет порядок переходов между блоками, т.е. состояниями. В результате моделирования можно вычислить число обращений к блокам программы и время выполнения программы, которые оцениваются средними значениями, дисперсиями, а при необходимости - функциями распределения.

Эргодическая марковская цепь также представляет собой множество состояний, которые связаны матрицей переходных вероятностей, но отличается тем, что из какого бы состояния процесс не исходил, после некоторого числа шагов он может оказаться в любом состоянии. Другими словами, он может из любого состояния перейти в некоторое другое за n шагов. По этой причине состояния называют эргодическими, т.е. возвратными. Процесс, порождаемый эргодической цепью, никогда не завершается, а последовательно переходит из одного состояния в другое. При этом переход из одного состояния в другое может осуществляться с разной частотой, что определяется переходными вероятностями, поэтому для эргодической цепи - основная характеристика - вероятность пребывания в некотором состоянии S_j, где j=1,2, ..., k, - это есть относительная частота попадания процесса в состояние Sj и одновременно доля времени, которое процесс проводит в каждом из таких состояний эргодической цепи. Эргодические цепи также широко используются для моделирования ВС, в частности, при исследовании вопросов надежности, а также в качестве базовых моделей взаимодействия устройств с задачами, поступающими на обработку. Марковский процесс с дискретными состояниями S1, ..., Sk, переходы между которыми разрешаются в любой момент времени, принято называть непрерывными марковскими цепями. Однородную непрерывную марковскую цепь, поведение которой в любой момент времени подчиняется одному и тому же закону, принято задавать матрицей интенсивностей

переходов Q = [q_{i j}]. Интенсивности переходов в общем случае определяются следующими формулами:

где p_ii (Dt) - вероятность перехода процесса из состояния S_i за время Dt в состояние S_i. Это означает, что если процесс находился в состоянии S_i, то интенсивность перехода в состояние S_j в течение промежутка времени Dt отличается от интенсивности перехода в состояние S_i на величину -q_ii Dt. Аналогичным образом, для второго случая интенсивность перехода будет определяться как q_{i j} Dt. В качестве примера рассмотрим граф марковской цепи, состоящий из трех состояний.

Основная характеристика непрерывной марковской цепи - это стационарное распределение вероятностей состояний: a = (a₁, ..., a_k), где a₁, ..., a_k - вероятности пребывания процесса в состояниях S₁, ... , S_k. Распределение задается вероятностным решением системы уравнений:

К системе, состоящей из (k-1) уравнений, добавляется нормирующее уравнение: a1 + a2 + ... + ak = 1 (3), которое, в свою очередь определяется значениями вероятностей a = {a₁, a₂, ..., a_k} . Уравнения (1), (2), (3) принято называть уравнениями равновесия с помощью которых определяются условия равновесия входных и выходных параметров. В частности, для нашего примера таковыми уравнениями равновесия будет являться следующая система:

Cостояние	Интенсивность входящего потока	Интенсивность выходного потока
S1	ma2	(l/2 + l) a1
S2	la1 + ma3	(m + l)a2
S3	l/2a1 + la2	ma3

Этот подход широко используется при исследовании СМО. В соответствии с марковскими свойствами все предыдущие процессы сказываются на поведении в будущем только через текущее состояние, т.е. определяя дальнейший ход событий не требуется знать, как долго процесс находился в текущем состоянии. Отсюда следует вывод, что распределение оставшегося времени пребывания процесса в некотором состоянии S_i, должно зависеть только от самого состояния, а не от времени пребывания в нем. Этим свойством обладает только одно распределение - экспоненциальное, поэтому уравнения равновесия можно применять для СМО с экспоненциальным распределением, однако, если допустить произвольное распределение времени пребывания процесса в том или ином состоянии, то этот процесс становится полумарковским и ведет себя только относительно моментов изменения состояний, т.е. как обычная дискретная марковская цепь и принято говорить, что в эти моменты времени имеют место вложенные марковские цепи. Характеристики полумарковских цепей и процессов определяются значительно сложнее, чем марковских, поскольку вероятности состояний связаны с параметрами процесса системами дифференциальных уравнений с частными производными.

Предлагаю ознакомиться с аналогичными статьями: