АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
УДК 519.872
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ
Т.И. Алиев
Для вероятностных распределений с коэффициентами вариации, отличными от единицы, получены математические зависимости для аппроксимации по двум заданным моментам распределения с использованием мультиэкспоненциальных распределений. Для аппроксимации распределений с коэффициентами вариации меньше единицы предлагается использовать гипоэкспоненциальное распределение, которое, в отличие от распределения Эрланга, имеющего дискретные значения коэффициента вариации, позволяет формировать случайные величины с любым значением коэффициента вариации в интервале (0; 1). Ключевые слова: вероятностное распределение, коэффициент вариации, аппроксимация, гипоэкспоненциальное
распределение, гиперэкспоненциальное распределение, распределение Эрланга. Введение
В качестве моделей вычислительных систем и сетей широкое применение находят математические модели массового обслуживания, позволяющие проводить анализ эффективности их функционирования и
88 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
решать задачи системотехнического проектирования [1, 2]. При этом наибольшее распространение получили так называемые экспоненциальные модели, в которых протекающие в исследуемых системах процессы описываются случайными величинами, распределенными по экспоненциальному закону, обладающему свойством отсутствия последействия. Это замечательное свойство экспоненциального распределения используется при построении моделей в терминах марковских процессов, представляющих собой особый класс случайных процессов, развитие которых не зависит от предыстории процесса [3]. Благодаря этому для многих моделей массового обслуживания удается достаточно просто получить конечные результаты, в том числе в явном виде и в аналитической форме, для расчета характеристик исследуемой системы. Исходя из этого, часто при исследовании систем, в которых временные процессы отличаются от экспоненциальных, стремятся свести эти процессы к экспоненциальному представлению.
Для экспоненциального закона распределения случайных величин, определенных в области положительных значений, коэффициент вариации, описывающий разброс значений случайной величины, равен единице. Если реальные временные интервалы имеют значения коэффициента вариации, отличающиеся от единицы, использование экспоненциального распределения может привести к значительным погрешностям конечных результатов. В этих случаях в качестве аппроксимирующих функций законов распределений могут использоваться мультиэкспоненциальные распределения, представляющие собой композицию экспоненциальных распределений, а именно: распределение Эрланга, когда коэффициент вариации временного интервала меньше единицы, 0 1 , и гиперэкспоненциальное распределение,
когда коэффициент вариации временного интервала больше единицы, 1 [3]. При этом аппроксима-
ция реального распределения в простейшем случае может выполняться по двум первым моментам рас-
пределения – математическому ожиданию и коэффициенту вариации.
Аппроксимация распределений с коэффициентом вариации 0 < ν < 1
Положим, что математическое ожидание и коэффициент вариации некоторой случайной величины , определенной в положительной области действительных чисел, соответственно равны t и , причем
0 1 . Для аппроксимации закона распределения такой случайной величины в теории массового обслуживания обычно используют распределение Эрланга [3]. Случайная величина, распределенная по закону Эрланга k-го порядка Ek , представляет собой сумму k экспоненциально распределенных случайных величин (фаз) с одинаковым математическим ожиданием M [] .
Математическое ожидание и коэффициент вариации случайной величины, распределенной по за-
кону Эрланга k-го порядка, равны соотвтственно
M Ek k M [];
Ek
1, k
где k 1, 2, ... – параметр распределения Эрланга, принимающий целочисленные значения.
Тогда для заданных реальных (измеренных) значений математического ожидания t и коэффициен-
та вариации (0 1) некоторой случайной величины , определенной в положительной области
действительных чисел, параметры аппроксимирующего распределения Эрланга будут определяться следующим образом:
k
1 2
;
M []
t k
,
где ]x[ означает ближайшее целое, большее x. Нетрудно убедиться, что распределение Эрланга позволяет
аппроксимировать только те реальные распределения, коэффициенты вариации которых имеют
следующие значения: 0,707 (при k = 2); 0,577 (при k = 3); 0,5 (при k = 4) и т.д.
Для аппроксимации распределений с любым значением коэффициента вариации, находящимся в
интервале (0; 1), рассмотрим многофазное распределение с разными значениями математического ожи-
дания экспоненциальных распределений в разных фазах: ti Mi[] (i 1, k) , которое будем называть
гипоэкспоненциальным распределением. Проанализируем свойства гипоэкспоненциального распределения на примере двухфазного рас-
пределения, математическое ожидание и второй начальный момент которого будут равны
M h2 t1 t2 ;
(2) h2
2 (t12
t1t2
t22 ) , откуда коэффициент вариации
h2
t12 t22 /(t1 t2 ) .
На рис. 1 показана зависимость коэффициента вариации гипоэкспоненциального распределения
2-го порядка от отношения t1 / t2 параметров экспоненциальных составляющих. Как видно из графика,
коэффициент вариации гипоэкспоненциального распределения изменяется в пределах от 1 до 0,7, точ-
нее, до значения 0,707, т.е. коэффициента вариации распределения Эрланга 2-го порядка, когда парамет-
ры экспоненциальных составляющих равны между собой, t1 t2 .
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
89
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
1
Коэффициент вариации
0,9
0,8
0,7
0,6 0,05
0,25
0,45 0,65 0,85 1,00
Отношение t1/t2
Рис. 1. Зависимость коэффициента вариации от отношения t1/t2
Очевидно, что для увеличения интервала изменения коэффициента вариации гипоэкспоненциаль-
ного распределения необходимо вместо двухфазного использовать многофазное (k-фазное, k 2 ) пред-
ставление. Математическое ожидание и коэффициент вариации гипоэкспоненциального распределения
k-го порядка будут равны
k
M hk ti ; i 1
k
hk
ti2
i 1
k
ti .
i 1
(1)
Коэффициент вариации гипоэкспоненциального распределения k-го порядка лежит в интерва-
ле (1/ k ; 1) , причем с увеличением порядка k левая граница этого интервала приближается к нулю
(k = 2, 3, …). Рассмотрим теперь задачу аппроксимации реального распределения с коэффициентом вариации
0 1 гипоэкспоненциальным распределением k-го порядка. Положим, что известны математическое ожидание t и коэффициент вариации (причем 0 1 ) некоторой случайной величины , определенной в положительной области действительных чисел. Для простоты без потери общности положим, что аппроксимирующее гипоэкспоненциальное распределение k-го порядка содержит только два типа
экспоненциальных фаз: k1 фаз с параметром 1 1/ t1 и k2 k k1 фаз с параметром 2 1/ t2 , где t1 и
t2 – математические ожидания экспоненциально распределенных случайных величин в фазах первого и
второго типов соответственно. Тогда из (1) следует, что математическое ожидание и коэффициент вариации будут равны
M hk k1 t1 k2 t2 ; hk k1 t12 k2 t22 (k1 t1 k2 t2 ) ,
причем k1 k2 k . Таким образом, для аппроксимации по двум моментам необходимо, чтобы выполнялись следую-
щие два условия:
k1 t1 k2 t2 t;
k1 t12 k2 t22 k1 t1 k2 t2
,
где t и – соответственно математическое ожидание и коэффициент вариации аппроксимируемого
(реального) распределения. Полагая, что значения k1 и k2 известны, решим полученную систему
уравнений относительно неизвестных t1 и t2 . Из первого уравнения системы следует, что
t2
t k1t1 k2
.
(2)
Подставляя это выражение во второе уравнение, после некоторых преобразований получим квад-
ратное уравнение с одним неизвестным t1 :
k1 (k1 k2 ) t12 2k1 t t1 (t 2 k22t 2 ) 0 . Решая это квадратное уравнение, получим:
t1
t k
1
где k k1 k2 .
k2
k1
k2
1
,
(3)
90 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
В качестве решения могут использоваться оба корня квадратного уравнения.
Для того чтобы в (3) под знаком квадратного корня была неотрицательная величина, необходимо
выполнение условия
k
1 2
,
(4)
которое определяет минимальное количество фаз в аппроксимирующем гипоэкспоненциальном распре-
делении, т.е. порядок распределения. Для того чтобы второе решение со знаком минус перед квадратным
корнем давало t1 0 , дополнительно необходимо выполнение условия
k2
1 2
.
(5)
Объединив условия (4) и (5), окончательно получим вполне очевидное условие
k2
1 2
k
.
(6)
Подставим теперь (3) в (2) и найдем t2 :
t2
t k
1
k1 k2
k2
1
,
для которого получим условие, аналогичное условию (6):
k1
1 2
k
.
Окончательно имеем следующие выражения для аппроксимации гипоэкспоненциальным распре-
делением k-го порядка законов распределения случайных величин с коэффициентом вариации 0 1 :
k
1 2
;
(7)
t1
t k
1
k2 k1
k2
1
или
t1
t k
1
k2 k1
k2
1
.
t2
t k
1
k1 k2
k2
1
t2
t k
1
k1 k2
k2
1
(8)
Алгоритм аппроксимации реального распределения с коэффициентом вариации 0 1 гипо-
экспоненциальным распределением k-го порядка при заданных значениях математического ожидания t
и коэффициента вариации случайной величины , определенной в положительной области действи-
тельных чисел, формулируется следующим образом:
1. на основе выражения (7) по заданному значению коэффициента вариации определяется
минимально необходимое число экспоненциальных фаз k в аппроксимирующем распределении как
ближайшее большее целое по отношению к 1 / 2 ;
2. выбирается значение k1 k и рассчитывается k2 k k1 ;
3. на основе (8) рассчитываются значения t1 и t2 .
Результаты аппроксимации на основе выражений (7) и (8) при разных значениях k1 и k2 k k1 различаются значениями третьего и более высоких моментов распределения, учет которых при аппрок-
симации реальных распределений не вызывает принципиальных трудностей, но сопровождается более
громоздкими математическими выкладками. К тому же, во многих случаях влияние этих моментов на
конечные результаты исследований оказывается незначительным. Пример 1. Пусть математическое ожидание и коэффициент вариации аппроксимируемого выра-
жения соответственно равны t 10 и 0, 4 .
В соответствии с изложенным выше алгоритмом:
1. минимально необходимое число экспоненциальных фаз k в аппроксимирующем распределении
k 7 ( k 1/ 0,16 6, 25 );
2. выберем значение k1 3 , тогда k2 7 3 4 ;
3. на основе (8) рассчитываются значения t1 2 и t2 1. Таким образом, в качестве аппроксимирующего распределения выбираем гипоэкспоненциальное
распределение 7-го порядка, в котором 3 экспоненциальные фазы имеют математическое ожидание, рав-
ное 2, и 4 фазы – математическое ожидание, равное 1.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
91
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
Аппроксимация распределений с коэффициентом вариации > 1
Положим, что математическое ожидание и коэффициент вариации некоторой случайной величины , определенной в положительной области действительных чисел, соответственно равны t и , причем 1 . В этом случае для аппроксимации закона распределения в теории массового обслуживания используют гиперэкспоненциальное распределение [3], представляющее собой композицию экспоненциальных распределений.
Случайная величина, распределенная по гиперэкспоненциальному закону, представляет собой совокупность случайных величин (фаз), распределенных по r разным экспоненциальным законам, причем появление случайной величины, принадлежащей i-ой фазе, происходит с вероятностью
r
qi (i 1, r), qi 1 . i 1
В простейшем случае гиперэкспоненциальное распределение может быть представлено в виде двух экспоненциальных распределений (рис. 2).
q exp(t1)
1–q
exp(t2)
Рис. 2. Двухфазное гиперэкспоненциальное распределение
Параметрами такого распределения являются: t1 и t2 – математические ожидания экспоненциальных распределений; q – вероятность формирования случайной величины по первой экспоненте. Полу-
ченное таким образом распределение является трехпараметрическим. Это означает, что аппроксимация
может выполняться по трем числовым моментам. Выбор значений параметров t1, t2 и q гиперэкспоненциального распределения по двум моментам предполагает наличие некоторого произвола.
Таким образом, задача аппроксимации гиперэкспоненциальным распределением сводится к опре-
делению значений параметров t1, t2 и q в зависимости от известных значений математического ожида-
ния t и коэффициента вариации аппроксимируемого закона распределения случайной величины .
Математическое ожидание и второй начальный момент гиперэкспоненциального распределения
соответственно равны
t q t1 (1 q) t2 ;
(9)
t (2) 2[qt12 (1 q) t22 ].
Тогда коэффициент вариации гиперэкспоненциального распределения
2
2[q t12
(1 q) t22 ] t2
1 ,
откуда
2[qt12 (1 q) t22 ] t 2 (1 2 ).
Из (9) имеем:
(10)
t2
t q t1 1 q
.
(11)
Подставив последнее выражение в (10), после некоторых преобразований получим квадратное уравнение
2q t12 4q t t1 [1 q (1 q )2 ]t 2 0 .
Решая это квадратное уравнение относительно t1 , получим:
t1 t 1
1 q 2q
( 2
1)
.
(12)
Для того чтобы гарантировать t1 0 , в качестве решения выберем корень уравнения со знаком
плюс перед знаком радикала:
t1 1
1 q 2q
(
2
1)
t
.
(13)
92 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
Подставим (13) в (11) и найдем t2 :
t2 1
q 2 (1
q)
(
2
1)
t
.
Потребуем, чтобы
t2
0 , т.е.
q 2(1
q)
(2
1)
1
.
Отсюда
(14)
q
1
2 2
.
(15)
Выражения (13)–(15) можно использовать для аппроксимации любого закона распределения с ко-
эффициентом вариации 1 двухфазным гиперэкспоненциальным распределением, для чего достаточ-
но выбрать значение вероятности q из условия (15) и рассчитать значения t1 и t2 в соответствии с (13) и
(14). В частном случае, когда
q
2 1 2
,
с
использованием
(13)
и
(14)
получим:
t1
2 1 2
t;
t2 0 .
(16)
Последние выражения соответствуют однофазному представлению гиперэкспоненциального
распределения, которое является частным случаем так называемого распределения Кокса.
Пример 2. Пусть 3 , тогда в соответствии с (15) q 0, 2 .
1.
Выберем
q
0,1 ,
тогда
в
соответствии
с
(13)
и
(14)
t1
7t;
t2
1 3
t
.
2. Выберем q 0, 2 , тогда в соответствии с (16) t1 5t ; t2 0 .
Заметим, что полученные для t1 и t2 выражения (13) и (14) симметричны. Можно показать, что если выбрать в качестве решения квадратного уравнения (12) второй корень со знаком минус перед знаком ра-
дикала и потребовать, чтобы выражение в квадратных скобках не было отрицательным, то получим:
t1 t 1
1 q 2q
( 2
1)
;
t2 t 1
q 2(1
q)
(
2
1)
,
а условие
для
выбора
значения
q
примет
вид
q
2 2
1 1
,
что
экспоненциальных фаз (рис. 2) гиперэкспоненциального распределения.
равносильно
перестановке
Заключение
Полученные соотношения позволяют выполнить на основе заданных двух моментов вероятностного распределения точный расчет параметров гипо- и гиперэкспоненциальных распределений, используемых для аппроксимации распределений случайных величин, определенных в положительной области действительных чисел и имеющих отличный от единицы коэффициент вариации. Благодаря этому процессы, протекающие, например, в неэкспоненциальных сетях массового обслуживания и системах с приоритетами, могут быть представлены в терминах марковского процесса. Использование гипоэкспоненциального распределения вместо распределения Эрланга позволяет выполнить аппроксимацию распределений с любым значением коэффициента вариации в интервале (0; 1), что повышает точность результатов расчета характеристик функционирования таких систем. Кроме того, предлагаемая аппроксимация по двум заданным моментам вероятностного распределения может использоваться для формирования случайных величин, распределенных по произвольному закону, при проведении имитационных экспериментов.
Литература
1. Алиев Т.И., Муравьева-Витковская Л.А. Приоритетные стратегии управления трафиком в мультисервисных компьютерных сетях // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 6. – С. 44–49.
2. Алиев Т.И. Задачи синтеза систем с потерями // Изв. вузов. Приборостроение. – 2012. – Т. 55. – № 10. – С. 57–63.
3. Клейнрок Л. Теория массового обслуживания: Пер. с англ. – М.: Машиностроение, 1979. – 432 с.
Алиев Тауфик Измайлович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, зав. кафедрой, :aliev@d1.ifmo.ru
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
93
УДК 519.872
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ
Т.И. Алиев
Для вероятностных распределений с коэффициентами вариации, отличными от единицы, получены математические зависимости для аппроксимации по двум заданным моментам распределения с использованием мультиэкспоненциальных распределений. Для аппроксимации распределений с коэффициентами вариации меньше единицы предлагается использовать гипоэкспоненциальное распределение, которое, в отличие от распределения Эрланга, имеющего дискретные значения коэффициента вариации, позволяет формировать случайные величины с любым значением коэффициента вариации в интервале (0; 1). Ключевые слова: вероятностное распределение, коэффициент вариации, аппроксимация, гипоэкспоненциальное
распределение, гиперэкспоненциальное распределение, распределение Эрланга. Введение
В качестве моделей вычислительных систем и сетей широкое применение находят математические модели массового обслуживания, позволяющие проводить анализ эффективности их функционирования и
88 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
решать задачи системотехнического проектирования [1, 2]. При этом наибольшее распространение получили так называемые экспоненциальные модели, в которых протекающие в исследуемых системах процессы описываются случайными величинами, распределенными по экспоненциальному закону, обладающему свойством отсутствия последействия. Это замечательное свойство экспоненциального распределения используется при построении моделей в терминах марковских процессов, представляющих собой особый класс случайных процессов, развитие которых не зависит от предыстории процесса [3]. Благодаря этому для многих моделей массового обслуживания удается достаточно просто получить конечные результаты, в том числе в явном виде и в аналитической форме, для расчета характеристик исследуемой системы. Исходя из этого, часто при исследовании систем, в которых временные процессы отличаются от экспоненциальных, стремятся свести эти процессы к экспоненциальному представлению.
Для экспоненциального закона распределения случайных величин, определенных в области положительных значений, коэффициент вариации, описывающий разброс значений случайной величины, равен единице. Если реальные временные интервалы имеют значения коэффициента вариации, отличающиеся от единицы, использование экспоненциального распределения может привести к значительным погрешностям конечных результатов. В этих случаях в качестве аппроксимирующих функций законов распределений могут использоваться мультиэкспоненциальные распределения, представляющие собой композицию экспоненциальных распределений, а именно: распределение Эрланга, когда коэффициент вариации временного интервала меньше единицы, 0 1 , и гиперэкспоненциальное распределение,
когда коэффициент вариации временного интервала больше единицы, 1 [3]. При этом аппроксима-
ция реального распределения в простейшем случае может выполняться по двум первым моментам рас-
пределения – математическому ожиданию и коэффициенту вариации.
Аппроксимация распределений с коэффициентом вариации 0 < ν < 1
Положим, что математическое ожидание и коэффициент вариации некоторой случайной величины , определенной в положительной области действительных чисел, соответственно равны t и , причем
0 1 . Для аппроксимации закона распределения такой случайной величины в теории массового обслуживания обычно используют распределение Эрланга [3]. Случайная величина, распределенная по закону Эрланга k-го порядка Ek , представляет собой сумму k экспоненциально распределенных случайных величин (фаз) с одинаковым математическим ожиданием M [] .
Математическое ожидание и коэффициент вариации случайной величины, распределенной по за-
кону Эрланга k-го порядка, равны соотвтственно
M Ek k M [];
Ek
1, k
где k 1, 2, ... – параметр распределения Эрланга, принимающий целочисленные значения.
Тогда для заданных реальных (измеренных) значений математического ожидания t и коэффициен-
та вариации (0 1) некоторой случайной величины , определенной в положительной области
действительных чисел, параметры аппроксимирующего распределения Эрланга будут определяться следующим образом:
k
1 2
;
M []
t k
,
где ]x[ означает ближайшее целое, большее x. Нетрудно убедиться, что распределение Эрланга позволяет
аппроксимировать только те реальные распределения, коэффициенты вариации которых имеют
следующие значения: 0,707 (при k = 2); 0,577 (при k = 3); 0,5 (при k = 4) и т.д.
Для аппроксимации распределений с любым значением коэффициента вариации, находящимся в
интервале (0; 1), рассмотрим многофазное распределение с разными значениями математического ожи-
дания экспоненциальных распределений в разных фазах: ti Mi[] (i 1, k) , которое будем называть
гипоэкспоненциальным распределением. Проанализируем свойства гипоэкспоненциального распределения на примере двухфазного рас-
пределения, математическое ожидание и второй начальный момент которого будут равны
M h2 t1 t2 ;
(2) h2
2 (t12
t1t2
t22 ) , откуда коэффициент вариации
h2
t12 t22 /(t1 t2 ) .
На рис. 1 показана зависимость коэффициента вариации гипоэкспоненциального распределения
2-го порядка от отношения t1 / t2 параметров экспоненциальных составляющих. Как видно из графика,
коэффициент вариации гипоэкспоненциального распределения изменяется в пределах от 1 до 0,7, точ-
нее, до значения 0,707, т.е. коэффициента вариации распределения Эрланга 2-го порядка, когда парамет-
ры экспоненциальных составляющих равны между собой, t1 t2 .
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
89
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
1
Коэффициент вариации
0,9
0,8
0,7
0,6 0,05
0,25
0,45 0,65 0,85 1,00
Отношение t1/t2
Рис. 1. Зависимость коэффициента вариации от отношения t1/t2
Очевидно, что для увеличения интервала изменения коэффициента вариации гипоэкспоненциаль-
ного распределения необходимо вместо двухфазного использовать многофазное (k-фазное, k 2 ) пред-
ставление. Математическое ожидание и коэффициент вариации гипоэкспоненциального распределения
k-го порядка будут равны
k
M hk ti ; i 1
k
hk
ti2
i 1
k
ti .
i 1
(1)
Коэффициент вариации гипоэкспоненциального распределения k-го порядка лежит в интерва-
ле (1/ k ; 1) , причем с увеличением порядка k левая граница этого интервала приближается к нулю
(k = 2, 3, …). Рассмотрим теперь задачу аппроксимации реального распределения с коэффициентом вариации
0 1 гипоэкспоненциальным распределением k-го порядка. Положим, что известны математическое ожидание t и коэффициент вариации (причем 0 1 ) некоторой случайной величины , определенной в положительной области действительных чисел. Для простоты без потери общности положим, что аппроксимирующее гипоэкспоненциальное распределение k-го порядка содержит только два типа
экспоненциальных фаз: k1 фаз с параметром 1 1/ t1 и k2 k k1 фаз с параметром 2 1/ t2 , где t1 и
t2 – математические ожидания экспоненциально распределенных случайных величин в фазах первого и
второго типов соответственно. Тогда из (1) следует, что математическое ожидание и коэффициент вариации будут равны
M hk k1 t1 k2 t2 ; hk k1 t12 k2 t22 (k1 t1 k2 t2 ) ,
причем k1 k2 k . Таким образом, для аппроксимации по двум моментам необходимо, чтобы выполнялись следую-
щие два условия:
k1 t1 k2 t2 t;
k1 t12 k2 t22 k1 t1 k2 t2
,
где t и – соответственно математическое ожидание и коэффициент вариации аппроксимируемого
(реального) распределения. Полагая, что значения k1 и k2 известны, решим полученную систему
уравнений относительно неизвестных t1 и t2 . Из первого уравнения системы следует, что
t2
t k1t1 k2
.
(2)
Подставляя это выражение во второе уравнение, после некоторых преобразований получим квад-
ратное уравнение с одним неизвестным t1 :
k1 (k1 k2 ) t12 2k1 t t1 (t 2 k22t 2 ) 0 . Решая это квадратное уравнение, получим:
t1
t k
1
где k k1 k2 .
k2
k1
k2
1
,
(3)
90 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
В качестве решения могут использоваться оба корня квадратного уравнения.
Для того чтобы в (3) под знаком квадратного корня была неотрицательная величина, необходимо
выполнение условия
k
1 2
,
(4)
которое определяет минимальное количество фаз в аппроксимирующем гипоэкспоненциальном распре-
делении, т.е. порядок распределения. Для того чтобы второе решение со знаком минус перед квадратным
корнем давало t1 0 , дополнительно необходимо выполнение условия
k2
1 2
.
(5)
Объединив условия (4) и (5), окончательно получим вполне очевидное условие
k2
1 2
k
.
(6)
Подставим теперь (3) в (2) и найдем t2 :
t2
t k
1
k1 k2
k2
1
,
для которого получим условие, аналогичное условию (6):
k1
1 2
k
.
Окончательно имеем следующие выражения для аппроксимации гипоэкспоненциальным распре-
делением k-го порядка законов распределения случайных величин с коэффициентом вариации 0 1 :
k
1 2
;
(7)
t1
t k
1
k2 k1
k2
1
или
t1
t k
1
k2 k1
k2
1
.
t2
t k
1
k1 k2
k2
1
t2
t k
1
k1 k2
k2
1
(8)
Алгоритм аппроксимации реального распределения с коэффициентом вариации 0 1 гипо-
экспоненциальным распределением k-го порядка при заданных значениях математического ожидания t
и коэффициента вариации случайной величины , определенной в положительной области действи-
тельных чисел, формулируется следующим образом:
1. на основе выражения (7) по заданному значению коэффициента вариации определяется
минимально необходимое число экспоненциальных фаз k в аппроксимирующем распределении как
ближайшее большее целое по отношению к 1 / 2 ;
2. выбирается значение k1 k и рассчитывается k2 k k1 ;
3. на основе (8) рассчитываются значения t1 и t2 .
Результаты аппроксимации на основе выражений (7) и (8) при разных значениях k1 и k2 k k1 различаются значениями третьего и более высоких моментов распределения, учет которых при аппрок-
симации реальных распределений не вызывает принципиальных трудностей, но сопровождается более
громоздкими математическими выкладками. К тому же, во многих случаях влияние этих моментов на
конечные результаты исследований оказывается незначительным. Пример 1. Пусть математическое ожидание и коэффициент вариации аппроксимируемого выра-
жения соответственно равны t 10 и 0, 4 .
В соответствии с изложенным выше алгоритмом:
1. минимально необходимое число экспоненциальных фаз k в аппроксимирующем распределении
k 7 ( k 1/ 0,16 6, 25 );
2. выберем значение k1 3 , тогда k2 7 3 4 ;
3. на основе (8) рассчитываются значения t1 2 и t2 1. Таким образом, в качестве аппроксимирующего распределения выбираем гипоэкспоненциальное
распределение 7-го порядка, в котором 3 экспоненциальные фазы имеют математическое ожидание, рав-
ное 2, и 4 фазы – математическое ожидание, равное 1.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
91
АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ …
Аппроксимация распределений с коэффициентом вариации > 1
Положим, что математическое ожидание и коэффициент вариации некоторой случайной величины , определенной в положительной области действительных чисел, соответственно равны t и , причем 1 . В этом случае для аппроксимации закона распределения в теории массового обслуживания используют гиперэкспоненциальное распределение [3], представляющее собой композицию экспоненциальных распределений.
Случайная величина, распределенная по гиперэкспоненциальному закону, представляет собой совокупность случайных величин (фаз), распределенных по r разным экспоненциальным законам, причем появление случайной величины, принадлежащей i-ой фазе, происходит с вероятностью
r
qi (i 1, r), qi 1 . i 1
В простейшем случае гиперэкспоненциальное распределение может быть представлено в виде двух экспоненциальных распределений (рис. 2).
q exp(t1)
1–q
exp(t2)
Рис. 2. Двухфазное гиперэкспоненциальное распределение
Параметрами такого распределения являются: t1 и t2 – математические ожидания экспоненциальных распределений; q – вероятность формирования случайной величины по первой экспоненте. Полу-
ченное таким образом распределение является трехпараметрическим. Это означает, что аппроксимация
может выполняться по трем числовым моментам. Выбор значений параметров t1, t2 и q гиперэкспоненциального распределения по двум моментам предполагает наличие некоторого произвола.
Таким образом, задача аппроксимации гиперэкспоненциальным распределением сводится к опре-
делению значений параметров t1, t2 и q в зависимости от известных значений математического ожида-
ния t и коэффициента вариации аппроксимируемого закона распределения случайной величины .
Математическое ожидание и второй начальный момент гиперэкспоненциального распределения
соответственно равны
t q t1 (1 q) t2 ;
(9)
t (2) 2[qt12 (1 q) t22 ].
Тогда коэффициент вариации гиперэкспоненциального распределения
2
2[q t12
(1 q) t22 ] t2
1 ,
откуда
2[qt12 (1 q) t22 ] t 2 (1 2 ).
Из (9) имеем:
(10)
t2
t q t1 1 q
.
(11)
Подставив последнее выражение в (10), после некоторых преобразований получим квадратное уравнение
2q t12 4q t t1 [1 q (1 q )2 ]t 2 0 .
Решая это квадратное уравнение относительно t1 , получим:
t1 t 1
1 q 2q
( 2
1)
.
(12)
Для того чтобы гарантировать t1 0 , в качестве решения выберем корень уравнения со знаком
плюс перед знаком радикала:
t1 1
1 q 2q
(
2
1)
t
.
(13)
92 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 2 (84)
Т.И. Алиев
Подставим (13) в (11) и найдем t2 :
t2 1
q 2 (1
q)
(
2
1)
t
.
Потребуем, чтобы
t2
0 , т.е.
q 2(1
q)
(2
1)
1
.
Отсюда
(14)
q
1
2 2
.
(15)
Выражения (13)–(15) можно использовать для аппроксимации любого закона распределения с ко-
эффициентом вариации 1 двухфазным гиперэкспоненциальным распределением, для чего достаточ-
но выбрать значение вероятности q из условия (15) и рассчитать значения t1 и t2 в соответствии с (13) и
(14). В частном случае, когда
q
2 1 2
,
с
использованием
(13)
и
(14)
получим:
t1
2 1 2
t;
t2 0 .
(16)
Последние выражения соответствуют однофазному представлению гиперэкспоненциального
распределения, которое является частным случаем так называемого распределения Кокса.
Пример 2. Пусть 3 , тогда в соответствии с (15) q 0, 2 .
1.
Выберем
q
0,1 ,
тогда
в
соответствии
с
(13)
и
(14)
t1
7t;
t2
1 3
t
.
2. Выберем q 0, 2 , тогда в соответствии с (16) t1 5t ; t2 0 .
Заметим, что полученные для t1 и t2 выражения (13) и (14) симметричны. Можно показать, что если выбрать в качестве решения квадратного уравнения (12) второй корень со знаком минус перед знаком ра-
дикала и потребовать, чтобы выражение в квадратных скобках не было отрицательным, то получим:
t1 t 1
1 q 2q
( 2
1)
;
t2 t 1
q 2(1
q)
(
2
1)
,
а условие
для
выбора
значения
q
примет
вид
q
2 2
1 1
,
что
экспоненциальных фаз (рис. 2) гиперэкспоненциального распределения.
равносильно
перестановке
Заключение
Полученные соотношения позволяют выполнить на основе заданных двух моментов вероятностного распределения точный расчет параметров гипо- и гиперэкспоненциальных распределений, используемых для аппроксимации распределений случайных величин, определенных в положительной области действительных чисел и имеющих отличный от единицы коэффициент вариации. Благодаря этому процессы, протекающие, например, в неэкспоненциальных сетях массового обслуживания и системах с приоритетами, могут быть представлены в терминах марковского процесса. Использование гипоэкспоненциального распределения вместо распределения Эрланга позволяет выполнить аппроксимацию распределений с любым значением коэффициента вариации в интервале (0; 1), что повышает точность результатов расчета характеристик функционирования таких систем. Кроме того, предлагаемая аппроксимация по двум заданным моментам вероятностного распределения может использоваться для формирования случайных величин, распределенных по произвольному закону, при проведении имитационных экспериментов.
Литература
1. Алиев Т.И., Муравьева-Витковская Л.А. Приоритетные стратегии управления трафиком в мультисервисных компьютерных сетях // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 6. – С. 44–49.
2. Алиев Т.И. Задачи синтеза систем с потерями // Изв. вузов. Приборостроение. – 2012. – Т. 55. – № 10. – С. 57–63.
3. Клейнрок Л. Теория массового обслуживания: Пер. с англ. – М.: Машиностроение, 1979. – 432 с.
Алиев Тауфик Измайлович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, зав. кафедрой, :aliev@d1.ifmo.ru
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
93