Stability of a cascade system with two stations and its extension for multiple stations

We consider a two-station cascade system in which waiting or externally arriving customers at station 1 move to the station 2 if the queue size of station 1 including an arriving customer itself and a customer being served is greater than a given threshold level \(c_{1} \ge 1\) and if station 2 is empty. Assuming that external arrivals are subject to independent renewal processes satisfying certain regularity conditions and service times are i.i.d. at each station, we derive necessary and sufficient conditions for a Markov process describing this system to be positive recurrent in the sense of Harris. This result is extended to the cascade system with a general number k of stations in series. This extension requires certain traffic intensities of stations \(2,3,\ldots , k-1\) for \(k \ge 3\) to be defined. We finally note that the modeling assumptions on the renewal arrivals and i.i.d. service times are not essential if the notion of the stability is replaced by a certain sample path condition. This stability notion is identical with the standard stability if the whole system is described by the Markov process which is a Harris irreducible T-process.

After the submission of this paper, we have learned that [7] disproves the conjecture of [11]. We thanks the Editor-in-chief for allowing us to revise the original submission taking [7] into account. We are grateful to the anonymous referee for pointing out various errors in the revised submissions and helpful suggestions for correcting them.

Authors and Affiliations

1. Department of Information Sciences, Tokyo University of Science, Noda, Chiba, Japan

   Masakiyo Miyazawa

2. School of Data Science, Chinese University of Hong Kong, Shenzhen, China

   Masakiyo Miyazawa

3. Institute of Applied Mathematical Research of Karelian Research Centre, Russian Academy of Sciences, Petrozavodsk, Karelia, Russia

   Evsey Morozov

4. Petrozavodsk State University, Petrozavodsk, Russia, 185910

   Evsey Morozov

5. Moscow Center for Fundamental and Applied Mathematics, Moscow State University, Moscow, Russia, 119991

   Evsey Morozov

Corresponding author

Correspondence to Masakiyo Miyazawa.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

1.1 The equivalence of (a) and (c) in Proposition 2.2

We prove that (a) is equivalent to (c) in Proposition 2.2. We first note that, under the assumption that \(X(\cdot )\) is a Harris irreducible T-process, \(X(\cdot )\) is either Harris recurrent or \(\sigma \)-transient by the irreducibility and the Doeblin decomposition (see Theorem 3.1 of [16]), where \(X(\cdot )\) is said to be \(\sigma \)-transient if S is a countable union of measurable sets \(A_{i}\) for \(i \ge 1\) such that \(\mathbb {E}_{x}(\eta _{A_{i}}) < \infty \) for all \(x \in S\) and for all \(i \ge 1\), in which case each \(A_{i}\) is said to be uniformly transient. If \(X(\cdot )\) is positive Harris recurrent, then it has an invariant probability measure. Denote it by \(\nu \). Then, (2.5) is immediate from (2.2) in Remark 2.1 because there exists a compact set \(C \subset S\) such that \(\nu (C) > 0\) by the tightness of \(\nu \) on S.

Conversely, if (2.5) holds, then \(\mathbb {E}_{x}(\eta _{C}) = \infty \) for the compact set C. Hence, \(X(\cdot )\) cannot be \(\sigma \)-transient, and therefore it is Harris recurrent by the Doeblin decomposition. Thus, there is a unique invariant measure. Suppose that this \(X(\cdot )\) is null recurrent, then it follows from (2.3) in Remark 2.1 that, for all \(x \in S\) and any compact set \(C \subset S\),

This contradicts (2.5), so \(X(\cdot )\) must be positive Harris recurrent.

1.2 Proof of (ii) of Lemma 3.1

By (i) of Lemma 3.1\({\varvec{X}}(\cdot )\) is a T-process. Let \(\varphi (B) = T({\varvec{x}}^{*},B)\), then \(T({\varvec{x}}^{*},B) > 0\) implies that \(T({\varvec{y}},B) > 0\) for \(\forall {\varvec{y}}\) in some open set \(V({\varvec{x}}^{*})\) containing \({\varvec{x}}^{*}\) by the lower semi-continuity of \(T(\cdot ,B)\). Furthermore, let e be the exponential distribution with unit mean, then \(K_{e}({\varvec{x}},V({\varvec{x}}^{*})) = \int _{0}^{\infty } \mathbb {P}_{{\varvec{x}}}({\varvec{X}}(u) \in V({\varvec{x}}^{*})) e^{-u} {\textrm{d}}u > 0\) for \(\forall {\varvec{x}} \in S\) since \({\varvec{x}}^{*}\) is reachable from any \({\varvec{x}} \in S\). Hence, for the sampling distribution a by which \({\varvec{X}}(\cdot )\) is a T-process,

where \(e * a\) is the convolution of distributions e and a on \(\mathbb {R}_{+}\), and \(K_{e * a}(\cdot ,\cdot )\) is \(e * a\)-sampling K-chain. This proves that \({\varvec{X}}(\cdot )\) is \(\varphi \)-irreducible because distribution \(e * a\) has an absolutely continuous component with respect to Lebesgue measure on \(\mathbb {R}_{+}\).

1.3 Proof of Lemma 3.2

Obviously, (2.5) implies (3.8) for \(X(\cdot ) = {\varvec{X}}(\cdot )\), so we only need to prove that (3.8) implies (2.5). Recall that \({\varvec{X}}_{2}(\cdot )\) is the Markov process describing the queue of class-2 customers. We first show that \({\varvec{X}}_{2}(\cdot )\) is a positive Harris recurrent if (3.8) holds for \(i=2\). Since \(R_{e,2}(\cdot )\) is a regenerative process with cycles \(\tau _{e,2}(\cdot )\) and \(R_{s,2}(\cdot )\) is dominated by such a regenerative process \(Y(\cdot )\) with cycles \(\tau _{s,2}(\cdot )\) in the sense that

both of \(R_{e,2}(\cdot )\) and \(R_{s,2}(\cdot )\) are tight on average. Hence, by Proposition 2.2, for any \({\varvec{x}}_{2} \in S\), any \(\varepsilon > 0\) and \(v = e, s\), there is a compact subset \(C_{v,2} \subset \mathbb {R}_{+}\) such that

Let \(\widetilde{C}_{2} = C_{2,e} \times C_{2,s}\), then

Integrating this inequality for \(u \in [0,t]\), it follows from (3.8) for \(i=2\) that there is some \({\varvec{x}}'_{2} \in S\),

By Proposition 2.2, this proves that \({\varvec{X}}_{2}(\cdot )\) is positive recurrent. Furthermore, it is tight on average by (b) of Proposition 2.2. Since \(Q_{1|2}(t) \le 1\) for \(\forall t \ge 0\), \(\{Q_{1|2}(t); t \ge 0\}\) is obviously tight on average. Similar to \(R_{e,2}(\cdot )\) and \(R_{s,2}(\cdot )\), \(R_{e,1}(\cdot )\), \(R_{s,1}(\cdot )\) and \(R_{s,1|2}(\cdot )\) are also tight on average. Hence, by a similar argument to \({\varvec{X}}_{2}(\cdot )\), (3.8) for \(i=1\) implies (2.5) for \(X(\cdot ) = {\varvec{X}}(\cdot )\).

1.4 Proof of Lemma 3.3

Note that, under Assumption 3.1, \({\varvec{X}}(\cdot )\) is \(\varphi \)-irreducible T-process by Lemma 3.1. (i) Since \({\varvec{X}}(\cdot )\) is positive Harris recurrent, it has the stationary distribution \(\nu \), and, by (2.2) in Remark 2.1,

Integrating both sides of this equation by \(\xi \) and applying the dominated convergence theorem, we have

This and the definition of \(\rho ^{*}_{i}(\xi )\) prove (3.12).

(ii) By Lemma 3.2, we only need to show that \(\rho ^{*}_{i}(\xi ) < 1\) for \(i=1,2\) is equivalent to (3.8) for some \({\varvec{x}} \in S\) and some \(\ell \ge 0\). Assume that \(\rho ^{*}_{i}(\xi ) < 1\) for \(i=1,2\). Because, by Fatou’s lemma,

we have

Hence, (3.8) holds for \(i=1,2\), \(\ell =0\) and some \({\varvec{x}}_{i} \in S\).

Conversely, assume (3.8) for \(i=1,2\) and some \({\varvec{x}}_{i} \in S\) and some \(\ell = 0\). Then, \({\varvec{X}}(\cdot )\) is positive Harris recurrent by Lemma 3.2. Hence, (3.12) holds by (i) of Lemma 3.3, and therefore we only need to show that \(\mathbb {P}_{\nu }(Q_{i}(0)=0) > 0\) for \(i=1,2\). To prove this, we first note that \({\varvec{X}}(\cdot )\) is Harris \(\varphi \)-irreducible for \(\varphi (B) = T({\varvec{x}}^{*},B)\) by Lemma 3.1. Hence, \(\varphi (B) > 0\) implies \(K_{a}({\varvec{x}},B) > 0\) for \(\forall {\varvec{x}} \in S\) for some sampling distribution a by Definition 2.2. Then, for the stationary distribution \(\nu \) of \({\varvec{X}}(\cdot )\), for any sampling distribution a on \(\mathbb {R}_{+}\),

Hence, \(\varphi (B) > 0\) implies \(\nu (B) > 0\) for any \(B \in {\mathscr {B}}(S)\). From the definition of \(\varphi \), \(\varphi (G) > 0\) for any open set G containing \({\varvec{x}}^{*}\) of Lemma 3.1. As this G, we choose \(G_{0}\) defined by

which obviously contains \({\varvec{x}}^{*}\). Since the discrete topology is taken on \(\mathbb {Z}_{+}^{2} \times \{0,1\}\), \(G_{0}\) is an open set. Hence, \(\varphi (G_{0}) > 0\), which implies that \(\mathbb {P}_{\nu }(Q_{1}(0)=0) = \nu (G_{0}) > 0\). This proves that \(\rho _{1}^{*}(\xi ) < 1\). Similarly, \(\rho ^{*}_{2}(\xi ) < 1\) is proved.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions