Question

A total of \(N\) customers move about among \(r\) servers in the following manner. When a customer is served by server \(i\), he then goes over to server \(j, j \neq i\), with probability \(1 /(r-1)\). If the server he goes to is free, then the customer enters service; otherwise he joins the queue. The service times are all independent, with the service times at server \(i\) being exponential with rate \(\mu, i=1, \ldots, r .\) Let the state at any time be the vector \(\left(n_{1}, \ldots, n_{r}\right)\), where \(n_{i}\) is the number of customers presently at server \(i, i=1, \ldots, r, \sum_{i} n_{i}=N\) (a) Argue that if \(X(t)\) is the state at time \(t\), then \(\\{X(t), t \geqslant 0\\}\) is a continuous-time Markov chain. (b) Give the infinitesimal rates of this chain. (c) Show that this chain is time reversible, and find the limiting probabilities.

Short answer

The given system is a continuous-time Markov chain with the infinitesimal generator matrix \(Q\) having elements \(q_{ij} = \mu\) if \(i \neq j\), \(q_{ij} = - \mu(r-1)\) if \(i=j\), and \(q_{ij} = 0\) otherwise. The Markov chain is time-reversible and has limiting probabilities \(\pi_i = \frac{1}{r}\) for all \(i = 1, 2, \ldots, r\).

Step-by-step solution

A continuous-time Markov chain is a stochastic process \(X(t)\) that possesses the Markov property, i.e., the future states depend only on the present state and not on the past states: \[P(X(s+t) = x_{s+t}|X(s) = x_s, X(s-1) = x_{s-1}, \ldots, X(0) = x_0) = P(X(s+t) = x_{s+t}|X(s) = x_s) \,.\] The main difference between continuous-time Markov chains and discrete-time Markov chains lies in the possible states' transitions in continuous time instead of only at fixed time steps. #Step 2: Showing the System is a Continuous-Time Markov Chain#

Let \(X(t) = (n_1(t), n_2(t), \ldots, n_r(t))\) be the state of the system at time \(t\), where \(n_i(t)\) represents the number of customers at server \(i\). It is given that the service times are exponential with rate \(\mu\). We need to show that the Markov property holds for the given system. Considering the movement of customers among the servers, we can see that their movement does not depend on their past locations but only on the current server they are in. When a customer is served by server \(i\), they move to server \(j\) with probability \(\frac{1}{r-1}\), independent of their previous locations. Thus, the future states depend only on the present state and the given system exhibits the Markov property. So, \(X(t)\) is a continuous-time Markov chain. #Step 3: Finding Infinitesimal Rates#

The infinitesimal rates of a continuous-time Markov chain are the transition rates from one state to another. Given that the service times at server \(i\) are exponential with rate \(\mu\), we can define the infinitesimal generator matrix \(Q = (q_{ij})_{r \times r}\) as follows: \[q_{ij} = \begin{cases} \mu & \text{if } i \neq j \\ - \mu(r-1) & \text{if } i=j \\ 0 & \text{otherwise .} \end{cases}\] #Step 4: Time Reversibility and Limiting Probabilities#

A Markov chain is time-reversible if it is possible to obtain the same set of transition probabilities going forward in time and going backward in time. In other words, the chain is time-reversible if there exists a limiting probability vector \(\pi = (\pi_1, \pi_2, \ldots, \pi_r)\) such that: \[\pi_i q_{ij} = \pi_j q_{ji} \,\,\, \text{ for all } i, j.\] Looking at the infinitesimal generator matrix \(Q\), we can see that the relationship \(\pi_i q_{ij} = \pi_j q_{ji}\) holds for all \(i,j\) since the rates are same. Thus, the Markov chain is time-reversible. To find the limiting probabilities, we need to solve the following set of linear equations: \[\pi_i \mu = \pi_j (-\mu) \,.\] Upon solving for \(\pi\), we can find that \(\pi_i = \frac{1}{r}\) for all \(i = 1, 2, \ldots, r\). In conclusion, the state of the given system is a continuous-time Markov chain, its infinitesimal rates are given by the generator matrix \(Q\), it is time-reversible, and the limiting probabilities are uniform: \(\pi_i = \frac{1}{r}\) for all \(i = 1, 2, \ldots, r\).