Stationary distribution of a discrete $M/M/1$ queue.

843 Views Asked by At

Consider a single-server processing system in which items arrive according to a Bernoulli process with probability $p$ of an arrival at each time $n=1,2,\ldots$. The service times of the items are i.i.d. with geometric distribution $\mathbb P(S=m)=(1-q)^{m-1}q$, $m\geqslant 1$ where $0<p<q<1$. Let $X_n$ be the number of items in the system at time $n$. Then $X_n$ is a Markov chain with transition probabilities \begin{align} p_{00} &= 1-p\\ p_{01} &= p\\ p_{i,i+1} &= p(1-q),\ i\geqslant 1\\ p_{i,i-1} &= q(1-p),\ i\geqslant 1\\ p_{i,i} &= pq + (1-p)(1-q),\ i\geqslant 1. \end{align}

The book I am reading, Basics of Applied Stochastic Processes by Serfozo, claims that the stationary distribution of $X_n$ is $\pi_i=(1-\rho)\rho^i$, where $\rho = \frac{p(1-q)}{q(1-p)}$. (This is the same as the result for the continuous-time $M/M/1$ queue.) However, we have \begin{align} \pi P_{\cdot0} &= (1-p)\pi_0 + q(1-p)\pi_1\\ &= (1-p)\pi_0 + q(1-p)\rho\pi_0\\ &= (1-pq)\pi_0\\ &\neq \pi_0, \end{align} so that $\pi\neq\pi P$ (here $P_{\cdot0}$ denotes the $0$ column of the transition matrix $P$). So $\pi$ cannot be a stationary distribution. Is there an error in the text? What is the correct form for $\pi$?

1

There are 1 best solutions below

2
On BEST ANSWER

This can either be an error in the solution, or an error in the setup.

First, let's find the stationary distribution when the transition probabilities are as you have stated them.

Assuming that the stationary distribution exists, which it will for $\rho<1$, it must satisfy $$\pi_i p_{i,i+1} = \pi_{i+1} p_{i+1,i}$$ for $i \ge 0$, just because transitions from $i$ to $i+1$ and from $i+1$ back to $i$ must alternate. This leads to $\pi_i = \rho^{i-1} \pi_1$ for $i\ge 1$, so the result is essentially the same as the continuous case no matter what is happening with $\pi_1$ and $\pi_0$.

Similarly, we have $\pi_0 \cdot p = \pi_1 \cdot q(1-p)$, so $$\pi_1 = \frac{p}{q(1-p)} \pi_0 = \frac{\rho}{1-q} \pi_0.$$ Therefore $$\pi_i = \frac{\rho^i}{1-q} \pi_0$$ for $i\ge 1$, and since the probabilities had better add up to $1$, we get $$\left(1 + \frac1{1-q} \sum_{i \ge 1} \rho^i \right)\pi_0 = 1$$ and this leads to $$ \pi_0 = \frac{(1-q)(1-\rho)}{1 - q(1-\rho)} = 1 - \frac pq. $$ Therefore the general expression is $$ \pi_i = \begin{cases}1 - \frac pq & i=0, \\ \frac{1 - \frac pq}{1-q} \rho^i & i \ge 1.\end{cases} $$ The constant is slightly off in the book, but the overall form is the same.


However, we would get $\pi_i = (1-\rho) \rho^i$ if we made the service times geometrically distributed with the other geometric distribution: the one with support $\{0,1,2,\dots\}$ rather than $\{1,2,3,\dots\}$. Here, with probability $q$, the service time is $0$, and in general $\mathbb P(S=m) = (1-q)^m q$ for $m \ge 0$.

In this case, we have $p_{00} = 1 - p + pq$ and $p_{01} = p(1-q)$ which matches $p_{i,i+1}$ for $i \ge 1$. This lets us write $\pi_i = \rho^i \pi_0$. Solving for $\pi_0$ in this case gives $\pi_0 = 1-\rho$ and therefore $\pi_i = (1-\rho) \rho^i$.