# How do derive the steady state probabilities M/M/1/k queueing system?

How do I derive the steady state probabilities for the $$M/M/1/k$$ queueing systems with finite system capacity $$k$$?

• What you are describing is usually called an $M/M/1/k$ queuing system. (Sometimes a different letter is used in place of $k$.) Here, $k$ refers to the capacity. Most textbooks (and probably most websites) that derive steady-state probabilities for $M/M/1$ will also do the same for $M/M/1/k$. – LarrySnyder610 Sep 20 '20 at 13:01

There are a couple of ways to derive the steady state probabilities for a $$M/M/1/k$$ queuing system with Markovian* arrivals (the first $$M$$), exponential service time distribution (the second $$M$$), a single server (the 1), and a finite total system capacity of $$k$$. Note this implies the queue can be at most $$k-1$$.

*Recall a system with $$M$$ arrivals has exponential interarrivals with rate $$\lambda$$ and mean interarrival time of $$\frac{1}{\lambda}$$. Equivalently, arrivals occur according to a homogeneous Poisson process with rate $$\lambda$$.

One approach
The $$M/M/1/k$$ queuing system can be thought of as a Continuous Time Markov Chain (CTMC), $$\{X(t), t>=0\}$$, where $$X(t)$$ represents the total number of customers in the system. We can take advantage of the system capacity (constraint) being finite.

If the arrivals happen at rate $$\lambda$$ and the service rate is $$\mu$$, then the transition rate diagram is given below. Note the finite number of states, with the statespace $$\mathcal S = \{0,1,2,3,\ldots,k\}$$.

The steady state probabilities, $$\mathbf \pi = [\pi_0\; \pi_1\; \pi_2\; \ldots\; \pi_k]$$, are obtained by the solution to the steady-state equations (flow out = flow in),

$$\lambda \pi_0 = \mu \pi_1 \\ (\lambda+\mu) \pi_1 = \lambda \pi_0 + \mu \pi_2 \\ (\lambda+\mu) \pi_2 = \lambda \pi_1 + \mu \pi_3 \\ \vdots \\ \lambda \pi_{k-1} = \mu \pi_k$$

and the normalization equation $$\sum_{i=0}^k \pi_k = 1$$. The steady-state equations contain the dependency pattern of a Birth-Death Process, with the final equation being modified due to the finite state space (though this will not hamper the solution).

Ignoring the requirement for the $$\pi$$'s to sum to 1 for now, set $$\pi_0 = 1$$. Then $$\hat \pi_j = \left(\frac{\lambda}{\mu}\right)^j$$, or letting $$\rho=\frac{\lambda}{\mu}$$, then $$\hat \pi = \rho^j$$.

To normalize the solution, we need to divide the $$\hat \pi$$'s by the normalization constant $$G = \hat \pi_0 + \hat \pi_1 + \hat \pi_2 +\hat \pi_3 + \cdots + \hat \pi_k$$, which is a finite sum because we have a finite state space.

Rearranging, \begin{align} G &= \hat \pi_0 + \hat \pi_1 + \hat \pi_2 +\hat \pi_3 + \cdots \hat \pi_k \\ &= 1 + \rho + \rho^2 + \rho^3 + \cdots + \rho^k \\ &= \left(\frac{1-\rho^{k+1}}{1-\rho} \right) \end{align} which gives $$\frac{1}{G} = \frac{1-\rho}{1-\rho^{k+1}}$$ which is valid for any value of $$\rho \in [0,1)$$ with the special case of $$\rho=1$$ requiring the trivial $$G = k+1$$ yielding $$\frac{1}{G}=\frac{1}{k+1}$$ for this exception case.

This implies that $$\begin{array}{ll} \pi_j = \rho^j\left(\frac{1-\rho}{1-\rho^{k+1}}\right) & \text{for } \rho\ne 1 \tag{Key Result} \\ \pi_j = \frac{1}{k+1} & \text{for } \rho = 1 \\ \end{array}$$