Формула Литтла

Среднее число заявок в системе равно произведению интенсивности входного потока на среднее время пребывания заявки в системе.

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

Понятие потока однородных событий возникло в математике как отражение различных физических явлений, например: потока вызовов на АТС, потока транспортных единиц, потока клиентов и так далее. Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин.

Реализация потока

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

• указанием различных моментов событий и числа событий, происходящих в каждый из этих моментов;

• указанием последовательности длительностей интервалов времени между событиями;

• указанием длительности интервалов между различными моментами, когда происходят события, и числа событий в каждый из этих моментов;

• функцией X(t), равной числу событий в интервале (0,t).

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

Теория

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

Ординарные потоки

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

Стационарные потоки

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

Существует связи между распределением числа событий стационарного потока в данном интервале времени и функциями Пальма — Хинчина, определяющими распределение числа событий в интервале, начинающемся в момент события потока. Для ординарных потоков однородных событий вероятность отсутствия событий в интервале длины t равна:

где F(t) — функция распределения времени между двумя событиями; n — математическое ожидание этого времени.

Пуассо́на пото́к (проце́сс), (устар. Пуассоновский процесс^[1]) — поток однородных событий, для которого число событий в интервале А не зависит от чисел событий в любых интервалах, не пересекающихся с А, и имеет экспоненциальное распределение^{[уточнить]} с параметром Λ(А). В теории случайных процессов описывает количество наступивших случайных событий, происходящих с постоянной интенсивностью.

Содержание 1 Классификация 1.1 Простой процесс Пуассона 1.2 Сложный (обобщённый) Пуассоновский процесс 2 Свойства 3 Критерий 4 Информационные свойства 4.1 ЦПТ 5 Применение 6 Литература 7 Примечания 8 См. также

Вероятностные свойства потока Пуассона полностью характеризуются функцией Λ(А), равной приращению в интервале А некоторой убывающей функции. Чаще всего поток Пуассона имеет мгновенное значение параметра λ(t) — функцию, в точках непрерывности которой вероятность события потока в интервале [t,t+dt] равна λ(t)dt. Если А — отрезок [a,b], то

Поток Пуассона, для которого λ(t) равна постоянной λ, называется простейшим потоком с параметром λ.^[2]

Потоки Пуассона определяются для многомерного и вообще любого абстрактного пространства, в котором можно ввести меру Λ(А). Стационарный поток Пуассона в многомерном пространстве характеризуется пространственной плотностью λ. При этом Λ(А) равна объему области А, умноженному на λ.

Классификация

Различают два вида процессов Пуассона: простой (или просто: процесс Пуассона) и сложный (обобщённый).

Простой процесс Пуассона

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

1. почти наверное.

2. — процесс с независимыми приращениями.

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

Сложный (обобщённый) Пуассоновский процесс

• Пусть последовательность взаимно независимых одинаково распределённых случайных величин.

• Пусть - простой пуассоновский процесс с интенсивностью , не зависящий от последовательности .

Обозначим через cумму первых k элементов введённой последовательности.

Тогда определим сложный Пуассоновский процесс как .

Свойства

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

.

• Траектории процесса Пуассона — кусочно-постоянные, неубывающие функции со скачками равными единице почти наверное. Более точно

при ,

где обозначает «о малое».

Критерий

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

1. .

2. Процесс имеет независимые приращения.

3. Процесс однородный.

4. Процесс принимает целые неотрицательные значения.

5. при .

Информационные свойства

• Пусть — моменты скачков процесса Пуассона. .

Зависит ли от предыдущей части траектории? — ?

Пусть .

. Распределение длин промежутков времени между скачка́ми обладает свойством отсутствия памяти ⇔ оно показательно.

• Рассмотрим отрезок на временно́й оси.

— число скачков на отрезке . Условное распределение моментов скачков совпадает с распределением вариационного ряда, построенного по выборке длины из .

Плотность этого распределения

ЦПТ

• Теорема.

Скорость сходимости: , где — константа Берри-Эссеена.

Применение

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

Использование потоков Пуассона значительно упрощает решение задач систем массового обслуживания, связанных с расчетом их эффективности. Но необоснованная замена реального потока потоком Пуассона там, где это недопустимо, приводит к грубым просчетам.

Па́льма пото́к — стационарный ординарный поток однородных событий, характеризующийся следующим свойством:^[1] если t₁, t₂, ... — последовательные моменты наступления событий, отсчитываемые от произвольного момента времени, то

t₁, t₂-t₁, ..., t_n-t_n-1, ... — независимые случайные величины, причём

t₂-t₁, ..., t_n-t_n-1, ... — положительные случайные величины с функцией распределения вероятностей F(x),

и среднее время между событиями

конечно, а t₁ имеет плотность вероятности

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

Цепь Маркова

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

Пример цепи с двумя состояниями

Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).

Содержание 1 Цепь Маркова с дискретным временем 1.1 Определение 1.2 Переходная матрица и однородные цепи 1.3 Конечномерные распределения и матрица перехода за n шагов 1.4 Классификация состояний цепи Маркова 1.5 Примеры 2 Цепь Маркова с непрерывным временем 2.1 Определение 2.2 Матрица переходных функций и уравнение Колмогорова — Чепмена 2.3 Матрица интенсивностей и дифференциальные уравнения Колмогорова 2.4 Свойства матриц P и Q 2.5 Граф переходов, связность и эргодические цепи Маркова 2.6 Примеры 3 Основное кинетическое уравнение 3.1 Функции Ляпунова для основного кинетического уравнения 3.1.1 Примеры функций Моримото 4 Литература

Цепь Маркова с дискретным временем

Определение

Последовательность дискретных случайных величин называется простой цепью Маркова (с дискретным временем), если

.

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

Область значений случайных величин называется простра́нством состоя́ний цепи, а номер  — номером шага.

Переходная матрица и однородные цепи

Матрица , где

называется ма́трицей перехо́дных вероя́тностей на -м шаге, а вектор , где

— нача́льным распределе́нием цепи Маркова.

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

.

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

.

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

Конечномерные распределения и матрица перехода за n шагов

Из свойств условной вероятности и определения однородной цепи Маркова получаем:

,

откуда вытекает специальный случай уравнения Колмогорова — Чепмена:

,

то есть матрица переходных вероятностей за шагов однородной цепи Маркова есть -я степень матрицы переходных вероятностей за 1 шаг. Наконец,

.

Классификация состояний цепи Маркова

• Возвратное состояние;

• Возвратная цепь Маркова;

• Достижимое состояние;

• Неразложимая цепь Маркова;

• Периодическое состояние;

• Периодическая цепь Маркова;

• Поглощающее состояние;

• Эргодическое состояние.

Примеры

• Ветвящийся процесс;

• Случайное блуждание;

Цепь Маркова с непрерывным временем

Определение

Семейство дискретных случайных величин называется цепью Маркова (с непрерывным временем), если

.

Цепь Маркова с непрерывным временем называется однородной, если

.

Матрица переходных функций и уравнение Колмогорова — Чепмена

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

и ма́трицей перехо́дных фу́нкций (переходных вероятностей)

.

Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: или

Матрица интенсивностей и дифференциальные уравнения Колмогорова

По определению, матрица интенсивностей или, что эквивалентно,

.

Из уравнения Колмогорова — Чепмена следуют два уравнения:

• Прямое уравнение Колмогорова

• Обратное уравнение Колмогорова

Для обоих уравнений начальным условием выбирается . Соответствующее решение

Свойства матриц P и Q

Для любого матрица обладает следующими свойствами:

1. Матричные элементы неотрицательны: (неотрицательность вероятностей).

2. Сумма элементов в каждой строке равна 1: (полная вероятность), то есть матрица является стохастической справа (или по строкам).

3. Все собственные числа матрицы не превосходят 1 по абсолютной величине: . Если , то .

4. Собственному числу матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): .

5. Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Матрица обладает следующими свойствами:

1. Внедиагональные матричные элементы неотрицательны: .

2. Диагональные матричные элементы неположительны: .

3. Сумма элементов в каждой строке равна 0:

4. Действительная часть всех собственных чисел матрицы неположительна: . Если , то

5. Собственному числу матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие):

6. Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Граф переходов, связность и эргодические цепи Маркова

Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:

• Множество вершин графа совпадает со множеством состояний цепи.

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

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

• Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):

А. Для любых двух различных вершин графа переходов найдется такая вершина графа («общий сток»), что существуют ориентированные пути от вершины к вершине и от вершины к вершине . Замечание: возможен случай или ; в этом случае тривиальный (пустой) путь от к или от к также считается ориентированным путем.

Б. Нулевое собственное число матрицы невырождено.

В. При матрица стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

• Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):

А. Граф переходов цепи ориентированно связен.

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

В. Для некоторого матрица строго положительна (то есть для всех ).

Г. Для всех матрица строго положительна.

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

Примеры

Рис. Примеры графов переходов для цепей Маркова: a) цепь не является слабо эргодической (не существует общего стока для состояний ); b) слабо эргодическая, но не эргодическая цепь (граф переходов не является ориентированно связным) c) эргодическая цепь (граф переходов ориентированно связен).

Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — . Остальные элементы определяются свойствами матрицы (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид:

Основное кинетическое уравнение

Основная статья: Основное кинетическое уравнение

Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей основное кинетическое уравнение имеет вид:

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

где

Если для основного кинетического уравнения существует положительное равновесие , то его можно записать в форме

Функции Ляпунова для основного кинетического уравнения

Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть  — выпуклая функция одного переменного. Для любого положительного распределения вероятностей ( ) определим функцию Моримото :

.

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

.

Последнее неравенство справедливо из-за выпуклости .

Примеры функций Моримото

• , ;

эта функция — расстояние от текущего распределения вероятностей до равновесного в -норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)

• , ;

эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на (где  — постоянная Больцмана,  — абсолютная температура):

если (распределение Больцмана), то

.

• , ;

эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:

• , ;

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

• , ;

это (минус) энтропия Фишера.

• , ;

это один из аналогов свободной энергии для энтропии Тсаллиса. Энтропия Тсаллиса (Tsallis entropy)

служит основой для статистической физики неэкстенсивных величин. При она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.