Распределение фазового типа

Фазовое распределение — это распределение вероятностей, построенное с помощью свертки или смеси экспоненциальных распределений . ^[1] Оно возникает из системы одного или нескольких взаимосвязанных пуассоновских процессов, происходящих последовательно , или фаз. Последовательность, в которой происходит каждая из фаз, сама по себе может быть стохастическим процессом . Распределение может быть представлено случайной величиной, описывающей время до поглощения марковского процесса с одним поглощающим состоянием. Каждое из состояний марковского процесса представляет одну из фаз.

Он имеет эквивалент в дискретном времени – распределение дискретного фазового типа .

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

Определение

Рассмотрим непрерывный во времени марковский процесс с m  + 1 состояниями, где m  ≥ 1, такой, что состояния 1,..., m являются переходными состояниями, а состояние 0 является поглощающим состоянием. Далее, пусть процесс имеет начальную вероятность начала в любой из m  + 1 фаз, заданную вектором вероятности ( α ₀ , α ), где α ₀ является скаляром, а α является вектором 1 ×  m .

Распределение типа непрерывной фазы представляет собой распределение времени от начала указанного выше процесса до поглощения в поглощающем состоянии.

Этот процесс можно записать в виде матрицы скоростей перехода ,

${\displaystyle {Q}=\left[{\begin{matrix}0&\mathbf {0} \\\mathbf {S} ^{0}&{S}\\\end{matrix}}\right],}$

где S — матрица размером m  ×  m , а S ⁰ = –S 1. Здесь 1 представляет собой вектор-столбец размером m  × 1, где каждый элемент равен 1.

Характеристика

Распределение времени X до достижения процессом поглощающего состояния называется распределенным по фазовому типу и обозначается PH( α , S ).

Функция распределения X определяется выражением:

${\displaystyle F(x)=1-{\boldsymbol {\alpha }}\exp({S}x)\mathbf {1} ,}$

и функция плотности,

${\displaystyle f(x)={\boldsymbol {\alpha }}\exp({S}x)\mathbf {S^{0}} ,}$

для всех x > 0, где exp( · ) — матричная экспонента . Обычно предполагается, что вероятность начала процесса в поглощающем состоянии равна нулю (т.е. α ₀ = 0). Моменты функции распределения определяются как

${\displaystyle E[X^{n}]=(-1)^{n}n!{\boldsymbol {\alpha }}{S}^{-n}\mathbf {1} .}$

Преобразование Лапласа распределения фазового типа определяется выражением

${\displaystyle M(s)=\alpha _{0}+{\boldsymbol {\alpha }}(sI-S)^{-1}\mathbf {S^{0}} ,}$

где I — единичная матрица.

Особые случаи

Следующие распределения вероятностей считаются частными случаями непрерывного фазового распределения:

• Вырожденное распределение , точечная масса в нуле или распределение типа пустой фазы  – 0 фаз.
• Экспоненциальное распределение  – 1 фаза.
• Распределение Эрланга  – 2 или более одинаковых фазы последовательно.
• Детерминированное распределение (или константа) — предельный случай распределения Эрланга, когда число фаз становится бесконечным, а время в каждом состоянии становится равным нулю.
• Распределение Коксиана – 2 или более (не обязательно идентичных) фаз последовательно, с вероятностью перехода в завершающее/поглощающее состояние после каждой фазы.
• Гиперэкспоненциальное распределение (также называемое смесью экспоненциальных) – 2 или более неидентичных фаз, каждая из которых имеет вероятность возникновения взаимоисключающим или параллельным образом. (Примечание: экспоненциальное распределение – это вырожденная ситуация, когда все параллельные фазы идентичны.)
• Гипоэкспоненциальное распределение  – 2 или более фаз последовательно, могут быть неидентичными или представлять собой смесь идентичных и неидентичных фаз, обобщает Эрланг.

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

Примеры

Во всех следующих примерах предполагается, что в нуле нет вероятностной массы, то есть α ₀ = 0.

Экспоненциальное распределение

Простейшим нетривиальным примером распределения фазового типа является экспоненциальное распределение параметра λ. Параметры распределения фазового типа: S = -λ и α = 1.

Гиперэкспоненциальное или смесь экспоненциального распределения

Смесь экспоненциального или гиперэкспоненциального распределения с λ ₁ ,λ ₂ ,...,λ _n >0 может быть представлена ​​как распределение фазового типа с

${\displaystyle {\boldsymbol {\alpha }}=(\alpha _{1},\alpha _{2},\alpha _{3},\alpha _{4},...,\alpha _{n})}$

с и ${\displaystyle \sum _{i=1}^{n}\alpha _{i}=1}$

${\displaystyle {S}=\left[{\begin{matrix}-\lambda _{1}&0&0&0&0\\0&-\lambda _{2}&0&0&0\\0&0&-\lambda _{3}&0&0\\0&0&0&-\lambda _{4}&0\\0&0&0&0&-\lambda _{5}\\\end{matrix}}\right].}$

Эту смесь плотностей экспоненциально распределенных случайных величин можно охарактеризовать с помощью

${\displaystyle f(x)=\sum _{i=1}^{n}\alpha _{i}\lambda _{i}e^{-\lambda _{i}x}=\sum _{i=1}^{n}\alpha _{i}f_{X_{i}}(x),}$

или его кумулятивная функция распределения

${\displaystyle F(x)=1-\sum _{i=1}^{n}\alpha _{i}e^{-\lambda _{i}x}=\sum _{i=1}^{n}\alpha _{i}F_{X_{i}}(x).}$

с ${\displaystyle X_{i}\sim Exp(\lambda _{i})}$

распределение Эрланга

Распределение Эрланга имеет два параметра: форму целого числа k > 0 и скорость λ > 0. Иногда это обозначается E ( k ,λ). Распределение Эрланга можно записать в виде распределения фазового типа, сделав S матрицей k × k с диагональными элементами -λ и наддиагональными элементами λ, с вероятностью начала в состоянии 1, равной 1. Например, E (5,λ),

${\displaystyle {\boldsymbol {\alpha }}=(1,0,0,0,0),}$

и

${\displaystyle {S}=\left[{\begin{matrix}-\lambda &\lambda &0&0&0\\0&-\lambda &\lambda &0&0\\0&0&-\lambda &\lambda &0\\0&0&0&-\lambda &\lambda \\0&0&0&0&-\lambda \\\end{matrix}}\right].}$

Для заданного числа фаз распределение Эрланга представляет собой распределение типа фазы с наименьшим коэффициентом вариации. ^[2]

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

Смесь распределений Эрланга

Смесь двух распределений Эрланга с параметрами E (3,β ₁ ), E (3,β ₂ ) и (α ₁ ,α ₂ ) (такими, что α ₁ + α ₂ = 1 и для каждого i , α _i ≥ 0) может быть представлена ​​как распределение фазового типа с

${\displaystyle {\boldsymbol {\alpha }}=(\alpha _{1},0,0,\alpha _{2},0,0),}$

и

${\displaystyle {S}=\left[{\begin{matrix}-\beta _{1}&\beta _{1}&0&0&0&0\\0&-\beta _{1}&\beta _{1}&0&0&0\\0&0&-\beta _{1}&0&0&0\\0&0&0&-\beta _{2}&\beta _{2}&0\\0&0&0&0&-\beta _{2}&\beta _{2}\\0&0&0&0&0&-\beta _{2}\\\end{matrix}}\right].}$

Распределение Коксиана

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

${\displaystyle S=\left[{\begin{matrix}-\lambda _{1}&p_{1}\lambda _{1}&0&\dots &0&0\\0&-\lambda _{2}&p_{2}\lambda _{2}&\ddots &0&0\\\vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\0&0&\ddots &-\lambda _{k-2}&p_{k-2}\lambda _{k-2}&0\\0&0&\dots &0&-\lambda _{k-1}&p_{k-1}\lambda _{k-1}\\0&0&\dots &0&0&-\lambda _{k}\end{matrix}}\right]}$

и

${\displaystyle {\boldsymbol {\alpha }}=(1,0,\dots ,0),}$

где 0 < p ₁ ,..., p _{k -1} ≤ 1. В случае, когда все p _i = 1, мы имеем распределение Эрланга. Распределение Коксиана чрезвычайно важно, поскольку любое ациклическое распределение фазового типа имеет эквивалентное представление Коксиана.

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

Характеристики

Минимумы независимых случайных величин PH

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

Генерация выборок из распределенных по фазе случайных величин

BuTools включает методы для генерации выборок из распределенных по фазе случайных величин. ^[3]

Аппроксимация других распределений

Любое распределение может быть произвольно хорошо аппроксимировано распределением фазового типа. ^{[4] [5]} Однако на практике аппроксимации могут быть плохими, когда размер аппроксимирующего процесса фиксирован. Аппроксимация детерминированного распределения времени 1 с 10 фазами, каждая из которых имеет среднюю длину 0,1, будет иметь дисперсию 0,1 (потому что распределение Эрланга имеет наименьшую дисперсию ^[2] ).

• BuTools — скрипт MATLAB и Mathematica для подгонки распределений фазового типа к 3 указанным моментам
• момент сопоставления скрипта MATLAB для подгонки минимального распределения фазового типа к 3 указанным моментам ^[6]
• KPC-toolbox — библиотека скриптов MATLAB для подгонки эмпирических наборов данных под марковские процессы прибытия и распределения фазового типа. ^[7]

Подгонка распределения фазового типа к данным

Методы подгонки распределения фазового типа под данные можно классифицировать как методы максимального правдоподобия или методы сопоставления моментов. ^[8] Было показано, что подгонка распределения фазового типа под распределения с тяжелыми хвостами в некоторых ситуациях практична. ^[9]

• PhFit — скрипт на языке C для подгонки распределений дискретного и непрерывного типа фазы к данным ^[10]
• EMpht — это скрипт на языке C для подгонки распределений фазового типа к данным или параметрическим распределениям с использованием алгоритма максимизации ожидания . ^[11]
• HyperStar был разработан вокруг основной идеи сделать подгонку фазового типа простой и удобной для пользователя, чтобы продвинуть использование распределений фазового типа в широком диапазоне областей. Он предоставляет графический пользовательский интерфейс и дает хорошие результаты подгонки при небольшом взаимодействии с пользователем. ^[12]
• jPhase — это библиотека Java, которая также может вычислять метрики для очередей, используя распределение подогнанного типа фазы ^[13]

Смотрите также

• Дискретное фазовое распределение
• Непрерывный марковский процесс
• Экспоненциальное распределение
• Гиперэкспоненциальное распределение
• Теория массового обслуживания

Ссылки

1. Харчол-Балтер, М. (2012). «Реальные рабочие нагрузки: высокая изменчивость и тяжелые хвосты». Моделирование производительности и проектирование компьютерных систем . стр. 347–348. doi :10.1017/CBO9781139226424.026. ISBN 9781139226424.
2. Aldous, David ; Shepp, Larry (1987). "Наименее изменчивое распределение фазового типа — эрланговское" (PDF) . Стохастические модели . 3 (3): 467. doi :10.1080/15326348708807067.
3. Хорват, ГБ; Рейнеке, П.; Телек, М.С.; Вольтер, К. (2012). "Эффективная генерация PH-распределенных случайных величин" (PDF) . Аналитические и стохастические методы моделирования и их применение . Конспект лекций по информатике. Том 7314. стр. 271. doi :10.1007/978-3-642-30782-9_19. ISBN 978-3-642-30781-2.
4. Больх, Гюнтер; Грейнер, Стефан; де Меер, Герман; Триведи, Кишор С. (1998). "Стационарные решения цепей Маркова". Сети очередей и цепи Маркова . С. 103–151. doi :10.1002/0471200581.ch3. ISBN 0471193666.
5. Кокс, DR (2008). «Использование комплексных вероятностей в теории стохастических процессов». Математические труды Кембриджского философского общества . 51 (2): 313–319. doi :10.1017/S0305004100030231. S2CID  122768319.
6. Osogami, T.; Harchol-Balter, M. (2006). "Закрытые решения для отображения общих распределений в квазиминимальные распределения PH". Оценка производительности . 63 (6): 524. doi :10.1016/j.peva.2005.06.002.
7. Casale, G.; Zhang, EZ; Smirni, E. (2008). "KPC-Toolbox: простая, но эффективная подгонка трасс с использованием марковских процессов прибытия". 2008 Пятая международная конференция по количественной оценке систем (PDF) . стр. 83. doi :10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5. S2CID  252444.
8. Ланг, Андреас; Артур, Джеффри Л. (1996). «Аппроксимация параметров для распределений фазового типа». В Чакраварти, С.; Альфа, Аттахиру С. (ред.). Матричные аналитические методы в стохастических моделях . CRC Press. ISBN 0824797663.
9. Рамасвами, В.; Пул, Д.; Ан, С.; Байерс, С.; Каплан, А. (2005). «Обеспечение доступа к экстренным службам при длительных звонках по коммутируемой линии в Интернете». Интерфейсы . 35 (5): 411. doi :10.1287/inte.1050.0155.
10. Хорват, Андраш С.; Телек, Миклош С. (2002). «PhFit: универсальный инструмент для установки фазового типа». Оценка производительности компьютера: методы и инструменты моделирования. Конспекты лекций по информатике. Том. 2324. с. 82. дои : 10.1007/3-540-46029-2_5. ISBN 978-3-540-43539-6.
11. Асмуссен, Сорен; Нерман, Олле; Олссон, Марита (1996). «Подбор распределений фазового типа с помощью алгоритма EM». Скандинавский статистический журнал . 23 (4): 419–441. JSTOR  4616418.
12. Райнеке, П.; Краус, Т.; Вольтер, К. (2012). «Подгонка распределений фазового типа на основе кластеров к эмпирическим данным». Компьютеры и математика с приложениями . 64 (12): 3840. doi : 10.1016/j.camwa.2012.03.016 .
13. Pérez, JF; Riaño, GN (2006). "jPhase: объектно-ориентированный инструмент для моделирования распределений фазового типа". Исходя из семинара 2006 года по инструментам для решения структурированных цепей Маркова (SMCtools '06) (PDF) . doi :10.1145/1190366.1190370. ISBN 1595935061. S2CID  7863948.

• MF Neuts (1975), Распределения вероятностей фазового типа, In Liber Amicorum, профессор почета Х. Флорина, страницы 173-206, Лувенский университет.
• MF Neuts. Матрично-геометрические решения в стохастических моделях: алгоритмический подход, Глава 2: Распределения вероятностей фазового типа; Dover Publications Inc., 1981.
• G. Latouche, V. Ramaswami. Введение в матричные аналитические методы в стохастическом моделировании, 1-е издание. Глава 2: Распределения PH; ASA SIAM, 1999.
• CA O'Cinneide (1990). Характеристика распределений фазового типа . Сообщения по статистике: Стохастические модели, 6 (1), 1-57.
• CA O'Cinneide (1999). Распределение фазового типа: открытые проблемы и некоторые свойства , Communication in Statistic: Stochastic Models, 15 (4), 731-757.