2

Let $X(t)$ denote the number of customers in a system at time $t$.

The process $\{ X(t), t \geq 0 \}$ at a $M/M/s$ queue is a reversible Markov process.

Is this statement true or false for:
(a) $s=1$?
(b) General $s$?

My attempt:
A reversible Markov process means that $P(X_{t-1} = j | X_t = i, X_{t+1} = i_{t+1}, X_{t-2} = i_{t+2}, \dots ) = P(X_{t-1} = j | X_t = i)$.

So is it possible to find the probability $X_{t-1} = j$ given that $X_t = i$? Intuitively I would say no, but here is the point that I get stuck.

clubkli
  • 759
  • What is a M/M/s queue? – Ian Dec 06 '15 at 22:05
  • See this page: link – clubkli Dec 06 '15 at 22:12
  • Is this in discrete time? The setting in the Wikipedia article is continuous time. At any rate, it is Markov: at a given number of total customers in the system, there is a certain probability (or rate, in continuous time) to decrease it by $1$, and a certain probability (or rate, in continuous time) to increase it by $1$. These depend only on how many customers there are (provided the number of servers is fixed of course). So the tricky question is about reversibility. – Ian Dec 06 '15 at 22:15
  • I guess it is in discrete time. – clubkli Dec 06 '15 at 22:22
  • But I am not sure about that. There is no limit on the number of customers the system can contain. So in the first case, for $s=1$, we have a fixed number of servers. There is a certain probability/rate to increase or decrease the number of customers. How should be checked then whether the process is reversible? – clubkli Dec 06 '15 at 22:36
  • 2
    To show reversibility you are looking for a distribution $\pi$ such that $\pi_i L_{ij} = \pi_j L_{ji}$, where $L$ is the generator. (In discrete time, $L=P-I$; in continuous time, $L$ is usually the object that you have to begin with, since it contains the transition rates.) In this case, for $i \neq j$, $L_{ij}$ is zero unless $j=i \pm 1$. So you should have that $\pi_0$ is some positive number to be determined, then $\pi_{k+1}=\pi_k \frac{L_{k,k+1}}{L_{k+1,k}}$ for $k=0,1,\dots$. Check whether this can be normalized. – Ian Dec 06 '15 at 22:39
  • And what should be checked if this is in continuous time? – clubkli Dec 06 '15 at 22:42
  • I edited my comment. – Ian Dec 06 '15 at 22:43
  • A stationary birth-death process is reversible (cf. http://math.stackexchange.com/questions/107657/simple-proof-that-stationary-birth-death-chains-are-reversible). So an $M/M/1$ queue is reversible, but not $M/M/s$, $s>1$. – Math1000 Feb 24 '16 at 00:34

1 Answers1

0

Any irreducible birth--and--death process that has positive recurrent states is reversible.

First, an irreducible continuous-time Markov process with positive recurrent states has a probability distribution $\mathbf{p}$ that is the unique solution to the equilibrium equations $\mathbf{p} Q = 0$ and the normalization condition $\mathbf{p} \mathbf{1} = 1$, where $Q$ is the transition rate matrix and $\mathbf{1}$ a vector of ones of appropriate dimension.

We employ Theorem 1.3 of Kelly, Reversibility and Stochastic Networks (1979). If $\mathbf{p}, ~ \mathbf{p} \mathbf{1} = 1$ satisfies

\begin{equation} p(i) q(i,j) = p(j) q(j,i) \tag{1} \end{equation}

for all states $i$ and $j$, then the Markov process is reversible and $\mathbf{p}$ is the equilibrium distribution.

The state space of a birth--and--death process is $\{0,1,2,\ldots\}$. The process is called a birth--and--death process because the process can only transition from state $i$ to states $i - 1$ or $i + 1$. This means that $(1)$ is trivially satisfied for $|i - j| > 1$.

Next, draw a barrier between state $i$ and $i + 1$, splitting the state space in two sets of states: a finite set $A$ and a countably infinite set $A^c$. Since the Markov process is in equilibrium (stationary), the rate at which the process enters the set of states $A$ is equal to the rate at which the process leaves the set of states $A$. Given that the process is currently in state $i$, it leaves the set $A$ with rate $q(i,i+1)$. The probability that the Markov process is in state $i$ in equilibrium is $p(i)$. So, the rate at which the Markov process leaves the set $A$ is $p(i) q(i,i + 1)$. Similarly, the rate at which the Markov process enters the set $A$ can be determined. Ultimately, we get

\begin{equation} p(i) q(i,i + 1) = p(i + 1)q(i + 1,i), \end{equation}

which has a solution since the Markov process is irreducible and has positive recurrent states (express all $p(i)$ in terms of $p(0)$ and use the normalization condition $\mathbf{p} \mathbf{1} = 1$). This proves the claim.

As a special case, an irreducible Markov process that models the $M/M/s$ queue is a birth--and--death process and if is it positive recurrent, it is reversible. Say the arrival rate is $\lambda$ and the service rate is $\mu$, then the Markov process associated with the $M/M/s$ queue is positive recurrent if $\lambda/(s\mu) < 1$.

Ritz
  • 1,693
  • 9
  • 18