M/M/1

Рассмотрим случайное блуждание по неотрицательным целым числам с отражающим барьером в $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}$ возникающий процесс с непрерывным временем устанавливается в равновесное распределение $\mathbf{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) = n\right)$ удовлетворяет

где $\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)$, и по завершении обслуживания немедленно поступают во вторую очередь. Очереди находятся в состоянии равновесия. Покажите, что: