How to calculate Markov Chain balance equations when number of servers change dynamically

Question

I'm trying to understand how balance equations work when the number of servers in a system can change on demand. For example, say the number of servers in a system is 1 when the number of customers is less than 5, but three when the number of customers is greater than or equal to 5. The maximum number of customers in a system is 8.

So then we have this state transition diagram that I'm trying to understand:

and the equation $\lambda P_3$ = $\mu P_4 + 2\mu P_4'$ and $\lambda P_4+ \lambda P_4' = 3 \mu P_5'$

So does this mean that the value for $P_4$ is the same for both $P_4$ and $P_4'$? and how do we calculate $P_0$ in this case? Is this still by assuming all probabilities sum to 1?

Answer 1

The balance equations that you've written down are correct, but you'll need to deduce at least one more "unusual" balance equation. You cannot simply assume $P_4 = P_4'$, and most of the time these will not be equal.

---

In general, all balance equations come from the single-state ones which say that for every state, the rate that we leave it equals the rate that we enter it. Together with the condition that all the stationary probabilities must sum to $1$, these are always enough to solve for the stationary distribution. But these single-state equations are often inconvenient: for example, for state $2$, they say that $(\lambda + \mu)P_2 = \lambda P_1 + \mu P_3$, which is much more annoying to deal with than the $\lambda P_2 = \mu P_3$ you're used to seeing.

To deduce better equations, we can take the sum of several individual balance equations, and cancel like terms, to deduce a more general rule: for any set of states $S$, the rate at which we leave $S$ (to go to its complement) equals the rate at which we enter it (from its complement). That's where $\lambda P_2 = \mu P_3$ comes from: it is the balance equation for the set $S = \{0,1,2\}$, and comes from adding up the three individual balance equations for those states.

In general, we can replace the individual balance equations by any other set of balance equations, provided that we take enough. This comes down to a linear algebra spanning set question, but a basic necessary condition is that for an $n$-state problem, we'll need at least $n-1$ balance equations. (The last equation is the condition that all probabilities sum to $1$.)

In this problem, we already have the following:

• We get the usual $\lambda P_0 = \mu P_1$, $\lambda P_1 = \mu P_2$, and $\lambda P_2 = \mu P_3$ from the balance equations between $S = \{0\}$, $S = \{0,1\}$, and $S = \{0,1,2\}$ and their complements.
• We get the usual $\lambda P_5 = 3\mu P_6$, $\lambda P_6 = 3\mu P_7$, and $\lambda P_7 = 3\mu P_8$ from the balance equations between $S = \{6,7,8\}$, $S = \{7,8\}$, and $S = \{8\}$ and their complements.
• We get $\lambda P_3 = \mu P_4 + 2\mu P_4'$ from the balance equation between $S = \{0,1,2,3\}$ and its complement.
• We get $\lambda P_4 + \lambda P_4' = 3 \mu P_5$ from the balance equation beween $S = \{0,1,2,3,4,4'\}$ and its complement.

But that's only $8$ balance equations, and we have $10$ states! So we need one more balance equation.

There's many of them we could write down, but maybe the simplest one is the one for $S = \{0,1,2,3,4\}$: $$\lambda P_4 = 2\mu P_4'.$$