Очереди

Рассмотрим случайное блуждание по неотрицательным целым числам с отражающим барьером в $0$, которое движется вправо или влево с соответствующими вероятностями $\rho /(1+\rho )$ и $1 /(1+\rho )$; находясь в $0$, частица переходит в 1 на следующем шаге. Покажите, что блуждание имеет стационарное распределение тогда и только тогда, когда $\rho < 1$, и в этом случае единственное такое распределение $\pi$ задаётся формулами $\pi_{0} = \frac{1}{2}(1-\rho ), \pi_{n} = \frac{1}{2}\left(1-\rho^{2}\right) \rho^{n-1}$ при $n \geq 1$.

Предположим теперь, что блуждающая частица из упражнения (11.2.1) задерживает свои шаги следующим образом. Находясь в точке $n$, она ждёт случайное время, имеющее экспоненциальное распределение с параметром $\theta_{n}$, прежде чем переместиться в следующее положение; различные «времена ожидания» независимы друг от друга и от прочей информации, касающейся шагов блуждания. Покажите, что при разумных предположениях относительно $\theta_{n}$ возникающий процесс с непрерывным временем устанавливается в равновесное распределение $\vect {v}$, задаваемое формулой $v_{n} = C \pi_{n} / \theta_{n}$ для некоторой подходящей константы $C$.

Применяя этот результат к случаю, когда $\theta_{0} = \lambda , \theta_{n} = \lambda +\mu$ при $n \geq 1$, выведите, что равновесное распределение очереди $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ есть $v_{n} = (1-\rho ) \rho^{n}, n \geq 0$, где $\rho = \lambda / \mu < 1$.

Рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с $\rho = \lambda / \mu$, удовлетворяющим $\rho < 1$, и предположим, что число $Q(0)$ людей в очереди в момент времени 0 имеет стационарное распределение $\pi_{n} = (1-\rho ) \rho^{n}$, $n \geq 0$. Пусть $W$ — время, проведённое типичным новым посетителем до начала его обслуживания. Покажите, что распределение $W$ задаётся формулой $\mathbb {P}\left(W \leq x\right) = 1-\rho e^{-x(\mu -\lambda )}$ при $x \geq 0$, и отметьте, что $\mathbb {P}\left(W = 0\right) = 1-\rho$.

Коробка содержит $i$ красных шаров и $j$ лимонных шаров, и они вынимаются случайным образом без возвращения. Каждый раз, когда вынимается красный (соответственно лимонный) шар, частица, совершающая блуждание по $\left\{ 0,1,2, \ldots \right\}$, делает один шаг вправо (соответственно влево); начало координат — удерживающий барьер, так что шаги влево из начала координат подавляются. Пусть $\pi (n ; i, j)$ — вероятность того, что частица окажется в положении $n$, стартовав из начала координат. Запишите систему разностных уравнений для $\pi (n ; i, j)$ и выведите, что

где $A(n ; i, j) = \binom {i}{n} /\binom {j+n}{n}$.

Пусть $Q$ — очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с $Q(0) = 0$. Покажите, что $p_{n}(t) = \mathbb {P}\left(Q(t\right) = n)$ удовлетворяет

где $\pi (n ; i, j)$ даны в упражнении (11.2.4).

Пусть $Q(t)$ — длина очереди $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ в момент времени $t$, и пусть $Z = \left\{ Z_{n}\right\}$ — цепь скачков процесса $Q$. Объясните, как стационарное распределение $Q$ может быть получено из стационарного распределения $Z$, и наоборот.

Две очереди имеют по одному серверу каждая, и все времена обслуживания независимы и экспоненциально распределены, с параметром $\mu_{i}$ для очереди $i$. Клиенты прибывают в первую очередь в моменты пуассоновского процесса интенсивности $\lambda \left( < \min \left\{ \mu_{1}, \mu_{2}\right\} \right)$, и по завершении обслуживания немедленно поступают во вторую очередь. Очереди находятся в состоянии равновесия. Покажите, что:

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{D}(d) / 1$, где $\rho = \lambda d < 1$. Покажите, что средняя длина очереди в моменты отправлений в состоянии равновесия равна $\frac{1}{2} \rho (2-\rho ) /(1-\rho )$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ и покажите, что производящая функция моментов типичного периода занятости задаётся формулой

для всех достаточно малых, но положительных значений $s$.

Рассмотрим очередь $M(\lambda ) / G / 1$ без зала ожидания. Клиенты, прибывающие, пока сервер занят, теряются. Покажите, что доля потерянных поступлений в долгосрочной перспективе равна $1 /\left(1+\rho^{-1}\right)$, где $\rho = \lambda \mathbb {E}\left[S\right]$ — интенсивность трафика.

Рассмотрим $\mathrm{G} / \mathrm{M}(\mu ) / 1$ и пусть $\alpha_{j} = \mathbb {E}\left[(\mu X)^{j} e^{-\mu X} / j!\right]$, где $X$ — типичное время между поступлениями. Предположим, что интенсивность трафика $\rho$ меньше 1. Покажите, что равновесное распределение $\pi$ вложенной цепи в моменты поступлений удовлетворяет

Поищите решение вида $\pi_{n} = \theta^{n}$ для некоторого $\theta$ и выведите, что единственное стационарное распределение задаётся формулой $\pi_{j} = (1-\eta ) \eta^{j}$ при $j \geq 0$, где $\eta$ — наименьший положительный корень уравнения $s = M_{X}(\mu (s-1))$.

Рассмотрим очередь $\mathrm{G} / \mathrm{M}(\mu ) / 1$ в состоянии равновесия. Пусть $\eta$ — наименьший положительный корень уравнения $x = M_{X}(\mu (x-1))$, где $M_{X}$ — производящая функция моментов времени между поступлениями. Покажите, что среднее число клиентов впереди нового прибывшего равно $\eta (1-\eta )^{-1}$, а среднее время ожидания равно $\eta \left\{ \mu (1-\eta )\right\}^{-1}$.

Рассмотрим $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$, где $\mu > 1$. Покажите, что длина очереди $Q(t)$ в непрерывном времени не сходится по распределению при $t \rightarrow \infty$, даже несмотря на то, что вложенная цепь в моменты поступлений эргодична.

Покажите, что для очереди $G / G / 1$ моменты начала периодов занятости сервера образуют процесс восстановления.

Рассмотрим очередь $\mathrm{G} / \mathrm{M}(\mu ) / 1$ в состоянии равновесия вместе с двойственной (неустойчивой) очередью $\mathrm{M}(\mu ) / \mathrm{G} / 1$. Покажите, что периоды простоя последней очереди распределены экспоненциально. Используя теорию двойственности очередей, выведите для первой очереди, что: (a) распределение времени ожидания представляет собой смесь экспоненциального распределения и атома в нуле, и (b) равновесная длина очереди геометрическая.

Рассмотрим $\mathrm{G} / \mathrm{M}(\mu ) / 1$ и пусть $G$ — функция распределения $S-X$, где $S$ и $X$ — типичные (независимые) время обслуживания и время между поступлениями. Покажите, что уравнение Винера–Хопфа

для предельного распределения времени ожидания $F$ удовлетворяется функцией $F(x) = 1-\eta e^{-\mu (1-\eta ) x}, x \geq 0$. Здесь $\eta$ — наименьший положительный корень уравнения $x = M_{X}(\mu (x-1))$, где $M_{X}$ — производящая функция моментов $X$.

Рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с $\rho = \lambda / \mu < 1$. Пусть $Q_{\rho }$ — случайная величина с равновесным распределением длины очереди, и покажите, что $(1-\rho ) Q_{\rho }$ сходится по распределению при $\rho \uparrow 1$, причём предельное распределение является экспоненциальным с параметром 1.

Рассмотрим открытый процесс миграции с $c$ станциями, в котором особи прибывают на станцию $j$ с интенсивностью $v_{j}$, особи перемещаются от $i$ к $j$ с интенсивностью $\lambda_{i j} \phi_{i}\left(n_{i}\right)$, а особи покидают станцию $i$ с интенсивностью $\mu_{i} \phi_{i}\left(n_{i}\right)$, где $n_{i}$ обозначает число особей, находящихся в данный момент на станции $i$. Покажите, что, когда $\phi_{i}\left(n_{i}\right) = n_{i}$ для всех $i$, система ведёт себя так, как будто клиенты перемещаются по сети независимо. Определите явный вид стационарного распределения при условии неприводимости и объясните связь с теоремой Бартлетта из задачи (8.10.6).

Пусть $Q$ — очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / s$, где $\lambda < s \mu$, и предположим, что $Q$ находится в состоянии равновесия. Покажите, что процесс отправлений является пуассоновским процессом с интенсивностью $\lambda$, и что отправления до момента времени $t$ независимы от значения $Q(t)$.

Клиенты прибывают по закону пуассоновского процесса с интенсивностью $\lambda$ в магазин с двумя серверами. Времена обслуживания этих серверов независимы и экспоненциально распределены с соответствующими параметрами $\mu_{1}$ и $\mu_{2}$. Прибывающие клиенты образуют единую очередь, и человек в голове очереди переходит к первому свободному серверу. Когда оба сервера свободны, следующему прибывшему выделяется сервер, выбранный согласно одному из следующих правил:

Рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$, изменённую так, что по завершении обслуживания клиент уходит с вероятностью $\delta$ или вновь присоединяется к очереди с вероятностью $1-\delta$. Найдите распределение полного времени, в течение которого клиент обслуживается. Отсюда покажите, что равновесие возможно, если $\lambda < \delta \mu$, и найдите стационарное распределение. Покажите, что в состоянии равновесия процесс отправлений пуассоновский, но если вновь присоединяющийся клиент отправляется в конец очереди, составной процесс поступлений не является пуассоновским.

Рассмотрим открытый процесс миграции в состоянии равновесия. Если не существует пути, по которому особь на станции $k$ могла бы достичь станции $j$, покажите, что поток особей, перемещающихся непосредственно со станции $j$ на станцию $k$, образует пуассоновский процесс.

Покажите, что открытый процесс миграции невзрывной.

Пусть $X$ — неприводимая марковская цепь с непрерывным временем и генератором $\mathbf{G}$ на пространстве состояний $T = S \cup \left\{ \infty \right\}$, где $S$ счётно и непусто. Покажите, что распределение $\vect {\pi }$ на $T$ удовлетворяет $\vect {\pi } \mathbf{G} = \mathbf{0}$ тогда и только тогда, когда для $j \in S, \sum_{i \in T} \pi_{i} g_{i j} = 0$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$ с ограничением, что прибывающие клиенты, которые видят $N$ клиентов впереди себя в очереди, уходят и никогда не возвращаются. Найдите стационарное распределение длины очереди для случаев $k = 1$ и $k = 2$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с ограничением, что если прибывающий клиент видит $n$ клиентов впереди себя в очереди, он присоединяется к очереди с вероятностью $p(n)$, а иначе уходит в негодовании.

В московском супермаркете покупатели стоят в очереди у кассы, чтобы оплатить нужный им товар; затем они переходят во вторую очередь, где ожидают выдачи этого товара. Если покупатели прибывают в магазин по закону пуассоновского процесса с параметром $\lambda$, и все времена обслуживания независимы и экспоненциально распределены с параметром $\mu_{1}$ на первой кассе и $\mu_{2}$ на второй, найдите стационарные распределения длин очередей, когда они существуют, и покажите, что в любой заданный момент времени длины двух очередей независимы в состоянии равновесия.

Рассмотрим M/G/1 с модификацией, при которой сервер может обслуживать одновременно до $m$ клиентов. Если длина очереди меньше $m$ в начале периода обслуживания, то она обслуживает всех, кто ожидает в этот момент. Найдите формулу, которой удовлетворяет производящая функция вероятностей стационарного распределения длины очереди в моменты отправлений, и вычислите эту производящую функцию явно в случае, когда $m = 2$ и времена обслуживания экспоненциально распределены.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$, где $\lambda < \mu$. Найдите производящую функцию моментов длины $B$ типичного периода занятости и покажите, что $\mathbb {E}\left[B\right] = (\mu -\lambda )^{-1}$ и $\operatorname {Var}\left(B\right) = (\lambda +\mu ) /(\mu -\lambda )^{3}$. Покажите, что плотность $B$ равна

где $I_{1}$ — модифицированная функция Бесселя.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ в состоянии равновесия. Получите выражение для средней длины очереди в моменты отправлений. Покажите, что среднее время ожидания в состоянии равновесия прибывающего клиента равно $\frac{1}{2} \lambda \mathbb {E}\left[S^{2}\right] /(1-\rho )$, где $S$ — типичное время обслуживания и $\rho = \lambda \mathbb {E}\left[S\right]$.

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

Пусть $W_{t}$ — время, которое клиенту пришлось бы ждать в очереди $\mathrm{M}(\lambda ) / \mathrm{G} / 1$, если бы он прибыл в момент времени $t$. Покажите, что функция распределения $F(x ; t) = \mathbb {P}\left(W_{t} \leq x\right)$ удовлетворяет

где $S$ — типичное время обслуживания, независимое от $W_{t}$. Предположим, что $F(x, t) \rightarrow H(x)$ для всех $x$ при $t \rightarrow \infty$, где $H$ — функция распределения, удовлетворяющая $0 = h-\lambda H+\lambda \mathbb {P}\left(U+S \leq x\right)$ при $x > 0$, где $U$ независима от $S$ и имеет функцию распределения $H$, а $h$ — плотность $H$ на $(0, \infty )$. Покажите, что производящая функция моментов $M_{U}$ величины $U$ удовлетворяет

где $\rho$ — интенсивность трафика. Можете считать, что $\mathbb {P}\left(S = 0\right) = 0$.

Рассмотрим очередь $\mathrm{G} / \mathrm{G} / 1$, в которой времена обслуживания постоянно равны $2$, тогда как времена между поступлениями принимают либо значение 1, либо 4 с равной вероятностью $\frac{1}{2}$. Найдите предельное распределение времени ожидания.

Рассмотрим крайне идеализированную модель телефонной станции с бесконечным числом доступных каналов. Вызовы поступают по закону пуассоновского процесса с интенсивностью $\lambda$, и каждый требует один канал в течение времени, имеющего экспоненциальное распределение с параметром $\mu$, независимо от процесса поступлений и от продолжительности других вызовов. Пусть $Q(t)$ — число вызовов, обрабатываемых в момент времени $t$, и предположим, что $Q(0) = I$.

Определите производящую функцию вероятностей $Q(t)$ и выведите $\mathbb {E}\left[Q(t\right]), \mathbb {P}\left(Q(t\right) = 0)$ и предельное распределение $Q(t)$ при $t \rightarrow \infty$.

Предполагая, что очередь находится в состоянии равновесия, найдите долю времени, в течение которого ни один канал не занят, и среднюю длину периода простоя. Выведите отсюда, что средняя длина периода занятости равна $\left(e^{\lambda / \mu }-1\right) / \lambda$.

Клиенты прибывают в магазин по закону пуассоновского процесса с интенсивностью $\lambda$, где $0 < \lambda < 1$. Их обслуживают по одному в порядке прибытия, и каждому требуется время обслуживания единичной длины. Пусть $Q(t)$ — число людей в очереди в момент времени $t$. Сравнивая $Q(t)$ с $Q(t+1)$, определите предельное распределение $Q(t)$ при $t \rightarrow \infty$ (можете считать, что рассматриваемые величины сходятся). Отсюда покажите, что средняя длина очереди в состоянии равновесия равна $\lambda \left(1-\frac{1}{2} \lambda \right) /(1-\lambda )$.

Пусть $W$ — время ожидания только что прибывшего клиента, когда очередь находится в состоянии равновесия. Выведите из приведённых выше результатов, что $\mathbb {E}\left[W\right] = \frac{1}{2} \lambda /(1-\lambda )$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{D}(1) / 1$ и предположим, что очередь пуста в момент времени 0. Пусть $T$ — самый ранний момент времени, в который клиент уходит, оставляя очередь пустой. Покажите, что производящая функция моментов $M_{T}$ величины $T$ удовлетворяет

и выведите среднее значение $T$, различая случаи $\lambda < 1$ и $\lambda \geq 1$.

Предположим $\lambda < \mu$, и рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1, Q$ в состоянии равновесия.

Рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$, где $k \geq 1$. Покажите, что стационарное распределение $\vect {\pi }$ существует тогда и только тогда, когда $\lambda < k \mu$, и вычислите его в этом случае.

Предположим, что стоимость эксплуатации этой системы в состоянии равновесия составляет

где положительные константы $A$ и $B$ представляют соответственно затраты на найм сервера и неудовлетворённость задержанных клиентов.

Покажите, что при фиксированном $\mu$ существует единственное значение $\lambda^{*}$ в интервале $(0, \mu )$ такое, что дешевле иметь $k = 1$, чем $k = 2$, тогда и только тогда, когда $\lambda < \lambda^{*}$.

Клиенты прибывают в магазин по закону пуассоновского процесса с интенсивностью $\lambda$. Они образуют единую очередь. Имеется два сервера, обозначенных 1 и $2$, серверу $i$ требуется экспоненциально распределённое время с параметром $\mu_{i}$ для обслуживания любого данного клиента. Клиент в голове очереди обслуживается первым свободным сервером; когда оба свободны, прибывающий клиент с равной вероятностью выбирает любой из них.

Рассмотрим очередь $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$, где $\mu > 1$, и пусть $Q_{n}$ — число людей в очереди непосредственно перед $n$-м прибытием. Пусть $Q_{\mu }$ — случайная величина, имеющая в качестве распределения стационарное распределение марковской цепи $\left\{ Q_{n}\right\}$. Покажите, что $\left(1-\mu^{-1}\right) Q_{\mu }$ сходится по распределению при $\mu \downarrow 1$, причём предельное распределение является экспоненциальным с параметром 2.

Такси прибывают на стоянку по закону пуассоновского процесса с интенсивностью $\tau$, а пассажиры прибывают по закону (независимого) пуассоновского процесса с интенсивностью $\pi$. Если нет ожидающих пассажиров, такси ждут, пока не прибудут пассажиры, а затем отъезжают с пассажирами, по одному на такси. Если нет такси, пассажиры ждут, пока не прибудут такси. Предположим, что первоначально на стоянке нет ни такси, ни пассажиров. Покажите, что вероятность того, что $n$ пассажиров ожидают в момент времени $t$, равна $(\pi / \tau )^{\frac{1}{2} n} e^{-(\pi +\tau ) t} I_{n}(2 t \sqrt{\pi \tau })$, где $I_{n}(x)$ — модифицированная функция Бесселя, т.е. коэффициент при $z^{n}$ в разложении в степенной ряд функции $\exp \left\{ \frac{1}{2} x\left(z+z^{-1}\right)\right\}$

Станки поступают на ремонт по закону пуассоновского процесса с интенсивностью $\lambda$. Каждый ремонт включает два этапа, при этом $i$-й прибывший станок находится в ремонте в течение времени $X_{i}+Y_{i}$, где пары $\left(X_{i}, Y_{i}\right), i = 1,2, \ldots$, независимы и имеют общее совместное распределение. Пусть $U(t)$ и $V(t)$ — числа станков на $X$-этапе и $Y$-этапе ремонта в момент времени $t$. Покажите, что $U(t)$ и $V(t)$ — независимые пуассоновские случайные величины.

Страховая компания выплачивает независимые и одинаково распределённые страховые требования $\left\{ K_{n}: n \geq 1\right\}$ в моменты пуассоновского процесса с интенсивностью $\lambda$, где $\lambda \mathbb {E}\left[K_{1}\right] < 1$. Страховые взносы поступают с постоянной скоростью 1. Покажите, что максимальный дефицит $M$, который когда-либо накопит компания, имеет производящую функцию моментов

Для очереди $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с $\lambda < \mu$, находящейся в состоянии равновесия, покажите, что ожидаемое время до первого опустошения очереди равно $\lambda (\mu -\lambda )^{-2}$.

Рассмотрим очередь $M(\lambda ) / G / \infty$. Используя теорему о вознаграждении при восстановлении, покажите, что ожидаемая продолжительность периода занятости равна $\left(e^{\rho }-1\right) / \lambda$, где $\rho = \lambda \mathbb {E}\left[S\right]$.