I'm new to queueing theory but think I have a problem sufficiently well-described by a M/M/∞ queue. I am seeking to determine the proportion of time that is spent servicing $n$ customers (specifically $n=0$ for an idle/empty queue). I've learned how to do this for a M/M/1 queue, but not for a M/M/∞ queue (or for a M/G/∞ queue, which I anticipate desiring eventually).
An additional aspect (for which I have yet to find standard terminology with which to get useful search results) is that I have $r$ different customer types, each having their own arrival rate $\lambda_r$ and service rate $\mu_r$. In the context of M/M/1 this doesn't seem like it would create too much additional difficulty since, as long as I assume that customer types are independent, the result of independent Poisson processes is also a Poisson process with overall rates $\lambda = \sum_r \lambda_r$ and $\mu = \sum_r \mu_r$. (Is that correct?)
Best Answer
With an M/M/$\infty$ system, each state $n \ge 0$ has a transition to state $n+1$ with a rate of $\lambda$ (the arrival rate), and each state $n \ge 1$ has a transition to state $n-1$ with a rate of $n \mu$ (since there are $n$ customers, each of whom has an $\text{Exp}(\mu)$ service time remaining).
The easiest way to solve for the steady-state probabilities is by using local balance equations. If $\pi_n$ is the fraction of time we are in state $n$, then we have $$\pi_{n-1} \cdot \lambda = \pi_n \cdot (n \mu)$$ for all $n \ge 1$. The left-hand side represents the rate of $n-1 \to n$ transitions; the right-hand side represents the rate of $n \to n-1$ transitions. These rates should be equal because such transitions must alternate: if you step $n-1 \to n$, you can't take another $n-1 \to n$ step until an $n \to n-1$ step occurs.
This leads us to $\pi_n = \frac{\lambda}{n\mu} \pi_{n-1} = \frac{(\lambda/\mu)^n}{n!} \pi_0$ by induction, and even if you're a bit skeptical of the local balance equations, you can verify that this satisfies the stationary equations. Finally, $$ \sum_{n=0}^\infty \pi_n = 1 \implies \sum_{n=0}^\infty \frac{(\lambda/\mu)^n}{n!} \pi_0 = 1 \implies e^{\lambda/\mu} \pi_0 = 1 $$ from which we conclude that $\pi_0 = e^{-\lambda/\mu}$ and $\pi_n = e^{-\lambda/\mu} \frac{(\lambda/\mu)^n}{n!}$. You might recognize this as the probability mass function of a $\text{Poisson}(\lambda/\mu)$ random variable.
With $r$ different customer types - actually the M/M/1 queue feels like it would be a nightmare to analyze in that case, but the M/M/$\infty$ is easy. Rather than all the customers arriving into the same M/M/$\infty$ system, we can give each customer type its own M/M/$\infty$ system, and that doesn't change anything because $r$ copies of $\infty$ is still $\infty$. Because no customers ever have to wait in line, no customer ever cares about how many customers of other types there are - so the $r$ individual M/M/$\infty$ systems are independent.
A state of this combined system would be $(n_1, n_2, \dots, n_r)$ where $n_i$ is the number of customers of type $i$ that are currently being serviced. Since the systems are independent, the stationary distribution of the combined system is $$ \pi_{n_1, n_2, \dots, n_r} = \prod_{i=1}^r e^{-\lambda_i/\mu_i} \frac{(\lambda_i/\mu_i)^{n_i}}{n_i!}. $$ Ultimately, you probably want to know a formula for $\pi_n$, the fraction of time there are $n$ total customers. This is no longer the probability of a single state, but a sum over states: $$ \pi_n = \sum_{n_1 + n_2 + \dots + n_r = n} \pi_{n_1, n_2, \dots, n_r}. $$ To our rescue comes the multinomial theorem: $$ \sum_{n_1 + n_2 + \dots + n_r = n} \frac{n!}{n_1! n_2! \dotsm n_r!} x_1^{n_1} x_2^{n_2} \dotsm x_r^{n_r} = (x_1 + x_2 + \dots + x_r)^n. $$ In particular, it implies that $\pi_n = e^{-\rho} \frac{\rho^n}{n!}$ where $\rho = \frac{\lambda_1}{\mu_1} + \frac{\lambda_2}{\mu_2} + \dots + \frac{\lambda_r}{\mu_r}$: it is also Poisson.