Вероятности и неприятности. Математика повседневной жизни - Сергей Борисович Самойленко
K(τ) = M[F(τ)∙F(t — τ)].
Здесь символ M[F(τ)] обозначает математическое ожидание (среднее значение) функции f(t). Величина временного лага τ показывает, насколько далеко мы заглядываем в прошлое. Для важного класса случайных функций, которые называются эргодическими, усреднение может производиться не по множеству реализаций случайного процесса, как для множества пуассоновских процессов, а по одному достаточно длинному ряду наблюдений за единственной реализацией. В физике, экономике или климатологии эргодичность случайных последовательностей очень важна, поскольку мы располагаем одним-единственным миром и можем наблюдать за ним долго, но неспособны исследовать множество его различных реализаций.
Автокорреляция позволяет различать истинно стохастические процессы, детерминированные процессы с наложенным на них шумом и процессы, порождаемые динамическим хаосом. С ее помощью можно отделять в экспериментальных данных основные временные закономерности, присущие процессу, порождающему эти данные, от случайного, не связанного с ними шума. Это один из основных инструментов анализа временных рядов. С его помощью сейсмологи расшифровывают запись землетрясения, выделяя из, казалось бы, совершенно беспорядочного сигнала первичные волны, пришедшие непосредственно от землетрясения, волны, отраженные от границ внутренних слоев Земли, вплоть до самого ядра, и обменные волны, рождающиеся на этих границах. Так сильные землетрясения на несколько часов делают нашу планету «прозрачной», как бы подсвечивая ее изнутри лучами сейсмических волн.
Корреляция в переводе с латыни — «отношение»; получается, что автокорреляция — «отношение к самому себе» или «связь с самим собой в прошлом». Согласитесь, это красивый образ не только для случайной функции, но и для человека.
Мне только спросить!
Но вернемся к очередям и проблемам, с ними связанным. Есть в нашей жизни досадное явление — «обочечники». Это ушлые водители, объезжающие пробку по обочине и потом встревающие в поток. Есть настырные посетители поликлиник и касс, норовящие просочиться к заветному окошку или двери с формулой «Мне только спросить…». В любую отлаженную бюрократическую систему то и дело врываются неотложные дела, не терпящие промедления. Понятно, что порой без таких случаев не обойтись: в больницах бывают неотложные пациенты, в операционной системе компьютера есть задачи с очень высоким приоритетом; наконец, на дороге мы обязаны пропускать спецтранспорт, едущий по экстренному случаю. Но как внеочередники влияют на всю очередь? Подобные случаи моделируются очередями с приоритетом (рис. 7.8), и для них тоже есть развитая теория, поскольку в жизни они встречаются чуть ли не чаще простых очередей.
Рис. 7.8. Очередь с приоритетом
Пусть в нашей M/M/1-очереди с вероятностью ε могут появляться особые клиенты, назовем их VIP (very impatient person — очень нетерпеливые персоны), которые встают не в конец очереди, а вклиниваются в ее начало, заставляя ждать всех стоящих позади. При этом они всё же дают оператору завершить работу с текущим клиентом, не прерывая его. Если внеочередников наберется несколько, они могут образовать свою VIP-очередь. Вспомним, что пуассоновский поток можно представить как случайное «разбрасывание» по временному интервалу какого-то известного количества событий. Поскольку все клиенты приходят независимо, то, согласно нашему условию, мы получим поток нетерпеливых клиентов ελ и поток обычных клиентов (1–ε)λ, при этом общий поток останется неизменным. Среднее время ожидания для VIP будет равно как в простой M/M/1-очереди, поскольку они в своей VIP-очереди «не замечают» присутствия обычных клиентов. Для того, кто ждет на общих основаниях, время ожидания вырастет и составит уже:
Как показывает рисунок 7.9, пока VIP-ов немного, очереди они мешают не сильно. Но если доля внеочередников оказывается близкой к единице, то никакого преимущества они уже не имеют, зато немногочисленным скромным очередникам приходится ждать существенно дольше. При ε, стремящемся к единице, среднее время ожидания рядовых очередников стремится к μ/(μ — λ)2 (больше двух часов в нашем случае!); и вообще, если μ лишь немного превышает λ, очередь остается устойчивой, однако время ожидания в ней вырастает катастрофически!
Рис. 7.9. Соотношение средних времен ожидания для очереди с нетерпеливыми VIP-клиентами
Но вот что любопытно. Можно найти среднее время ожидания для всей группы клиентов как взвешенную сумму εWVIP + (1 — ε)W0, и она окажется равной 1/(μ — λ)2, то есть такой же, как для обыкновенной M/M/1-очереди без всяких VIP-ов. Выходит, системе в целом внеочередники не мешают. На время занятости оператора они тоже не влияют, распределение времен ожидания остается экспоненциальным. Мы уже говорили в предыдущей главе, что для экспоненциального распределения кривая Лоренца и, соответственно, коэффициент Джини не зависят от параметра распределения, а значит, все M/M/1-очереди имеют одинаковую степень несправедливости — 0,5. Отсюда следует, что наш обобщенный критерий несправедливости для всех ожидающих в очереди также останется равным 0,5.
Стационарный бардак
А теперь немного изменим политику очередности. Пусть внеочередники будут сверхнаглыми, и если так случится, что один такой клиент придет вслед за другим, то вместо формирования нормальной очереди второй вклинится перед первым. Эта задача уже отличается от классического подхода к очередям с приоритетом. Давайте сразу рассмотрим предельный случай, когда доля наглых клиентов равна единице. Тогда наша очередь (рис. 7.10) превращается в то, что программисты называют стеком, — последовательность элементов, подчиняющуюся правилу «первым вошел, последним вышел» (FILO — first in, last out) — в противовес очереди, для которой выполняется правило «первым вошел, первым вышел» (FIFO — first in, first out).
Рис. 7.10. Очередь как стек
Такая «очередь наоборот» выглядит неестественно, но если вместо людей мы рассмотрим пачку документов, то можем увидеть знакомую картину на рабочем столе, когда входящие документы не сортируются по времени, складываются в стопку по мере поступления, а потом обрабатываются начиная сверху.
