This comes down to just using the detailed balance property of the invariant distribution and using induction specifically: Base case: \(n = 0\) clearly \(\lambda _0 = \lambda _0\). Induction case: The induction hypothesis is that

We now need a case distribution again: \(n = 1\) or \(n \neq 1\). If \(n = 1\) then:

q.e.d. Otherwise:

q.e.d.

First we will use the previous theorem to get a general formula of the form:

And then we will prove that only this distribution will sum to \(1\), e.g. by for example stating if

then it sums to higher than \(1\) and if:

than it will be lower than one. This will simply be by using linearity of limits.

This follows rather quickly from 12. Simply state the invariant distribution definition at index \(n-1\) and then simple rewriting yields an equality of the form:

Where we already know that \(c\neq 0\) and thus \(a=0\) is the only correct option.

This will just be copying the proof from 12, but this time instead of using the property that at index \(0\) we have that our markov chain only goes in one direction, we now plug-in \(0\) our zero value of \(\lambda _{n-1}\) and \(a_n = 0\) (as the departurerate is \(0\) at this index).

We will need to do induction over \(i\). base case \(i = 0\):
  then use 14. induction case \(i\):
  we know that the invariant distribution of \(i-1\) is zero. If the departurerate of \(i\) is not zero i.e. \(i \notin A\) then simply apply induction hypothesis. Otherwise apply previous lemma and note that if we let \(m = \min {n \in A \colon n {\gt} i} - 1\) then we have two cases:

1. if \(m = i\) then we have:

   \[ (\Lambda +a_i)\lambda _i = \Lambda \lambda _{i-1} + a_{i+1} \lambda _{i+1} \]

   Using the definitions we find that the RHS is \(0\) and since \(\Lambda {\gt} 0, a_i \geq 0\) we find that \(\lambda _i = 0\).

2. otherwise we instead find the following set of equations:

   \[ \lambda _m = \prod _{j=i+1}^m \frac{\Lambda }{a_j} \lambda _i, \]

   from the previous lemma. But also:

   \[ (\Lambda +a_m)\lambda _m = \Lambda \lambda _{m-1} + a_{m+1}\lambda _{m+1} \]

   and plugging in \(a_{m+1} = 0\) we get:

   \[ \lambda _m = \frac{\Lambda }{\Lambda + a_m}\lambda _{m-1} \]

   Which can again be rewritten using the formula from the previous lemma to:

   \[ \frac{\Lambda }{\Lambda + a_m}\prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j} \]

   Now we can then substitute \(\lambda _m\) in the previous equation to get:

   \begin{align*} \prod _{j=i+1}^m \frac{\Lambda }{a_j} \lambda _i & = \frac{\Lambda }{\Lambda + a_m}\prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j}\\ \frac{\Lambda }{a_m}\prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j} \lambda _i & = \frac{\Lambda }{\Lambda + a_m}\prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j}\\ (\frac{\Lambda }{a_m} - \frac{\Lambda }{\Lambda + a_m})\prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j} \lambda _i & = 0\\ (\frac{\Lambda }{a_m} - \frac{\Lambda }{\Lambda + a_m}) = 0 & \vee \prod _{j=i+1}^{m-1} \frac{\Lambda }{a_j} \lambda _i = 0\\ (\frac{\Lambda (\Lambda + a_m)-\Lambda ^2}{a_m(\Lambda + a_m)}) = 0 & \vee \lambda _i = 0\\ \Lambda (\Lambda + a_m)-\Lambda ^2 = 0 & \vee \lambda _i = 0\\ \Lambda (\Lambda + a_m)-\Lambda ^2 = 0 & \vee \lambda _i = 0\\ \Lambda a_m = 0 & \vee \lambda _i = 0\\ \text{contradiction!} & \vee \lambda _i = 0\\ \end{align*}

   Thus \(\lambda _i = 0\).

We will need to do a case distinction: either the rate is \(0\) or it is isn’t.
If it is: Apply previous lemma.
If it isn’t: Simply apply 13

We will need to do a case distinction: either the rate is \(0\) or it is isn’t.
If it is: Apply the shifted invariant distribution’s value lemma.
If it isn’t: Simply apply 13

Clearly we first use ?? We will need to do a few case distinctions:

1. First of all if there exists an index \(m {\gt} n\) with departure rate \(0\). Then both \(P\) and \(Q\)’s invariant distribution is \(0\) for all indices \(i {\lt} m\) by 16. Thus \(c = 1\) in the \(i {\lt} n\) case. Furthermore by 15 we find that both invariant distributions are the same and therefore \(c = 1\) in both cases.

2. Otherwise if \(Q\)’s departure rate is \(0\) at index \(n\) then by 14 \(Q\)’s invariant distribution for all indices \(i {\lt} n\) equals \(0\), whereas \(P\)’s departurerate is at least non-zero for \(i = n-1\) by 15 or 12 and using that the sum of an invariant distribution must be \(1\). Thus clearly \(c=0\) for all \(i {\lt} n\). Furthermore by the fact that the invariant distribution must sum to \(1\) and \(P\) has non-zero values we know that \(\sum _{i=n}^\infty \lambda _{P,i} = 1 - \sum _{i=0}^{n-1}\lambda _{P,i} {\lt} 1\). We see that, because \(\sum _{i=n}^\infty \lambda _{P,i} {\lt} 1\) and that \(\sum _{i=n}^\infty \lambda _{Q,i} = 1\). Now using 15 or 12 on \(P\) and 15 for \(Q\) we find that \(C = 1/\sum _{i=n}^\infty \lambda _{P,i}\).

3. If \(Q\)’s departure rate is non-zero then we find using 15 or 12 for both of them, that after \(n\) that our product of \(P\) must contain a smaller fraction compared to \(\lambda _0\) or \(\lambda _k\) for some \(k {\lt} n\). Specifically \(P\)’s fraction is \(\frac{a_{P,n}}{a_{Q,n}}\) times smaller from then on. Since \(\sum _{i=0}^\infty \lambda _{P,i} = 1\) we find that:

   \begin{align} 1 & = \sum _{i=0}^{n-1} \lambda _{P,i} + \sum _{i=n}^{\infty } \lambda _{P,i} \nonumber \\ & = \frac{\lambda _{P,0}}{\lambda _{Q,0}} \sum _{i=0}^{n-1} \lambda _{Q,i} + \frac{\lambda _{P,0}}{\lambda _{Q,0}}\frac{a_{Q,n}}{a_{P,n}}\sum _{i=n}^{\infty } \lambda _{Q,i} \nonumber \\ & = \left(\sum _{i=0}^{n-1} \lambda _{Q,i} + \frac{a_{Q,n}}{a_{P,n}}\sum _{i=n}^{\infty } \lambda _{Q,i}\right) \frac{\lambda _{P,0}}{\lambda _{Q,0}} \label{eqn} \hspace{36pt}(1) \end{align}

   Now note that:

   \[ \left(\sum _{i=0}^{n-1} \lambda _{Q,i} + \frac{a_{Q,n}}{a_{P,n}}\sum _{i=n}^{\infty } \lambda _{Q,i}\right) {\lt} 1 \]

   by the fact that

   \[ \sum _{i=0}^{n-1} \lambda _{Q,i} + \sum _{i=n}^{\infty } \lambda _{Q,i} = 1 \]

   and

   \[ \frac{a_{Q,n}}{a_{P,n}} {\lt} 1 \]

   (thus using concavity of summation :D). Thus \(\frac{\lambda _{P,0}}{\lambda _{Q,0}} {\gt} 1 \implies \lambda _{P,0} {\gt} \lambda _{Q,0}\), and therefore \(c {\lt} 1\) for \(i \leq n - 1\) and \(C {\gt} 1\) for \(i \geq n\), (because it must still sum to \(1\)). Furthermore \(c\) is of the form:

   \[ 1 + (\frac{a_{Q,n}}{a_{P,n}}-1)\sum _{i=n}^{\infty }\lambda _{Q,i} \]

   by:

   \begin{align*} \frac{\lambda _{P,0}}{\lambda _{Q,0}} & = \frac{1}{\sum _{i=0}^{n-1}\lambda _{Q,i} + \frac{a_{Q,n}}{a_{P,n}} \sum _{i=n}^\infty \lambda _{Q,i}}\\ \iff \lambda _{Q,0} & = \left(\sum _{i=0}^{n-1}\lambda _{Q,i} + \frac{a_{Q,n}}{a_{P,n}} \sum _{i=n}^\infty \lambda _{Q,i}\right)\lambda _{P,0}\\ & =\left(1-\sum _{i=n}^{\infty }\lambda _{Q,i} + \frac{a_{Q,n}}{a_{P,n}} \sum _{i=n}^\infty \lambda _{Q,i}\right)\lambda _{P,0}\\ & =\left(1 + (\frac{a_{Q,n}}{a_{P,n}}-1) \sum _{i=n}^\infty \lambda _{Q,i}\right)\lambda _{P,0}\\ \end{align*}

   And \(C\) is of the form:

   \[ C = \frac{a_{P,n}}{a_{Q,n}}c = 1 + (\frac{a_{P,n}}{a_{Q,n}}-1) \sum _{i=0}^{n-1}\lambda _{Q,i} \]

   this follows from:

   \[ \sum _{i=n}^\infty \lambda _{Q,i} = \frac{a_{P,n}}{a_{Q,n}}\frac{\lambda _{Q,0}}{\lambda _{P,0}}\sum _{i=n}^\infty {\lambda _{P,i}} \]

   again by 15 or 12. Plugging in \(\lambda _{Q,0} = c \lambda _{P,0}\) yields:

   \[ \frac{a_{P,n}}{a_{Q,n}}\frac{c\lambda _{P,0}}{\lambda _{P,0}}\sum _{i=n}^\infty {\lambda _{P,i}} \]

   And therefore we clearly attain:

   \begin{align*} C & = \frac{a_{P,n}}{a_{Q,n}} c \\ & = \frac{a_{P,n}}{a_{Q,n}}\left(1 + (\frac{a_{Q,0}}{a_{P,0}}-1)\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\\ & = \frac{a_{P,n}}{a_{Q,n}}\left(1 + (\frac{a_{Q,0}}{a_{P,0}}-1)(1-\sum _{i=0}^{n-1}\lambda _{Q,i})\right)\\ & = \frac{a_{P,n}}{a_{Q,n}} + (1-\frac{a_{P,n}}{a_{Q,n}})(1-\sum _{i=0}^{n-1}\lambda _{Q,i})\\ & = \frac{a_{P,n}}{a_{Q,n}} + 1 - \frac{a_{P,n}}{a_{Q,n}} - (1-\frac{a_{P,n}}{a_{Q,n}})\sum _{i=0}^{n-1}\lambda _{Q,i}\\ & = 1 - (1-\frac{a_{P,n}}{a_{Q,n}})\sum _{i=0}^{n-1}\lambda _{Q,i}\\ & = 1 + (\frac{a_{P,n}}{a_{Q,n}}-1)\sum _{i=0}^{n-1}\lambda _{Q,i} \end{align*}

Because \(c \leq 1\) for \(i {\lt} n\) and \(C \geq 1\) for \(i \geq n\) we find that:

We will use the same case distinctions again:

1. Clearly if \(c = C = 1\) then it is true;

2. If \(Q\)’s rate at index \(n\) is \(0\) then we have that the \(c\) term yields \(0\) and because \(C = \frac{1}{\sum _{i=n}^{\infty }\lambda _{P,i}}\), we find that:

   \begin{align*} C \cdot \sum _{i=n}^\infty i \lambda _{P,i} & = \frac{1}{\sum _{i=n}^{\infty }\lambda _{P,i}}\sum _{i=n}^\infty i \lambda _{P,i}\\ & = (\frac{1}{\sum _{i=n}^{\infty }\lambda _{P,i}} - 1 + 1)\sum _{i=n}^\infty i \lambda _{P,i}\\ & = (\frac{1}{\sum _{i=n}^{\infty }\lambda _{P,i}} - 1)\sum _{i=n}^\infty i \lambda _{P,i} + \sum _{i=n}^\infty i \lambda _{P,i}\\ & \geq n(\frac{1}{\sum _{i=n}^{\infty }\lambda _{P,i}} - 1)\sum _{i=n}^\infty \lambda _{P,i} + \sum _{i=n}^\infty i \lambda _{P,i}\\ & = n(1 - \sum _{i=n}^\infty \lambda _{P,i}) + \sum _{i=n}^\infty i \lambda _{P,i}\\ & = n(1 - (1-\sum _{i=0}^{n-1} \lambda _{P,i})) + \sum _{i=n}^\infty i \lambda _{P,i}\\ & = n\sum _{i=0}^{n-1} \lambda _{P,i} + \sum _{i=n}^\infty i \lambda _{P,i}\\ & \geq \sum _{i=0}^{n-1}i \lambda _{P,i} + \sum _{i=n}^\infty i \lambda _{P,i} \end{align*}

3. If both \(Q\)’s rate at index \(n\) is not \(0\) then we have:

   \begin{align*} & c \cdot \sum _{i=0}^{n-1} i \lambda _{P,i} + C \cdot \sum _{i=n}^\infty i \lambda _{P,i} \\ & = \left(1 + (\frac{a_{Q,n}}{a_{P,n}}-1)\sum _{i=n}^{\infty }\lambda _{Q,i}\right) \sum _{i=0}^{n-1} i \lambda _{P,i} + \left(1 + (\frac{a_{P,n}}{a_{Q,n}}-1) \sum _{i=0}^{n-1}\lambda _{Q,i}\right) \sum _{i=n}^\infty i \lambda _{P,i} \end{align*}

   It is evident that this expression is greater than or equal to

   \[ \sum _{i=0}^{n-1}i \lambda _{P,i} + \sum _{i=n}^\infty i \lambda _{P,i} \]

   if and only if:

   \[ (\frac{a_{Q,n}}{a_{P,n}}-1)\left(\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (\frac{a_{P,n}}{a_{Q,n}}-1) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right) \]

   Thus we will prove this instead:

   \begin{align*} & (\frac{a_{Q,n}}{a_{P,n}}-1)\left(\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (\frac{a_{P,n}}{a_{Q,n}}-1) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right) \\ & = (\frac{a_{Q,n} - a_{P,n}}{a_{P,n}})\left(\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (\frac{a_{P,n} - a_{Q,n}}{a_{Q,n}}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right) \\ & = (\frac{a_{Q,n}^2 - a_{P,n}a_{Q,n}}{a_{P,n}a_{Q,n}})\left(\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (\frac{a_{P,n}^2 - a_{P,n}a_{Q,n}}{a_{P,n}a_{Q,n}}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right) \end{align*}

   Again this is only greater than or equal to \(0\) if \(a_{P,n}a_{Q,n}\) times the expression is zero, thus we can prove the same for the simplified expression:

   \begin{align*} & (a_{Q,n}^2 - a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{Q,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ & \geq (a_{Q,n}^2 - a_{P,n}a_{Q,n})\left(C\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ & = (a_{Q,n}^2 - a_{P,n}a_{Q,n})\left(\frac{a_{P,n}}{a_{Q,n}}c\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ & = (a_{P,n}a_{Q,n} - a_{P,n}^2)\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(c\sum _{i=0}^{n-1} i \lambda _{P,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ & = -(a_{P,n}^2- a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{Q,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ \end{align*}

   Now notice that \(-(a_{P,n}^2- a_{P,n}a_{Q,n}) \leq 0\) by \(a_{P,n} \geq a_{Q,n}\) and thus we can ............ to \(n-1\) whereas the right hand term can instead be changed to \(n\) i.e. we get:

   \begin{align*} & -(a_{P,n}^2- a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} i \lambda _{Q,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty i \lambda _{P,i}\right)\\ & \geq -(a_{P,n}^2- a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left((n-1)\sum _{i=0}^{n-1} \lambda _{Q,i}\right) + (a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(n\sum _{i=n}^\infty \lambda _{P,i}\right)\\ & = -(n-1)(a_{P,n}^2- a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} \lambda _{Q,i}\right) + n(a_{P,n}^2 - a_{P,n}a_{Q,n}) \left(\sum _{i=0}^{n-1}\lambda _{Q,i}\right)\left(\sum _{i=n}^\infty \lambda _{P,i}\right)\\ & = (a_{P,n}^2- a_{P,n}a_{Q,n})\left(\sum _{i=n}^{\infty }\lambda _{P,i}\right)\left(\sum _{i=0}^{n-1} \lambda _{Q,i}\right) \end{align*}

   Now note that \((a_{P,n}^2- a_{P,n}a_{Q,n}) \geq 0\), \(\sum _{i=n}^{\infty }\lambda _{P,i} \geq 0\), \(\sum _{i=0}^{n-1} \lambda _{Q,i} \geq 0\) and therefore likewise their product is greater than or equal to zero, which completes the proof.

We will create a set of intermediary policies between \(P\) and \(Q\) to prove what we wanted to prove. Let \(n \in \mathbb {N}\) and let \(R_n\) denote the policy whose departure rate at index \(j \leq n\) equals \(P\)’s departure rate and at index \(j {\gt} n\) \(Q\)’s. Then using induction on \(n\) we find that: \(\mathbb {E}[N]^{Q} \geq \mathbb {E}[N]^{R_i}\). Furthermore using induction on \(n\) we find that \(\mathbb {E}[N]^{R_n}\) is monotonically increasing. Lastly after cleaning up the proof of 20 we actually find that our