Waiting time paradox #1: автобусы, очереди, и хэш-таблицы

Ничего не доводи до крайности: человек, желающий трапезовать слишком поздно, рискует трапезовать на другой день поутру.
(Козьма Прутков)

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

Пост собран по информации из разных мест, но основным источником вдохновения послужил курс лекций по системам массового обслуживания (Basic queueing theory) профессора Роберта Купера, и его же статьи. Я встречался с парадоксом времен ожидания и раньше, но он не показался мне сильно интересным – мало ли этих парадоксов в тервере? Профессор Купер сумел поменять мое мнение – он рассказывает так интересно, что я не могу не поделиться

О чем вообще речь: что такое waiting time paradox?

Допустим, вы приходите на остановку, и ждете там автобус. Неизвестно, когда именно он придет – зависит от неизбежных на дороге случайностей – но известно, что среднее время между приходами автобусов 10 минут. Сколько, в среднем, вам придется дожидаться автобуса?

Первая мысль, которая приходит в голову (если вы не сталкивались с этой задачей раньше): средний интервал 10 минут, вы прибываете в случайную точку этого интервала – значит до конца, в среднем, останется половина интервала, 10/2 = 5 минут.

Казалось бы да, но нет. Допустим, автобусы приходят через раз: то через 1 минуту, то через 19 (каждый второй попадает в пробку) – среднее время между автобусами 10 минут. Но вероятность прийти на остановку во время 19-ти минутного интервала – в 19 раз больше, чем во время 1-минутного. Пассажир в 19 раз чаще будет попадать на сильно задержавшийся автобус (и ждать его долго). И значит среднее время ожидания для пассажира будет (9.5*19 + 0.5*1)/20 ~= 9 минут – т.е. почти вдвое больше 5 минут, которые можно было бы ожидать интуитивно

Так же и в общем случае: если автобусы не приходят строго регулярно, значит есть интервалы больше и меньше среднего значения. Но вероятность прийти на остановку во время более длинного интервала – больше, ведь более длинные интервалы занимают больше места на временной оси. Поэтому для приходящего на остановку человека более длинные интервалы между автобусами имеют больший вес в его "среднем времени ожидания"
Т.е. разница возникает из-за разного смысла среднего значения у пассажира, приходящего на остановку, и уезжающего на автобусе, и у наблюдателя, который все время стоит на остановке, и просто записывает интервалы между автобусами

У парадокса есть альтернативные названия – inspection paradox, или size-biased sampling – они как раз подчеркивают, что суть в том, что вроде бы наблюдатель смотрит на систему в случайный момент времени, но этот случайный момент оказывается неявно скоординирован с событиями в системе. Приходящий в случайный момент времени пассажир, тем не менее, более вероятно попадает на более длинный интервал между автобусами

Но это еще не все сюрпризы автобусной остановки (beware: math inside)

Правда, чтобы увидеть больше – придется построить какую-никакую математическую модель, и получить явную формулу. Например, так: вероятность прибыть на остановку во время интервала длиной [T..T+dT) пропорциональна вероятности возникновения интервала такой длины, и самой длине этого интервала, T:
$$P(arrive\ in\ interval\ of\ length \in T..T+dT) = k\cdot T\cdot p(T)dT$$
(за p(T) я обозначил плотность вероятности распределения длин интервалов между автобусами). Коэффициент пропорциональности k получается из нормировки общей вероятности на 1:
$$\int_0^\infty k p(T) T dT = 1 \implies k E[T]=1 \implies k=\frac{1}{E[T]}$$
И теперь уже можно посчитать средний интервал между автобусами, который застанет пришедший на остановку в случайный момент пассажир:
$$E[I] = \int_0^\infty T\big(\frac{Tp(T)}{E[T]}\big)dT = \frac{1}{E[X]}\int_0^\infty T^2p(T)dT = \frac{E[T^2]}{E[T]} = \frac{E[T]^2+D[T]}{E[T]} = E[T]\Big(1 + \frac{D[T]}{E[T]^2}\Big)$$
(А среднее время ожидания действительно будет равно половине этого наблюдаемого интервала).

В конце я преобразовал формулу так, чтобы было явно видно, что средний наблюдаемый интервал между автобусами практически всегда больше чем среднее время между прибытиями автобусов – на величину, равную дисперсии деленной на квадрат среднего (стандартное отклонение в единицах среднего называется коэффициентом, или индексом вариации случайной величины, так что эта добавка как раз получается равна квадрату индекса вариации). Единственный случай, когда среднее время ожидания будет равно среднему времени между прибытиями – это когда дисперсия равна 0, то есть автобусы приходят строго регулярно.

Конструкция "время, которое придется ждать некого случайного события, если начать ждать в случайный момент времени" – в английской литературе называется residual time, либо forward-recurrence time. В русской я встречал только "остаточное время", но не уверен, насколько это общеупотребимый термин

Так зачем была нужна формула?

Потому что у этой системы есть еще пара свойств, заметить которые без формулы, "на пальцах", довольно сложно – они более нетривиальны, чем уже описанное

Вопрос первый: хорошо, среднее время ожидания почти всегда больше, чем половина среднего интервала между автобусами. А насколько сильно оно может быть больше?

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

Пример: пусть интервал между автобусами равен 1/N с вероятностью $$\frac{N}{1+N}$$, и N с вероятностью $$\frac{1}{1+N}$$. Средний интервал равен 1, независимо от N, а вот среднее время ожидания при больших N будет расти как ~N/2 – т.е. его можно сделать сколь угодно большим.

Вопрос второй: может ли среднее время ожидания уменьшиться если средний интервал между автобусами увеличивается?

Хотя и понятно, что вопрос с подвохом, но интуитивно кажется что если автобусы начинают приходить реже – то конечно же время ожидания должно увеличиться. Однако формула этого вовсе не обещает. Наоборот: формула задает немонотонную зависимость [W] от E[T].

Выше я построил серию графиков для разных значений дисперсии: время ожидания сначала убывает (!) при росте среднего интервала, и только потом начинает возрастать.

Если сложно поверить, что так может быть (мне было сложно), то вот численный пример: пусть автобусы в 90% случаев приходят каждую минуту, а в 10% случаев задерживаются на 11 минут. Среднее время между приходами автобуса 0.9*1+0.1*11=2 минуты, дисперсия 9, среднее время ожидания по формуле выше ~3.25 минут.

Теперь автобусное депо увеличило время ожидания на остановках, и поэтому все автобусы теперь приходят на 0.5 минуты реже. Среднее время между автобусами увеличится до 2.5 минут, дисперсия останется той же, а среднее время ожидания уменьшится до ~3.1 минуты!

Как так может быть, что события начинают происходить реже – но ждать события приходится меньше?

Наилучшее интуитивное объяснение, которое я пока для себя нашел: весь парадокс вертится вокруг того, что, с точки зрения пассажира, интервалы длиннее среднего имеют бОльший вес в его сумме для среднего времени ожидания, потому что попасть в них вероятнее. Что произойдет, если каждый интервал, входящий в сумму, слегка увеличить? С одной стороны все интервалы, входящие в сумму для среднего – вырастут. Но одновременно относительный вес больших интервалов в этой сумме – уменьшится, а относительный вес маленьких интервалов – увеличится. Эти два процесса вносят противоположный вклад в сумму для среднего, и итоговая сумма может как увеличиваться, так и уменьшаться, в зависимости от.

Формула как раз и показывает, когда и чей вклад важнее: области доминирования разных процессов разделяются точкой $$E[T]=\sqrt{D[T]}$$. Пока стандарное отклонение больше среднего – перераспределение относительных весов мелких и крупных интервалов более значимо, и второй процесс доминирует, а как только среднее становится больше стандартного отклонения – начинает доминировать первый

То есть если среднее больше стандарного отклонения, то зависимость между интервалом между автобусами, и временем ожидания автобуса прямая, "интуитивная". А вот когда среднее меньше стандартного отклонения – зависимость обратная, контр-интуитивная: при росте одного другое уменьшается.

Странно, но когда пишут про парадокс времени ожидания – чаще всего останавливаются на самой первой его части, про то, что время ожидания больше половины среднего интервала. Именно в таком виде я его и встречал раньше. По-моему, первая часть не очень-то заслуживает громкого названия парадокса. Да, неожиданно, что средний наблюдаемый период больше среднего интервала – но не то, чтобы прямо парадоксально. Можно сходу не заметить, что тут что-то необычное происходит, но как только поймешь (или тебе укажут) что интуитивная гипотеза $$E[W]=\frac{E[T]}{2}$$ не верна, что ты чего-то не учел – разобраться, что именно не учел, и описать это математически уже несложно

А вот другие особенности поведения этого "наблюдаемого интервала", как по мне, уже действительно парадоксальны. Особенно, конечно, мозг взрывает немонотонность. Это тот (нечастый) случай, когда вывести формулу гораздо легче, чем потом объяснить себе, почему происходит то, что эта формула демонстрирует.

И хотя эта часть парадокса времен ожидания явно более интересная, ее почему-то реже упоминают. Я могу предположить, что это потому, что первая часть себя проявляет всегда, а вот для остальных эффектов нужны какие-то специфичные условия: распределения с большим коэффициентом вариации в жизни встречаются, но не на каждом углу.

Например, распределение Пуассона – модель по-умолчанию для случайных процессов – имеет стандартное отклонение равное среднему значению, т.е. коэффициент вариации равен 1, т.е. для него время ожидания никогда не будет себя вести аномально

Почему это интересно?

Потому что парадокс времени ожидания очень много где вылезает, заметно или не заметно. Он возникает, когда мы вроде-бы-случайным-образом наблюдаем какие-то случайные события – но при этом вероятность наблюдения были каким-то образом зависит от свойств событий (в нашем случае – от продолжительности интервала). Т.е. события типа А сами по себе более "заметны" для наблюдения, (чаще попадаются под руку) чем события типа B. Тогда наблюдаемые статистические свойства событий будут отличаться от их исходных статистических свойств.

(Не очень понятно, насколько сильно тут стоит обобщать, чтобы не переборщить – а то можно сказать, что любой sampling bias это обобщенный парадокс времен ожидания)

Ситуаций, где такие условия возникают – много. Проще даже сказать наоборот: мало ситуаций, где такие условия не возникают. Обеспечить статистически не искаженное (unbiased) наблюдение за системой довольно непросто – я бы сказал, что в большинстве случаев наблюдения будут как-то, да искаженными, если не предпринимать специальных усилий.

Несколько примеров проявлений парадокса времен ожидания в разных контекстах:

• coordinated omission – статистическая аномалия в результатах бенчмарков, прославленная трудами Gil Tene – это тот же самый парадокс времени ожидания, только вывернутый наизнанку
• среднее время отклика сервера может быть сколь угодно большим, даже загрузка сервера мала, и если среднее время обработки одного запроса мало – но время обработки имеет большую дисперсию
• количество сравнений, нужных чтобы найти запись по ключу в хэш-таблице, может быть больше, чем количество сравнений, нужных чтобы обнаружить отсутствие записи с таким ключом (wtp-2)
• если сервер обрабатывает заявки из нескольких очередей, то время обработки заявки может уменьшаться если при переключении от очереди к очереди добавить паузу (wtp-3)

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

Ссылки

1. MAP 6264: Basic queueing theory (youtube) профессора Роберта Купера. Отличное введение в теорию массового обслуживания. ДЗ №2 как раз про парадокс времени ожидания, но он там дальше всплывает по всему курсу
2. The Waiting Time Paradox, or, Why Is My Bus Always Late?
3. Inspection paradox is everythere
4. wiki: Residual time