В стационарном состоянии длина M/M/1-очереди n описывается геометрическим распределением:
Мы встречали его в предыдущей главе, рассматривая простейшую несимметричную марковскую цепь. Зная это распределение, можно вычислить ожидаемую длину .
Для нашего примера средняя длина очереди составит 7,5 человек. Время обслуживания клиента (сумма времени ожидания своей очереди и собственно времени работы с оператором) в M/M/1-очереди описывается экспоненциальным распределением с параметром μ − λ. Это приводит к значению среднего времени ожидания .
Среднее время работы с каждым клиентом не превышает 2 минут, однако среднее время ожидания для нашего примера равно 15 минутам. Как видно, для стационарной M/M/1-очереди выполняется равенство:
λW = L.
Это и есть формула Литтла, которой мы воспользовались, стоя в очереди и от нечего делать занявшись подсчетами. Будучи очень простой, формула на удивление сильна: она выполняется для очень широкого класса очередей и в самых разных задачах. То, что в формулу Литтла входит только λ, а не μ, отражает основное свойство стабильной (устойчивой) очереди: она может задерживать клиентов, но не меняет их поток, который определяется значением λ. И даже если скорость работы оператора μ будет очень велика, среднее время ожидания все равно определяется входным потоком и уже скопившимся числом клиентов. А поскольку для устойчивых очередей λ<μ, мы получаем еще один закон подлости:
Важная характеристика очереди — время занятости оператора, или длительность непрерывных периодов времени, в которые он обслуживает клиентов. Обозначим это время B. Периоды занятости перемежаются периодами простоя, когда по какой-то причине клиентов в очереди не оказывается. Клиенты приходят, ждут и уходят, а оператор остается работать, поэтому разумно предположить, что B>W. В действительности ожидаемое, среднее время занятости для M/M/1-очередей равно среднему времени ожидания, то есть B=W. Уже не вполне интуитивно понятный результат, но и это еще не всё: при той же интенсивности труда среднее время обслуживания клиента может стать существенно больше среднего времени работы оператора! Вот это уже кажется парадоксом. Получается, оператор в среднем умудряется работать меньше, чем в среднем обслуживается клиент!
Как мы уже говорили, средние значения надо использовать осторожно. Объяснить этот парадокс и понять, что происходит в очереди, можно, привлекая дисперсию распределения времени обслуживания одного клиента pout(t). Еще в 1930-е австрийскому математику Феликсу Поллачеку удалось в общем виде вычислить отношение W/B для произвольной M/G/1-очереди:
Здесь σ — дисперсия распределения pout(t). В случае M/M/1-очереди σ = 1/μ, и это отношение равно 1. Но может случиться, что при том же значении среднего распределение pout(t) будет иметь большую дисперсию, и тогда W окажется больше B. На рисунке 7.5 показан пример, в котором pin(t) распределено экспоненциально с λ = 30 чел./ч, а pout(t) описывается гамма-распределением, соответствующим интенсивности μ = 34 чел./ч с дисперсией σ = 2/μ.
Рис. 7.5. Распределения для периодов между появлением новых клиентов (сплошная линия — экспоненциальное распределение) и времени обслуживания одного клиента (пунктирная линия — гамма-распределение)
Очередь остается стабильной, поскольку λ< μ и клиенты в среднем обслуживаются быстрее, чем приходят новые. Оператор работает хорошо: большинство клиентов обслуживаются очень быстро; но обратите внимание на долю «трудных» клиентов, которые формируют достаточно толстый хвост распределения. Их мало, но каждый отнимает много времени, и все в очереди вынуждены их ждать. Для примера, приведенного на рисунке, среднее время ожидания оказалось равно 35 минутам, хотя среднее время занятости оператора прежнее (15 минут). Получается, что, не переставая работать, оператор в среднем филонит, пока мы страдаем в очереди от безделья!
Динамика такой очереди отличается от динамики M/M/1. Для нее характерен несимметричный пилообразный рисунок с плавной восходящей линией и резким сбросом. Пока оператор занят «трудным» клиентом, постепенно вырастает длинный хвост, а потом, освободившись, оператор очень быстро с ним справляется (рис. 7.6).
Рис. 7.6. Динамика M/G/1-очереди, где время ожидания клиентов вдвое превосходит время занятости оператора. Горизонтальные темные полосы показывают периоды долгого ожидания очередного «трудного» клиента
Совсем немного о случайных функциях
Здесь мы ненадолго остановимся и обсудим, что же все-таки такое случайный процесс.
Все очереди движутся по-разному. Ступеньки пуассоновского процесса не повторяют друг друга, и мы располагаем только какими-то статистическими свойствами случайных процессов. Но это уже явно не просто случайное число, а кое-что посложнее. С чем же мы имеем дело? Случайный процесс порождает некую последовательность. Его повторение приведет к новой последовательности, скорее всего с другим числом точек. А можно ли обобщить все эти случайные последовательности? Главным свойством случайных величин мы считаем их непостоянство: от раза к разу, от эксперимента к эксперименту каждая из них меняет свое значение, оставаясь при этом одним объектом. Мы смогли однозначно характеризовать его распределением случайной величины — функцией, сопоставляющей каждое значение случайной величины (или диапазон значений) и его вероятность.
Говоря о стохастических последовательностях, мы имеем дело уже не со случайной величиной, а со случайной функцией. Например, для пуассоновского процесса это функция от времени, возвращающая случайную величину — число отсчетов, наблюдаемых за указанное время. Можно ли такую случайную функцию характеризовать так же однозначно и точно, как случайная величина определяется своим распределением?
Построим на одном графике большое число пуассоновских «лесенок» одинаковой интенсивности, а потом для каждого момента времени создадим срез всех этих данных и усредним их, получив одну точку. Вот что мы увидим (рис. 7.7).
Рис. 7.7. Черная сплошная линия — результат усреднения множества реализаций пуассоновского процесса с интенсивностью 1/4
Облаком всевозможных последовательностей оказалась окружена прямая линия, имеющая наклон, равный интенсивности потока. Это график математического ожидания случайной функции. В отличие от настоящего пуассоновского процесса, то есть подсчета числа событий, значения этой функции — уже не целые числа. Как и среднее значение случайной величины, она характеризует случайную функцию, но вовсе не полностью. Например, можно рассмотреть аналог дисперсии, показав, насколько велик ожидаемый разброс значений от среднего. Стандартное отклонение показано на рисунке пунктиром. Но и две функции — среднее и дисперсия — не дадут полной характеризации. Одна и та же случайная функция способна породить бесчисленное множество последовательностей одинаковой интенсивности. Вновь перенесемся в аэропорт и представим себе две одинаковые очереди, идущие параллельно, например к стойке регистрации. Их движение описывается идентичными случайными функциями, средние графики неразличимы, однако наблюдаемая разница в шагах между двумя параллельными одинаковыми очередями подчиняется нетривиальному распределению Скеллама.
Может быть, если для каждого среза времени мы выясним распределение случайной величины F(t) (скажем, найдя его плотность вероятности pF(t)), то получим исчерпывающую информацию о случайной функции F? Наконец, можно ли синтезировать случайный процесс, генерируя случайные числа согласно распределениям pF(t)?
Ответ на все эти вопросы: нет. Случайные функции устроены сложнее, чем случайные числа. Рассуждая о марковских цепях, мы говорили, что они порождают случайные процессы, не имеющие памяти. При этом мы имели в виду, что на будущее в этих процессах влияет не прошлое, а только настоящий момент. Это свойство — отсутствие памяти — характерно для экспоненциального распределения и связанного с ним пуассоновского процесса. Характеристика памяти процесса — величина, называемая автокорреляционной функцией, которая определяется как среднее от произведения двух значений функции, вычисленных в разделенные известным промежутком τ моменты времени:
K(τ) = M[F(τ)∙F(t — τ)].
Здесь символ M[F(τ)] обозначает математическое ожидание (среднее значение) функции f(t). Величина временного лага τ показывает, насколько далеко мы заглядываем в прошлое. Для важного класса случайных функций, которые называются эргодическими, усреднение может производиться не по множеству реализаций случайного процесса, как для множества пуассоновских процессов, а по одному достаточно длинному ряду наблюдений за единственной реализацией. В физике, экономике или климатологии эргодичность случайных последовательностей очень важна, поскольку мы располагаем одним-единственным миром и можем наблюдать за ним долго, но неспособны исследовать множество его различных реализаций.
Автокорреляция позволяет различать истинно стохастические процессы, детерминированные процессы с наложенным на них шумом и процессы, порождаемые динамическим хаосом. С ее помощью можно отделять в экспериментальных данных основные временн