Вероятности состояний. Общее правило составления уравнений колмогорова

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

Пусть система S имеет n возможных состояний .

Задача: составить уравнения, описывающие вероятности состояний поведения данной системы.

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

Например, для графа состояний, приведенного на рис. 1, уравнения Колмогорова имеют вид:

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

,

,

. (1.2.1)

Следовательно, одно из уравнений системы можно отбросить и заменить уравнением (1.2.1).

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

Марковский процесс

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

Рассмотрим элементарный пример марковского случайного процесса. По оси абсцисс   случайным образом перемещается точка  . В момент времени   точка   находится в начале координат   и остается там в течение одной секунды. Через секунду бросается монета; если выпал герб - точка   перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и т. д. Процесс изменения положения точки (или, как говорят, «блуждания») представляет собой случайный процесс с дискретным временем   и счетным множеством состояний

Схема возможных переходов для этого процесса показана на рис

Покажем, что этот процесс - марковский. Действительно, представим себе, что в какой-то момент времени   система находится, например, в состоянии   - на одну единицу правее начала координат. Возможные положения точки через единицу времени будут   и   с вероятностями 1/2 и 1/2; через две единицы -  ,  ,   с вероятностями 1/4, ½, 1/4 и так далее. Очевидно, все эти вероятности зависят только от того, где находится точка в данный момент  , и совершенно не зависят от того, как она пришла туда.

Потоки событий. Характеристики потоков

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

Важной характеристикой потока событий является его интенсивность λ - среднее число событий, приходящихся на единицу времени. Интенсивность потока может быть постоянной (λ = const) или переменной, т.е. зависящей от времени t, например, поток машин на автостраде днем интенсивнее, чем ночью.

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

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

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

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

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

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

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

Рассмотрим одноканальную СМО с неограниченной очередью, показанную на рисунке

Если обозначить среднее время пребывания требований в очереди w рассматривать СМО как очередь q, то, используя формулу Литтла можно найти среднее количество требований в очереди:

Если обозначить среднее время обслуживания в устройстве  и рассматривать СМО как устройство S, то, используя формулу Литтла можно найти среднее количество требований в устройстве:

Всегда имеет место уравнение T = w+, где Т - среднее время пребывания требований в СМО с одним устройством обслуживания.

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

Для обозначения СМО используются три параметра для первых параметров: X/Y/Z, где X - распределение времени поступления; Y – распределение времени обслуживания; Z- число обслуживающих устройств.

В теории СМО некоторые аналитические решения были получены для систем вида D/D/l, M/M/1 и М/G/l. Для других значений параметров систем обслуживания аналитические решения не были получены, то есть эта проблема мотивирует использование моделирования.

Самая известная модель - это так называемая СМО типа М/М/1, где М - марковские процессы распределения времени поступления и обслуживания с одним устройством. Например, в системе М/М/1 время между двумя поступлениями в систему требований и время обслуживания имеют экспоненциальные распределения. Такая СМО иногда используется как модель для одного процессора компьютерной системы или как стандартное устройство ввода-вывода (например, магнитный диск). Система D/D/1 - детерминированная система, тогда как D/M/1 – смешанная. Если о системе мало известно, это обозначается какG/G/m, то есть система с произвольными распределениями и m устройствами.

Изучая любую систему, важно оценить характер ее рабочей нагрузки (например, при моделировании компьютерной системы важно знать: когда новые программы (задачи) поступают в систему; сколько времени нужно процессору для выполнения любой из них; как часто программа обращается к устройству ввода-вывода). Этот процесс можно отобразить графиком работы системы (графический метод моделирования), на котором показаны входы задач в систему, ресурсы к которым они обращаются, как долго задачи их используют и т.д.

Если описанный сценарий зафиксирован соответствующим графиком и часто возникает в моделируемой системе, то тогда он целиком отвечает выборке, которая получена методом измерений при наблюдении за работой компьютера. Тем не менее, моделирование при использовании такого описания рабочей нагрузки только воссоздает результаты работы этого специфического сценария. Этого недостаточно для выполнения системой других сценариев. Даже незначительное несоответствие заданному сценарию может привести к драматическим последствиям работы компьютера.

Часто рабочая нагрузка на систему определяется одним или несколькими распределениями вероятностей в отличие от заданных сценариев. Например, можно бросать монету каждые 15 мин на протяжении операции исследования системы, и если монета падает лицевой стороной, то новая задача поступает в систему в этот момент времени. Если монета падает обратной стороной, то никакая задача не поступает в систему. Это пример метода розыгрыша случайной величины (метод Монте-Карло), который используется для моделирования вероятностных систем.

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